MATLAB: Genetic Algorithms

AIM

To write a code in MATLAB to optimise the stalagmite function and to find the global maxima of the function using genetic algorithm.

OBJECTIVE

Plot graphs for all 3 studies and for F maximum vs no. of iterations.

THEORY

1. Understanding genetic algorithm
The genetic algorithm is inspired by the process that drives biological evolution. The process of evolution starts with the selection of fittest individuals from a population. Then they produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found. And this is the main working principle for the algorithm because at each step, the genetic algorithm selects randomly 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.

2. The genetic algorithm (ga) can be applied 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 uses three main types of rules at each step to create the next generation from the current population:
i. Selection rules select the individuals, called parents, that contribute to the population at the next generation.
ii. Crossover rules combine two parents to form children for the next generation.
iii. Mutation rules apply random changes to individual parents to form children.

3. The genetic algorithm differs from a classical, derivative-based, optimisation algorithm in two main ways as under-mentioned in the table:

CLASSICAL ALGORITHM (CA)	GENETIC ALGORITHM (GA)
Generates a single point at each iteration. The sequence of points approaches an optimal solution.	Generates a population of points at each iteration. The best point in the population approaches an optimal solution.
Selects the next point in the sequence by a dterministic computation.	Selects the next population by computation which uses random number generations.

Working principle of genetic algorithm

The working of a genetic algorithm is also derived from biology, which is as follows,

1) Initialization.

2) Fitness Assignment.

3) Selection.

4) Cross Over.

5) Mutuation.

6) Stopping Criteria.

Some advantages of genetic algorithms this method are the following:

1) They usually perform better than traditional feature selection techniques.

2) Genetic algorithms can manage data sets with many features.

3) They don't need specific knowledge about the problem under study.

4) These algorithms can be easily paralelized in computer clusters.

Working of Genetic Algorithm:

The following outline summarizes how the genetic algorithm works:

1) The algorithm begins by creating a random initial population.The algorithm then creates a sequence of new populations.

2) At each step, the algorithm uses the individuals in the current generation to create the next population.

To create the new population, the algorithm performs the following steps:

a) Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.

b) Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.

c) Selects members, called parents, based on their expectation.

d) Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.

e) Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.

f) Replaces the current population with the children to form the next generation.The algorithm stops when one of the stopping criteria is met.Note,Genetic Algorithm is only used to generate minimum solution. So the value of stalagmite function is taken negative to maximise the function.

GOVERNING FORMULA

Syntax For ga :

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)

where,

1) x=optimum solution/variables.

2) no_of_variables=Number of variables, specified as a positive integer.

3) A,b= Linear inequality constraints.

4) Aeq,beq=Linear equality constraints.

5) lb,ublb=Lower bounds ub=Upper bounds

6) nonlcon : Use for nonlinear constraints.

7) IntCon : to get solution in integer.

8) options: Minimize with non default options.

Writing for the main code :

1. First, Linspace command is used to define x and y with 150 elements between zero and 0.6 including the bounds.

2. Then num_cases is set which will be used as counter for iterations to 50.

3. Then a 2D grid is made using meshgrid command is created from x and y input to be outputted to xx and yy.

4. Then for loop is used to solve the genetic algorithm for every element in the 2D mesh grid.

5. The length of rows and columns (which have equal length) are used as counters.

6. Then the input vector is declared as ga requires input vector which is each value in the mesh grid

7. Then output of stalagmite function is stored in matrix.

8. Then tic command is used to start a timer

9. Then for loop bounded by the number of iterations is formed.

10. Then ga code is entered for unbounded statistical study which have the following format

[inputs,fopt] = ga(fun,nvars).

Inputs represent the values of parameters x and y for which the function has the least value .

(fopt)function - The function to be optimized, in this case Stalagmite

(nvars) - the number of design variables, in this case only x and y are the variables to be plotted.

11. Then smallest (minimum ) value of the function for each iteration is chosen as output and its x and y coordinates, Which are stored in separate variable.

12. Then toc command is used to stop the timer and the output is stored in study_time 1.

13. Then figure 1 is plotted by the following steps:

14. First subplot command is used to partition the plot window in order to draw more than one plot in the same windows ,two rows and one column are specified and then the position of each plot is selected.

15. Then Hold on command is used to prevent plot from being removed.

16. The surfc command is used to plot contour with xx value and yy value from the mesh grid as input and negative optimum value is used because we need to maximize the function.

17. Then x, y ,and z axis are labeled.

18. Then shading interp is used to smoothen the function plot and to remove the grid lines.

19. Then plot 3 command is used to plot a point in 3 dimensions, here it will plot -fopt because we need the maximum value of the function, not the minimum.

20. Then the graph title is selected,and -fopt value of the function is plotted on the second plot in the second row.

21. Then its x and y axis are labeled.

22. Then the same study is made but this time it is bounded (has lower and upper limit) which requires the same commands and steps except the ga command which have the following format:

