Week 4.1 - Genetic Algorithm

AIM :- To optimize the stalagmite function and find the global maxima of the function.

Genetic Algorithm is a search based optimization technique based on the principles of Genetics and Natural selection.It is used to find optimal or near optimal solutions to various problems which take more time to solve.

Matlab Code:-

clear all
close all
clc

% Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50  % No.of iterations

% Creating a 2dimensional mesh
[xx ,yy] = meshgrid(x,y);
% Evaluating the stalagmite function
for i = 1:length(xx)
    for j = 1:length(yy)
        input_vector(1) = xx(i,j);
        input_vector(2) = yy(i,j);
        input_vector = [input_vector(1),input_vector(2)];
        f(i,j) = stalagmite(input_vector); %Calling the stalagmite function
    end
end

%study 1 - Statistical behaviour(Unbounded condition)

tic           % TicToc command is used to calculate the iteration time
for i = 1:num_cases
    [input, f_opt(i)] = ga(@stalagmite,2);
    xopt(i) = input(1);
    yopt(i) = input(2);
end
Timeofstudy1 = toc

figure(1)
subplot(2,1,1)
hold on 
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-f_opt,'marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('Unbounded inputs')
subplot(2,1,2)
plot(-f_opt)
xlabel('Iteration')
ylabel('function minimum')

% Study2 - Statistical behaviour(upper&lower bounds)
tic
for i=1:num_cases
    [input,f_opt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i) = input(1);
    yopt(i) = input(2);
end
Timeofstudy2 = toc

figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-f_opt,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(-f_opt)
xlabel('Iteration')
ylabel('function minimum')

%Study3- Increasing iterations of 'f'
options = optimoptions('ga'); %calculating optimum solution for 'f' and save in options(variable)
options = optimoptions(options,'PopulationSize',230) %Increasing the population size
tic
for i = 1:num_cases
    [input,f_opt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(i)=input(1);
    yopt(i)=input(2);
end
Timeofstudy3 = toc

figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-f_opt,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(-f_opt)
xlabel('Iteration')
ylabel('function minimum')

Matlab Program for the function:-

function [f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
term1 = 5.1*pi*x;
term2 = 5.1*pi*y;
term3 = ((x-0.0667)^2/0.64);
term4 = ((y-0.0667)^2/0.64);
term5 = (-4*log(2));

f1x = (sin(term1+0.5)).^6;
f1y = (sin(term2+0.5)).^6;
f2x = exp(term5*term3);
f2y = exp(term5*term4);

f = -(f1x*f1y*f2x*f2y);
end

Code Procedure:-

1) Use clear all,close all,clc commands to clear memory.Define x and y using linspace command giving 150 values between 0 and 0.6 and then create 2 dimensional array using meshgrid command.

2) Using for loop we have to define an array called input_vector1,input_vector2 for each value of x and y and save these value in input_vector.

3) To calculate maxima,type the new function stalagmite by using below formula

f(x,y)=f1x*f2x*f1y*f2y

f1x=[sin(5.1*pi*x + 0.5)]^6

f1y=[sin(5.1*pi*y + 0.5)]^6

f2x=exp[-4ln(2)(x-0.0667)^2/0.64]

f2y=exp[-4ln(2)(y-0.0667)^2/0.64]

4) Now this function is called in for loop & passing the number of variable as input.This loop will generate the data for plot.

5) Study1-Staistical behaviour - To define the search space use num_cases = 50, means it runs 50 times, then I use 'for' loop and run the code 1 to 50 times,then I call 'f' and use the new function which I created @stalagmite,pass 2 variable as input and store the output in f_opt,and then store x,y in xopt,yopt. Using surfc command to see the output,use shading interp command to prevent grid lines.Use tictoc command to calculate the time taken for evaluation.Use subplot command to show stalagmite function in 1st plot and plotting the minimum value that 'f' trying to predict over 50 studies. 2nd plot for showing the no.of iteration at x-axis and during each iteration value changes which represents as function maxima on y-axis

6) Study2-Staistical behaviour(upper&lower bounds) - In this case we setup the bound condition for x&y. Using syntax 'ga' we are giving x,y the upper limit and lower limit to 0 and 1

