Local search — hill climbing, simulated annealing আর genetic algorithm

এই পর্বে মডিউল ৭ শেষ হচ্ছে। আগের পর্বগুলোতে (পর্ব ৩৯ থেকে ৪৩) প্রশ্ন ছিল “লক্ষ্যে পৌঁছানোর পথ কোনটি”। এখানে প্রশ্ন: “সবচেয়ে ভালো শেষ অবস্থাটি কোনটি”; কীভাবে সেখানে পৌঁছালাম, তার দাম নেই। কোড পাতাতেই চলবে (ব্রাউজারের ভেতরে Python, Pyodide); প্রথমবার চালাতে কয়েক সেকেন্ড লাগতে পারে, SciPy-র block-এ আরও একটু বেশি।

১ · যখন পথ নয়, শুধু শেষ অবস্থাই গুরুত্বপূর্ণ

বাজারঘর (এই কোর্সের কাল্পনিক অনলাইন দোকান) একজন রাইডারকে সকালে ২০টি পার্সেল দেয়, ঢাকার মতো একটি কাল্পনিক ১০ × ১০ কিলোমিটার এলাকায় ছড়ানো ২০টি ঠিকানায়। রাইডারের প্রশ্ন একটাই: কোন ক্রমে গেলে মোট পথ সবচেয়ে কম হবে, আর শেষে আবার গুদামে ফেরা যাবে? এটি বিখ্যাত travelling salesman problem (TSP). উত্তর হলো ২০টি ঠিকানার একটি ক্রম; কীভাবে সেটি খুঁজে পেলেন, রাইডারের তাতে কিছু যায় আসে না।

আরও দুটি উদাহরণ। 8-queens ধাঁধায় ৮ × ৮ দাবার বোর্ডে ৮টি রানি এমনভাবে বসাতে হয় যাতে কেউ কাউকে আক্রমণ না করে (একই সারি, কলাম বা কর্ণে দুটি রানি নয়); উত্তর একটি বোর্ড। পরীক্ষার রুটিনে উত্তর একটি পূর্ণ সময়সূচি, যেখানে কোনো শিক্ষার্থীর দুটি পরীক্ষা একই সময়ে পড়ে না। এগুলো সবই optimization সমস্যা: অনেক সম্ভাব্য উত্তরের মধ্যে একটি মাপকাঠিতে সবচেয়ে ভালোটি খোঁজা।

এমন সমস্যাকে লেখা হয় complete-state formulation দিয়ে: প্রতিটি state নিজেই একটি পূর্ণ প্রার্থী-সমাধান, শুধু ভালো বা খারাপ। পর্ব ৩৯-এর (সমস্যাকে search হিসেবে দেখা) ছকে state ছিল “এখন কোথায় আছি”, আর উত্তর ছিল goal পর্যন্ত চালের ধারা। পার্থক্যটি পাশাপাশি:

State space কত বিশাল, একটু হিসাব করি। ২০টি ঠিকানার TSP-তে গুদাম থেকে শুরু ধরে বাকি ১৯টির ক্রম 19! রকম, আর একই চক্র উল্টো দিকে ঘুরলে দৈর্ঘ্য একই, তাই আলাদা পথ 19! ÷ 2 ≈ 6.1 × 10¹⁶টি। প্রতি সেকেন্ডে একশো কোটি পথ মাপলেও সব দেখতে প্রায় ২ বছর। 8-queens-এ প্রতি কলামে একটি রানি রাখলে বোর্ড 8⁸ = 16,777,216টি, সমাধান মাত্র ৯২টি। এই combinatorial explosion-এর সামনে local search কয়েক হাজার ধাপে ভালো উত্তর দেয়; দাম হলো নিশ্চয়তা, সে কখনো বলতে পারে না “এর চেয়ে ভালো উত্তর নেই”।

২ · State-space landscape — চূড়া, উপত্যকা, সমতল আর শিরা

Local search বোঝার সবচেয়ে কাজের ছবি হলো একটি ভূদৃশ্য, state-space landscape. অনুভূমিক অক্ষে সব state সাজানো, আর প্রতিটি state-এর উচ্চতা হলো তার objective function-এর মান, মানে “এই সমাধান কত ভালো” তার একটি সংখ্যা। লক্ষ্য সবচেয়ে উঁচু চূড়া (maximise). অনেক সমস্যায় আসে একটি খরচ, যা কমাতে হয় (minimise): TSP-তে পথের দৈর্ঘ্য, 8-queens-এ আক্রমণ করা জোড়ার সংখ্যা। খরচ c কমানো আর −c বাড়ানো একই কাজ, তাই “hill climbing” TSP-তে আসলে পাহাড় বেয়ে নামে।

দ্বিতীয় ধারণা neighbourhood বা প্রতিবেশী: একটি state থেকে একটি ছোট বদলে যে state-গুলোতে যাওয়া যায়। 8-queens-এ বদলটি হতে পারে একটি রানিকে নিজের কলামেই অন্য সারিতে সরানো: ৮টি কলাম × ৭টি সারি = ৫৬টি প্রতিবেশী। TSP-তে প্রচলিত বদল তালিকার একটি টুকরো উল্টে দেওয়া (অংশ ৬-এর 2-opt); ২০টি ঠিকানায় এমন বদল 20 × 17 ÷ 2 = 170টি।

ছবির নামগুলো এই পর্ব জুড়ে বারবার আসবে:

