Week 4.1 - Genetic Algorithm

Finding global maxima for stalagmite function using Genetic Algorithm

A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution.

Five phases in a genetic algorithm are

Initial population, Fitness function, Selection, Crossover, Mutation

• 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 (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).

• Fitness Function

The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). 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 generation. Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance 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 from within 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.

GA Syntax:

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

where: fun = Function which we are optimizing,

nvars = number of design variables,

A, b = subject to the linear inequalities A*x ≤ b,

Aeq, beq = subject to the linear equalities Aeq*x = beq,

lb, ub = lower and upper bounds on the design variables,

nonlcon = subjects the minimization to the constraints defined in nonlcon, for nonlinear constraintsGA

options = minimizes with the default optimization parameters replaced by values in options

[input,fval(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);

we are using above syntax for ga due to we don’t have any linear and non-linear inequalities. So these are represent by [].

[x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.

Program for Global Maxima of stalagmite function using genetic algorithm

First we generate 150 values between 0 to 0.6 for x and y using linspace command, using meshgrid command with x and y we create 2D array. Using nested loop we assign xx and yy value to input vector which is input to stalagmite function. We consider 50 cases or iteration for GA. In first case only function and number of design variables is given that’s why we are getting results which are out of the function boundaries. To solve this in second problem we add bounds so that generated results are with in function boundaries. Still we are getting multiple results. So we increase initial population size to get more accurate results. In last case we get the desired result.

clear all
close all
clc
 
%Defining our Search space 
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50;
 
%Creating 2D Mesh
[xx yy] = meshgrid(x,y);
 
% Evaluating the stlagmite 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(input_vector);
    end
end
 
%Case 1 Unbounded Inputs
tic
for i=1:num_cases
[input,fval(i)]=ga(@stalagmite,2);
x_out(i)=input(1);
y_out(i)=input(2);
end
case_1_time=toc
 
figure(1)
subplot(2,1,1)
hold on;
surfc(xx,yy,f)
xlabel('x axis')
ylabel('y axis')
title('Unbounded Input','color','k')
shading interp
plot3(x_out,y_out,fval,'marker','o','markersize',6,'markerfacecolor','r');
 
subplot(2,1,2)
plot(fval);
xlabel('No of Iterations')
ylabel('value of function')
 
%Case:2 Inserting Bounding Box
 tic
for i=1:num_cases
[input,fval(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
x_out(i)=input(1);
y_out(i)=input(2);
end
case_2_time=toc
figure(2);
subplot(2,1,1)
hold on;
surfc(xx,yy,f)
xlabel('x axis')
ylabel('y axis')
title('case 2','color','k')
shading interp
plot3(x_out,y_out,fval,'marker','o','markersize',6,'markerfacecolor','r');
subplot(2,1,2)
plot(fval)
xlabel('No Of Iterations')
ylabel('value of function')
 
%Case:3 Increasing population size to 100
options=optimoptions('ga');
options=optimoptions(options,'populationsize',100)
 
 tic
for i=1:num_cases
[input,fval(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
x_out(i)=input(1);
y_out(i)=input(2);
end
case_3_time=toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
xlabel('x axis');
ylabel('y axis');
title('Case 3','color','k')
plot3(x_out,y_out,fval,'marker','o','markersize',6,'markerfacecolor','r')
subplot(2,1,2)
plot(fval)
xlabel('No Of Iterations')
ylabel('value of function')
 
%Case:4 Increasing population size to 200
options=optimoptions('ga');
options=optimoptions(options,'populationsize',200)
 
 tic
for i=1:num_cases
[input,fval(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
x_out(i)=input(1);
y_out(i)=input(2);
end
case_4_time=toc
figure(4)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
xlabel('x axis');
ylabel('y axis');
title('Case 4','color','k')
plot3(x_out,y_out,fval,'marker','o','markersize',6,'markerfacecolor','r')
subplot(2,1,2)
plot(fval)
xlabel('No Of Iterations')
ylabel('value of function')

%Maxima
display(input)

Stalagmite function

To get Maxima value - sign is given to function f1

GA is use to optimize the function means it finds minima of function

function [f] = stalagmite(input_vector)
f1x = ((sin(5.1*pi*input_vector(1) + 0.5)).^6);
f1y = ((sin(5.1*pi*input_vector(2) + 0.5)).^6);
 
term1 = ((input_vector(1)-0.0667).^2)/0.64 ;
term2 = ((input_vector(2)-0.0667).^2)/0.64 ;
 
f2x = exp(-4*log(2)*term1);
f2y = exp(-4*log(2)*term2);
 
f1 = f1x*f1y*f2x*f2y ;
f=-f1;
end

Outputs