Optimisation by using Genetic Algorithm

Aim: Write a code in MATLAB to optimise the stalagmite function

Objective :

1. To write a code in MATLAB to optimise the stalagmite function
2. To find the global maxima of the function.

Therotical background:

A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

Notion of natural selection

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 parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.

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

Five phases are considered in a genetic algorithm.

1. Initial population
2. Fitness function
3. Selection
4. Crossover
5. Mutation

1. 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).

2. 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.

3. 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.

4. 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. Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached

5. 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.

6. Termination

The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). Then it is said that the genetic algorithm has provided a set of solutions to our problem.

Flowchart:

How the genetic algorithm works

The following outline summarizes how the genetic algorithm works:

1. The algorithm begins by creating a random initial population.
2. The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population. To create the new population, the algorithm performs the following steps:
1. Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
2. Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
3. Selects members, called parents, based on their expectation.
4. Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.
5. Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.
6. Replaces the current population with the children to form the next generation.

3. The algorithm stops when one of the stopping criteria is met.

MAIN PROGRAM:

clear all 
close all 
clc

%defining our search place

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[xx yy] = meshgrid(x,y);
%creating 2dimensional mesh


%evaluating 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_func(input_vector);
    end 
end

surface(xx,yy,-f)
shading interp
[input,func] = ga(@stalagmite_func,2)
xlabel('x value')
ylabel('y value')
zlabel('z axis')
colorbar
num_cases = 50

%time to study how long it takes 
tic
%study 1- satistical behavior
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite_func,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study_1time = toc
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
xlabel('x axis')
ylabel('y axis')
zlabel('z axis')
colorbar
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function maximum')

tic
%study 2- satistical behavior with upper and lower bounds
for i = 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.1;0.1]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study_2time = toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
xlabel('x axis')
ylabel('y axis')

colorbar
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function maximum')

%study 3- increasing GA iterations

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

tic

for i = 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.1;0.1],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study_3time = toc
figure(4)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
xlabel('x axis')
ylabel('y axis')
colorbar
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs with modified population size')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function maximum')

Explanation:

1. First we have cleared and closed all files and workspace.
2. We have defined input vector by using ‘linspace ‘command.
3. We have created two dimensional array by using mesh grid command.
4. We have used for loop to get function by using each value of array.
5. We made surface plot with the help of two dimensional array and function as we have taken negative of function to get maxima.
6. We used ‘shading interp’ command to get smooth plot so that we can understand it better.
7. Then we have used in-built genetic algorithm function (ga) to get maxima.
8. As we know ga function always minimizes the function but we have modified the function in way so that we can get maxima.
9. We have labeled surface plot by using some command.
10. We also used a ‘colorbar’ command that displays the current colormap along with numerical rulings so that the color scale can be interpreted.

11. We have set our number of cases (iterations) to 50
12. We have performed study_1 and to calculate the time study_1 required we have used tic-toc command.
13. We have again used for loop which will run 50 times , and each it will save the output of ‘ga’ function
14. We have created the new figure window and used ‘subplot’ command to plot more than one plot in single figure window.
15. We made surface plot first then made a plot of negative of function value while doing that we used plot3 command to get 3-d plot .
16. In this way we have performed study_1 and similarly we performed the study_2 which bound our study to certain range , where we have used different syntax of ‘ga’ function.
17. Still the result we are getting , we are not satisfied with that so we increased the population size to 150 and performed study_3.
18. And for each study we have used tic toc command to calculate time study takes to complete.

function [F] = stalagmite_func(input_vector)
 x = input_vector(1);
 y = input_vector(2);
P = (sin((5.1*pi.*x)+0.5)).^6;
Q = (sin((5.1*pi.*y)+0.5)).^6;
R = (exp(-4*log(2)*((x-0.0667).^2)/0.64));
S = (exp(-4*log(2)*((y-0.0667).^2)/0.64));
F = -(P.*Q.*R.*S);

end

Explanation:

1. In this code we have written code for stalagmite function.
2. First,we defined the function and the input that function required.
3. we also defined some term that are P,Q,R,S and f in the body of function.
4. close the for loop with end key-word.

Result:

1] unbounded study

2] bounded study

3] bounded with increased population size

Conclusion: We have understood the genetic algorithm to perform optimazation problem.

Result: Optimization problem is solved using genetic algorithm successfully.