Week 4 - Genetic Algorithm

WEEK 4- Genetic Algorithm

Aim:

• 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 and explain the syntax for ga in MATLAB.
• 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. Results should remain constant after different run

Objectives:

• Explain about optimisation and different methods of optimisation
• Explain Gentic algorithm and its use in optimisaton of stalagmite function
• Produce a set of values of 2D matrix using meshgrid command
• Obtain the global maxima using genetic algorithm optimistaion techique and plot the graph
• Characteristics of ga function and the requirement of bounded inputs
• Obtain the global maxima of the 2D matrix in a bounded limit and plot the graph for the same
• Explain the dependecy of population function on genetic algorithm and use of optimoption functions
• Obtain the global maxima of the 2D matrix in a bounded limit with increased population number and plot the graph
• Compare the results of the three plot and explain.

Optimistaion Technique:

Selection of a best element (with regard to some criterion) from some set of available alternatives.Optimisation problem consist of maximising or minimising a real function by systematically choosing input values from within an allowed set and computuing the value of function.More generally, optimization includes finding "best available" values of some objective function given a defined domain (or input), including a variety of different types of objective functions and different types of domains.

Besides various methods(converging iterative and finite algorithm method) to find the maximum or minimum of the given functions there are certain heuristis method to optimise the function. They are

• Memetic algorithm
• Differential evolution
• Evolutionary algorithms
• Dynamic relaxation
• Genetic algorithms
• Hill climbing with random restart
• Nelder-Mead simplicial heuristic: A popular heuristic for approximate minimization (without calling gradients)
• Particle swarm optimization
• Cuckoo search
• Gravitational search algorithm
• Artificial bee colony optimization
• Simulated annealing
• Stochastic tunneling
• Tabu search

The main disadvantage of such algorithms/ heuristics are that the method doesnot guarantee to find the results. But they are used in practical cases.

Genetic Algorithm

A genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection. This algorithm is based on the concept of Darwins theory of evolution.

Main steps follwed for genetic algorithm are

1.Population Initialization- Initialising a population from which a optimisig of values is done.

There are two primary methods to initialize a population in a GA. They are −

• Random Initialization − Populate the initial population with completely random solutions.
• Heuristic initialization − Populate the initial population using a known heuristic for the problem.

It has been observed that the entire population should not be initialized using a heuristic, as it can result in the population having similar solutions and very little diversity. It has been experimentally observed that the random solutions are the ones to drive the population to optimality. Therefore, with heuristic initialization, we just seed the population with a couple of good solutions, filling up the rest with random solutions rather than filling the entire population with heuristic based solutions. In our opeation make use of random initialisation and in the third case we use heuristic initalisation.

2. Fitness Function: The fitness function simply defined is a function which takes a candidate solution to the problem as input and produces as output how “fit” our how “good” the solution is with respect to the problem in consideration.

Calculation of fitness value is done repeatedly in a GA and therefore it should be sufficiently fast. A slow computation of the fitness value can adversely affect a GA and make it exceptionally slow.

In most cases the fitness function and the objective function are the same as the objective is to either maximize or minimize the given objective function. However, for more complex problems with multiple objectives and constraints, an Algorithm Designer might choose to have a different fitness function.

The fitness function should be sufficiently fast to compute.It must quantitatively measure how fit a given solution is or how fit individuals can be produced from the given solution.

In our case the fitness function we use is the stalagmite function

where the fitness function f(x,y)=(-(f1,x)*(f2,x)*(f1,y)*(f2,y)

Function to call the stalagmite function

function[f]= stalagmite(input_vector)
  fx=(sin(5.1*pi*input_vector(1)+0.5))^6;
  fy=(sin(5.1*pi*input_vector(2)+0.5))^6;

  fxx=exp((-4*log(2)*(((input_vector(1)-0.0667)^2)/0.64)));
  fyy=exp(-4*log(2)*(((input_vector(2)-0.0667)^2)/0.64));
  
  f=-(fx*fy*fxx*fyy);
end

Program to optimise of a set of values using ga solver

close all
clear all
clc

num_cases=150;
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[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);
  end
end

tic
for i=1:num_cases
 [inputs,fopt(i)]= ga(@stalagmite,2);
  xopt(i)=inputs(1);
  yopt(i)=inputs(2);
end
fopt=-fopt;
time_study1=toc




figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbound inputs')
%figure(2)
subplot(2,1,2)
plot(fopt)
xlabel('Iteration')
ylabel('Function minimum')













%study2



tic
for i=1:num_cases
 [inputs2,fopt2(i)]= ga(@stalagmite,2,[],[],[],[],[0,0],[1,1]);
  xopt2(i)=inputs2(1);
  yopt2(i)=inputs2(2);
end
fopt2=-fopt2;
time_study2=toc

figure(2)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt2,yopt2,fopt2,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
%figure(2)
subplot(2,1,2)
plot(fopt2)
xlabel('Iteration')
ylabel('Function minimum')




%Case_study 3: MAximising the population size to optimise the result


options= optimoptions ('ga');
options=optimoptions(options,'PopulationSize',250);

tic
for i=1:num_cases
  [inputs3, fopt3(i)]=ga(@stalagmite,2,[],[],[],[],[0,0],[1,1],[],[],options);
  xopt3(i)=inputs3(1);
  yopt3(i)=inputs3(2);
end
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt3,yopt3,fopt3,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with optioptims function')
subplot(2,1,2)
plot(-fopt3)
xlabel('Iteration')
ylabel('Function minimum')

time_study3=toc
rng('default');

3.

• Produce a set of values of 2D matrix using meshgrid command

We have created two arraies x and y. Values od each array varies from 0 to 0.6 divided into 150 values. The values thus obtained are meshed into a 2 dimensional array using meshgrid command.

x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[xx yy]=meshgrid(x,y);

We have two loops of the length of rrays xx and yy. During each loop value of the 2D array is saved into a temporary filename input_vector. The values are then passed on to the stalagmite function which is the required fitness function. Retured value of the stalagmite function indicate the fitness value. The values ae stored into an array name f.

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

• Obtain the global maxima using genetic algorithm optimistaion techique and plot the graph.

Created a for loop and length of the iteration is limited to 150 cases. The Value of the stalagmite function is passed into an inbuilt solver named 'ga' which calculated te optimised values. The optimised values are stored into varables xopt,yopt,fopt which stores the positionof x,y and the optimised value itself respectively.

for i=1:num_cases
[inputs,fopt(i)]= ga(@stalagmite,2);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end

Since the inbuilt solver ga calculate the global minima and we are asked to find the global maxima. Hence we multiply the values with -1.
fopt=-fopt;

Total time taken for the unbounded iteration is calculated in the array name time_study1.
time_study1=toc

The optimised function and the position of the function is calculated. The optimised function is plotted using surfc command and plot3 command. The figur

figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r') is given the name figure(1) with title'Unbounded inputs'.

title('Unbound inputs')

From the graph it is clearly understood that an optimised value is not obtained in the first case.

• Obtain the global maxima of the 2D matrix in a bounded limit and plot the graph for the same

The results are varying and doesnot yield a optimised value. Hence the ga function needed to be producing values within a bounded area which is done in study 2

Syntax for the ga function is [x fval] = ga(fun,nvars,A,b,Aeq,beq,lb,ub) where

x is the input values at which optimised values are obtained

fval is the optimised value.

fun is the fitness function

nvars is the number of variables

finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. Since our program contains no inequalities Set A=[] and b=[] )

