Week 4.1 - Genetic Algorithm

Objective : -

To study of optimizing the stalagmite function and find the global maxima of the function by using genetic algorithm in matlab.

Theory-preparation :-

• A stalagmite is an upward-growing mound of mineral deposits that have precipitated from water dripping onto the floor of a cave. Most stalagmites have rounded or flattened tips.

• A stalagmite function refers to function with which are over a stalagmite kind of surface for find out the local and the global minima of that function.

• In this matlab using a method called 'Optimization'.It is a program which select the best element from theset of population.

• Optimization is done by systematically choosing input values within an allowed set and computing the results of the function.

• In matlab to study optimization by using genetic algorithm method which is a inbuild function in matlab to find the global maxima of that given stalagmite function.

Genetic Algorithm :-

• The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions.

There are 5 steps in Genetic Algorithm such as :-

Diagram of Genetic Algorithm steps :-

• Initial population:-

• Every generation represents a parameter (variables) in the solution. This collection of parameters that forms the solution is the chromosome. Therefore, the population is a collection of chromosomes.

• Order of generations on the chromosome matters.

• Chromosomes are often depicted in binary as 0’s and 1’s, but other encodings are also possible.

• Fitness function :-

• We have to select the best ones to reproduce offspring out of the available chromosomes, so each chromosome is given a fitness value.

• The fitness score helps to select the individuals who will be used for reproduction.

• Selection :-

• The purpose of the selection phase is select the fittest individuals and let them pass thrie generations to the next generations.

• Two pairs of individuals (parents) are selected based on their fittness score.

• Crossover :-

• Crossover is the most vital stage in the genetic algorithm. During crossover, a random point is selected while mating a pair of parents to generate offsprings.

• The new offspring are added to the population.

• Mutations :-

• In a few new offspring formed, some of their genes can be subjected to a low random probability mutation. This indicates that some of the bits in the bit chromosome can be flipped. Mutation happens to take care of diversity among the population and stop premature convergence.

• This is how the population set for the process calculated, with all the steps the genetic algorithm finds the population for each iteration and execute the algorithm untill the condition find to the best optimum value get satisfied.

• Here to find the stalagmite functions global maxima in matlab. Here is inbuild function to perform all these values with a command called 'ga'.By selecting the initial population then performing all the ga tasks.

Syntax for 'ga' :-

fun - Objective function

nvars - number of variables

A - Linear inequality constraints, specified as a real matrix.

B - Linear inequality constraints, specified as a real vector.

Aeq - Linear equality constraints, specified as a real matrix.Aeq is an Me-by-nvars matrix,where Me is the number of equalities.

Beq - Linear equality constraints, specified as a real vector. Beq is an Me- element vector related to the Aeq matrix.

lb - lower bounds

ub - Upper bounds

nonicon - Nonlinear constrains, specified as a funtion handle or function name.

options - Optimization options,specified as the output of optimoptions or a structure.

• The 'ga' command in matlab can only find the maxima global points. So to find the maxima points we have to change the function '-ve' so that it cab be find the global maxima for the same function.

• The 'ga' command in matlab selects the random values to start the algorithm,with that it will go on doing the algorithm untill it satisfied the condition in the forloop and comes to stops.

• However to find the global maxima that is the optimum values for the given stalagmite function we need to alter the program as the optimizations begins with the random ste of values for doing the algorithm,it is not find the best optimum points for that we have to change syntax little bit so we can get the optimum point.

Matlab program for global maxima by using Genetic Algorithm :-

% close all
% clear all
% clc

% defining search input
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

% creating 2 dimentional array
[xx,yy] = meshgrid(x,y);
num_cases = 50;

% evaluate the stalagmite function

for i = 1:length(x)
    for j = 1:length(y)
        input_vector(1) = xx(i,j);
        input_vector(2) = yy(i,j);
        
        f(i,j) = stalagmite_func(input_vector);
    end
   
end

% study 1(Unbounded condition)