[inputs,fopt] = ga(fun,nvars,A,b,Aeq,beq,lb,ub)

Inputs, fopt,fun and nvars are the same as Study 1A -

Linear inequality constraints : real matrix, if there are none,then []b - Linear inequality constraints : real vector, if there are none, then []Aeq - Linear equality constraints : real matrix, if there are none, then []beq - Linear equality constraints : real vector, if there are none, then []lb - Lower bounds, specified as a real vector or arrayub - Upper bounds, specified as a real vector or array.

23. The range of the genetic algorithm is Bounded by introducing values for lower and upper bounds and hence the values of global maxima and the values of x and y will be within the defined search space in inputs.

24. Then increasing population size study was done which is the same as before but it had different ga code of:

[inputs,fopt]=ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options)

Inputs, fopt,fun and nvars,A,b,Aeq,beq,lb,ub are the same as Study 1 and Study 2 respectively)

nonlcon - Nonlinear constraints, specified as a function handle or function name.

If there are none,then []IntCon - Integer variables, specified as a vector of positive integers, if there are none, then []Options - Optimization options, specified as the output of optimoptions or a structure.

25. The range of the genetic algorithm is Bounded as in Study 2 but to improve the accuracy, the commands optimoptions is introduced to increase the Population Size.

26. Then total time is computed.

27. Then using fprintf command the results are printed in the command windows.

28. Then the study time is printed.

29. Then x,y coordinates of the maximum optimum value are printed.

30. Then the optimum value of the function (maximum value) is printed which is calculated from the (negative mean) of the all iterations of the output value ,and the negative sign is used to get the maximum value.

MAIN CODE

%Creating x and y array
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_cases=50;

%Creating two dimensional mesh
[xx,yy]=meshgrid(x,y);

%Calculating the stalagmite function
for i=1:length(xx)
    for j=1:length(yy)
        a(1)=xx(i,j);
        a(2)=yy(i,j);
        f(i,j)=stalagmite(a);
    end
end

%Study-1
tic
for i=1:num_cases
   [inputs,fopt(i)]=ga(@stalagmite,2);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study1_time=toc

figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title('Unbounded inputs')
xlabel('x values')
ylabel('y values')
plot3(xopt,yopt,fopt,'marker','o','markersize',6,'markerfacecolor','r')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function maximum')

%Study-2
tic
for i=1:num_cases
    [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study2_time=toc

figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title('Bounded inputs')
xlabel('x values')
ylabel('y values')
plot3(xopt,yopt,fopt,'marker','o','markersize',6,'markerfacecolor','r')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function maximum')

%Study-3
options=optimoptions('ga')
options=optimoptions(options,'PopulationSize',170)
tic
for i=1:num_cases
    [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
fopt=-fopt;
f=-f;
study3_time=toc

figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
xlabel('x values')
ylabel('y values')
plot3(xopt,yopt,fopt,'marker','o','markersize',6,'markerfacecolor','r')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function maximum')
max_value=fopt

Stalagmite function code explaination:

1. First the function is declared and its input vector is specified.

2. Next, the equations are written with inputs from mesh grid.

3. Then, in the last step negative sign is used because we want to maximize the function.

FUNCTION CODE

%stalagmite function code
function [F]=stalagmite(a) 
x = a(1); 
y = a(2); 
f1=(sin((5.1*pi*x)+ 0.5))^6; 
f2=(sin((5.1*pi*y)+ 0.5))^6; 
f3= exp((-4*log(2)*((x-0.0667)^2))/(0.64)); 
f4= exp((-4*log(2)*((y-0.0667)^2))/(0.64)); 
F = -(f1*f2*f3*f4);
end

REPORT

1) Initially create a x and y array and number of iterations you want.

2) Then create xx and yy array by using meshgrid command.

3) By using nested for loop, calculate the stalagmite function and store the value in f. Here we use -ve sign in stalagmite function, because we calculate the global maxima.

4) Then you find out all the three studies.

5) Study-1, it calulate the global maxima by taking random samples from the function. Here we use tic-toc command for calculating the time taken for study-1.

6) Syntax for ga in study-1 is [inputs,fopt(i)]=ga(@stalagmite,2);

7) Study-2, it calculate the global maxima by giving boundary limits for the inputs.

8) Syntax for ga in study-2 is [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);. In that you see the boundary limits 0 to 1.

9) Study-3, it calculate the global maxima by giving population size by which we can find the specific optimum point.

10) Syntax for ga in study-3 is [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);. Here, options=optimoptions('ga'); options=optimoptions(options,'PopulationSize',170) ;

11)In that the population size given is 170. The maximum value of stalagmite function is +1 obtained.

PLOTS SUPPORTING STUDY-1,STUDY2 and STUDY-3

Study 1: UNBOUNDED INPUT

Time taken :

Study time 2: Bounded Inputs

Time taken for study:

Study 3 :

Time taken for study :

Population properties