Genetic Algorithm

by Sajjad Ahmed Niloy

Genetic Algorithms

Breeds a population of solutions over generations to find the best one.

How it Works

Initial Population: Start with many random solutions.
Fitness Evaluation: Score how good each solution is.
Selection: The best solutions are chosen to be "parents".
Crossover & Mutation: Parents create "offspring" by combining and randomly changing genes.
New Generation: The new population replaces the old, and the cycle repeats.

Analogy: Breeding Racehorses

Start with many horses. Let the fastest ones breed. Their offspring are likely to be fast. Over many generations, you evolve an even faster horse.

Pros

Excellent for global optimization.
Handles very complex problems.

Cons

Computationally expensive.
Many parameters to configure.

Simulation

A population of random phrases evolves to match the target. Watch how the "Best Phrase" gets closer each generation and see a live sample of the population's "DNA".

Speed:

Deconstructing the Simulation:

1. The "DNA": Each possible solution is a string of characters, like `"aBcde Fgh..."`. This is the "chromosome", and each character is a "gene".

2. Fitness Function: To decide which phrases are "better", we score them. The fitness score is simply the number of characters that correctly match the target phrase (`"Genetic Algorithm!"`). A higher score means a better phrase.

3. The Mating Pool (Selection): The algorithm creates a "mating pool" for reproduction. Phrases with higher fitness scores are added to the pool more times, giving them a higher chance of being selected as "parents" for the next generation.

4. Reproduction (Crossover & Mutation):
• Crossover: Two "parent" phrases are chosen. The "child" phrase is created by taking the first half of one parent's characters and the second half of the other parent's characters.
• Mutation: To introduce new possibilities, each character in the new child has a very small chance (e.g., 1%) of being replaced by a completely random new character. This is crucial for innovation and preventing stagnation.

This cycle repeats, and with each generation, the average fitness of the population increases until the target phrase is evolved.

Python Code Example

# --- Conceptual Example ---
# Goal: Evolve a string to match a target
import random

TARGET = "HELLO"
POP_SIZE = 100
VALID_GENES = " ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def random_char():
    return random.choice(VALID_GENES)

def fitness(individual):
    # Higher score is better
    score = sum(1 for i, c in enumerate(individual) if c == TARGET[i])
    return score

# 1. Initialization
population = ["".join(random_char() for _ in range(len(TARGET))) for _ in range(POP_SIZE)]

for generation in range(500):
    # 2. Selection
    parents = sorted(population, key=fitness, reverse=True)[:10]

    # 3. Crossover & 4. Mutation
    offspring = []
    for _ in range(POP_SIZE):
        p1, p2 = random.sample(parents, 2)
        child = "".join(p1[i] if random.random() < 0.5 else p2[i] for i in range(len(TARGET)))
        
        if random.random() < 0.2: # Mutate
             child_list = list(child)
             child_list[random.randint(0, len(TARGET)-1)] = random_char()
             child = "".join(child_list)
        offspring.append(child)
    
    population = offspring
    if TARGET in population:
        break

print(f"Best solution found: {max(population, key=fitness)}")
                        