• Global maximum: পুরো ভূদৃশ্যের সবচেয়ে উঁচু বিন্দু, আসল সেরা উত্তর। খরচ কমানোর ভাষায় global minimum.
• Local maximum: এমন চূড়া যার প্রতিটি প্রতিবেশী নিচু, কিন্তু অন্য কোথাও আরও উঁচু চূড়া আছে। খরচের ভাষায় local minimum, যা পর্ব ৩৪-এ gradient descent-এর ফাঁদ হিসেবে দেখেছেন।
• Plateau: সমতল অংশ, যেখানে প্রতিবেশীদের মান সমান। দুই রকম: একদিকে চড়াই থাকলে তার নাম shoulder (ছবির বেগুনি অংশ), আর চারপাশ নিচু হলে সমতল local maximum. সমতলে “কোন দিকে উঁচু” প্রশ্নের উত্তর নেই, তাই লোভী পদ্ধতি থেমে যায়।
• Ridge: দুই বা বেশি মাত্রায় তির্যকভাবে ওঠা সরু শিরা। প্রতিটি অনুমোদিত বদল যদি শুধু উত্তর-দক্ষিণ বা পূর্ব-পশ্চিমে যায়, তাহলে যেকোনো এক পায়েই শিরা থেকে নামতে হয়; ফলে শিরার প্রতিটি বিন্দু local maximum-এর মতো আচরণ করে।

৩ · Hill climbing — steepest-ascent আর first-choice

সবচেয়ে সরল local search-এর নাম hill climbing, কখনো একে greedy local search-ও বলা হয়। নিয়মটি তিন লাইনের:

current = একটি শুরুর state
loop:
    best = current-এর সব প্রতিবেশীর মধ্যে সবচেয়ে ভালোটি
    যদি best, current-এর চেয়ে ভালো না হয়:  current ফেরত দিন (থামা)
    current = best

এই রূপের নাম steepest-ascent hill climbing: প্রতি ধাপে সব প্রতিবেশী মেপে সবচেয়ে খাড়া চড়াই। পর্ব ৪১-এর (Heuristic আর A*) greedy best-first search-এর আত্মীয়, তবে কোনো frontier নেই, পেছনের বিকল্পও মনে রাখা হয় না। নিচের ধাপগুলো ছবি ৪৪.১-এর ভূদৃশ্যে এই নিয়ম চালায়; প্রতিবেশী শুধু বাঁ আর ডানের state.

Steepest-ascent-এ প্রতি ধাপে সব প্রতিবেশী মাপতে হয়; 8-queens-এ ৫৬টি, কিন্তু হাজার পার্সেলের রুটে লাখের ঘরে। তখন কাজে আসে first-choice hill climbing: এলোমেলোভাবে একটি করে প্রতিবেশী বানানো, আর প্রথম যেটি ভালো, সেখানেই চলে যাওয়া। প্রতিটি পা কম খাড়া, কিন্তু অনেক সস্তা; কত বার চেষ্টার পর হাল ছাড়বেন, তার একটি সীমা রাখতে হয়।

8-queens-এ hill climbing, ধাপে ধাপে

বোর্ডকে লিখি ৮টি সংখ্যায়: q[c] মানে কলাম c-তে রানি কোন সারিতে, তাই কলামের সংঘাত আপনা থেকেই নেই। খরচ h = একে অপরকে আক্রমণ করা রানির জোড়া (একই সারি বা কর্ণ); সমাধান মানে h = 0. নিচের ট্রেস ডেস্কটপে একটি seed থেকে (সত্যিকারের run, Python 3.14.4); সমান সেরা চাল একাধিক থাকলে কলাম a থেকে প্রথমটি নেওয়া। বোর্ডে সারি 8 ওপরে, কলাম a বাঁয়ে।

1h = আক্রমণের জোড়া(q)2for ৫৬টি প্রতিবেশী: h মাপা3best = সবচেয়ে ছোট h4if best < h: সেই চাল দেওয়া5else: থামা (local min)

মাত্র ৪টি চালেই h = 9 থেকে 1: hill climbing খুব দ্রুত ভালো জায়গায় পৌঁছায়, আর তত দ্রুতই আটকে যায়। কত ঘন ঘন আটকায়, তা অনেক বোর্ডে চালিয়েই মাপা যায়।

৪ · ১০০০টি বোর্ডে মাপা — sideways move আর random restart

নিচের কোড ১০০০টি এলোমেলো বোর্ডে steepest-ascent চালায় দুই নিয়মে: শুধু উন্নতিতে চাল, আর সমান মানেও পাশে হাঁটা (পরপর সর্বোচ্চ ১০০ বার, যাতে সমতলে চিরকাল না ঘোরে)। সমান সেরা চাল একাধিক থাকলে এলোমেলোভাবে একটি। শেষে random restart: সমাধান না পাওয়া পর্যন্ত নতুন বোর্ডে আবার শুরু, এমন ২০০টি সমাধানে গড়ে কত বার শুরু লাগে। গতির জন্য প্রতিবেশীর h বের করা হয়েছে প্রতিটি সারি আর কর্ণে কয়টি রানি আছে তার হিসাব থেকে; ফল একই, শুধু দ্রুত।

