Genetic Algorithms Implementation in Python

Note: this page has been created with the use of AI. Please take caution, and note that the content of this page does not necessarily reflect the opinion of Cratecode.

Genetic algorithms (GAs) are a type of optimization and search technique inspired by the process of natural selection. They have been used to solve complex problems in various fields, from optimization to machine learning. In this article, we will walk you through the implementation of a genetic algorithm in Python.

Problem Representation

The first step in implementing a genetic algorithm is to represent the problem in a way that can be used by the algorithm. In GAs, we have a population of individuals, each representing a possible solution to the problem. The representation of an individual depends on the problem at hand. For example, if you're solving a traveling salesperson problem, the individual could be represented as a list of cities visited in order.

individual = ["City A", "City B", "City C", "City D", "City E"]

Population Initialization

Next, we need to create an initial population of individuals. This can be done randomly or using some heuristic. For simplicity, let's create a random population of size n for our traveling salesperson example.

import random

def random_population(n, cities):
    population = []
    for _ in range(n):
        individual = random.sample(cities, len(cities))
        population.append(individual)
    return population

cities = ["City A", "City B", "City C", "City D", "City E"]
population = random_population(10, cities)

Fitness Evaluation

Now that we have a population, we need to evaluate the fitness of each individual. The fitness function depends on the problem. In our example, the fitness could be the total distance traveled by the salesperson. The goal is to minimize this distance, so lower fitness values are better.

def distance(city_a, city_b):
    # Calculate the distance between city_a and city_b
    pass

def fitness(individual):
    total_distance = 0
    for i in range(len(individual) - 1):
        total_distance += distance(individual[i], individual[i + 1])
    total_distance += distance(individual[-1], individual[0])  # Return to the first city
    return total_distance

Selection

Selection is the process of choosing individuals from the current population to create a new generation. There are various selection strategies, such as roulette wheel selection and tournament selection. For this example, let's use tournament selection.

def tournament_selection(population, fitness_function, tournament_size):
    selected = []
    for _ in range(len(population)):
        competitors = random.sample(population, tournament_size)
        winner = min(competitors, key=fitness_function)
        selected.append(winner)
    return selected

Crossover

Crossover is the process of combining the traits of two individuals to create offspring. There are many ways to perform crossover, depending on the problem representation. For our example with a list of cities, we can use ordered crossover.

def ordered_crossover(parent_a, parent_b):
    start, end = sorted(random.sample(range(len(parent_a)), 2))
    child = [None] * len(parent_a)
    child[start:end] = parent_a[start:end]

    for gene in parent_b:
        if gene not in child:
            i = child.index(None)
            child[i] = gene

    return child

Mutation

Mutation is the process of introducing small random changes in an individual to maintain diversity in the population. For our example, we can swap two cities in the list.

def swap_mutation(individual, mutation_rate):
    for i in range(len(individual)):
        if random.random() < mutation_rate:
            j = random.randint(0, len(individual) - 1)
            individual[i], individual[j] = individual[j], individual[i]

Main Loop

Finally, we can put everything together in the main loop of the genetic algorithm. We will run the algorithm for a fixed number of generations or until a termination condition is met.

population_size = 50
generations = 100
mutation_rate = 0.1
tournament_size = 5

population = random_population(population_size, cities)

for generation in range(generations):
    selected = tournament_selection(population, fitness, tournament_size)
    offspring = []
    for i in range(0, population_size, 2):
        child_a = ordered_crossover(selected[i], selected[i + 1])
        child_b = ordered_crossover(selected[i + 1], selected[i])
        offspring.append(child_a)
        offspring.append(child_b)

    for child in offspring:
        swap_mutation(child, mutation_rate)

    population = offspring

best_individual = min(population, key=fitness)
print("Best solution:", best_individual)

And that's it! You've implemented a genetic algorithm in Python. This is just a starting point, and there are many ways to improve and customize the algorithm for your specific problem. Happy evolving!

FAQ