This tutorial aims to provide a comprehensive understanding of Genetic Algorithms, a search heuristic inspired by the process of natural selection. By the end of this tutorial, you'll have a solid grasp of how Genetic Algorithms work and how they're used to solve optimization and search problems.
Genetic Algorithms (GAs) are adaptive heuristic search algorithms that are inspired by the evolutionary ideas of natural selection and genetics. The basic concept of Genetic Algorithms is designed to simulate processes in natural evolution, such as inheritance, mutation, selection, and crossover (also called recombination).
In Genetic Algorithms, a solution to a problem is represented as a chromosome. The actual solution representation is called a phenotype, while the encoded solution (chromosome) is called a genotype. For instance, if we're trying to optimize a function that takes two integers as input, each solution can be represented as a chromosome consisting of two genes.
Selection is the process of choosing the fittest individuals from the population for reproduction. The fittest individuals are selected based on their fitness score.
Crossover, also known as recombination, is the process of generating new offspring by combining the genes of the parents.
Mutation is a genetic operator that alters one or more gene values in a chromosome. It serves to maintain and introduce diversity in the genetic population and is usually applied with a low probability.
The following Python code demonstrates a simple Genetic Algorithm for finding the maximum value of a function. Here, we will be attempting to maximize the function f(x, y) = x * sin(4πx) - y * sin(4πy + π) + 1.
import random
import math
def fitness(x, y):
return x * math.sin(4*math.pi*x) - y * math.sin(4*math.pi*y + math.pi) + 1
def mutate(parent):
gene = random.randint(0,1)
if gene == 0:
parent[gene] = random.random()
else:
parent[gene] = random.random()
return parent
def crossover(parent1, parent2):
child = [parent1[0], parent2[1]]
return child
def genetic_algorithm():
parent1 = [random.random(), random.random()]
parent2 = [random.random(), random.random()]
for _ in range(10000):
child = crossover(parent1, parent2)
child = mutate(child)
if fitness(child[0], child[1]) > fitness(parent1[0], parent1[1]):
parent1 = child
if fitness(child[0], child[1]) > fitness(parent2[0], parent2[1]):
parent2 = child
return parent1, parent2
print(genetic_algorithm())
In the code above, fitness is our objective function that we want to maximize. mutate and crossover are our genetic operators. We run the algorithm for a fixed number of iterations (10000 in this case) and print the best solution found.
In this tutorial, we've learned the basics of Genetic Algorithms, how they work, and how to implement a simple Genetic Algorithm. You've seen how Genetic Algorithms can be used to solve optimization problems by simulating the process of natural selection.
Happy learning!