Week 4.1 - Genetic Algorithm

Object:

• Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.
• Clearly expalin 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 times.
• Plot graphs for all 3 studies and for F maximum vs no. of iterations. Title and axes labels are a must, legends could be shown if necessary.

Code:

clear all
close all
clc

%Defing our search space 
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_cases=50;

%creating a 2D mesh
[xx yy]=meshgrid(x,y);

%creating 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);
        f(i,j)=stalagmite_fun(input_vector);
    end
end

%case1
%unbounded
tic

for i=1:num_cases
    [input, fval(i)]= ga(@stalagmite_fun,2);
    x_out(i)=input(1);
    y_out(i)=input(2);
end
study1_time=toc

figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('x')
ylabel('y')
title('unbounded input','color','k')
shading interp
hold on;
plot3(x_out,y_out,-fval,'marker','O','markersize',5,'MarkerfaceColor','r')
subplot(2,1,2)
plot(-fval);
xlabel('No of Iteration')
ylabel('Max function')


%case2
%bounded

tic 

for i=1:num_cases
    [input, fval(i)]=ga(@stalagmite_fun,2,[],[],[],[],[0,0],[0.6;0.6]);
    x_out(i)=input(1);
    y_out(i)=input(2);
end

study2_time=toc
figure(2);
subplot(2,1,1)
hold on;
surfc(xx,yy,-f)
xlabel('x')
ylabel('y')
title('bounded','color','k')
shading interp
plot3(x_out,y_out,-fval,'marker','O','markersize',5,'MarkerfaceColor','r')
subplot(2,1,2)
plot(-fval);
xlabel('No of Iteration')
ylabel('Max function')


%case3
%increased initial population
options=optimoptions('ga');
options=optimoptions(options,'PopulationSize',170);
tic 

for i=1:num_cases
    [input, fval(i)]=ga(@stalagmite_fun,2,[],[],[],[],[0,0],[0.6;0.6],[],[],options);
    x_out(i)=input(1);
    y_out(i)=input(2);
end

study3_time=toc
figure(3);
subplot(2,1,1)
hold on;
surfc(xx,yy,-f)
xlabel('x')
ylabel('y')
title('bounded with increased population size','color','k')
shading interp
plot3(x_out,y_out,-fval,'marker','O','markersize',5,'MarkerfaceColor','r')
subplot(2,1,2)
plot(-fval);
xlabel('No of Iteration')
ylabel('Max function')

stalagmite function:

function [f]= stalagmite_fun(input_vector)

f1x=(sin((5.1*pi).*input_vector(1)+0.5))^6;
f1y=(sin((5.1*pi).*input_vector(2)+0.5))^6;

f2x=exp(((input_vector(1)-0.0667).^2/0.64).*(-4*log(2)));
f2y=exp(((input_vector(2)-0.0667).^2/0.64).*(-4*log(2)));
f1=f1x*f1y*f2x*f2y;
f=-f1;
end

Concept of Stalagmite and Genetic Algoritham:

Stalagmite:

A stalagmite function generally refers to the function with which we are generating values over a stalagmite kind of surface for finding out the local and global maxima and minima of that particular given function.

The stalagmite function is defined below

Genetic Algorithms:

Genetic Algorithms are search based algorithms based on the concepts of natural selection and genetics. Genetic Algorithms is a subset of a much larger branch of computation know as Evolutionary Computation.

In Genetic Algorithms we have a pool or a population of possible solutions to the given problem. this solution then undergoes recombination 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 Darwinian theory of “survival of the Fittest”.

In this way we keep evolving better individuals or solutions over generations till we reach a stopping criterion

Genetic Algorithms are sufficiently randomized in natural, but they perform much better then random local search, as they exploit historical information as well.

The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parent’s have better fitness, their offspring will be better than parents and have a better chance at surviving. The process keeps on iterating and at the end, a generation with the fittest individuals will be found.

This notion can be applied foe a search problem. We consider a set of solution for a problem and select the set of best ones out of them.

Five phases are considered in genetic algorithm.

They are: -

Initial population:

The process begins with a set of individuals which is called a population. Each individual is a solution to the problem you want to solve.

An individual is characterized by a set of parameters known as Genes. Genes are joined into a string to a form a Chromosome.

In a genetic algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, binary values are used, we say that we encode the genes in a chromosome.

Fitness Function:

