Understanding Genetic Algorithms In Python

Introduction

Genetic Algorithms are part of evolutionary algorithms, a search heuristic used to solve search and optimization problems based on the principles of genetics and evolution. In this blog post, we will build a very simple Genetic algorithm with Python to solve a very random problem -- let's say finding the optimal list with maximum sum.

The Process

A Genetic algorithm often involves:

1. Selection: The fittest individuals are chosen for reproduction.
2. Crossover: A set of parents are selected and they produce offspring.
3. Mutation: Offsprings undergo mutation, which slightly changes their genes.
4. Repeat: Go back to step 1 and repeat the process until the end condition is met.

Implementation

Let's dive into a Python implementation. To keep it simple, we will focus on finding the optimal list with maximum sum. We will use Python's built-in modules.

Initial Population

First, we create an initial population (random lists of integers):

import random

def create_population(size, min_value, max_value, length):
    return [[random.randint(min_value, max_value) for _ in range(length)] for _ in range(size)]

Fitness Function

Next, we need a fitness function, which will evaluate how good our individuals are. In this case, the fitness of an individual is the sum of its elements:

def calculate_fitness(individual):
    return sum(individual)

Selection and Reproduction

For selection, we will choose two parents using the roulette wheel method based on the fitness scores. For reproduction, we do a simple crossover between the parents:

def selection_and_reproduction(population):
    sorted_population = sorted(population, key=calculate_fitness, reverse=True)
    population = sorted_population[:len(sorted_population)//2]  # survival of the fittest
    for _ in range(len(sorted_population)//2, len(sorted_population)): # reproducing and populating the rest
        parent1, parent2 = random.sample(population, 2)  # selecting parents randomly
        half = len(parent1) // 2
        child = parent1[:half] + parent2[half:]  # generating offspring
        population.append(child)
    return population

Mutation

For our example, mutation will be simply replacing one random element of the individual list by a new random number:

def mutation(population, min_value, max_value):
    for individual in population:
        if random.random() <= 0.1:  # assuming a mutation rate of 10%
            place_to_mutate = random.randint(0, len(individual)-1)
            new_value = random.randint(min_value, max_value)
            individual[place_to_mutate] = new_value
    return population

Main Program

Finally, let's write our main program using the above functions:

def main():
    population = create_population(10, -10, 10, 5)
    print("Initial population:", population)
    for generation in range(100):  # Let's try for 100 generations
        population = selection_and_reproduction(population)
        population = mutation(population, -10, 10)
    print("Final population:", population)

if __name__ == "__main__":
    main()

And that's it! When you run this program, you will get different results each time due to the randomness-factor in genetic algorithms.