Genetic Algorithm: 32-Bit All Ones Problem

import random

# ============================================================
# Configuration
# ============================================================
WORD_SIZE       = 32        # Number of bits in each word
POPULATION_SIZE = 100       # Initial population size
SURVIVORS       = 10        # Number of fittest individuals to keep
OFFSPRING       = 9         # New words generated from each survivor
MAX_GENERATIONS = 10000     # Safety limit to prevent infinite loops

# ============================================================
# Helper Functions
# ============================================================

def random_word():
    """Generate a random 32-bit integer."""
    return random.randint(0, (2**WORD_SIZE) - 1)

def count_ones(word):
    """Count the number of 1-bits in a word (fitness function)."""
    return bin(word).count('1')

def toggle_random_bit(word):
    """Toggle (flip) a random bit in the word (mutation)."""
    bit_position = random.randint(0, WORD_SIZE - 1)
    return word ^ (1 << bit_position)

def word_to_binary_string(word):
    """Convert a word to a readable 32-bit binary string."""
    return format(word, f'0{WORD_SIZE}b')

# ============================================================
# Genetic Algorithm
# ============================================================

def genetic_algorithm():
    # ----- Step 1: Create initial population -----
    population = [random_word() for _ in range(POPULATION_SIZE)]
    generation = 0

    print("=" * 60)
    print("       GENETIC ALGORITHM: 32-Bit All Ones Problem")
    print("=" * 60)
    print(f"Population Size : {POPULATION_SIZE}")
    print(f"Survivors/Gen   : {SURVIVORS}")
    print(f"Offspring Each  : {OFFSPRING}")
    print(f"Word Size       : {WORD_SIZE} bits")
    print("=" * 60)

    while generation < MAX_GENERATIONS:
        generation += 1

        # ----- Step 2: Evaluate fitness (count 1-bits) -----
        fitness_pairs = [(word, count_ones(word)) for word in population]

        # ----- Step 3: Check for a perfect solution -----
        best_word, best_fitness = max(fitness_pairs, key=lambda x: x[1])

        # Print progress every 100 generations or on the first few
        if generation <= 5 or generation % 100 == 0 or best_fitness == WORD_SIZE:
            print(
                f"Generation {generation:>5} | "
                f"Best Fitness: {best_fitness:>2}/{WORD_SIZE} | "
                f"Best Word: {word_to_binary_string(best_word)}"
            )

        # ----- EXIT CONDITION: All 32 bits are 1 -----
        if best_fitness == WORD_SIZE:
            print("=" * 60)
            print(f"SOLUTION FOUND in Generation {generation}!")
            print(f"   Word   : {word_to_binary_string(best_word)}")
            print(f"   Decimal: {best_word}")
            print(f"   Fitness: {best_fitness}/{WORD_SIZE}")
            print("=" * 60)
            return best_word, generation

        # ----- Step 4: Selection (keep top 10 fittest) -----
        fitness_pairs.sort(key=lambda x: x[1], reverse=True)
        survivors = [word for word, fitness in fitness_pairs[:SURVIVORS]]

        # ----- Step 5: Mutation (generate 9 offspring per survivor) -----
        new_population = []
        for survivor in survivors:
            # Keep the survivor itself
            new_population.append(survivor)
            # Generate 9 new words by toggling a random bit
            for _ in range(OFFSPRING):
                mutated = toggle_random_bit(survivor)
                new_population.append(mutated)

        population = new_population

    # Safety: If max generations reached
    print(f"No solution found after {MAX_GENERATIONS} generations.")
    return None, generation

# ============================================================
# Run the Algorithm
# ============================================================

if __name__ == "__main__":
    solution, generations = genetic_algorithm()
    print(f"Solution found in {generations} generations.")