The Fitness Function determines how fit an individual. It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.

Selection:

The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generations.

Two pairs of individuals are selected based on their fitness scores. Individuals with fitness have more chances to be selected for reproduction.

Crossover

Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random form with in the genes.

Mutation

In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.

Mutation occurs to maintain diversity within the population and prevent premature convergence.

Stopping Criteria:

Generation: The algorithm stops when the numbers of generations reach the values of Generations.

Time limits: The algorithm stops after running for an amount of time in seconds equal to time limits.

Fitness limit: The algorithm stops when the values of the fitness function for the best point in the current population is less than or equal to fitness limit.

Syntex

X=ga(fun,nvars)

X=ga(fun,nvars,A,b)

X=ga(fun,nvarsA,b,Aeq,beq)

X=ga(fun,nvarsA,b,Aeq,beq,lb,ub)

X=ga(fun,nvarsA,b,Aeq,beq,lb,ub,nonlcon)

X=ga(fun,nvarsA,b,Aeq,beq,lb,ub,nonlcon,options)

X=ga(fun,nvarsA,b,Aeq,beq,lb,ub,nonlcon,intcon)

X=ga(fun,nvarsA,b,Aeq,beq,lb,ub,nonlcon,intcon,options)

X=ga(problem)

[x,fval]=ga (__)

[x,fval,exitflag,output]=ga (__)

[x,fval,exitflag,output,population,scores]=ga (__)

ga- Find minimum of function using genetic algorithm

X=ga(fun,nvars,A,b,Aeq,beq,ub,nonlcon,option)

fun- function to be optimized

nvars- the dimensions (number of design variables) of fun.

A,b- linear inequalities

Aeq,beq- linear inequalities

Lb,ub- lower and upper bounds on the design variables

nonlcon- constraints

option- to change the default parameters of ga

Explanation:

First, we initialize the values of x and y taking 150 values between the interval 0 and 0.6

We consider no of iteration num_cases=50

Since we need to plot a 3D surface plot, we take the 2D array of x and y using meshgrid command and store them in input vector array, so that it can be used as an argument to all the function stalagmite.

We create another function file for the stalagmite function. Here we take the output as –f since ga only minimizes a given function. So, if –f is considered it automatically given us the maxima.

First case

We take no of iteration=num_cases and we use the genetic algorithm function to calculate the maxima of the function. We store the output into results which contain Maximas and fval, which contain the value at which the maxima are obtained.

Now we store the results into xopt, yopt. Now we need to plot the surface of x, y, -f to get the 3D plot.

We use the plot3 command to make a plot of xopt, yopt and –fval to plot the optimum Maximas

Also let us plot the –fval function so that we can visualize the optimum values at each iteration.

To get the time taken to complete cycle we used the tic toc command to record the time.

Second case

Let us specify the lower and upper bounded of x and y in this case, the ga is initiated with random population only.

Now we store the results into xopt, yopt. Now we need to plot the surface of x, y, -f to get the 3D plot.

We use the plot3 command to make a plot of xopt, yopt and –fval to plot the optimum Maximas

Also let us plot the –fval function so that we can visualize the optimum values at each iteration.

To get the time taken to complete cycle we used the tic toc command to record the time.

Third case

In this case let us increase our initial population which is default as 50 to 170.

Here in this case to set an initial population we to use command called optimumoptions and get our value of ‘populationsize’ to 170

Now we store the results into xopt, yopt. Now we need to plot the surface of x, y, -f to get the 3D plot.

We use the plot3 command to make a plot of xopt, yopt and –fval to plot the optimum Maximas

Also let us plot the –fval function so that we can visualize the optimum values at each iteration.

To get the time taken to complete cycle we used the tic toc command to record the time.

OUTPUT:

case 1:

Here we can see the optimal values went outside the values of x and y resulting in falling away from stalagmite surface.

The study time=3.1833

study1_time:

case 2:

Though the optimum values are within the limits it could not give us the exact maxima values.

The study time = 3.6499 which is more than above study.

study2_time:

case 3:

Though the time of execution is more I this case we are successful to find the out the correct maxima for the stalagmite function.

So, by increasing the initial population size of the ga wen increase the accuracy of the algorithm.

The study time = 9.0802 which is more than above two studies.

study3_time:

values of x and y for maximun values of function

I didn't get any error in program, when I run the program not faceing the any type of error in the command window.