evolution.py

#!/usr/bin/env python3
"""
Evolution Algo Simulation

A Python program using evolutionary algorithms to evolve any 3-word target.
Models natural selection with species grouping, elitism, crossover, and mutation.
"""

import random
import argparse
from typing import List

# ============================================================================
# CONFIGURATION
# ============================================================================

POPULATION_SIZE = 60
GENOME_MUTATION_RATE = 0.01  # Per-genome (not per-gene) for slower, more stable evolution
SPECIES_THRESHOLD = 1  # Tight niches - requires genomes to be nearly identical to speciate together
VERBOSE = True

MIN_VOCAB_SIZE = 50
MAX_GENERATION_CAP = 20000
CROSSOVER_RATE = 0.7

WORD_POOL = [
    # Animals
    "DOG", "FOX", "BIRD", "RABBIT", "CAT", "HORSE", "MOUSE", "WOLF",
    "BEAR", "LION", "TIGER", "EAGLE", "SHARK", "WHALE", "SNAKE",
    # Verbs
    "SEES", "CHASES", "LIKES", "EATS", "RUNS", "JUMPS", "SLEEPS",
    "HUNTS", "GROWS", "CHANGES", "FIGHTS", "WALKS", "FLIES", "SWIMS",
    # Objects
    "MEAT", "BUG", "FOOD", "FISH", "BONE", "TREE", "ROCK", "WATER",
    "GRASS", "STONE", "LEAF", "RAT", "DEER", "FROG",
    # Pronouns/Other
    "I", "YOU", "HE", "SHE", "IT", "WE", "THEY",
    "BIG", "SMALL", "FAST", "SLOW", "OLD", "NEW", "YOUNG", "WILD"
]

# ============================================================================
# GLOBAL STATE (set during main())
# ============================================================================

TARGET: List[str] = []        # Target phrase (e.g., ["CAT", "EATS", "FISH"])
GENOME_LENGTH: int = 0        # Number of words per genome (same as len(TARGET))
VOCAB: List[str] = []         # Vocabulary pool for genome generation
VOCAB_SIZE: int = 0           # Total vocabulary size
SEARCH_SPACE: int = 0         # Total possible combinations (vocab^genome_length)
MAX_GENERATIONS: int = 0      # Maximum generations allowed (capped)

# ============================================================================
# 1. USER INPUT
# ============================================================================

def get_user_input() -> List[str]:
    """Prompt user for target phrase."""
    while True:
        user_input = input("Enter 3-word target: ").strip().upper()
        words = user_input.split()

        if len(words) == 3 and all(w.isalpha() for w in words):
            return words

        print("Please enter exactly 3 alphabetic words.")


# ============================================================================
# 2. VOCABULARY GENERATION
# ============================================================================

def generate_vocabulary(target_words: List[str]) -> List[str]:
    """Build vocabulary from target + random pool words."""
    vocab = set(target_words)

    available = [w for w in WORD_POOL if w not in vocab]
    random.shuffle(available)

    while len(vocab) < MIN_VOCAB_SIZE:
        if available:
            vocab.add(available.pop())
        else:
            vocab.add(f"WORD{len(vocab)}")

    return sorted(vocab)


# ============================================================================
# 3. SEARCH SPACE & MAX GENERATIONS
# ============================================================================

def compute_parameters(vocab_size: int, genome_length: int) -> tuple[int, int]:
    """Calculate search space and maximum generations allowed.

    Args:
        vocab_size: Number of words in vocabulary.
        genome_length: Number of words per genome (target length).

    Returns:
        Tuple of (search_space, max_generations).
    """
    search_space = vocab_size ** genome_length
    expected = search_space / POPULATION_SIZE
    max_generations = int(expected * 10) + 50

    # Cap at hard limit
    max_generations = min(max_generations, MAX_GENERATION_CAP)

    return search_space, max_generations


# ============================================================================
# 4. GENOME & POPULATION
# ============================================================================

Genome = List[str]


def create_random_genome() -> Genome:
    """Create a random genome."""
    return [random.choice(VOCAB) for _ in range(GENOME_LENGTH)]


def initialize_population() -> List[Genome]:
    """Create random population with maximum initial diversity."""
    return [create_random_genome() for _ in range(POPULATION_SIZE)]


# ============================================================================
# 5. FITNESS FUNCTION
# ============================================================================

def calculate_fitness(genome: Genome, target: List[str]) -> int:
    """Count matching words at matching positions."""
    return sum(1 for gene, target_gene in zip(genome, target)
                if gene == target_gene)


def evaluate_population(population: List[Genome], target: List[str]) -> List[int]:
    """Evaluate fitness for entire population."""
    return [calculate_fitness(ind, target) for ind in population]


# ============================================================================
# 6. MUTATION
# ============================================================================

def mutate(genome: Genome) -> Genome:
    """Mutate genome based on GENOME_MUTATION_RATE. Exactly 1 gene mutates if selected."""
    if random.random() < GENOME_MUTATION_RATE:
        mutated = genome.copy()
        position = random.randint(0, GENOME_LENGTH - 1)
        choices = [w for w in VOCAB if w != genome[position]]
        mutated[position] = random.choice(choices)
        return mutated
    return genome


