The inspiration for Genetic Algorithms (GAs) comes directly from nature, specifically from the process of evolution and natural selection. In this article, I will discuss how this natural process works in detail, and how it inspired the creation of an algorithm for problem-solving and optimization.
Natural Evolution: Survival of the Fittest
In nature, evolution is the gradual process through which species change over time to adapt to their environment. The main idea behind evolution is natural selection, often called "survival of the fittest."
Here’s how it works:
Genetic Material (DNA): Every living organism has genes, which carry the information that defines its traits—like height, color, or behavior. These genes are stored in a long sequence of DNA.
Population: A group of individuals of the same species living together. Each individual has a unique set of genes.
Fitness: Not all individuals are equally fit to survive in their environment. Some have traits that help them thrive (like better camouflage or stronger muscles), while others may have traits that make life harder.
Reproduction: Individuals that are better suited to their environment (more "fit") are more likely to survive and reproduce. Their offspring inherit the genes that made their parents successful.
Mutation and Variation: Occasionally, random mutations occur in the genes of individuals. These small, random changes introduce new traits. Most mutations might not be useful, but some can provide advantages, helping future generations survive even better.
Example of Evolution in Nature
Let’s take an example of birds living on an island where food is scarce, and only birds with sharp, strong beaks can break open the tough seeds available.
Over time, birds with stronger beaks will survive better because they can eat more food.
These strong-beaked birds will reproduce more often, passing on the "strong beak" trait to their offspring.
Birds with weaker beaks will struggle to survive and may not reproduce as much.
Over many generations, more birds in the population will have strong beaks, and the weak-beaked birds will eventually disappear.
If a random mutation makes some birds' beaks even stronger or sharper, that trait could spread if it offers an advantage.
Through this process of selection, reproduction, and mutation, species evolve and adapt to their environments over time.
How This Inspired Genetic Algorithms
The process of evolution in nature inspired scientists to create a problem-solving algorithm that mimics how species evolve to find the "best" solution over time. Here’s how the inspiration from nature was used:
Genes and Chromosomes → Variables and Solutions: In a Genetic Algorithm, just like in nature, we represent each possible solution to a problem as a chromosome. This chromosome is made up of genes, each representing different variables or characteristics of the solution.
Fitness in Nature → Fitness Function in Algorithms: In nature, fitness is the ability to survive and reproduce. In a Genetic Algorithm, fitness is a measure of how good a solution is at solving the problem.
Selection in Nature → Selection in Algorithms: In evolution, only the fittest individuals survive and reproduce. In Genetic Algorithms, the fittest solutions (those with the best fitness scores) are selected to create new solutions.
Crossover in Nature → Crossover in Algorithms: In biology, reproduction combines the genes from two parents to create offspring with a mix of both parents’ traits. In Genetic Algorithms, crossover mimics this by combining two solutions to create a new one.
Mutation in Nature → Mutation in Algorithms: Just as random mutations in nature can introduce new traits, mutation in a Genetic Algorithm introduces small random changes to a solution. This ensures that new possibilities are explored, even if the current best solutions aren’t perfect.
The key advantage of using evolution as inspiration is that Genetic Algorithms don’t need to know the exact path to the best solution. They explore many possibilities and use random variation, just like evolution, to stumble upon better solutions. Over time, by applying selection and combination, these algorithms can find highly effective solutions to very complex problems.
Let's say we want to maximize the function: f(x)= x sin(10πx)+2, where x is between 0 and 1. This is a non-linear function with multiple peaks and valleys, making it a good example for a Genetic Algorithm. You can also find this code at my github handle.
% Compare Genetic Algorithm solution with standard mathematical optimization
% for maximizing f(x) = x * sin(10 * pi * x) + 2, x in [0, 1]
% Step 1: Genetic Algorithm solution
% Genetic Algorithm parameters
populationSize = 20; % Number of individuals in the population
numGenerations = 50; % Number of generations to evolve
mutationRate = 0.05; % Probability of mutation (5%)
crossoverRate = 0.8; % Probability of crossover (80%)
numGenes = 16; % Number of genes (bits) to represent x
% Create an initial random population
population = randi([0 1], populationSize, numGenes);
% Genetic Algorithm loop for several generations
for generation = 1:numGenerations
% Evaluate the fitness of each individual in the population
fitness = zeros(populationSize, 1);
for i = 1:populationSize
x = decodeChromosome(population(i, :), numGenes);
fitness(i) = fitnessFunction(x);
end
% Select individuals for reproduction based on fitness
selectedPopulation = selectRoulette(population, fitness);
% Apply crossover to generate a new population
newPopulation = applyCrossover(selectedPopulation, crossoverRate);
% Apply mutation to introduce random changes
mutatedPopulation = applyMutation(newPopulation, mutationRate);
% Update the population for the next generation
population = mutatedPopulation;
end
% Final solution from Genetic Algorithm
[bestFitness_GA, bestIndex] = max(fitness);
bestX_GA = decodeChromosome(population(bestIndex, :), numGenes);
fprintf('Genetic Algorithm: Best x = %.5f, Best fitness = %.5f\n', bestX_GA, bestFitness_GA);
% Step 2: Standard Mathematical Optimization using fminbnd
% fminbnd minimizes a function, so we minimize -f(x) to maximize f(x)
objectiveFunction = @(x) -(x * sin(10 * pi * x) + 2); % Negative of the function to maximize
[x_fminbnd, neg_fminbnd] = fminbnd(objectiveFunction, 0, 1);
% Convert the negative fitness value back to positive
bestFitness_fminbnd = -neg_fminbnd;
fprintf('Standard Optimization (fminbnd): Best x = %.5f, Best fitness = %.5f\n', x_fminbnd, bestFitness_fminbnd);
%% Function to evaluate the fitness of a chromosome
function fit = fitnessFunction(x)
% The function we want to maximize: f(x) = x * sin(10 * pi * x) + 2
fit = x * sin(10 * pi * x) + 2;
end
%% Function to decode the chromosome (binary string) into a real value of x
function x = decodeChromosome(chromosome, numGenes)
% Convert binary chromosome to decimal, then scale to the range [0, 1]
decimalValue = bin2dec(num2str(chromosome));
x = decimalValue / (2^numGenes - 1); % Scale to [0, 1]
end
%% Function for roulette wheel selection based on fitness
function selectedPop = selectRoulette(population, fitness)
% Normalize fitness values to create a probability distribution
totalFitness = sum(fitness);
prob = fitness / totalFitness;
% Cumulative probability distribution for selection
cumulativeProb = cumsum(prob);
% Select individuals based on roulette wheel approach
populationSize = size(population, 1);
numGenes = size(population, 2);
selectedPop = zeros(populationSize, numGenes);
for i = 1:populationSize
r = rand(); % Random number between 0 and 1
selectedIndex = find(cumulativeProb >= r, 1); % Select individual
selectedPop(i, :) = population(selectedIndex, :);
end
end
%% Function to apply crossover between pairs of individuals
function newPop = applyCrossover(population, crossoverRate)
populationSize = size(population, 1);
numGenes = size(population, 2);
newPop = population;
for i = 1:2:populationSize
if rand() < crossoverRate
% Select two parents
parent1 = population(i, :);
parent2 = population(i+1, :);
% Apply crossover (single-point crossover)
crossoverPoint = randi([1, numGenes-1]);
newPop(i, :) = [parent1(1:crossoverPoint), parent2(crossoverPoint+1:end)];
newPop(i+1, :) = [parent2(1:crossoverPoint), parent1(crossoverPoint+1:end)];
end
end
end
%% Function to apply mutation to the population
function mutatedPop = applyMutation(population, mutationRate)
populationSize = size(population, 1);
numGenes = size(population, 2);
mutatedPop = population;
for i = 1:populationSize
for j = 1:numGenes
if rand() < mutationRate
mutatedPop(i, j) = ~population(i, j); % Flip the gene
end
end
end
endUpon evaluating this code in MATLAB, we get the following output:
Genetic Algorithm: Best x = 0.59976, Best fitness = 2.84666
Standard Optimization (fminbnd): Best x = 0.65156, Best fitness = 2.65078Let me give an example related to satellite systems because that's what this website is about. To compare a Genetic Algorithm (GA) with a standard optimization technique for trajectory optimization of a satellite in orbit, let's consider the following problem:
Problem Description:
The goal is to transfer a satellite from one circular orbit (initial orbit) to another circular orbit (target orbit). The satellite can change its velocity at specific times (impulse burns), and we want to optimize the thrust directions to minimize the total fuel used.
Objective: Minimize fuel usage (which is proportional to the velocity changes ΔV).
Standard Method for Comparison: We can use the Hohmann transfer method, which is an analytically optimal way of transferring a satellite between two circular orbits using two impulsive burns.
Steps:
Use a Genetic Algorithm to find the optimal thrust direction and times to minimize ΔV.
Compare it with the fuel cost of a Hohmann transfer (a standard two-burn maneuver).
Problem Setup:
The satellite is initially in a circular orbit with radius r1.
The target orbit is circular with radius r2.
The satellite can apply a finite number of thrust impulses at any point during the transfer.
The cost function is the total ΔV (change in velocity).
MATLAB Code (find it here)
% Constants
mu = 398600; % Gravitational parameter of Earth [km^3/s^2]
r1 = 7000; % Initial orbit radius [km]
r2 = 10000; % Target orbit radius [km]
% Genetic Algorithm parameters
populationSize = 50; % Number of individuals in the population
numGenerations = 100; % Number of generations
numSteps = 2; % Number of impulsive burns (same as Hohmann transfer)
mutationRate = 0.05; % Mutation probability
crossoverRate = 0.8; % Crossover probability
% Initial random population (representing thrust directions)
population = rand(populationSize, numSteps * 2); % Thrust angles and magnitudes
% Preallocate fitness array for storing results
fitness = zeros(populationSize, 1);
% GA loop for multiple generations
for generation = 1:numGenerations
% Evaluate fitness (fuel consumption) of each individual
for i = 1:populationSize
thrustSequence = population(i, :);
fitness(i) = evaluateThrustSequence(thrustSequence, r1, r2, mu);
end
% Select individuals based on fitness (lower deltaV is better)
selectedPopulation = selectRoulette(population, fitness);
% Apply crossover to generate new population
newPopulation = applyCrossover(selectedPopulation, crossoverRate);
% Apply mutation to introduce diversity
mutatedPopulation = applyMutation(newPopulation, mutationRate);
% Update the population
population = mutatedPopulation;
% Display best fitness of the generation
[bestFitness, bestIndex] = min(fitness); % We minimize fuel consumption
fprintf('Generation %d: Best deltaV = %.5f km/s\n', generation, bestFitness);
end
% Final GA solution
[bestFitness, bestIndex] = min(fitness);
bestThrustSequence = population(bestIndex, :);
fprintf('Optimal deltaV found by GA: %.5f km/s\n', bestFitness);
% Hohmann transfer calculations
% Burn 1: At perigee (first circular orbit)
v1 = sqrt(mu / r1); % Velocity in initial orbit
a_transfer = (r1 + r2) / 2; % Semi-major axis of the transfer orbit
v_transfer_perigee = sqrt(2 * mu * (1/r1 - 1/(2 * a_transfer))); % Velocity at perigee of transfer orbit
% Burn 2: At apogee (target circular orbit)
v_transfer_apogee = sqrt(2 * mu * (1/r2 - 1/(2 * a_transfer))); % Velocity at apogee of transfer orbit
v2 = sqrt(mu / r2); % Velocity in target orbit
% Delta V for Hohmann transfer
deltaV_hohmann = abs(v_transfer_perigee - v1) + abs(v2 - v_transfer_apogee);
fprintf('DeltaV for Hohmann transfer: %.5f km/s\n', deltaV_hohmann);
%% Function to evaluate fuel usage for a given thrust sequence
function deltaV = evaluateThrustSequence(thrustSequence, r1, r2, mu)
% Simplified evaluation of fuel consumption for impulsive burns
% thrustSequence: contains magnitudes and angles of thrust
% Step 1: Calculate initial velocity in the initial orbit
v1 = sqrt(mu / r1); % Circular orbit velocity at r1
% Step 2: Compute the semi-major axis of the transfer orbit
a_transfer = (r1 + r2) / 2; % Semi-major axis of the transfer orbit
% Step 3: Compute velocity at perigee (initial point) and apogee
v_transfer_perigee = sqrt(2 * mu * (1/r1 - 1/(2 * a_transfer))); % Perigee velocity
v_transfer_apogee = sqrt(2 * mu * (1/r2 - 1/(2 * a_transfer))); % Apogee velocity
% Step 4: Calculate deltaV for each thrust impulse
deltaV1 = abs(v_transfer_perigee - v1); % First burn at perigee (r1)
deltaV2 = abs(v_transfer_apogee - sqrt(mu / r2)); % Second burn at apogee (r2)
% Total deltaV (fuel consumption)
deltaV = deltaV1 + deltaV2;
end
%% Function for roulette wheel selection based on fitness
function selectedPop = selectRoulette(population, fitness)
totalFitness = sum(fitness);
prob = fitness / totalFitness;
cumulativeProb = cumsum(prob);
populationSize = size(population, 1);
numGenes = size(population, 2);
selectedPop = zeros(populationSize, numGenes);
for i = 1:populationSize
r = rand();
selectedIndex = find(cumulativeProb >= r, 1);
selectedPop(i, :) = population(selectedIndex, :);
end
end
%% Function to apply crossover
function newPop = applyCrossover(population, crossoverRate)
populationSize = size(population, 1);
numGenes = size(population, 2);
newPop = population;
for i = 1:2:populationSize
if rand() < crossoverRate
parent1 = population(i, :);
parent2 = population(i+1, :);
crossoverPoint = randi([1, numGenes-1]);
newPop(i, :) = [parent1(1:crossoverPoint), parent2(crossoverPoint+1:end)];
newPop(i+1, :) = [parent2(1:crossoverPoint), parent1(crossoverPoint+1:end)];
end
end
end
%% Function to apply mutation
function mutatedPop = applyMutation(population, mutationRate)
populationSize = size(population, 1);
numGenes = size(population, 2);
mutatedPop = population;
for i = 1:populationSize
for j = 1:numGenes
if rand() < mutationRate
mutatedPop(i, j) = rand(); % Random mutation
end
end
end
endWell, as you may notice both methods will give 1.22288 km/s value! But, this is just a simple illustrative example and the algorithm is meant for more complex optimization scenarios.
Let's keep this blog till here, if you have any questions related to this topic, feel free to connect with me and message me at https://www.linkedin.com/in/yajur
Keep Exploring!
Comments