Evolution and Genetic Algorithm

সমস্যা: কৃত্রিম বুদ্ধিমত্তায় (AI) Evolution এবং Genetic Algorithm

সমাধান:

1. মূল ধারণা: AI-তে Evolution

AI ধারণাটি জীববিজ্ঞানের evolution বা “বিবর্তন”-এর নীতি থেকে ধার নেয়:
অনেক প্রার্থী (candidates) একে অপরের সঙ্গে প্রতিযোগিতা করে, ভালো প্রার্থীরা টিকে থাকে ও পুনরায় মিলিত হয়ে নতুন প্রজন্ম তৈরি করে,
এবং এলোমেলো পরিবর্তন (random changes) বৈচিত্র্য আনে — এর ফলে প্রজন্মের পর প্রজন্মে সমাধান আরও উন্নত হয়।
এই প্রক্রিয়াটি স্বয়ংক্রিয়ভাবে সম্পন্ন করা হয় Genetic Algorithm (GA) ব্যবহার করে।

2. Genetic Algorithm (GA) কী?

GA হলো একটি search এবং optimization পদ্ধতি, যা natural selection দ্বারা অনুপ্রাণিত।
এটি ক্রমান্বয়ে প্রার্থী সমাধানের (candidate solutions) একটি population উন্নত করে নিচের ধাপগুলোর মাধ্যমে:
- Selection: ভালো প্রার্থী বাছাই করা।
- Crossover: দুটি parent-এর অংশ মিলিয়ে সন্তান তৈরি করা।
- Mutation: ছোট এলোমেলো পরিবর্তন আনা।

3. গুরুত্বপূর্ণ পরিভাষা (Key Terms)

Chromosome: কোড করা প্রার্থী সমাধান (যেমন: bit string, অক্ষর, সংখ্যা ইত্যাদি)।
Gene: Chromosome-এর একটি নির্দিষ্ট অবস্থান।
Population: একটি প্রজন্মে থাকা সমস্ত Chromosome-এর সেট।
Fitness Function: একটি স্কোর যা বলে দেয় একটি Chromosome কত ভালো কাজ করছে।
Selection: Parent বাছাইয়ের পদ্ধতি (যেমন: tournament, roulette wheel)।
Crossover: দুই parent-এর অংশ মিশিয়ে নতুন সন্তান তৈরি করা (যেমন: one-point crossover)।
Mutation: এলোমেলোভাবে কিছু gene পরিবর্তন করে বৈচিত্র্য বজায় রাখা।
Elitism: সেরা কয়েকটি Chromosome অপরিবর্তিত রেখে পরবর্তী প্রজন্মে নেওয়া।
Convergence: যখন population আর উল্লেখযোগ্যভাবে পরিবর্তন হয় না (অর্থাৎ optimum-এর কাছে পৌঁছে যায়)।

4. Standard GA-এর কাজের ধারা (Workflow)

সমাধানগুলোকে Chromosome আকারে উপস্থাপন করো এবং Fitness Function নির্ধারণ করো।
একটি random প্রাথমিক Population তৈরি করো।
প্রতিটি Chromosome-এর Fitness নির্ণয় করো।
নিম্নলিখিত ধাপগুলো পুনরাবৃত্তি করো যতক্ষণ না Stop Condition পূর্ণ হয় (যেমন সর্বাধিক প্রজন্ম বা লক্ষ্য Fitness):
- Selection: ভালো Fitness-যুক্ত Parent বাছাই করো।
- Crossover: Parent-দের মিশিয়ে সন্তান তৈরি করো।
- Mutation: কিছু Gene এলোমেলোভাবে পরিবর্তন করো।
- Elitism: সেরা Chromosome রেখে নতুন Population তৈরি করো।
সর্বশেষে, সেরা Chromosome রিপোর্ট করো।

5. ধাপে ধাপে উদাহরণ : একটি শব্দ “Evolve” করা

লক্ষ্য: Genetic Algorithm ব্যবহার করে “CAT” শব্দটি evolve করা।
উপস্থাপন (Representation): প্রতিটি Chromosome একটি ৩-অক্ষরের string (প্রতিটি অক্ষর একটি gene)।
Alphabet: বড় হাতের A–Z।
Fitness: যত বেশি অক্ষর লক্ষ্য শব্দের (CAT) সঙ্গে মিলবে, Fitness তত বেশি।