7) Study3 - Increasing f iterations:- In this case in addition to specifying bounds,we also increase the population size,to find the global maxima the population size should be more.We can find only local maxima in study 2,following the same procedure as in study2,and increase the population size to 230 and applying the constraint 'optimoptions' to allow the ga to predict the optimum solution from 230 population size.

Theory about ga:-

Optimization:- It is the process of making something better.Optimization refers to finding the values of inputs in such a way that we get the best output values.This refers to maximizing or minimizing the functions by varying the inputs.The set of all possible solutions or the values which the inputs can take make up the search space.We have to find one point in this search space which gives the optimal solution.

Genetic algorithm:- Genetic algorithms 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 optimization problems and search problems.

In GAs we have a population of possible solutions to the given problem.These solutions then undergo recombinations and mutation ,producing new children and the process is repeated over various generations.Each individual is assigned a fitness value and the fitter individuals are given a higher chance to mate and yield more fitter individuals.This is in line with the Darwin theory of "Survival of the fittest".In this way we keep evolving better individuals till we reach a stopping criterion.

Genetic algorithms are sufficiently randomized in nature,but they perform much better than random local search,as they exploit historical information as well.The genetic algorithm uses 3 main steps 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.

*Crossover rules - combine two parents to form children for the next generation.

*Mutation rules - apply random changes to individual parents to form children.

Outline Of the Algorithm:

*The algorithm begins by creating a random initial population.

*The algorithm then creates a sequence of new populations.At each step the algorithm uses the individuals in the current genration to create the next population.To create the new population, the algorithm performs the following steps:

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

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

3.Selects members,called parents,based on their expectation.

4.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.

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

6.Replaces the current population with the children to form a next generation.

Operators of Genetic Algorithms:-

Once the initial generation is created,the algorithm evolve 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 there genes to the next generations.

2)Crossover operator:- 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 maintain the diversity from one generation of population of chromosomes to the next.If mutation is not performed, the chromosomes will become to similar to each other,convergence takes place soon and results in local minima.

Stopping criteria:-

When there has been no improvement in the population for X iterations,when we reach an absolute number of generations,when the objective function value has reached a certain pre-defined value.

For example,in a genetic algorithm we keep a counter which keeps track of the generations for which there has been no improvement in the population.Initially,we set this counter to zero.Each time we don't generate off springs which are better than the individuals in the population,we increment the counter.

However,if the fitness any of the off-springs is better,then we reset the counter to zero.The algorithm terminates when the counter reaches a predetermined value.

Like other parameters of a GA, the termination condition is also highly problem specific and the GA designer should try out various options to see what suits his particular problem the best.

Syntax for ga - ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options)

ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)

ga - To find the minimum of the function using genetic algorithm

fun - finds a local minimum to function

nvars - number of variables

A - Linear inequality constraints,specified as a real matrix

b - Linear inequality constraints,specified as a real vector

Aeq - Linear inequality constraints,specified as a real matrix

beq - Linear inequality constraints,specified as a real matrix

lb - Lower bound

ub - Upper bound

nonlcon - Nonlinear constraints specified as a function handle

options - Optimization options,specified as the output

Significance of running multiple iterations:- We do multiple iteration is to get the Global maxima in desired range.The main motive of doing so is to get the only 1 desired optimum output which is required for given problem.

Results:

Study1 ) (gastudy1.png)

Here on plotting stalagmite function,I am plotting the minimum value that 'ga' predicts,which is all over the place on graph,'it happens due to random sample during each iteration the value changes.Also in command window we can observe the time taken for iteration(Timeofstudy1 = 2.8838sec)

Study2) (gastudy2.png)

In this study we have given upper and lower limits for x,y as 0 to 1 since the optimum output lies all over the graph.

Here from the graph,it is observed that the function predicts minimum points is between 3 peaks,it is much clear than study1.From y-axis of the graph the minimum value lies between 0.4 & 0.6, it is much accurate,but still not clear.Also the time of study2 =3.6440sec which is more than study1

Study3) (gastudy3.png)

In addition with specifying bounds , here we are increasing the initial population size.Here from subplot1,it shows maxima only lies around 1peak, maxima lies at around the value 0.847 that ga predicts,In this study it is giving the optimum value,on increasing the number of iterations and applying constraints,but it has its' drawbacks, as ga slows down as it have more number of samples,to process and evaluate them for the function.Time of study3 = 9.5861sec which is very high compared to study1.