Week 4.1 - Genetic Algorithm

Aim:-Write a code in MATLAB to optimize the stalagmite function and find the global maxima of the function.

Stalagmite function:-

What is GA?

genetic algorithm having two words first 'Genetic; means genes and genetic variation, the second term 'algorithm means sequence or order.

A Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. It is frequently used to find optimal or near-optimal solutions to difficult problems which otherwise would take a lifetime to solve.

In GAs, we have a pool or a population of possible solutions to the given problem. These solutions then undergo recombination and mutation (like in natural genetics), producing new children, and the process is repeated over various generations. Each individual (or candidate solution) is assigned a fitness value (based on its objective function 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”.

Basic Terminology

• Population − It is a subset of all the possible (encoded) solutions to the given problem.

• Chromosomes − A chromosome is one such solution to the given problem.

• Gene − A gene is one element position of a chromosome.

• Allele − It is the value a gene takes for a particular chromosome.

• Genotype − Genotype is the population in the computation space. In the computation space, the solutions are represented in a way that can be easily understood and manipulated using a computing system.

• Phenotype − Phenotype is the population in the actual real-world solution space in which solutions are represented in a way they are represented in real-world situations.

• Decoding and Encoding − Decoding is a process of transforming a solution from the genotype to the phenotype space, while encoding is a process of transforming from the phenotype to the genotype space.

• Fitness Function − A fitness function simply defined is a function that takes the solution as input and produces the suitability of the solution as the output. In some cases, the fitness function and the objective function may be the same, while in others it might be different based on the problem.

• Genetic Operators − These alter the genetic composition of the offspring. These include crossover, mutation, selection, etc.

Basic Structure:-

Mutation:-Mutation is the occasional introduction of new features into the solution strings of the population pool to maintain diversity in the population.

Crossover:-Combining of two different chromosomes to get the new off spring .

selection:- Selecting the best one.

GA Syntex:-

1. x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values.
3. [x,fval,exitflag,output,population,scores] = ga(___) also returns a matrix population, whose rows are the final population, and a vector scores, the scores of the final population.

Stalagmite function code: "INSERT SAMPLE CODE"

function A=stalagmite(input_vector) 

x=input_vector(1);
y=input_vector(2);
f1=(sin(5.1*pi*x+0.5))^6;    % subfunction 1
f2=(sin(5.1*pi*y+0.5))^6;    %sub function 2
f3=exp(-4*log(2)*(((x-0.0667).^2)/0.64)); %subfunction 3
f4=exp(-4*log(2)*(((y-0.0667).^2)/0.64)); % subfunction 4
A=-(f1*f2*f3*f4); % main function optimisation function
end

Main code"INSERT SAMPLE CODE"

clear all
close all
clc
x=linspace(0,0.6,150); %range of X
y=linspace(0,0.6,150); % range of Y
num_space=50;          % no of iteration 
%meshgrid
[xx,yy]=meshgrid(x,y); 
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(input_vector);    %input_vector @ stalagmite
    end   
end
%study 1- Iteration value is fixed without limit 
tic   % to record the time study -start

for i=1:num_space;          %iteration size
    [results,fopt(i)]=ga(@stalagmite,2);  % use of ga 
    xopt(i)=results(1);
    yopt(i)=results(2);
end
time_study1=toc % to record the time study -end
figure(1)
subplot(2,1,1)       % subplot use to add the mulipal fig in same window
surfc(x,y,f)
shading interp
xlabel('x')
ylabel('y')
title('Fig 1-Optimization_stalagmite')
hold on
plot3(xopt,yopt,fopt)
subplot(2,1,2) % subplot use to add the mulipal fig in same window
plot(fopt)

%study 2- with given upper and lower bound of an variable.
tic
lb=[0;0]   %lower bound           
ub=[0.6;0.6] %upper bound
for i=1:num_space;
    [results,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i)=results(1);
    yopt(i)=results(2);
end
time_study1=toc
figure(2)
subplot(2,1,1)
surfc(x,y,f)
shading interp
xlabel('x')
ylabel('y')
title('Fig 2-Optimization_stalagmite')
hold on
plot3(xopt,yopt,fopt)
subplot(2,1,2)
plot(fopt)
xlabel('iteration')
ylabel('fmax')

%study third with given upper bound , lower bound and poppulation size.
tic
options=optimoptions('ga') % used to assigen the solve 'ga'
options=optimoptions(options,'populationsize',300) % poppulation size
lb=[0;0]   %lower bound           
ub=[0.6;0.6] %upper bound
for i=1:num_space;
    [results,fopt(i)]=ga(@stalagmite,2,[],[],[],[],lb,ub,[],[],options)
    xopt(i)=results(1);
    yopt(i)=results(2);
end
time_study3=toc
figure(3)
subplot(2,1,1)
surfc(x,y,f)
shading interp
title('Fig 3-Optimization_stalagmite')
hold on
plot3(xopt,yopt,fopt)
subplot(2,1,2)
plot(fopt)
xlabel('iteration')
ylabel('fmax')

output:

time_study1 = 6.1744

time_study2 = 5.8657 % time study reduced due to fixing the boundary .

time_study3 = 23.4398 % tine study increases due to increase in poppulation size.

Error faced during coating:

1-The main error I was facing is not getting the correct plot.

I was not able to identify the error, after taking help from the technical support person i was able to identify the error.

The error was : in place of Input_vectro I typed Input_vectro

2- The second error I was getting in assigning the population command.

I took help from math work to solve the issue.

References:-

http://www.iitg.ac.in/rkbc/presentation/Genetic%20Algorithms.pdf

https://skill-lync.com/knowledgebase/genetic-algorithm-explained

https://in.mathworks.com/help/gads/ga.html#d123e39036

https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_introduction.htm