Week 4.1 - Genetic Algorithm
Theory of Genetic Algorithm:
Genetic Algorithms(GAs) are adaptive heuristic search algorithms that belong to the larger part of evolutionary algorithms. Genetic algorithms are based on the ideas of natural selection and genetics. These are intelligent exploitation of random search provided with historical data to direct the search into the region of better performance in solution space. They are commonly used to generate high-quality optimization and search problems solutions.
Genetic algorithms simulate the process of natural selection, which means those species who can adapt to changes in their environment can survive and reproduce and go to the next generation. In simple words, they simulate “survival of the fittest” among individuals of consecutive generations for solving a problem. Each generation consists of a population of individuals and each individual represents a point in search space and possible solution. Each individual is represented as a string of character/integer/float/bits. This string is analogous to the Chromosome.
Fitness Score
A Fitness Score is given to each individual which shows the ability of an individual to “compete”. The individual having optimal fitness score (or near-optimal) is sought.
The GAs maintains the population of n individuals (chromosome/solutions) along with their fitness scores. The individuals having better fitness scores are given more chances to reproduce than others. The individuals with better fitness scores are selected who mate and produce better offspring by combining chromosomes of parents. The population size is static so the room has to be created for new arrivals. So, some individuals die and get replaced by new arrivals eventually creating a new generation when all the mating opportunity of the old population is exhausted. It is hoped that over successive generations better solutions will arrive while at least fit die.
Each new generation has on average more “better genes” than the individual (solution) of previous generations. Thus each new generation has better “partial solutions” than previous generations. Once the offspring pro as having no significant difference from offspring produced by previous populations, the population is converged. The algorithm is said to be converted to a set of solutions for the problem.
Operators of Genetic Algorithms
Once the initial generation is created, the algorithm evolves the generation using the following operators –
1) Selection Operator: The idea is to give preference to the individuals with good fitness scores and allow them to pass their genes to successive generations.
2) Crossover Operator: This represents mating between individuals. Two individuals are selected using a selection operator and crossover sites are chosen randomly. Then the genes at these crossover sites are exchanged thus creating a completely new individual (offspring). For example –
3) Mutation Operator: The key idea is to insert random genes in offspring to maintain the diversity in the population to avoid premature convergence. For example –
The whole algorithm can be summarized as –
1) Randomly initialize populations p
2) Determine fitness of population
3) Until the convergence repeat:
- a) Select parents from population
- b) Crossover and generate a new population
- c) Perform mutation on new population
- d) Calculate fitness for new population
Stopping criteria:
ga uses four different criteria to determine when to stop the solver. ga stops when it reaches the maximum number of generations; by default, this number is 100 times the number of variables. ga also detects if the best fitness value does not change for some time given in seconds (stall time limit), or for some number of generations (maximum stall generations). Another criteria is the maximum time limit in seconds. Modify the stopping criteria to increase the maximum number of generations to 300 and the maximum stall generations to 100.
Syntax of ga:
[x,fval] = ga(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)
Where,
- Nvars- number of variables
- A,b – Linear inequality constraints
- Aeq,beq – Linear equality constraints
- Lb- lower bound
- Ub- lower bound
- Nonlcon: use for nonlinear constarints
- Options: Minimize with nondefault options
- x- coordinates of minimum value
- fval- minima value
Matlab code- Stalagmite function
function [f] = stalagmite(input_vector)
x=input_vector(1);
y=input_vector(2);
f1=(sin(16.02.*x+0.5)).^6;
f2=exp(-4.332*(x-0.667));
f3=(sin(16.02.*y+0.5)).^6;
f4=exp(-4.332*(y-0.667));
f=-(f1*f2*f3*f4);
end
Note: ga is used for minima function, our problem is for finding maxima. Thus the stalagmite function is taken negatively to maximize.
% Study 1 - Statistical behavior of function
clear all
close all
clc
% Defining our search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
% Defining the number of iterations
num_cases=50;
%Creating a 2 dimensional mesh
[xx yy]=meshgrid(x,y);
%Evaluating the stalagnite function
for i=1:length(xx)
for j=1:length(yy)
input_vector(1)=xx(i,j);
input_vector(2)=yy(i,j);
f(i,j)=stalagmite(input_vector);
end
end
% To change the direction of graph
F=-f;
% Intoducing the stopwatch timer.
tic;
% Running the function with number of iterations
for i=1:num_cases
[inputs, fopt(i)]=ga(@stalagmite,2);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study1_time=toc;
fprintf('\nThe total time required for the function evaluation is %f secs\n',study1_time)
fprintf('The maxima function x coordinate is %f\n',xopt(50))
fprintf('The maxima function y coordinate is %f\n',yopt(50))
fprintf('The maxima function value is %f\n',-fopt(50))
figure(1)
subplot(2,1,1)
hold on
% Plotting the function
surface(x,y,F)
% Shading the graph for better look
shading interp
% Plotting the maximum point travelling to reach the optimum value
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')
% Labelling the graph
xlabel('X value-->');
ylabel('Y value-->');
zlabel('Function value-->');
title('Maximize the function-Study1--Unbound inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations-->')
ylabel('Function maximum-->')
title('Plot of function optimization with number of iteration')
%Defining the axis to see the clear line graph
% Study 2- Statistical behavior- with upper and lower bounds
clear all
close all
clc
% Defining our search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
% Defining the number of iterations
num_cases=50;
%Creating a 2 dimensional mesh
[xx yy]=meshgrid(x,y);
%Evaluating the stalagnite function
for i=1:length(xx)
for j=1:length(yy)
input_vector(1)=xx(i,j);
input_vector(2)=yy(i,j);
f(i,j)=stalagmite(input_vector);
end
end
% To change the direction of graph
F=-f;
% Intoducing the timer.
tic
for i=num_cases
[inputs, fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study2_time=toc;
fprintf('\nThe total time required for the function evaluation is %f secs\n',study2_time)
fprintf('The maxima function x coordinate is %f\n',xopt(50))
fprintf('The maxima function y coordinate is %f\n',yopt(50))
fprintf('The maxima function value is %f\n',-fopt(50))
figure(2)
subplot(2,1,1)
hold on
% Plotting the function
surfc(x,y,F)
% Shading the graph for better look
shading interp
% Plotting the maximum point travelling to reach the optimum value
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')
% Labelling the graph
xlabel('X value-->');
ylabel('Y value-->');
zlabel('Function value-->');
title('Maximize the function-Study1--Bounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations-->')
ylabel('Function minimum-->')
title('Function optimization with number of iteration')
%Defining the axis to see the clear line graph
axis([0 60 -1 1])
% Study 3- Statistical behavior-Increasing GA iterations
clear all
close all
clc
% Defining our search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_cases=50;
%Creating a 2 dimensional mesh
[xx yy]=meshgrid(x,y);
%Evaluating the stalagnite function
for i=1:length(xx)
for j=1:length(yy)
input_vector(1)=xx(i,j);
input_vector(2)=yy(i,j);
f(i,j)=stalagmite(input_vector);
end
end
F=-f;
% Intoducing the timer.
options=optimoptions('ga');
options=optimoptions(options,'PopulationSize',200);
tic
for i=num_cases
[inputs, fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study3_time=toc;
fprintf('\nThe total time required for the function evaluation is %f secs\n',study3_time)
fprintf('The maxima function x coordinate is %f\n',xopt(50))
fprintf('The maxima function y coordinate is %f\n',yopt(50))
fprintf('The maxima function value is %f\n',-fopt(50))
figure(3)
subplot(2,1,1)
hold on
% Plotting the function
surfc(x,y,F)
% Shading the graph for better look
shading interp
% Plotting the maximum point travelling to reach the optimum value
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')
% Labelling the graph
xlabel('X value-->');
ylabel('Y value-->');
zlabel('Function value-->');
title('Maximize the function-Study1--Bounded inputs')
subplot(2,1,2)
plot(fopt)
% Labelling the graph
xlabel('Iterations-->')
ylabel('Function minimum-->')
title('Function optimization with number of iteration')
%Defining the axis to see the clear line graph
axis([0 60 -1 1])
Significance of multiple iterations
It is done to evaluate the function for number of cases to reach optimum value soon with that number of cases
References
- Geeks for geeks
- Mathswork-matlab