(1) Setup

Chromosome দৈর্ঘ্য: ৩
Population Size: ৬
Selection: ২ জনের Tournament (দুইজনের মধ্যে ভালোটি নির্বাচন)
Crossover: One-point (position 1 বা 2-এর পরে কাটা)
Mutation: অল্প সম্ভাবনায় (প্রতি gene-এ) এলোমেলোভাবে নতুন অক্ষর বসানো
Elitism: প্রতিটি প্রজন্মে সেরা Chromosome অপরিবর্তিত রাখা

(2) Generation 0: Random Population (উদাহরণস্বরূপ)

Individual	Chromosome	Target মিল (CAT অনুযায়ী)	Fitness
1	Q Z P	_ _ _	0
2	C Q R	C _ _	1
3	B A T	_ A T	2
4	D A X	_ A _	1
5	C A P	C A _	2
6	W T T	_ _ T	1

➡️ সেরা উদাহরণ: “C A P” ও “B A T” (Fitness = 2)

(3) Selection:
Tournament পদ্ধতিতে ভালো Fitness-যুক্ত Chromosome-এর নির্বাচনের সম্ভাবনা বেশি।
Parent হিসেবে সাধারণত সেরা কয়েকটি (যেমন “C A P” ও “B A T”) বেছে নেওয়া হয়।

(4) Crossover (One-point):
Crossover Point → Position 2 এবং 3-এর মাঝে

Parent 1: C A | P
Parent 2: B A | T

ফলাফল:

Child 1: C A | T → “C A T” ✅ (perfect match)
Child 2: B A | P → “B A P”

(5) Mutation:
অল্প সম্ভাবনায় (প্রতি gene-এ) Mutation ঘটতে পারে।
যদি “B A P”-এ Mutation ঘটে, কোনো একটি অক্ষর এলোমেলোভাবে বদলাতে পারে;
না ঘটলে সেটি অপরিবর্তিত থাকবে।

(6) পরবর্তী প্রজন্ম:

আগের প্রজন্মের সেরা Chromosome অপরিবর্তিত রাখো (Elitism)।
নতুন Child গুলো যোগ করো।
অন্য স্থানে নতুন Crossover ও Mutation প্রয়োগ করো।

ধীরে ধীরে Selection ও Crossover-এর মাধ্যমে সঠিক অক্ষরগুলো একত্রিত হয়ে “C A T” দ্রুত তৈরি হয়।

(7) থামার শর্ত(Stop Criteria):

যখন লক্ষ্য শব্দ “CAT” তৈরি হয় বা সর্বাধিক প্রজন্ম পূর্ণ হয়, তখন থামো।
শেষে সেরা Chromosome (এখানে “CAT”) রিপোর্ট করো।

6. কেন এটি কাজ করে (Why this works)

Selection: সঠিক অংশ থাকা Chromosome-গুলোকে অগ্রাধিকার দেয়।
Crossover: বিভিন্ন Parent-এর সঠিক অংশগুলো মিলিয়ে নেয়।
Mutation: নতুন বৈচিত্র্য আনে ও স্থবিরতা (stagnation) রোধ করে।

এই তিনটি মিলে একটি guided random search তৈরি করে, যা নির্দিষ্ট নিয়ম জানা না থাকলেও ভালো সমাধান খুঁজে পায়।

7. ব্যবহারিক পরামর্শ (Practical Tips)

Fitness Function এমনভাবে বানাও যাতে সেটি বাস্তব সফলতার সঙ্গে সম্পর্কিত হয়।
বৈচিত্র্য বজায় রাখো (Mutation rate, Tournament size ইত্যাদি নিয়ন্ত্রণ করে)।
Elitism ব্যবহার করো যাতে সেরা সমাধান হারিয়ে না যায়।
Population Size, Mutation Rate ইত্যাদি মান বাস্তব পরীক্ষার মাধ্যমে নির্ধারণ করো।

Example : Travelling Salesman Problem

Here’s the full transcribed text from the image titled “GA Approach”, which outlines the steps for applying a Genetic Algorithm (GA) to solve the Traveling Salesman Problem (TSP):

🧬 GA Approach:

