What are genetic algorithm phases?
Genetic algorithms (GAs) are strong optimization and search methods derived from the concepts of genetics and natural selection. These algorithms use natural evolution as a model to determine the best answers to challenging issues. The key to genetic algorithms' effectiveness is their capacity to repeatedly generate a population of viable solutions across several generations. The procedure is divided into multiple stages, each enhancing the algorithm's efficacy and efficiency.
Genetic algorithm phases
We will discuss the following phases one by one, along with the applications:
Initialization
A population of viable solutions is generated during the initialization phase, the first stage of a genetic algorithm. Each solution represents a candidate solution to the problem, sometimes referred to as an individual or chromosome. Usually, these individuals are created at random somewhere in the solution space of the problem. One important factor affecting the algorithm's performance is the population size.
This part is notably useful in:
Engineering design: Generating initial designs for structures, circuits, or systems.
Finance: Creating diverse portfolios of financial instruments for investment strategies.
Sample code for initialization
Let’s have a look at how we can code initialization in Python to create an initial population of a certain population size and chromosome length.
# Sample initialization codeimport randomdef initialize_population(population_size, chromosome_length):population = []for _ in range(population_size):chromosome = [random.choice([0, 1]) for _ in range(chromosome_length)]population.append(chromosome)return population# Testing the functionpop = initialize_population(5, 5)print(pop)
Code explanation
Line 2: We import the
randommodule, allowing access to functions for generating random numbers.Line 4: We define a function named
initialize_populationthat takes two parameters:population_size(the number of individuals in the population) andchromosome_length(the length of each individual's chromosome).Lines 6–8: We generate a chromosome for an individual by creating a list of length
chromosome_lengthwith random binary values (0 or 1).Lines 11–12: We test the function by storing it in a
popvariable, and then printing it.
Selection
In the selection phase, individuals from the population are chosen to be parents for the next generation. Each individual's fitness level frequently determines the probability of selection; those who are more fit are more likely to be chosen. Various selection techniques, including tournament and roulette wheel selection, guide the population's evolution.
Selection is notably useful in:
Machine learning: Selecting promising models for the next generation in evolutionary algorithms.
Routing algorithms: Choosing routes with higher fitness in network optimization problems.
Sample code for selection
Let's look at how we can code selection in Python using a roulette wheel mechanism, in which the individuals with higher fitness are picked more frequently.
from numpy.random import choice# Sample roulette wheel selection codedef roulette_wheel_selection(population, fitness_values):total_fitness = sum(fitness_values)probabilities = [fitness / total_fitness for fitness in fitness_values]selected_index = choice(range(len(population)), p=probabilities)return population[selected_index]# Testing with dummy datapop = [[1,0,0,1,0], [1,0,1,0,1], [1,1,1,1,0]]fitness = [0.81, 0.22, 0.45]parent = roulette_wheel_selection(pop, fitness)print(parent)
Code explanation
Line 4: We define a function named
roulette_wheel_selectionthat takes two parameters:population(a list of individuals) andfitness_values(a list of fitness values corresponding to each individual in the population).Lines 5–8: We calculate the total fitness of the population by summing up all fitness values provided, the selection probability for each individual in the population based on its fitness value, and randomly selecting an index from the range of population indexes, with the probability distribution determined by the
pparameter, which represents the selection probabilities computed earlier usingtotal_fitness,probabilitiesandselected_indexrespectively.Lines 11–15: We test the function by giving it some test values
popandfitnessand storing it in aparentvariable. Then we print the selected individual.
Crossover (Recombination)
A crucial genetic operation called crossover occurs when parents exchange genetic material to have children. This stage mimics the way genetic recombination occurs naturally. Various crossover techniques, such as single-point or uniform crossover, create diverse offspring.
Crossover is notably useful in:
Scheduling problems: Combining schedules from different individuals to create better timetables.
Image processing: Blending features from different images creates new and diverse images.
Sample code for crossover
Let's examine how to code a single-point crossover in Python to create two children from two sample parents.
import random# Sample single-point crossover codedef single_point_crossover(parent1, parent2):crossover_point = random.randint(1, len(parent1) - 1)child1 = parent1[:crossover_point] + parent2[crossover_point:]child2 = parent2[:crossover_point] + parent1[crossover_point:]return child1, child2# Testing with dummy dataparent_A = [1, 0, 0, 1, 0, 1]parent_B = [1, 1, 0, 0, 0, 1]child_A, child_B = single_point_crossover(parent_A, parent_B)print(child_A, child_B)
Code explanation
Line 4: We define a function named
single_point_crossoverthat takes two parameters:parent1andparent2, representing the chromosomes of two parents.Line 5: We generate a random integer representing the crossover point. This value determines the position where the crossover will occur within the chromosomes.
Line 6: We create
child1by combining the genes ofparent1up to the crossover point with the genes ofparent2after the crossover point.Line 7: We create
child2by combining the genes ofparent2up to the crossover point with the genes ofparent1after the crossover point.Lines 11–15: We test the function by giving it some test values
parent_Aandparent_Band storing it inchild_Aandchild_Bvariables. Then we print the newly generated individuals.
Mutation
By introducing tiny, unpredictable changes to each individual, mutation keeps the algorithm from converging prematurely to a suboptimal solution. The individual's genetic variety is preserved in part by mutation. The nature of the problem and the algorithm's performance can be used to modify the mutation rates.
Mutation is notably useful in:
Robotics: Adjusting robot parameters to adapt to unforeseen environmental changes.
Chemical engineering: Modifying chemical reaction parameters for optimal outcomes.
Sample code for mutation
Let's have a look at how we can code a mutation in Python that randomly mutates an individual's chromosome depending on some mutation rate.
import random# Sample bit flip mutation codedef bit_flip_mutation(individual, mutation_rate):mutated_individual = [bit ^ (random.random() < mutation_rate) for bit in individual]return mutated_individual# Testing with dummy dataindividual = [1, 0, 0, 0, 1]mutate_probability = 0.5mutated = bit_flip_mutation(individual, mutate_probability)print(individual)print(mutated)
Code explanation
Line 4: We define a function named
bit_flip_mutationthat takes two parameters:individual, representing the chromosome of an individual, andmutation_rate, indicating the probability of mutation for each bit.Line 5: We apply bit flip mutation to the
individualchromosome.Lines 9–12: We test the function on an
individualand a mutation rate of0.5.
Note: You might need to run this several times to see the mutation in effect.
Replacement
The next generation is generated by replacing some of the least fit members of the existing population after crossing over and mutating to create children. The replacement phase raises the general quality of the population by guaranteeing that only the fittest individuals make it to the following generation.
Replacement is notably useful in:
Optimization problems: Solving complex optimization problems in logistics and resource allocation.
Genomic studies: Identifying optimal gene combinations in genetic programming.
Sample code for replacement
Let's look at how we can code replacement in Python to replace the current generation with a mix of current and newly generated individuals based on their best fitness.
# Sample replacement codedef replace_population(current_population, offspring_population, fitness_values):combined_population = list(zip(current_population, fitness_values)) + list(zip(offspring_population, [0] * len(offspring_population)))combined_population.sort(key=lambda x: x[1], reverse=True)new_population = [individual for individual, _ in combined_population[:len(current_population)]]return new_population# Testing with dummy datapop = [[1,0,0,1,0], [1,0,1,0,1], [1,1,1,1,0]]fitness = [0.81, 0.22, 0.45]children = [[1,1,0,1,0], [1,0,1,1,0], [1,1,1,1,0]]new_pop = replace_population(pop, children, fitness)print(new_pop)
Code explanation
Line 2: We define a function named
replace_populationthat takes three parameters:current_population(the current population of individuals),offspring_population(the offspring population produced through genetic operations), andfitness_values(the fitness values corresponding to individuals in the populations).Line 3: We combine the current population with the offspring population into a single list
combined_population.Line 4: We sort the combined population based on fitness values in descending order.
Line 5: We select individuals for the new population by extracting the required number of individuals from the sorted combined population.
Lines 9–14: We test the function on a
pop, theirfitness, and theirchildrento create a new population.
Conclusion
Iteratively moving through these stages, genetic algorithms evolve a population of potential solutions. Genetic algorithms have shown effective optimization methods in various fields, including engineering, finance, artificial intelligence, and beyond. This is done by striking a balance between exploration and exploitation through selection, crossover, mutation, and replacement. It is necessary to comprehend these stages in genetic algorithms to tackle difficult issues.
Free Resources
