Week 4.1 - Genetic Algorithm

Genetic Algorithm

Aim:

To write a code in matlab to optimise stalagmite function and to find the Global Maximum of the function.

Optimization:

Optimization is a process of discovering the optimised solution to a problem .Its is an iterative process which analyses the possible solutions for the best solution. It includes maximizing criteria like productivity,efficiency,strength,reliability while minimizing factors like cost,lead time etc. It is a tiring process to perform the iterations manually. So to make it easier we can use Optimization algorithm. Genetic Algorithm is one of the optimization alorithm.

Genetic Algorithm:

Genetic Algorithm is based on evolution theory proposed by Charles Darwin. It is a natural selection process Genetic algorithm always returns the minimum values. we can use Genetic Algorithm for problems where there is a clear way to evaluate fitness. If your search space is not well constrained or your evaluation process is computationally expensive, discontinuous objective function, nondifferentiable, stochastic, or highly nonlinear. Genetic Algorithms may not find solutions in a sane amount of time. GA's rely on biologically inspired processes crossover, mutation and, selection.

Process followed by Genetic Algorithm:

Genetic Alogorithm starts with population initialization, the sample data in the population undergoes three steps,

Selection: In selection process fittest individuals i.e the parents are selected from the sample data. The more fitter individulas in the population produce fitter offsprings over a time.

Crossover: crossover is used to combine the genetic information of two parents to generate new offspring. for example Set of genes from parent A is combined with set of genes with parent B. A better offsprings with both the parents qualities are produced.

Mutation: mutation is used to maintain genetic diversity from one generation of a population of genetic algorithm chromosomes to the next. If mutation is not performed it results in convergence and local minima. It is analogous to biological mutation. Mutation alters one or more gene values in a chromosome from its initial state.

Stalagmite Function: Stalagmite and stalactite are mathematical functions that resembles Stalagmite and Stalactitestructures in nature. Stalagmite is formed on the cave floor and Stalactite is formed from the roof of the cave. These formations are formed due to redeposition of minerals from water droplets which evaporates leaving behind minerals. When stalactite and stalagmite meet it is called Stalagnates.

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

main function:

clear all

close all

clc

% defining the search space

x = linspace(0,0.6,150);

y = linspace(0,0.6,150);

% to create 2d mesh

[xx yy] = meshgrid(x,y);

% % assigning valus to inputs

for i = 1:length(xx)% takes values until length of xx

for j = 1:length(yy)% takes values until length of xx

inputs(1) = xx(i,j);

inputs(2) = yy(i,j);

f(i,j) = stalagmite(inputs);

end

end

num_case = 50; % creating a variable and assigning the number to which iterations performed

tic % Starts the timer

% Study case-1

for z = 1:num_case% takes values until length of num_cases

[inputs,fopt(z)] = ga(@stalagmite,2);% solve stalagmite function using GA and assigning to variables

xopt(z) = inputs(1);

yopt(z) = inputs(2);

end

Time_study1 = toc % Gives time taken to perform the case

figure(1)

subplot(2,1,1) % creates sub-plot in the figure

hold on

surfc(xx,yy,-f) % Creates a surface

shading interp % varies the color in each line segment and face by interpolating the colormap index or true color value across the line or face.

plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')% plot3 command used to plot in 3 axis

% marker is used to create a visible points on the plot

title('unbounded inputs')

xlabel('x-axis')

ylabel('y-axis')

zlabel('z-axis')

subplot(2,1,2)

plot(-fopt)

xlabel('iterations')

ylabel('Function maximum')

% Study Case-2 Defining upper and lower bounds

tic

for z = 1:num_case

[inputs,fopt(z)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4]);

%defines a set of lower and upper bounds on the design variables

xopt(z) = inputs(1);

yopt(z) = inputs(2);

end

Time_study2 = toc

figure(2)

subplot(2,1,1)

hold on

surfc(xx,yy,-f)

shading interp

plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','b')

title('Bounded inputs')

xlabel('x-axis')

ylabel('y-axis')

zlabel('z-axis')

subplot(2,1,2)

plot(-fopt)

xlabel('iterations')

ylabel('Function maximum')

clc

% Study Case-3 Increasing iterations

options = optimoptions('ga');% returns a set of default options for the SolverName solver.

options = optimoptions(options,'PopulationSize',270);%Defining population size

tic

for z = 1:num_case

[inputs,fopt(z)] = ga(@stalagmite, 2,[],[],[],[],[0;0],[0.4;0.4],[],[],options);

% takes the values of options and solves ga in required population

xopt(z) = inputs(1);

yopt(z) = inputs(2);

end

Time_study3 = toc;

figure(3)

subplot(2,1,1)

hold on

surfc(xx,yy,-f)

shading interp

plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')

title('Increased population')

xlabel('x-axis')

ylabel('y-axis')

zlabel('z-axis')

subplot(2,1,2)

plot(-fopt)

xlabel('iterations')

ylabel('Function maximum')

% The Global Maximum at the position

display(inputs,'Global maximum')

subfunction stalagmite function:

function [f]=stalagmite(inputs)

x = inputs(1);

y = inputs(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);

end

Code Explaination:

Defining the search space for the GA to be performed. Using the mesh command to create 2d matrix.Writing stalagmite function which will be called in the main function.

Negative sign is used in the stalagmite function to get the global maximum as GA always returns global minima.

Assigning the values to inputs using for loop and to be used in the stalagmite function .

Getting values of stalagmite to the variable f.

Applying Genetic algorithm on stalagmite function.

Assigning the Genetic algoritm values to inputs, and then assigning to xopt,yopt ,foptusing for loop.

Three studies are made to get the optimised results.in the first study bounds are not defined. In the second study boundaries are defined. In the third study population size is defined.

Used tic and toc commands to know the time taken for each case.

creating surface using surf command among xx,yy,f ,using plot3 command to plot xopt,yopy,fopt. Plot fopt to show the optimized point.

unbounded inputs: (plots for case-1)

bounded inputs:(plots for case-2)

increasing population:(plots for case-3)

results shown in command window:

Stopping criteria:

1. The iterations stops when the iteration limit is reached.

2. When it is known that there won't be any change in the result for the iteration .

3. When the population limit is reached.

Results:

The Genetic Algorithm is implemented on stalagmite function for optimization and to get global maxima.

And Required graphs are plotted.