Chromosome Representation:
A permutation of city indices.
- Example: For 5 cities, a chromosome could be [1, 3, 5, 2, 4].
Fitness Function:
The total distance of the route represented by the chromosome.
- Calculate the distance for each route permutation and use the inverse of this distance as the fitness value (shorter distances have higher fitness).
Selection:
Roulette wheel selection or tournament selection to choose parent chromosomes based on fitness.
Crossover:
Order crossover (OX) where segments of parents are exchanged while maintaining city sequence.
- Example:
  - Parent1 = [1, 3, 5, 2, 4]
  - Parent2 = [2, 4, 3, 1, 5]
  - Offspring could be: [1, 3, 5, 4, 2]
Mutation:
Swap mutation where two cities in the chromosome are swapped to introduce variation.
- Example: Mutate [1, 3, 5, 2, 4] → [1, 3, 2, 5, 4]
Replacement:
Replace the least fit chromosomes in the population with the new offspring.
Termination:
Continue for a set number of generations or until a satisfactory solution is found.

“Step 1: Initialization”, which sets up the Genetic Algorithm (GA) for solving the Traveling Salesman Problem (TSP):

🚀 Step 1: Initialization

Cities: Assume 5 cities with the following distances between them:

	1	2	3	4	5
1	0	2	10	4	5
2	2	0	6	7	3
3	10	6	0	6	4
4	4	7	6	0	6
5	5	3	4	6	0

Initial Population: Let’s assume an initial population of 4 chromosomes:

Chromosome 1: [1, 3, 5, 2, 4]
Chromosome 2: [2, 5, 1, 4, 3]
Chromosome 3: [4, 2, 3, 1, 5]
Chromosome 4: [5, 2, 1, 3, 4]

“Step 2: Calculate Fitness”, which includes detailed distance and fitness calculations for four chromosomes in the Genetic Algorithm approach to solving the Traveling Salesman Problem (TSP):

🧮 Step 2: Calculate Fitness

Chromosome 1: [1, 3, 5, 2, 4]

Route: 1 → 3 → 5 → 2 → 4 → 1
Distance: (8 + 3 + 5 + 4 + 9 = 29)
Fitness: ( \frac{1}{29} \approx 0.0345 )

Chromosome 2: [2, 5, 1, 4, 3]

Route: 2 → 5 → 1 → 4 → 3 → 2
Distance: (5 + 7 + 9 + 7 + 6 = 34)
Fitness: ( \frac{1}{34} \approx 0.0294 )

Chromosome 3: [3, 4, 2, 1, 5]

Route: 3 → 4 → 2 → 1 → 5 → 3
Distance: (7 + 2 + 1 + 5 + 7 = 31)
Fitness: ( \frac{1}{31} \approx 0.0323 )

Chromosome 4: [5, 2, 4, 3, 1]

Route: 5 → 2 → 4 → 3 → 1 → 5
Distance: (4 + 4 + 7 + 8 + 3 = 26)
Fitness: ( \frac{1}{26} \approx 0.0385 )

Here’s the full transcribed content from the fifth image titled “Step 3: Selection, Step 4: Crossover, Step 5: Mutation”, which outlines the next stages in the Genetic Algorithm process for solving the Traveling Salesman Problem (TSP):

🎯 Step 3: Selection

Using roulette wheel selection, we select parents based on their fitness.

🔗 Step 4: Crossover

Parents: Let’s select Chromosome 1 and Chromosome 2 for crossover.

Order Crossover (OX):

Parent 1: [1, 3, 5, 4, 2]
Parent 2: [2, 1, 5, 3, 4]
Offspring 1: [1, 3, 5, 4, 2]
Offspring 2: [2, 5, 1, 3, 4]

🔄 Step 5: Mutation

Offspring 1 before mutation: [1, 3, 5, 4, 2]

Swap mutation: Swap city 3 and city 5
After mutation: [1, 5, 3, 4, 2]

Offspring 2 before mutation: [2, 5, 1, 3, 4]

Swap mutation: Swap city 1 and city 4
After mutation: [2, 5, 4, 3, 1]

Here’s the full transcribed content from the sixth image titled “Step 6: Replacement & Step 7: Termination”, which concludes the Genetic Algorithm cycle for solving the Traveling Salesman Problem (TSP):