Image by Author
Genetic algorithms are techniques based on natural selection used to solve complex problems. They are used to arrive at reasonable solutions to the problem rather than other methods because the problems are complicated. In this article, we will cover the basics of genetic algorithms and how they can be implemented in Python.
Genetic Components
Fitness Function
The fitness function gauges the proximity of a considered solution to the best possible solution to the problem. It provides a fitness level for each person in the population, which describes the quality or efficiency of the current generation. This score defines the choice while the higher fitness value suggests an improved solution.
For instance, suppose we are involved in the process of dealing with an actual function, f(x) in which x is a set of parameters. The optimal value to find is x so that f(x) assumes the largest value.
Selection
This is a process that defines which individuals within the present generation are to be favored and thus reproduce and contribute to the next generation. It is possible to identify many selection methods, and each of them has its own features and suitable contexts.
- Roulette Wheel Selection:
Depending on the fitness level of the individual, the probability of choosing the individual is also maximal. - Tournament Selection:
A group is randomly selected and the best of them is taken. - Rank-Based Selection:
People are sorted according to fitness and selection chances are proportionally allocated according to the fitness scores.
Crossover
Crossover is a basic concept of genetic algorithm that aims at the exchange of genetic information of two parent individuals to form one or more progeny. This process is closely similar to the crossover and recombination of the biology happening in nature. Applying the basic principles of heredity, crossover attempts to produce offspring that will embody desirable characteristics of the parents and, thus, possess better adaptation in the next generations. Crossover is a relatively broad concept which can be divided into several types each of which has their peculiarities and the sphere where they can be applied effectively.
- Single-Point Crossover: A crossover point is chosen on the parent chromosomes and only one crossover actually happens. Prior to this position all genes are taken from the first parent, and all genes since this position are taken from the second parent.
- Two-Point Crossover: Two breakpoints are selected and the part between them is swapped between the two parent chromosomes. It also favors interchanging of genetic information as opposed to single point crossover.
Mutation
In Genetic Algorithms, mutation is of paramount significance because it provides diversity which is a crucial factor when avoiding convergence directly towards the area of the optimum solutions. Therefore, getting random changes in the string of an individual mutation allows the algorithm to go into other regions of the solution space that it cannot reach by means of crossover operations alone. This stochastic process ensures that no matter what, the population will evolve or shift its position in the areas of the search space which have been identified as optimal by the genetic algorithm.
Steps To Implement A Genetic Algorithm
Let’s try to implement the genetic algorithm in Python.
Problem Definition
Problem: Compute on the specific function; f(x) = x^2f(x) = x^2; only integer values of x.
Fitness Function: For the case of a chromosome that is binary being x, an example of the fitness function could be f(x)= x^2.
def fitness(chromosome):
x = int(''.join(map(str, chromosome)), 2)
return x ** 2
Population Initialization
Generate a random chromosome of a given length.
def generate_chromosome(length):
return [random.randint(0, 1) for _ in range(length)]
def generate_population(size, chromosome_length):
return [generate_chromosome(chromosome_length) for _ in range(size)]
population_size = 10
chromosome_length = 5
population = generate_population(population_size, chromosome_length)
Fitness Evaluation
Evaluate the fitness of each chromosome in the population.
fitnesses = [fitness(chromosome) for chromosome in population]
Selection
Use roulette wheel selection to select parent chromosomes based on their fitness.
def select_pair(population, fitnesses):
total_fitness = sum(fitnesses)
selection_probs = [f / total_fitness for f in fitnesses]
parent1 = population[random.choices(range(len(population)), selection_probs)[0]]
parent2 = population[random.choices(range(len(population)), selection_probs)[0]]
return parent1, parent2
Crossover
Use single-point crossover by choosing a random cross-over position in a parents’ string and swapping all the gene values after this location between the two strings.
def crossover(parent1, parent2):
point = random.randint(1, len(parent1) - 1)
offspring1 = parent1[:point] + parent2[point:]
offspring2 = parent2[:point] + parent1[point:]
return offspring1, offspring2
Mutation
Implement mutation by flipping bits with a certain probability.
def mutate(chromosome, mutation_rate):
return [gene if random.random() > mutation_rate else 1 - gene for gene in chromosome]
mutation_rate = 0.01
Wrapping Up
To sum up, genetic algorithms are consistent and efficient for solving optimization problems that cannot be solved directly as they mimic the evolution of species. Thus, once you grasp the essentials of GAs and understand how to put them into practice in Python, the solution to complex tasks will be much easier. Selection, crossover, and mutation keys enable you to make modifications in solutions and get the best or nearly best answers constantly. Having read this article, you are prepared to apply the genetic algorithms to your own tasks and thereby improve in different tasks and problem solving.
Jayita Gulati is a machine learning enthusiast and technical writer driven by her passion for building machine learning models. She holds a Master’s degree in Computer Science from the University of Liverpool.
