Neural Sync Active

🧬 Genetic Algorithms

Registry Synced

🧬 Genetic Algorithms

849 words

4 min read

Reading compass

Now · 1. 🎯 Learning Objectives

🧬 Genetic Algorithms

1. 🎯 Learning Objectives

Explain the biological analogy: selection, crossover, mutation
Trace one generation of a GA: selection → crossover → mutation
Implement PMX (Partially Mapped Crossover) and Cycle Crossover for TSP
Analyze GA parameters: population size, crossover rate, mutation rate
Distinguish path representation vs ordinal representation for TSP

2. 📖 Core Content

3.1 Intuition: Evolution as Search

Evolution searches through the space of possible organisms by:

Selection: Fit individuals reproduce more
Crossover: Offspring combine traits from two parents
Mutation: Random changes introduce variation A Genetic Algorithm (GA) applies these principles to search problems. Individuals are candidate solutions, fitness is solution quality, and evolution drives improvement over generations.

3.2 GA Algorithm Outline


text
GeneticAlgorithm(population_size, generations, fitness, crossover_rate, mutation_rate):
    // Initialize random population
    population = [random_individual() for _ in range(population_size)]
    for gen in range(generations):
        // Evaluate fitness
        fitnesses = [fitness(ind) for ind in population]
        // Selection
        mating_pool = select_parents(population, fitnesses)
        // Crossover
        offspring = []
        for i in range(0, population_size, 2):
            p1, p2 = mating_pool[i], mating_pool[i+1]
            if random() < crossover_rate:
                c1, c2 = crossover(p1, p2)
            else:
                c1, c2 = p1, p2
            offspring.extend([c1, c2])
        // Mutation
        for i in range(population_size):
            if random() < mutation_rate:
                offspring[i] = mutate(offspring[i])
        population = offspring
    return best_individual(population)

3.3 Selection Methods

Fitness Proportionate Selection (Roulette Wheel):

Probability of selection ∝ fitness
$P(i) = f(i) / \sum_j f(j)$ Tournament Selection:
Pick k individuals randomly
Select the best among them
Repeated to fill mating pool Rank Selection:
Sort by fitness, select proportional to rank
Reduces domination by super-fit individuals

3.4 Crossover for TSP (Permutation Encoding)

TSP requires permutation encoding — each city appears exactly once. Standard crossover (1-point, 2-point) can produce invalid tours with duplicate cities. Partially Mapped Crossover (PMX):

Choose two crossover points
Copy the segment between points from parent 1 to child 1
Map the segment from parent 2 to maintain permutation PMX Example: Parent 1: [1, 2, 3, | 4, 5, 6, | 7, 8, 9] Parent 2: [9, 3, 7, | 8, 2, 5, | 1, 4, 6] Crossover points: positions 3 and 6 Child 1 starts: [?, ?, ?, | 4, 5, 6, | ?, ?, ?] Mapping from parent 2's segment [8, 2, 5]:

8 → ? At position 3 in P1 = 4. Put 8 at position where 4 goes? Actually PMX:
1. Copy segment: Child1[3:6] = [4,5,6]
2. Map P2[3:6] = [8,2,5] to P1 positions:
  - 8 maps to 4 (from segment mapping)
  - 2 maps to 5
  - 5 maps to 6
3. Fill remaining positions from P2, resolving via mapping Cycle Crossover (CX):

Find cycles in the permutation mapping between parents
Copy alternating cycles from each parent Order Crossover (OX):
Copy a segment from parent 1
Fill remaining positions with cities from parent 2 in order, skipping duplicates

3.5 Mutation for TSP

Swap mutation: Swap two random cities Insert mutation: Move one city to a new position Inversion mutation: Reverse a sub-sequence

3.6 Worked Example: GA for TSP (5 cities)

Cities: A(0,0), B(1,2), C(3,1), D(4,3), E(2,4) Population size: 4 Initial population:

[A, B, C, D, E] fitness = 1/distance
[A, C, B, D, E]
[B, A, C, E, D]
[C, D, A, B, E] Fitness calculation: Distance matrix → total tour distance → fitness = 1/total Selection: Roulette wheel based on fitness Crossover (PMX): Combine two selected parents Mutation: Small probability of swapping two cities After one generation, the average fitness should increase.

4. 📐 Key Formulas

Concept	Formula
Selection probability	$P(i) = f(i) / \sum f(j)$
Crossover rate	Typically 0.7-1.0
Mutation rate	Typically 0.01-0.1 per gene
Population size	50-500 (problem dependent)

5. ⚠️ Common Pitfalls

Pitfall 1: Premature Convergence

The mistake: Population converges to a single solution too quickly. Solution: Increase mutation rate, use larger population, or use tournament selection instead of roulette wheel.

Pitfall 2: Invalid Offspring from Crossover

The mistake: Using standard 1-point crossover on permutation encoding creates invalid tours (duplicate cities). Correct approach: Use PMX, Cycle Crossover, or Order Crossover designed for permutations.

Pitfall 3: Selection Pressure Too High

The mistake: Only the fittest individuals reproduce, diversity collapses. Solution: Use rank selection or tournament selection to give weaker individuals a chance.

6. 📝 Practice Questions

Q1: Using PMX, cross Parent1=[1,2,3,4,5,6,7,8,9] and Parent2=[9,3,7,8,2,5,1,4,6] with crossover points 3 and 6.

Answer: Child1: Copy P1[3:6]=[4,5,6]. Mapping from P2[3:6]=[8,2,5] → [4,5,6]: 8↔4, 2↔5, 5↔6. Fill remaining: from P2: 9 (not in child yet) → pos 0; 3 → pos 1; 7 → pos 2; 8 maps to 4 (already used) → pos 6; 1 → pos 7; 4 already in segment → pos 8... Child1: [9,3,7,4,5,6,8,1,2]. Q2: What is the purpose of mutation in a GA?

Answer: Mutation maintains diversity in the population and prevents premature convergence to local optima. It allows the algorithm to explore regions of the search space not reachable through crossover alone. Join Discord PreviousBeam Search & VNDNextACO & Emergent