% Genetic algoritm
% defining the search space
x=linspace(0,.6,150);
y=linspace(0,.6,150);
% creating 2D
[xx yy] = meshgrid(x,y);
%evaluating the stalagmite function at all values
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
% no of iterations
num_cases =50;
% Study1 - statistical behaviour without boundary
%for calculating study time tic toc command
tic
for k = 1:num_cases
[inputs,fopt(k)] = ga(@stalagmite,2);
xopt(k) = inputs(1);
yopt(k) = inputs(2);
end
study1_time =toc;
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
xlabel('x value');
ylabel('y value');
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'MarkerFaceColor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(fopt);
xlabel('Iterations')
ylabel('Function maximum')
% Study 2 - Statistical behavior with upper and lower boundaries
tic
for m= 1:num_cases
[inputs,fopt(m)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt(m) = inputs(1);
yopt(m) = inputs(2);
end
study2_time=toc;
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,f)
xlabel('x value');
ylabel('y value');
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'MarkerFaceColor','r');
title('bounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function maximum')
% study 3 -Increasing iterations of GA from 50 to 180
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',180);
tic
for n= 1:num_cases
[inputs,fopt(n)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(n) = inputs(1);
yopt(n) = inputs(2);
end
study3_time=toc;
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,f)
xlabel('x value');
ylabel('y value');
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'MarkerFaceColor','r');
title('bounded inputs with 180 iteration')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function maximum')
[inputs,fval] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options)
study1_time
study2_time
study3_time
%program for stalagmite function
function[F] = stalagmite(input_vector)
x= input_vector(1);
y =input_vector(2);
f1x =(sin(5.1*pi*x+0.5)).^6;
f1y =(sin(5.1*pi*y+0.5)).^6;
f2x =exp(-4*log(2)*((x-0.0667).^2)/0.64);
f2y =exp(-4*log(2)*((y-0.0667).^2)/0.64);
[F] = -(f1x.*f1y.*f2x.*f2y);
% since the ga function provide the minimum value
% inverse of actual equation give maximum value
end
AIM
Create a code to optimise the stalagmite function and find the global maxima of the function using ga
Plot graphs for studies for f maximum vs no. of iterations
Statistical behaviour without boundary
Statistical behaviour with lower and upper boundary
Statistical behaviour by increasing iteration.
CONTENT
Genetic Algorithms
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 solutions for optimisation problems and search problems.
Genetic algorithms simulate the process of natural selection which means those species who can adapt to changes in their environment are able to survive and reproduce and go to next generation. In simple words, they simulate “survival of the fittest” among individual of consecutive generation for solving a problem. Each generation consist 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.
Foundation of Genetic Algorithms
Genetic algorithms are based on an analogy with genetic structure and behaviour of chromosomes of the population. Following is the foundation of GAs based on this analogy –
Individual in population compete for resources and mate
Those individuals who are successful (fittest) then mate to create more offspring than others
Genes from “fittest” parent propagate throughout the generation, that is sometimes parents create offspring which is better than either parent.
Thus each successive generation is more suited for their environment.
Search space
The population of individuals are maintained within search space. Each individual represents a solution in search space for given problem. Each individual is coded as a finite length vector (analogous to chromosome) of components. These variable components are analogous to Genes. Thus a chromosome (individual) is composed of several genes (variable components).
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) are 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 chance 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 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 least fit die.
Operators of Genetic Algorithms
Once the initial generation is created, the algorithm evolves the generation using 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 selection operator and crossover sites are chosen randomly. Then the genes at these crossover sites are exchanged thus creating a completely new individual (offspring).
3) Mutation Operator: The key idea is to insert random genes in offspring to maintain the diversity in the population to avoid premature convergence.
After mutation the fitness of the resultant chromosomes evaluated and if they met the criteria
They are given as output or else the cycle is repeated
Syntax for ga
x = ga(fun,nvars)
finds a local unconstrained minimum, x, to the objective function, fun. nvars is the
dimension(number of design variables) of fun.
x = ga(fun,nvars,A,b)
finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b.
ga evaluates the matrix product A*x as if x is transposed (A*x’).
x = ga(fun,nvars,A,b,Aeq,beq)
finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b.
(Set A=[ ] and b=[ ] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x’).
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
Defines a set of lower and upper bounds on the design variables, x, so that a solution is found In the range lb ≤ x ≤ ub. (Set Aeq=[ ] and beq=[ ] if no linear equalities exist.)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)
subjects the minimisation to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimises the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)
minimises with the default optimisation parameters replaced by values in options. (Set nonlcon=[ ] if no nonlinear constraints exist.)
Create options usingoptimoptions
Syntax for option
options = optimoptions(SolverName,Name,Value)
returns options with specified parameters set using one or more name-value pair arguments.
Program to define the stalagmite function
The stalagmite function takes the ‘input_vector’ and calculate the corresponding value
The equation for stalagmite function is given by
`f(x,y)=f1x*f2x*f1y*f2y`
`f1x = [sin(5.1pix+0.5)]^6`
`f1y = [sin(5.1piy+0.5)]^6`
`f2x = exp[-4In(2)*(x-0.667)^2/0.64]`
`f2y = exp[-4In(2)*(y-0.667)^2/0.64]`
The two variables of the input are x and y.
Since the Matlab ga function find the minimum value of a function .(-ve ) is added to the final equation for the function stalagmite to get the maximum value
The syntax
function[F] = stalagmite(input_vector)
The input value is stored in x and y
x= input_vector(1) y =input_vector(2)
f1x =(sin(5.1*pi*x+0.5)).^6. Finding the value for f1x
f1y =(sin(5.1*pi*y+0.5)).^6 finding the value for f1y
f2x =exp(-4*log(2)*((x-0.0667).^2)/0.64) finding the value for f2x
f2y =exp(-4*log(2)*((y-0.0667).^2)/0.64) finding the value for f2y
The final equation
[F] = - (f1x.*f1y.*f2x.*f2y)
The program for ga
The x and y co-ordinates define the workspace .it is created using linespace command
The array of x and y values is created using mesh grid
Two loops are nested to access the coordinates of the grid and stored in input_vector . This is the input value for the stalagmite function and the output is stored in ‘f’ by calling the stalagmite function. -ve sign is used to find the global maxima
num_cases represent the no of iteration to done initially.
Study1 - statistical behaviour without boundary
The ga for stagalmite function run without providing the boundary condition .
[inputs,fopt(k)] = ga(@stalagmite,2)
The coordinates are stored in inputs and assigned to xopt and opt
The final value is stored in fopt
The tic toe command is used to store the time for this study
The two subplot is created in same figure window using subplot command
Surface is plotted using stalagmite function values.shading interp to remove the meshed line
Plot3 command is used to plot the x,y,f optimum values obtianed over 50 studies.
This helps to visualise how the algorithm is performing.
In the 2nd sub plot directly plotted the optimum value fopt against iteration.
To each iteration the maximum value changes .
Study 2 - Statistical behavior with upper and lower boundaries
The ga for stagalmite function run with providing boundaries
The syntax is
[inputs,fopt(m)] = ga(@stalagmite,2,[ ],[ ],[ ],[ ],[0;0],[1;1])
Here the lower and upper boundaries for x and y is limited
Same method of study 1is carried out for plotting and the the output is changed to more narrow range
Study 3 Increasing iterations of GA from 50 to 180
The syntax is
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',180);
[inputs,fopt(n)] = ga(@stalagmite,2,[ ],[ ],[ ],[ ],[0;0],[1;1],[ ],[ ],options)
Third study runs providing the upper bounds and lower bounds and also increasing
the iteration to 180. The output of ga normally give minimum value but the
stalagmite function is coded in such a way that it gives the maximum value as
output.
RESULT
Plot graphs for studies for f maximum vs no. of iterations
Statistical behaviour without boundary
Statistical behaviour with lower and upper boundary
Statistical behaviour by increasing iteration.
The time taken for each study is displayed . the maximum value of function and corresponding x and y coordinates is displayed