Set Aeq=[] and beq=[] since no linear equalities exist

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

Similar to the stuy 1 we have initialsed a for loop for a length of the order of num_cases=150. Contrary to study 1 we have initialised ga funnction with lower and upper bound values of [0,0] and [1,1] respectively.

for i=1:num_cases
[inputs2,fopt2(i)]= ga(@stalagmite,2,[],[],[],[],[0,0],[1,1]);
xopt2(i)=inputs2(1);
yopt2(i)=inputs2(2);
end
fopt2=-fopt2;
time_study2=toc

figure(2)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt2,yopt2,fopt2,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')

plot(fopt2)
xlabel('Iteration')
ylabel('Function minimum')

On plotting the graph of function minimum vs number of iteration gives a fluctuating graph. The fluctuatons obtained is within the mesh grid limit of xx and yy. Thus a more bounded optimised function is obtained. But the global maxima continued to be varying. Hence a improved method is required.

• Obtain the global maxima of the 2D matrix in a bounded limit and plot the graph for the same with increased populatio size

The population size in the function is determine. A function called optimoptions is used to optimise the given stalagmite function. Thepopulation size is inputted as 250.
options= optimoptions ('ga');
options=optimoptions(options,'PopulationSize',250);

The syntax for ga algorithm is

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

• fitnessfcn - Fitness functions
• nvars -Number of design variables
• Aineq - A matrix for linear inequality constraints
• Bineq - b vector for linear inequality constraints
• Aeq - Aeq matrix for linear equality constraints
• Beq- beq vector for linear equality constraints
• lb -Lower bound on x
• ub -Upper bound on x
• nonlcon- Nonlinear constraint function
• solver used -'ga'
• options- Options created using optimoptions or exported from the Optimization app

The optimised function is obtained using new improved syntax. The system uses another variable names optons thereby calling the optimoptions command.

for i=1:num_cases
[inputs3, fopt3(i)]=ga(@stalagmite,2,[],[],[],[],[0,0],[1,1],[],[],options);
xopt3(i)=inputs3(1);
yopt3(i)=inputs3(2);
end

On running the improved comand the outputs were obtained on a plot named figure 3.
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt3,yopt3,fopt3,'marker','o','markersize',5,'markerfacecolor','r')
title('Bound inputs with increased population')
subplot(2,1,2)
plot(-fopt3)
xlabel('Iteration')
ylabel('Function minimum')

time_study3=toc
rng('default');

The results obtained on the plot shows the optimisation function optimoptions has optimised the function with an increased population size of 250.

Thus optimised value is obtained at input value[0.0668,0.0668]

Errors obtained

• Programming was done vigorosly on OCTAVE package but results were not obtained. Optimoption functions is not available in Octave. Optimset function are available in Octave but the results are poor. After meeting with the support system it was understood ga functio in octave is not upto the mark and Matlab is required.

Conclusion

We have done 3 case studies for finding the maima of a given function named stalagmite function. A solver named ga has been used to optimise the function. The ga function cn be used with a variety of syntax to provide required conditions. Without any bounded conditions,ga solver doesnot provided the global maxima. Hence bounded conditions are provided in study 2. Even then the results are obtained within a bound. Aim of the experiment is to find the globl maxima. o optain that we increased the population function using optimoption parameters. using optimoption functions our results are converged and global maximum is obtained. Hence we identified genetic algorithm with specified conditions can provide the optimised values of the functions