def crossover(parent1: Genome, parent2: Genome) -> Genome:
    """Single-point crossover between two parents."""
    point = random.randint(1, GENOME_LENGTH - 1)
    return parent1[:point] + parent2[point:]


def reproduce(survivors: List[Genome]) -> List[Genome]:
    """Create offspring through crossover and mutation."""
    offspring = []

    while len(offspring) < POPULATION_SIZE:
        parent1 = random.choice(survivors)
        parent2 = random.choice(survivors)

        if random.random() < CROSSOVER_RATE:
            child = crossover(parent1, parent2)
        else:
            child = parent1.copy()

        offspring.append(mutate(child))

    return offspring


# ============================================================================
# 7. SPECIES GROUPING
# ============================================================================

def hamming_distance(genome1: Genome, genome2: Genome) -> int:
    """Count positions where genomes differ."""
    return sum(g1 != g2 for g1, g2 in zip(genome1, genome2))


def group_into_species(population: List[Genome]) -> List[List[tuple]]:
    """Group population into species by similarity."""
    fitness_scores = evaluate_population(population, TARGET)
    individuals = list(zip(population, fitness_scores))

    species = []

    for genome, fitness in individuals:
        assigned = False

        for sp in species:
            representative = sp[0][0]
            if hamming_distance(genome, representative) <= SPECIES_THRESHOLD:
                sp.append((genome, fitness))
                assigned = True
                break

        if not assigned:
            species.append([(genome, fitness)])

    return species


# ============================================================================
# 8. SELECTION
# ============================================================================

def select_within_species(species: List[List[tuple]]) -> List[Genome]:
    """Select survivors within each species. Keep top 50%."""
    survivors = []

    for sp in species:
        sp.sort(key=lambda x: x[1], reverse=True)
        keep_count = max(1, len(sp) // 2)
        survivors.extend([genome for genome, _ in sp[:keep_count]])

    return survivors


# ============================================================================
# 9. ELITISM
# ============================================================================

def preserve_elite(survivors: List[Genome], population: List[Genome],
                   fitness_scores: List[int]) -> List[Genome]:
    """Ensure best genome survives unchanged. Maintain population size."""
    best_idx = fitness_scores.index(max(fitness_scores))
    best_genome = population[best_idx].copy()

    # Truncate to make room for elite
    survivors = survivors[:POPULATION_SIZE - 1]

    # If survivors are too few, replenish randomly (maintain diversity)
    while len(survivors) < POPULATION_SIZE - 1:
        survivors.append(random.choice(population))

    survivors.insert(0, best_genome)

    return survivors


# ============================================================================
# 10. MAIN EVOLUTION LOOP
# ============================================================================

def evolve() -> tuple[int, Genome] | tuple[None, None]:
    """Run the evolutionary algorithm until solution or max generations.

    Returns:
        Tuple of (generation, solution_genome) if found,
        or (None, None) if no solution within max generations.
    """
    population = initialize_population()

    for generation in range(MAX_GENERATIONS + 1):
        fitness_scores = evaluate_population(population, TARGET)

        max_fitness = max(fitness_scores)
        if max_fitness == GENOME_LENGTH:
            solution_idx = fitness_scores.index(max_fitness)
            return generation, population[solution_idx]

        if VERBOSE and generation % 10 == 0:
            avg_fitness = sum(fitness_scores) / len(fitness_scores)
            best_idx = fitness_scores.index(max_fitness)
            print(f"Gen {generation:4d} | Best: {max_fitness}/{GENOME_LENGTH} "
                  f"| Avg: {avg_fitness:.2f} | "
                  f"{' '.join(population[best_idx])}")

        species = group_into_species(population)
        survivors = select_within_species(species)
        survivors = preserve_elite(survivors, population, fitness_scores)
        population = reproduce(survivors)

    return None, None


# ============================================================================
# 11. MAIN
# ============================================================================

def main():
    """Entry point."""
    global TARGET, GENOME_LENGTH, VOCAB, VOCAB_SIZE, SEARCH_SPACE, MAX_GENERATIONS

    parser = argparse.ArgumentParser(description="Evolutionary Algorithm Simulation")
    parser.add_argument('--seed', action='store_true',
                        help='Enable reproducible mode with seed 42')
    args = parser.parse_args()

    if args.seed:
        random.seed(42)
        print(f"Random seed: 42")

    TARGET = get_user_input()
    GENOME_LENGTH = len(TARGET)
    VOCAB = generate_vocabulary(TARGET)
    VOCAB_SIZE = len(VOCAB)
    SEARCH_SPACE, MAX_GENERATIONS = compute_parameters(VOCAB_SIZE, GENOME_LENGTH)

    print("=" * 50)
    print("EVOLUTIONARY ALGORITHM SIMULATION")
    print("=" * 50)
    print(f"Target: {' '.join(TARGET)}")
    print(f"Vocabulary size: {VOCAB_SIZE}")
    print(f"Search space: {SEARCH_SPACE}")
    print(f"Max generations: {MAX_GENERATIONS}")
    print("=" * 50)

    generation, solution = evolve()

    print("=" * 50)
    if solution:
        print(f"SOLUTION FOUND at generation {generation}")
        print(f"Genome: {' '.join(solution)}")
    else:
        print("No solution found within max generations")
    print("=" * 50)


if __name__ == "__main__":
    main()