Week 4.1 - Genetic Algorithm

Genetic Algorithm for analysis of stalagmite function in MATLAB

Aim :

Optimization of Stalagmite Function Using Genetic Algorithm

Objective :

• Write a code in MATLAB to optimize the stalagmite function and find the global maxima of the function.
• Clearly explain the concept of genetic algorithm in your own words and also explain the syntax for ga in MATLAB in your report.
• Make sure that your code gives the same output, even if it is made to run several time.

Theory :

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

Genetic algorithms are based on an analogy with genetic structure and behavior of chromosome 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 represent 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.

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

3) Mutation Operator: The key idea is to insert random genes in offspring to maintain the diversity in population to avoid the premature convergence.

Following are the Syntax used for finding the maximum of function using genetic algorithm :

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,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,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions

where,

fun = Objective function

nvars = Numbers of variables

A = Linear inequality constraints

b = Linear inequality constraints

Aeq = Linear equality constraints

beq = Linear equality constraints

lb = Lower bounds

ub = Upper bounds

nonlcon = Nonlinear constraints

options = Optimization options

STEP BY STEP EXPLANATION:

• Then we write main code were we define two inputs x and y both of which are one dimensional equally spaced array containing 100 elements. We utilise meshgrid command to create an array of x and y values.To improve our Genetic Algorithm, we undertake three cases to optimise the function so that we can accurately find the global maxima of the function. We need to do this because the GA randomly takes values and global maxima can change according to that.In case 2 we put an upper bound and lower bound on ‘ga’ function and again plot two plots which we plot during case 1.
• In case 3 we increase GA iterations. We do this because in GA after successive iterations, the population "evolves" toward an optimal solution i.e more the number of iterations, more optimal the solution will be. Now we use same commands to plot the graph and curve.
• In case 1 we evaluate all possible global maxima for all the iterations using a loop. We two plot in one figure using subplot command. ‘surfc’ command is used for x vs y graph and for function max vs iteration we use simple ‘plot’ command. The values in figure (1) are unbounded values.
• Now we use for loop to input values of 2D array in stalagmite function. Here we encounter an problem i.e. every time the code is executed different values for stalagmite function are obtained. This is overcome by introducing another loop into the code. We then input these values in genetic algorithm. For genetic algorithm ‘ga’ function is used.
• First, we write a code to define the stalagmite function. Here we break down the formula into 4 terms for convenience.

CODE:

Main Code:

clear all
close all
clc
 
x=linspace(0,1,100);
y=linspace(0,1,100);
 
[xx,yy]=meshgrid(x,y);
 
for i=1:length(xx)
    for j=1:length(yy)
        
        inputs(1)=xx(i,j);
        inputs(2)=yy(i,j);
        F(i,j)=stalagmite(inputs);
    end
end
 
num=100;
tic
 
% Case1 : Statistical Behaviour
 
for i=1:num
   [inputs,Fout(i)]=ga(@stalagmite,2);
    xout(i)=inputs(1);
    yout(i)=inputs(2);
end
 
 
 
casel_time=toc; 
 
figure(1)
subplot(2,1,1) 
surfc(xx,yy,-F) 
shading interp 
hold on
plot3(xout,yout,-Fout,'marker','*','markersize',5,'markerfacecolor','r') 
title('Unbounded Inputs')
subplot(2,1,2) 
plot(-Fout)
xlabel('Iterations')
ylabel('Function Maximum')
tic
 
%Case2 : Statistical Behaviour with upper bound & lower bound
 
for i=1:num
    [inputs,Fout(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.3;0.3],[],[]);
    xout(i)=inputs(1);
    yout(i)=inputs(2);
end
 
case2_time=toc; 
 
figure(2)
subplot(2,1,1) 
surfc(x,y,-F)
shading interp 
hold on
plot3(xout,yout,-Fout,'marker','*','markersize',5,'markerfacecolor','g')
title('Bounded Inputs')
subplot(2,1,2) 
plot(-Fout)
xlabel('Iterations')
ylabel('Function Maximum')
tic
 
%Case3 : Increasing Iterations
 
options=optimoptions('ga'); 
options=optimoptions(options,'populationsize',200);
 
for i=1:num
[inputs,Fout(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xout(i)=inputs(1);
yout(i)=inputs(2);
end
 
case3_time=toc;
 
figure(3)
subplot(2,1,1)
surfc(x,y,-F) 
shading interp 
hold on
plot3(xout,yout,-Fout,'marker','*','markersize',5,'markerfacecolor','b')
title('Bounded Inputs with Increased Population size')
subplot(2,1,2) 
plot(-Fout)
xlabel('Iterations')
ylabel('Function Maximum')

Function code:

function [F] =stalagmite(inputs)
 
x=inputs(1);
y=inputs(2);
 
 term1=(sin((5.1*pi*x)+0.5))^6;
 term2=exp((-4)*log(2)*((x-0.0667)^2)/0.64);
 term3=(sin((5.1*pi.*y)+0.5))^6;
 term4=exp((-4)*log(2)*((y-0.0667).^2)/0.64);
     
 F= -(term1*term2*term3*term4);
 
end

OUTPUT/RESULT/CONCLUSION:

• Case 1 :

• Case 2 :

• Case 3 :

CONCLUSION:

we have studied genetic algorithm & learned about the theory of evolution and is importance which helps to predict the genetic mutation possibilities. GA in matlab help us to find the local and global minimas which helps in engineering level optimization for perfect solution and giving the visual context of the solution.

REFERENCES, IF ANY:

• https://in.mathworks.com/help/gads/what-is-the-genetic-algorithm.htmlhttps://en.wikipedia.org/wiki/Genetic_algorithm
• https://in.mathworks.com/help/gads/ga.html#d120e39545
• https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

ERROR:

1. obviously many typo errors were happen related to capital letter, space, forget to write 'end' , quete sign and all

2. the plots obtained were not proper beacuse 'ga' function is used to find minima but we have to find maxima so we have to introduce negative sign in function code.

3. even after using negative sign in function code the graph was not proper.

so, to overcome this problem we introduced negative sign with each value of function output F in main code to reverse the direction of plot.