import random
N = 8                               # q[c] = কলাম c-তে রানির সারি (0–7)
def climb(q, max_side=0):           # steepest-ascent hill climbing; h = আক্রমণের জোড়া
    R, D1, D2 = [0] * N, [0] * (2 * N), [0] * (2 * N)   # সারি আর দুই কর্ণে রানি কতটি
    for c, r in enumerate(q): R[r] += 1; D1[r - c + N] += 1; D2[r + c] += 1
    h = sum(k * (k - 1) // 2 for k in R + D1 + D2); steps = side = 0
    while h > 0:
        best, moves = h + 1, []
        for c in range(N):          # ৫৬টি প্রতিবেশী: একটি রানিকে নিজের কলামে সরানো
            r0 = q[c]; a0 = R[r0] + D1[r0 - c + N] + D2[r0 + c] - 3
            for r in range(N):
                if r == r0: continue
                v = h - a0 + R[r] + D1[r - c + N] + D2[r + c]
                if v < best: best, moves = v, [(c, r)]
                elif v == best: moves.append((c, r))
        if best > h or (best == h and side >= max_side): break   # আটকে গেছে
        side = side + 1 if best == h else 0                      # পাশে হাঁটা গোনা
        c, r = random.choice(moves); r0 = q[c]
        R[r0] -= 1; D1[r0 - c + N] -= 1; D2[r0 + c] -= 1
        R[r] += 1; D1[r - c + N] += 1; D2[r + c] += 1
        q[c], h, steps = r, best, steps + 1
    return h == 0, steps
board = lambda: [random.randrange(N) for _ in range(N)]
random.seed(42); T = 1000
for name, ms in [("শুধু উপরে", 0), ("পাশে ≤100", 100)]:
    res = [climb(board(), ms) for _ in range(T)]
    ok = [k for s, k in res if s]; bad = [k for s, k in res if not s]
    print(f"{name}: সফল {len(ok)}/{T} = {100 * len(ok) / T:.1f}%, গড় ধাপ"
          f" সফলে {sum(ok) / len(ok):.1f}, ব্যর্থে {sum(bad) / len(bad):.1f}")
tries = []
for _ in range(200):                # random restart: সমাধান না পাওয়া পর্যন্ত নতুন বোর্ড
    k = 1
    while not climb(board())[0]: k += 1
    tries.append(k)
print(f"random restart: ২০০টি সমাধানে গড় {sum(tries) / 200:.2f} বার শুরু, সর্বোচ্চ {max(tries)}")

শুধু উপরে: সফল 134/1000 = 13.4%, গড় ধাপ সফলে 4.1, ব্যর্থে 3.1
পাশে ≤100: সফল 936/1000 = 93.6%, গড় ধাপ সফলে 18.7, ব্যর্থে 51.6
random restart: ২০০টি সমাধানে গড় 6.98 বার শুরু, সর্বোচ্চ 32

এই সংখ্যাগুলো কতটা নির্ভরযোগ্য? ১০০০টি স্বাধীন চেষ্টায় অনুপাত p̂ = 0.134 হলে তার standard error √(p̂(1 − p̂) ÷ n) = √(0.134 × 0.866 ÷ 1000) ≈ 0.011, মানে মোটামুটি ±১ শতাংশ-বিন্দুর অনিশ্চয়তা; অন্য seed-এ ১২% বা ১৫% স্বাভাবিক, ৩০% নয়। Russell ও Norvig-এর পাঠ্যবইয়ে এই পরীক্ষার উল্লেখিত সংখ্যাও (প্রায় ১৪% আর sideways-সহ প্রায় ৯৪%) কাছাকাছি; তবে এখানকার সংখ্যা এই পাতার নিজের মাপ, যা আপনি নিজে চালিয়ে যাচাই করতে পারেন। Sideways-এর সীমা কীভাবে গোনা হয় বা টাইয়ে কোন চাল, এমন খুঁটিনাটিতে সংখ্যা একটু বদলায়।

৫ · Simulated annealing — মাঝে মাঝে খারাপ চাল নেওয়ার সাহস

Random restart আটকে গেলে কাজ ফেলে নতুন করে শুরু করে। অন্য ভাবনা: মাঝে মাঝে নিচে নামতে দেওয়া, যাতে ছোট চূড়া থেকে নেমে বড় চূড়ার ঢালে ওঠা যায়। কিন্তু সবসময় এলোমেলো হাঁটলে কোথাও পৌঁছানো যায় না; দরকার শুরুতে বেশ এলোমেলো, শেষে প্রায় খাঁটি hill climbing. এটাই simulated annealing.

নিয়মটি খরচ কমানোর ভাষায় (TSP-তে পথের দৈর্ঘ্য)। প্রতি ধাপে একটি এলোমেলো প্রতিবেশী বানান, আর তার খরচ থেকে বর্তমান খরচ বাদ দিয়ে পান Δ (ডেল্টা). Δ < 0 মানে ভালো: সবসময় নিন। নইলে নিন এই সম্ভাবনায়,

P(গ্রহণ) = exp(−Δ ÷ T)

T হলো তাপমাত্রা, একটি ধনাত্মক সংখ্যা যা ধীরে ধীরে কমে, আর exp মানে e^x (e ≈ 2.718). বাস্তবে 0 থেকে 1-এর একটি এলোমেলো সংখ্যা u টেনে u < P হলে চালটি নেওয়া হয়। একই T-তে অল্প খারাপ চাল বেশি সম্ভাব্য; একই Δ-তে T যত কম, সম্ভাবনা তত কম। এই নিয়মের নাম Metropolis criterion, ১৯৫৩ সালের Nicholas Metropolis ও সহকর্মীদের পদার্থবিজ্ঞানের simulation থেকে।

1g = নতুন খরচ - বর্তমান খরচ   # Δ2if g < 0: নেওয়া (সবসময়)3else: p = exp(-g / T)4     নেওয়া যদি u < p5T = a * T                      # ঠান্ডা করা

Temperature schedule — কত দ্রুত ঠান্ডা করবেন

কোন ধাপে T কত, এই নিয়মের নাম temperature schedule. প্রচলিত কয়েকটি:

• Geometric: T_k+1 = a·T_k, a একটু কম 1. সবচেয়ে প্রচলিত, এই পাতার কোডেও। শুরু T₀ আর শেষ T₁ ঠিক করলে K ধাপে a = (T₁ ÷ T₀)^1/K.
• Linear: প্রতি ধাপে T একই পরিমাণ কমে।
• Logarithmic: T_k = c ÷ log(k + 2)-এর মতো খুব ধীর ঠান্ডা। তাত্ত্বিক কাজে (Geman ও Geman ১৯৮৪, পরে Hajek ১৯৮৮) দেখানো হয়েছিল, যথেষ্ট ধীরে ঠান্ডা করলে সেরা উত্তরে পৌঁছানোর সম্ভাবনা ১-এর দিকে যায়; কিন্তু সেই গতি বাস্তবে প্রায়ই সব সমাধান একে একে দেখার চেয়েও ধীর।
• Reheating বা restart: অনেকক্ষণ উন্নতি না হলে T আবার একটু বাড়ানো।

ব্যবহারিক নিয়ম: কয়েকটি এলোমেলো খারাপ চালের গড় Δ মেপে T₀ এমন রাখুন যাতে শুরুতে তার অর্ধেক বা বেশি গৃহীত হয়, আর শেষের T এমন ছোট যাতে সবচেয়ে ছোট খারাপ চালও প্রায় কখনো নয়। সংখ্যাগুলো এককের ওপর নির্ভর করে: পথ কিলোমিটারে না মিটারে, তাতেই Δ হাজার গুণ বদলায়।

৬ · ডেলিভারি রুটে TSP — nearest neighbour, 2-opt আর annealing পাশাপাশি

এবার রাইডারের সমস্যা। ২০টি পয়েন্টের স্থানাঙ্ক seed-করা এলোমেলো সংখ্যা, ঢাকার মতো একটি কাল্পনিক ১০ × ১০ কিমি বাক্সে; দূরত্ব সোজা রেখায় (আসল রাস্তায় বেশি, তবে পদ্ধতির ভাবনা একই)। তিনটি পদ্ধতি:

• Nearest neighbour: প্রতিবার সবচেয়ে কাছের না-যাওয়া পয়েন্টে যাওয়া। Local search নয়, greedy নির্মাণ; দ্রুত, কিন্তু শেষ দিকে প্রায়ই লম্বা লাফ।
• 2-opt hill climbing: প্রতিবেশী মানে একটি টুকরো উল্টানো; steepest-ascent, যতক্ষণ কোনো উল্টানোয় পথ ছোট হয়।
• Simulated annealing: একই প্রতিবেশী, এলোমেলো একটি করে, Metropolis নিয়মে; ২০,০০০ ধাপ।

দুটি রেখা একে অপরকে কাটলে (X-এর মতো) সেই পথ সেরা হতে পারে না, কারণ ত্রিভুজের নিয়মে আড়াআড়ি দুটি রেখার চেয়ে দুই পাশের দুটির মোট দৈর্ঘ্য কম; মাঝের টুকরো উল্টালেই কাটাকাটি খোলে।

নিচের কোড 2-opt-কে ১০টি এলোমেলো শুরু থেকে আর annealing-কে ১০টি seed দিয়ে চালায়, তারপর সেরা পথ আর দৈর্ঘ্য বনাম ধাপের ছবি আঁকে। পরের block এর সংজ্ঞাগুলো ব্যবহার করবে (একই namespace).

import math, random, numpy as np, matplotlib.pyplot as plt
n = 20                        # ২০টি কাল্পনিক ডেলিভারি পয়েন্ট, ১০ × ১০ কিমি বাক্সে
P = np.random.default_rng(44).uniform(0, 10, (n, 2)).round(1)
D = np.hypot(*(P[:, None] - P[None]).T).tolist()        # দূরত্বের টেবিল (কিমি)
tour_len = lambda t: sum(D[t[k - 1]][t[k]] for k in range(n))
def gain(t, i, j):            # t[i..j] উল্টালে (2-opt চাল) দৈর্ঘ্য কত বদলায়
    a, b, c, d = t[i - 1], t[i], t[j], t[(j + 1) % n]
    return D[a][c] + D[b][d] - D[a][b] - D[c][d]
def two_opt(t):               # steepest-ascent hill climbing, 2-opt প্রতিবেশী
    while True:
        g, i, j = min((gain(t, i, j), i, j) for i in range(1, n - 1) for j in range(i + 1, n))
        if g > -1e-9: return t                # কোনো প্রতিবেশী ভালো নয়: থামা
        t[i:j + 1] = t[i:j + 1][::-1]
def anneal(seed, iters=20000, T0=10.0, T1=0.01):
    r = random.Random(seed); t = r.sample(range(n), n)
    cur, T, a, hist = tour_len(t), T0, (T1 / T0) ** (1 / iters), []
    for k in range(iters):
        i = r.randrange(1, n - 1); j = r.randrange(i + 1, n); g = gain(t, i, j)
        if g < 0 or r.random() < math.exp(-g / T):     # খারাপ চালও মাঝে মাঝে
            t[i:j + 1] = t[i:j + 1][::-1]; cur += g
        T *= a; hist.append(cur)                       # ঠান্ডা করা: T ← a·T
    return t, cur, hist
nn = [0]                      # nearest neighbour: সবসময় সবচেয়ে কাছের অদেখা পয়েন্ট
while len(nn) < n: nn.append(min(set(range(n)) - set(nn), key=lambda j: D[nn[-1]][j]))
r = random.Random(1)
two = [tour_len(two_opt(r.sample(range(n), n))) for _ in range(10)]
sa = sorted((anneal(s) for s in range(10)), key=lambda s: s[1])
print("nearest neighbour:", round(tour_len(nn), 2), " তার ওপর 2-opt:", round(tour_len(two_opt(nn[:])), 2))
print("2-opt, ১০টি এলোমেলো শুরু:", np.round(two, 1), "গড়", round(np.mean(two), 2))
print("SA, ১০টি seed:", np.round([s[1] for s in sa], 1), "গড়", round(np.mean([s[1] for s in sa]), 2))
fig, (a1, a2) = plt.subplots(1, 2, figsize=(9, 3.8))
a1.plot(*P[sa[0][0] + sa[0][0][:1]].T, "o-"); a1.set_title(f"Best SA route: {sa[0][1]:.2f} km")
a2.plot(sa[0][2], lw=0.8, label="SA: current tour length")
a2.axhline(np.mean(two), color="red", ls="--", label="2-opt mean of 10 starts")
a2.set_xlabel("iteration"); a2.set_ylabel("km"); a2.legend(fontsize=8); plt.show()

nearest neighbour: 41.01  তার ওপর 2-opt: 38.5
2-opt, ১০টি এলোমেলো শুরু: [39.1 39.  39.1 39.5 39.1 39.  41.4 38.5 39.  38.5] গড় 39.21
SA, ১০টি seed: [38.5 38.5 38.5 38.5 38.5 38.5 38.5 38.5 38.5 39.5] গড় 38.6

38.5 কি আসলেই সেরা? ২০টি পয়েন্টে তা নিশ্চিত বলা যায় Held–Karp dynamic programming দিয়ে, খরচ প্রায় n² · 2ⁿ. ডেস্কটপে একই পয়েন্টে (সত্যিকারের run, Python 3.14.4, NumPy 2.5.1, প্রায় সাড়ে চার সেকেন্ড):

Held-Karp, n = 20 (exact): optimum 38.501 km

তাহলে annealing-এর ৯টি আর 2-opt-এর ২টি run সত্যিকারের সেরা পথই পেয়েছে, যদিও local search নিজে তা জানত না। n = 40 হলে Held–Karp-এর টেবিল কোনো সাধারণ কম্পিউটারের মেমরিতে আঁটবে না, অথচ annealing-এর খরচ প্রায় একই; তাই বাস্তবে ফল মাপা হয় lower bound বা সবচেয়ে ভালো জানা উত্তরের সঙ্গে। গভীর আলোচনা DSA কোর্সের NP-hard সমস্যা বাস্তবে আর approximation algorithm পর্বে।

৭ · অনেক state একসঙ্গে — local beam search আর genetic algorithm

Local beam search একসঙ্গে k-টি state রাখে: প্রতি ধাপে সবগুলোর সব প্রতিবেশী তৈরি, আর তাদের সেরা k-টি পরের ধাপে। এটি k-টি আলাদা random restart নয়: ভালো জায়গার state-এর “বংশ” বেশি জায়গা পায়, খারাপ জায়গার state বাদ পড়ে। দুর্বলতা বৈচিত্র্য হারানো; প্রতিকার stochastic beam search, যেখানে ভালোর সম্ভাবনা বেশি রেখে এলোমেলোভাবে k-টি বাছা হয়।

এক পা এগোলেই genetic algorithm (GA), প্রাকৃতিক নির্বাচনের অনুকরণে। John Holland ১৯৭৫ সালে “Adaptation in Natural and Artificial Systems” বইয়ে এর কাঠামো দেন; David Goldberg-এর ১৯৮৯ সালের বই একে ব্যাপকভাবে পরিচিত করে। উপাদানগুলো:

• Population: একসঙ্গে অনেক প্রার্থী-সমাধান (এখানে ৬০টি পথ)।
• Fitness: কে কত ভালো; এখানে পথ যত ছোট, fitness তত বেশি।
• Selection: এখানে tournament selection: এলোমেলো ৩টি পথ টেনে সবচেয়ে ছোটটি জেতে।
• Crossover: দুই বাবা-মায়ের অংশ মিলিয়ে সন্তান। পথে সাধারণ কাটাকুটিতে একই ঠিকানা দুবার আসতে পারে, তাই order crossover (OX): প্রথমজনের একটি টুকরো হুবহু, বাকি ঘর দ্বিতীয়জনের ক্রমে। কৃতিত্ব সাধারণত Lawrence Davis-এর ১৯৮৫ সালের কাজকে দেওয়া হয়।
• Mutation: ছোট এলোমেলো বদল; এখানে ৩০% সন্তানের একটি টুকরো উল্টানো।
• Elitism: প্রতি প্রজন্মের সেরাটি অক্ষত পরের প্রজন্মে।

1L = [দৈর্ঘ্য(t) for t in pop]2p1 = tournament(pop, 3)3p2 = tournament(pop, 3)4child = ox(p1, p2)5if u < pm: টুকরো উল্টানো6new = [elite] + সন্তানেরা

এবার ২০টি পয়েন্টের আসল সমস্যায় GA: population ৬০, ১২০ প্রজন্ম, ৫টি seed. আগের block-এর পয়েন্ট, দূরত্ব আর tour_len এখানেও ব্যবহৃত।

def ox(p1, p2, r):            # order crossover: p1-এর একটি টুকরো, বাকিটা p2-এর ক্রমে
    i, j = sorted(r.sample(range(n), 2))
    child = [None] * n; child[i:j + 1] = p1[i:j + 1]
    rest = [c for c in p2[j + 1:] + p2[:j + 1] if c not in child[i:j + 1]]
    for k, c in zip([*range(j + 1, n), *range(i)], rest): child[k] = c
    return child
def ga(seed, size=60, gens=120, pm=0.3):
    r = random.Random(seed)
    pop = [r.sample(range(n), n) for _ in range(size)]
    best, mean = [], []
    for g in range(gens):
        L = [tour_len(t) for t in pop]                 # fitness: পথ যত ছোট তত ভালো
        best.append(min(L)); mean.append(sum(L) / size)
        pick = lambda: pop[min(r.sample(range(size), 3), key=L.__getitem__)]  # tournament
        new = [pop[L.index(min(L))][:]]                # elitism: সেরাটি অক্ষত থাকে
        while len(new) < size:
            c = ox(pick(), pick(), r)
            if r.random() < pm:                        # mutation: একটি টুকরো উল্টানো
                i, j = sorted(r.sample(range(n), 2)); c[i:j + 1] = c[i:j + 1][::-1]
            new.append(c)
        pop = new
    return best, mean
runs = [ga(s) for s in range(5)]
print("GA, ৫টি seed, শেষ প্রজন্মের সেরা:", [round(b[-1], 1) for b, m in runs],
      "গড়", round(np.mean([b[-1] for b, m in runs]), 2))
print("seed 0-এর সেরা, প্রজন্ম 0, 20, 60, 119:", [round(runs[0][0][g], 1) for g in (0, 20, 60, 119)])
print("মোট পূর্ণ পথ মাপা হয়েছে, প্রতি run:", 60 * 120)
fig, ax = plt.subplots(figsize=(6, 3.4))
ax.plot(runs[0][0], label="best in population"); ax.plot(runs[0][1], label="population mean")
ax.axhline(sa[0][1], color="gray", ls=":", label="best SA tour")
ax.set_xlabel("generation"); ax.set_ylabel("tour length (km)")
ax.set_title("Genetic algorithm on the 20-stop toy (seed 0)"); ax.legend(fontsize=8)
plt.show()

GA, ৫টি seed, শেষ প্রজন্মের সেরা: [38.9, 39.0, 39.0, 38.5, 38.5] গড় 38.78
seed 0-এর সেরা, প্রজন্ম 0, 20, 60, 119: [93.7, 58.0, 46.0, 38.9]
মোট পূর্ণ পথ মাপা হয়েছে, প্রতি run: 7200

GA জাদু নয়, তাকে tune করতে হয়। একই কোড ডেস্কটপে mutation-এর হার pm আর population বদলে, প্রতি ঘরে ৫টি seed-এর গড়, প্রতি run-এ একই ৭২০০টি পথ-মাপ (সত্যিকারের run, Python 3.14.4):

Mutation না থাকলে population দ্রুত একই রকম পথে ভরে যায়, crossover নতুন কিছু বানাতে পারে না: premature convergence. ছোট population-এ এটি আরও তীব্র (69.79, nearest neighbour-এর চেয়েও খারাপ)। Mutation খুব বেশি হলে বড় population-এ ভালো গঠন বারবার ভাঙে। মাঝের হারটি এই সমস্যা আর বাজেটের জন্য ভালো, অন্য সমস্যায় অন্য সংখ্যা। GA-এর hyperparameter অনেক; তাই “GA ব্যবহার করেছি” যথেষ্ট নয়, কোন সেটিং, কত seed, কোন বাজেট আর কার সঙ্গে তুলনা, তা জানাতে হয়।

৮ · Continuous local search — gradient descent আর SciPy-র optimiser

অনেক সমস্যার state হলো কয়েকটি বাস্তব সংখ্যা, যেমন মডেলের parameter; তখন প্রতিবেশী অসীম। Function মসৃণ হলে সবচেয়ে খাড়া দিক বলে দেয় gradient, সব প্রতিবেশী মাপতে হয় না। পর্ব ৩৪-এর gradient descent তাই steepest-ascent hill climbing-এর continuous রূপ (খরচ কমানোর দিকে), আর সেখানেও local minimum-এর ফাঁদ। Convex function-এ, যেমন বাটিতে, local minimum একটিই, তাই local search-ই যথেষ্ট।

বাস্তবে ব্যবহার হয় scipy.optimize. minimize কোনো method না দিলে (সীমা বা শর্ত না থাকলে) BFGS চালায়, যা gradient-এর ইতিহাস থেকে বাঁকও আন্দাজ করে; gradient-এর সূত্র না দিলে finite difference দিয়ে মাপে। Global optimiser: dual_annealing (annealing-এর সাধারণীকৃত রূপ, local search-সহ) আর differential_evolution (Rainer Storn আর Kenneth Price-এর ১৯৯৭ সালের population-ভিত্তিক পদ্ধতি)। পরীক্ষার জন্য Rastrigin function: ডিমের ট্রের মতো, প্রায় প্রতিটি পূর্ণসংখ্যা বিন্দুর কাছে একটি গর্ত, সবচেয়ে গভীরটি (0, 0)-এ, মান 0.

import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import minimize, dual_annealing, differential_evolution

bowl = lambda v: (v[0] - 3) ** 2 + (v[1] + 1) ** 2      # মসৃণ বাটি, তলা (3, −1)
r = minimize(bowl, [0.0, 0.0])                          # কোনো method না দিলে BFGS
print("বাটি:", np.round(r.x, 4), " nfev =", r.nfev, " success =", r.success)

def f(v):                     # Rastrigin: অনেক গর্তওয়ালা function, সেরা f = 0 বিন্দু (0, 0)-এ
    x, y = v
    return 20 + x**2 - 10 * np.cos(2 * np.pi * x) + y**2 - 10 * np.cos(2 * np.pi * y)
box = [(-5.12, 5.12), (-5.12, 5.12)]
starts = np.random.default_rng(42).uniform(-5.12, 5.12, (8, 2))
loc = [minimize(f, s) for s in starts]                  # local: ঢাল ধরে নামা
for s, o in zip(starts, loc):
    print(f"শুরু ({s[0]:5.2f}, {s[1]:5.2f}) → ({o.x[0]:5.2f}, {o.x[1]:5.2f}),"
          f" f = {o.fun:6.3f}, nfev = {o.nfev}")
da = dual_annealing(f, box, rng=42)
de = differential_evolution(f, box, rng=42)
for name, o in [("dual_annealing", da), ("differential_evolution", de)]:
    print(f"{name:22s}: x = {np.round(o.x, 4) + 0}, f = {o.fun:.1e}, nfev = {o.nfev}")

g = np.linspace(-5.12, 5.12, 300); X, Y = np.meshgrid(g, g)
fig, ax = plt.subplots(figsize=(5, 4.4))
ax.contourf(X, Y, f([X, Y]), levels=30, cmap="viridis")
for s, o in zip(starts, loc):
    ax.annotate("", o.x, s, arrowprops=dict(arrowstyle="->", color="white"))
ax.plot(*np.array([o.x for o in loc]).T, "wo", ms=4, label="BFGS end points")
ax.plot(*de.x, "r*", ms=14, label="differential_evolution")
ax.set_title("Rastrigin: local (BFGS) vs global search"); ax.legend(fontsize=8)
plt.show()

বাটি: [ 3. -1.]  nfev = 9  success = True
শুরু ( 2.81, -0.63) → ( 2.98, -0.99), f =  9.950, nfev = 33
শুরু ( 3.67,  2.02) → ( 3.98,  1.99), f = 19.899, nfev = 30
শুরু (-4.16,  4.87) → (-3.98,  4.97), f = 40.793, nfev = 33
শুরু ( 2.67,  2.93) → ( 2.98,  2.98), f = 17.909, nfev = 27
শুরু (-3.81, -0.51) → (-3.98, -0.99), f = 16.914, nfev = 42
শুরু (-1.32,  4.37) → ( 0.00,  3.98), f = 15.919, nfev = 51
শুরু ( 1.47,  3.31) → (-0.99, -2.98), f =  9.950, nfev = 54
শুরু (-0.58, -2.79) → (-0.99, -3.98), f = 16.914, nfev = 30
dual_annealing        : x = [0. 0.], f = 7.1e-15, nfev = 4064
differential_evolution: x = [0. 0.], f = 0.0e+00, nfev = 1923

দুটি ব্যবহারিক কথা। এক, seed দেওয়া হয়েছে rng=42 দিয়ে; পুরোনো কোড আর টিউটোরিয়ালে একই কাজে seed= দেখবেন, তাই আপনার version-এর docs মিলিয়ে নিন। দুই, global optimiser-কে সীমার বাক্স (bounds) দিতে হয়; বাক্স ভুল হলে সেরা উত্তর বাইরেই থেকে যায়। কোটি parameter-এর মডেলে এই global পদ্ধতিগুলো অচল; সেখানে gradient-ভিত্তিক local search-ই ব্যবহারিক পথ।

৯ · No free lunch, বাস্তবের ব্যবহার আর সৎভাবে ফল জানানো

No free lunch theorem — সাবধানে বলা

এত পদ্ধতির মধ্যে কোনটি সেরা? David Wolpert আর William Macready ১৯৯৭ সালে IEEE Transactions on Evolutionary Computation-এ “No Free Lunch Theorems for Optimization” প্রবন্ধে একটি কঠোর উত্তর দেন। মোটামুটি কথাটি এই: একটি সসীম search space-এ সম্ভাব্য সব objective function-এর ওপর গড় নিলে, যেকোনো দুটি search পদ্ধতির (যারা একই বিন্দু বারবার মাপে না) গড় কর্মক্ষমতা সমান। এলোমেলো খোঁজাও সেই গড়ে annealing বা GA-এর সমান।

এর মানে “সব পদ্ধতি সমান” নয়। সব সম্ভাব্য function-এর বেশির ভাগই কাঠামোহীন, যেখানে কাছের বিন্দুর মান থেকে কিছুই বোঝা যায় না। বাস্তবের সমস্যা তেমন নয়: কাছাকাছি দুটি পথের দৈর্ঘ্য কাছাকাছি, local search ঠিক এই কাঠামোয় বাজি ধরে। আসল শিক্ষা: কোনো পদ্ধতির সুবিধা আসে সমস্যার কাঠামো সম্পর্কে তার অনুমান থেকে; কাঠামো না মিললে সুবিধাও নেই। “আমার algorithm সব সমস্যায় সেরা” দাবি টেকে না।

বাস্তবে কোথায় local search

প্রকাশিত কাজে local search-এর ধারণা দেখা যায় যানবাহনের রুট পরিকল্পনা (vehicle routing), shift আর পরীক্ষার রুটিন, চিপের অংশ সাজানো (VLSI placement) আর গুদামের নকশায়। বাস্তব সফটওয়্যারে প্রায়ই কৌশল মেশানো থাকে: দ্রুত নির্মাণ-পদ্ধতি দিয়ে শুরু, তারপর 2-opt-এর মতো local search, ওপরে annealing বা tabu, কখনো integer programming-এর সঙ্গে জোড়া। কোন কোম্পানি ঠিক কী ব্যবহার করে, তা সাধারণত প্রকাশ্য নয়। বাংলাদেশে ডেলিভারি বা রুটিনের কাজে এমন প্রয়োগ সম্ভব, তবে কোথায় কতটা হচ্ছে তার নির্ভরযোগ্য তথ্য আমাদের জানা নেই।

Seed আর গড় — একটি ভাগ্যবান run নয়

এই পর্বের প্রতিটি তুলনা অনেক run-এর, কারণ একটি run একটি নমুনা। সৎ রিপোর্টের অভ্যাস:

• Seed ঠিক করে লিখে রাখুন (পর্ব ১৬), আর seed-এর তালিকা আগে থেকে ঠিক করুন, ফল দেখে নয়।
• গড় আর ছড়ানো দুটিই জানান: গড়, standard deviation বা সেরা-খারাপ, সফলতার হারের standard error (পর্ব ৩৭).
• সমান বাজেটে তুলনা: সমান সময় বা function-হিসাব; ১০০ গুণ বেশি হিসাবে জেতা আসল জয় নয়।
• সরল baseline: random restart বা nearest neighbour; জটিল পদ্ধতি এদের না হারালে জটিলতার দাম নেই।
• Tuning-এর খরচও গুনুন: ৫০ বার tune করা পদ্ধতিকে একবারের সেটিং-এর পদ্ধতির সঙ্গে তুলনা অন্যায্য।

১০ · AI-এর যুগে — AI সহকারীর optimisation কোড যাচাই

“TSP-এর জন্য simulated annealing লিখে দাও” বললে AI সহকারী কয়েক সেকেন্ডে চলনসই কোড দেয়। কিন্তু “চলে” আর “ভালো কাজ করে” আলাদা কথা। AI সহকারীরা প্রায়ই যা করে:

• গ্রহণের নিয়মে চিহ্ন উল্টে ফেলে (exp(g / T)), বা খরচ কমানোর সমস্যায় maximise-এর নিয়ম বসায়; ফল বিশ্বাসযোগ্য দেখায়, অথচ পদ্ধতিটি এলোমেলো হাঁটা।
• প্রতি ধাপে পুরো পথ নতুন করে মাপে (শতগুণ ধীর), বা উল্টানোর index-এ এক ঘরের ভুল করে, যাতে কিছু চাল কখনো চেষ্টাই হয় না।
• Temperature এককের সঙ্গে মেলায় না (মিটারে T = 1 মানে প্রায় খাঁটি hill climbing), আর একটি run দেখিয়ে “annealing ভালো” বলে।
• পুরোনো বা বানানো API লেখে (seed বনাম rng, অস্তিত্বহীন parameter), আর warnings.filterwarnings("ignore") দিয়ে warning চাপা দেয়।
• না-মাপা দাবি করে: “GA সবসময় global optimum পায়”, বা না-চালানো আউটপুট বানিয়ে লেখে।

AI-এর কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• গ্রহণের নিয়ম হাতে মিলিয়েছি: ভালো চাল সবসময়, খারাপ চাল exp(−Δ/T), আর Δ-এর চিহ্ন খরচ কমানোর সঙ্গে সঙ্গতিপূর্ণ
• দ্রুত Δ-এর হিসাব কয়েকটি এলোমেলো চালে পুরো পথ মাপার সঙ্গে মিলিয়ে দেখেছি
• অনেক seed-এ চালিয়ে গড় আর ছড়ানো দেখেছি, একটি ভাগ্যবান run নয়; seed-এর তালিকা আগে ঠিক করা
• সমান বাজেটে একটি সরল baseline-এর (random restart বা nearest neighbour + 2-opt) সঙ্গে তুলনা করেছি
• ছোট সমস্যায় সম্ভব হলে নির্ভুল উত্তরের (brute force বা Held–Karp) সঙ্গে মিলিয়েছি
• প্রতিটি অচেনা SciPy function আর parameter অফিসিয়াল docs-এ (scipy.org) আমার version-এর জন্য মিলিয়েছি, আর গ্রাহকের আসল ঠিকানা AI-তে পেস্ট করিনি