What is Genetic Algorithm (GA)?
Genetic algorithm are optimization methods that mimic natural selction, where the key principle is survival of the fittest. Genetic algorithms use inheritance and mutation to find approximate solutions, and solutions are selected based on their fitness. The process continues until a satisfactory solution is found.
How does this algorithm work?
In genetic algorithms, to generate new and potentially more fit solutions, they create a population of potential solutions, and then evaluate, select and recombine individuals within the population to produce generations of optimal solutions. The basic steps of this process are:
1) Initialize a population of potential solutions to a problem.
2) Evaluate the fitness of each solution in the population based on the performance satisfying the constraints and objectives.
3) Select the fittest individuals from the population to act as parents to produce the next generation.
4) Create offspring by combining the genetic material of the parents selected using operators.
5) Repeat steps 2-4 until a satisfactory solution is found or a stopping criterion is met. This generates a new population of individuals that are better suited to the problem.
With GA, success depends on a variety of factors, such as genetic operators, population size, and selection criteria. There are various types of operators that can be used, such as:
-Mutation, which involves a random change of one or more genes to add new genetic diversity into a population.
-Crossover, a process where parts of genetic material are swapped between two selected parents to create offspring individuals. This operator can be performed in many ways, including single-point crossover, two-point crossover, or uniform crossover.
-Inversion, that implements reversing genetic material within an individual.
Applications of Genetic Algorithms
Since Genetic algorithms are used to solve optimization problems, they can be used in a wide range of applications, such as:
Finance: to optimize investment portfolios or predict stock prices and detect fraudulent transactions (Li, 2014).
Bioinformatics: for analysing and interpreting large data sets like DNA sequences or to optimize structures of drugs and vaccines.
Gaming: to create game content and optimize behaviour of differnet non player characters.
Robotics: used to optimize the movements and behaviours of robotics or autonomous vehicles.
Machine learning: generates better performance in models as it can optimize the parameters.
Advantages of Genetic Algorithms (GA)
There are many advantages for Genetic Algorithms, such as:
-Robustness (handles incomplete data and noisy data).
-Parallel processing (allows different tasks to be done concurrently, so there is a faster proceesing of large data).
-Handles complex problems (which would be difficult to solve using traditional methods).
-Global optimization (finds global optima instead of local optima)
Interactive Algorithm code
In this example, the fitness function is simple, however, in real-world applications, the fitness function would be more complex and represents an actual problem.
The following code is an implementation of Genetic Algorithm, where a fitness function represents the problem of finding the maximum value of f(x) = x^2. The plan is to begin with a population of candidate solutions, where the fitness is evaluated and to generate candidate solutions continuously by applying genetic operators to the fittest individuals.
Then we introduce the genetic algorithm function, which initializes a population of candidate solutions with random values between -10 and 10 to create new generations by calculating the fitness of each individual in the population, selecting the fittest to mate, generating offspring by mating the fittest parents and mutating the offspring (by adding a random value between -0.1 and 0.1 with a 50% probability).
The code then replaces the population with the fittest offspring, and then repeats this for specified number of generations. At the end of the loop, the fittest individual in the final population is returned as the result of the genetic algorithm.
The main function takes user input for the GA parameters, runs the GA, and prints the maximum value of the fitness function obtained by the fittest individual. When experimenting with this code, you would realise that the maximum fitness function achieved by the GA depends on the specific parameters used.
A higher number of individuals in each generation (SizeOfPopulation) allows for a better search space exploration and reduces the chance of premature convergence (causes the algorithm to converge too quickly to a suboptimal solution). Here, a larger ‘SizeOfPopulation’ increases the probability of finding the maximum value of the fitness function.
The probability of a gene being mutated by the crossover operator (RateOfMutation) increases the new genetic material in the population which also decreases the chance of premature convergence. However, if the ‘RateOfMutation’ is too high it can cause a slower convergence to the optimal solution since it can cause the algorithm to lose the fittest individuals. In this example a higher mutation rate increases the probability of finding the maximum value of the fitness function.
A larger number of generations for the genetic algorithm to run (NoOfGens) causes the search space exploration to be more comprehensive and in depth so a higher number of generations increases the probability of finding the maximum value of the fitness function.
Therefore the maximum fitness function achieved by the GA will depend on the specific parameter values that are used as input, but these parameters also increase the computational cost of the algorithm, which could make it impractical to use on significant issues. In summary, choosing the optimal parameters for a genetic algorithm requires careful balance and experimentation. This implies that starting with a small values for the inputs and gradually increasing them until the GA converges to a satisfactory solution is a good start.
import random
def fit_func(x): #fitness function represents the problem that we want to solve with GA.
#In this case, GA is trying to find the maximum value of the function.
return x**2
def GA(SizeOfPopulation, NoOfGens, RateOfMutation): # genetic algorithm
#SizeOfPopulation= no of individuals in each generation
#NoOfGens = no of generations to run GA
#RateOfMutation = probability of mutation on offspring
population = [random.uniform(-10, 10) for i in range(SizeOfPopulation)] # Initialize the population with random values between -10 and 10.
for gen in range(NoOfGens):
calc_fitness = [fit_func(individual) for individual in population] # Calculate the fitness of each individual in the population
# Select the fittest individuals to mate
parents = []
for i in range(SizeOfPopulation // 2):
parent1 = population[calc_fitness.index(max(calc_fitness))]
calc_fitness[calc_fitness.index(max(calc_fitness))] = -1
parent2 = population[calc_fitness.index(max(calc_fitness))]
calc_fitness[calc_fitness.index(max(calc_fitness))] = -1
parents.append((parent1, parent2))
offspring = [] # Generate offspring by mating the parents
for parent1, parent2 in parents:
offspring_value = (parent1 + parent2) / 2 # Generate offspring as weighted average of parents' values
if random.random() < 0.5: # Randomly choose whether to mutate offspring value
offspring_value += random.uniform(-0.1, 0.1)
offspring.append(offspring_value)
population = offspring # Replace the population with the fittest offspring
population.sort(reverse=True, key=fit_func) # Sort the population in descending order based on fitness
return population[0] # Return the fittest individual
# Run the genetic algorithm with user-defined parameters
SizeOfPopulation = int(input("Enter the population size: "))
gens = int(input("Enter the number of generations: "))
RateOfMutation = float(input("Enter the mutation rate: "))
if RateOfMutation < 0 or RateOfMutation > 1:
print("Error: Mutation rate should be between 0 and 1")
exit()
result = GA(SizeOfPopulation, gens, RateOfMutation)
print("The maximum value of the function is:", fit_func(result))