tic
for i = 1:num_cases
    [results,fopt(i)] = ga(@stalagmite_func,2);
    xopt(i) = results(1);
    yopt(i) = results(2);
end

study1_time_1 = toc

% plotting the optimization of stalagmite function

figure(1)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',3,'markerfacecolor','r')
title('stalagmite function unbounded')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function minimum')

% case study 2 (bounded condition)

tic
for i = 1:num_cases
    [results,fopt(i)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i) = results(1);
    yopt(i) = results(2);
end

study2_time_2 = toc

% plotting the optimization of stalagmite function

figure(2)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',3,'markerfacecolor','r')
title('stalagmite function bounded')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function minimum')

% case study 3 (increase initial population for 'ga' )

tic

options = optimoptions('ga');
options = optimoptions(options,'populationsize',300);

for i = 1:num_cases
    
    [results,fopt(i)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.6,0.6],[],[],options)
    xopt(i) = results(1);
    yopt(i) = results(2);
end

study3_time_3 = toc

% plotting the optimization function of stalagmite with increase population

figure(3)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',3,'markerfacecolor','r')
title('stalagmite function with increasing population')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function maxmima')

Program Screen shot :-

Coding for function :-

function [stalagmite] = stalagmite_func(input_vector)

x = input_vector(1);
y = input_vector(2);

f1_x = (sin(5.1*pi *x+0.5)).^6;
f1_y = (sin(5.1*pi *y+0.5)).^6;

f2_x = exp((-4*0.6931).*(x-0.0667)^2/(0.64));
f2_y = exp((-4*0.6931).*(y-0.0667)^2/(0.64));

stalagmite = -(f1_x.*f2_x.*f1_y.*f2_y)
end

Program screen shot : -

Step-wise explaination :-

• First of all giving the all input data for x and y.
• Next is 0 to 0.6 with linear space between x and y by 'linspace' command.
• Next is giving number of iteration as 50(num_cases).
• By the using of meshgrid command to create a 2 dimensional array from 1 dimensional array and get 3 dimentional points.
• Next is generate the co-ordinates points for the stalagmite surface need to give the three co-ordinates point in(x,y,z)axis. For doing this giving x and y values into the given stalagmite function using forloop to get z co-ordinate values as the output through a different function.

Given stalagmite function :-

• Next finding the 'Optimization' for the generated values using 'Genetic Algorithm' in matlab. It is done by the 'ga' command to execute the algorithm.
• Using the forloop can execute the algorithm for the stalagmite function untill all the iteration will satisfied, after all the iteration the algorithm stop running the program and will give the global maxima.
• By using 'plot3' command ploting the stalagmite function to create stalagmite surface for visualize the performance of algorithm.
• Since the (ga) execution with random values for the initial population, the optimum values for the function went outside .
• For improving the accuracy of the optimization process did another case study (2) where giving upper and lower bounds in the syntax of 'ga' as 0 to 0.6 .
• Now the plotting is done as before check the accuracy of the algorithm and to get the results of the global maxima, but this time also some deviation at four iterations where the global maxima is found with some variations.
• For this did another case study and increase the population to get high accuracy of the genetic algorithm to predict the global maximum.
• Finally the optimization process resulted in finding the global maxima of the given function.

Result of optimization Case study 1 (Unbounded) :-

In this case study 'ga' is executed with random population values, hence failed to find global maxima.And x and y values are went outside of the stalagmite surface.

Result of optimization Case study 2 (bounded) :-

In this study also intiated 'ga' with random population but specified upper and lower bound in the syntax.

though it was within function limits so it could not predict the exact global maxima, so need to another study for get final global maxima.

Result of optimization Case study 3 (increasing the population for 'ga') :-

Finally the optimization is done for the given stalagmite function to find the global maxima of the function using the method of 'genetic algorothm' using matlab.

Errors while programming :-

• While Function name type stalagmite instead of stalagmite_func occured error.

screen-shot of error :-

Solution :- Type the same name which the function name is saved in program.