Week 4.1 - Genetic Algorithm
Genetic Algorithm :
The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued
The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:
-
Selection rules select the individuals, called parents, that contribute to the population at the next generation. The selection is generally stochastic, and can depend on the individuals' scores.
-
Crossover rules combine two parents to form children for the next generation.
-
Mutation rules apply random changes to individual parents to form children.
The following is the flowchart of Genetic Algorithm;
The basic steps in creating a genetic algorithm is as follows;
- The algorithm creates a random initial population at beginning.
- Then to create new population, the algorithm scores each member of the current population by computing its fitness value and converts them into a more usable range of values.
- Then based on these new values the algorithm selects the parents.
- Then the algorithm produces children from the parents. Children are produced either by making random changes to a single parent whic is mutation or by combining the vector entries of a pair of parents which is crossover.
- In this way, the algorithm repalces the current population with the children to form the next generation.
- The algorithm stops when it reaches any one of the specified factors such as time limit,fitness limit,generations,function tolerance,constraint tolerance etc.
What is Stalagmite?
Stalagmite function is a mathematical model which helps to generate local minima and maxima. It is a three dimensional function and the way the function is designed is that it has a lot of local maxima or minima and one global maxima or minima. The name stalagmite is obtianed from a type of rock formation that rises from the floor of a cave due to the accumulation of material deposited on the floor from ceiling drippings.
'ga' Syntax :
The 'ga' syntax in matlab is used to find the minimum of function using the genetic algorithm concept. The following are the 3 types of 'ga' syntax;
The below program is used to optimise the stalagmite function & find the global maxima of the function. Also, this program generates the plots of F maximum vs Iterations & stalagmite function with x & y values.
ga_statistics.m;
clear all %1%
close all
clc
x=linspace(0,0.6,150); %2%
y=linspace(0,0.6,150);
num_cases=50; %3%
for i=1:length(x) %4%
for j=1:length(y)
input_vector(1)=x(i);
input_vector(2)=y(j);
f(i,j)=get_stalagmite(input_vector);
end
end
tic
for z=1:num_cases %5%
[inputs,fopt(z)]=ga(@get_stalagmite,2);
xopt(z)=inputs(1);
yopt(z)=inputs(2);
end
study_time1=toc
figure(1) %6%
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','.','markersize',5,'markerfacecolor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function maximum')
hold off
tic
for z=1:num_cases %7%
[inputs,fopt(z)]=ga(@get_stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt(z)=inputs(1);
yopt(z)=inputs(2);
end
study_time2=toc
figure(2) %8%
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','.','markersize',5,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function maximum')
hold off
options=optimoptions('ga'); %9%
options=optimoptions(options,'populationsize',300);
tic
for z=1:num_cases %10%
[inputs,fopt(z)]=ga(@get_stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(z)=inputs(1);
yopt(z)=inputs(2);
end
study_time3=toc
figure(3) %11%
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','.','markersize',5,'markerfacecolor','r')
title('bounded inputs with modified population size')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function maximum')
hold off get_stalagmite.m;
function A=get_stalagmite(input_vector) %1%
x=input_vector(1); %2%
y=input_vector(2);
f1=(sin(5.1*pi*x+0.5))^6; %3%
f2=exp((-4*log(2))*(((x-0.0667)^2)/0.64));
f3=(sin(5.1*pi*y+0.5))^6;
f4=exp((-4*log(2))*(((y-0.0667)^2)/0.64));
A=-(f1*f2*f3*f4); %4%
endStepwise Explanation :
ga_stalagmite.m;
1 - The first few lines are used to clear & close all previous data to avoid mixing of those data with the current program.
2 - These lines are used to input the stalagmite workspace.
3 - This line indicates the number of times 'ga' has to undergo iteration.
4 - This for loop function is used to obtain the function value of the stalagmite for different input values of x & y.
5 - This for loop function is used to obtain the optimum values with unbounded inputs.
6 - The following lines are used to obtain the plot for the unbounded input condition.
7 - This for loop function is used to obtain the optimum values with bounded inputs.
8 - The following lines are used to obtain the plot for the bounded input condition.
9 - These lines are used to generate the options value in the 'ga' syntax.
10 - This for loop function is used to obtain the optimum values with bounded inputs along with poplution size.
11 - The following lines are used to obtain the plot for the bounded input with population size condition.
get_stalagmite.m;
1 - This line is used to return the stalagmite value to the calling function in main program.
2 - These lines are used to declare the input values to the function.
3 - The next few lines are used to declare the formula to calculate the stalagmite function value.
4 - This line is used to obtain the output value of stalagmite function.
Output :
Unbounded Inputs :
In the above image, we can interfere that different optimum values are obtained each time the program runs due to unbounded input condition.
Bounded Inputs :
In the above image, the number of red dots have reduced due to defining of bounded input condition.
Bounded Inputs with Population Size :
In the above image, the number of red dots have come down to one as the population has been declared with bounded input condition.
From the above image, we can obtain the x,y & z values of global maxima.
Errors :
No major errors in the program were encountered apart from few mistyping & missing of few fundamental declaration.