Week 4 - Genetic Algorithm using MATLAB

Aim:

To write code using MATLAB and optimize stalagmite function and to figure out global maxima of the function.

Objective:

1. To write code to define the stalagmite function
2. write program to find the optimum valu of the stalagmite function through:

1. Statistical behaviour method.
2. Statistical behaviour with bounds method.
3. Statistical behaviour with bounds and population size method.

Theory:

Genetic algorithm is a search algorithm which is based on natural selection and natural genetics. It basically based on the concept of "survival of fittest"(Darwinian Theory), i.e the fittest one survives among the all in that generation. It is generally used to find the true or appropriate solution to optimization and search problem.

This technique is inspired by evolutionary biologies such as inheritance, mutation, crossover and selection. In each generation, the fitness of each individual is evaluated, multiple individuals are selected from the current population and modified to form a new population. This new population is used in the next iteration and this algorithm terminates when satisfied fitness is generated.

This following diagram depicts the steps performed by a Genetic Algorithm:

Real world applications of GAs include automotive design, computer gaming, robotics, investments, traffic/shipment routing and more.

Why GA?

Geometric algorithms give global maxima or global minimum (i.e global optimum solution) irrespective of the start of the function or region of function. The primary goal of optimization is an improvement.

The below figure demonstrates the difference between traditional optimization and genetic algorithm.

GA Operators:

Basically, there are three types of operators

1. Method of representation

The common representation methods are

• Binary strings
• Array of integers
• An array of letters.....etc

2. Method of selection

There are many different strategies to select the individuals to be copied over into the next generation

• Roulette Wheel Selection: Conceptually, this can be represented as a game of roulette -each individual gets a slice of the wheel, but more fit ones get larger slices than less fit ones.
• Elitist Selection: Chose only the fittest one in the generation.
• Cut off Selection: chose only that is above the certain cut-off for the target function.

3. Method of Reproduction

These two are primary methods

• Cross over:

Two parents produce two offsprings. So, it has two options.

(1). chromosomes are copied to the next generation

(2). The two parents randomly recombined(crossed over) and form new offspring.

• Mutation: Permanent alternation takes place, i.e it alters the properties of chromosomes.

GA Syntax:

x = ga(func,nvars,A,B,Aeq,Beq,lb,ub,nonlcon,intcon,options)

• nvars is the dimension (number of design variables) of function.

• A, B - linear inequalities A*x<= B. ga evaluates the matrix product A*x as if x is transposed (A*x').

• intcon- it takes integer variables.

Step wise Explaination of code:

1) Start the program with 'clear all','close all', and 'clc' commands

2) First, we have to write a program for the Stalagmite function. Solving the Genetic algorithm for stalagmite function gives us a minimum value of the function. To find the maximum value of the function, we need to change the sign of function, so that it will give value for the reverse case of minima, i.e. maxima.

3) Now we need to define the search space for finding the values of x & y in the stalagmite function. The search space is chosen to be between 0 to 0.6 with 150 intervals. For this we have used 'linspace()'. Genetic Algorithm can take no. of iterations each time we run the code giving different values each time. To save the time of calculations we have restricted our script to run for 50 iterations only. It doesn't mean function will give maximum value in 100 iterations. We will consider whatever maximum value that came within those 100 iterations. We have restricted our area of search.

4) As 'linspace()' creates the series of nos, x & y will be the column vector. As input to the stalagmite function, we need to convert the column vector to a row vector. The first step of this conversion is to create the 'meshgrid(x,y)'. Next, we use 'for' loop for conversion.

5) The next step is to obtain the results for 3 cases of the genetic algorithm in Matlab. In the first case, maximum value of the function is found out with no restrictions, no bounds, and no limits. Genetic algorithm is free to choose the population then reproduce and mutate.

6) To get the same value each time we run the program, we need to restrict the program within specific bounds namely upper bound and lower bound. The whole procedure for programming this case the same as that of the previous one, exception being for GA.

7) Even the results from the bounded cases are not the same every time the program terminates. Hence we now need to increase GA iterations. We can raise it to any value, we have chosen it as 300. In this case, syntax for GA is different than the previous case. GA has to give this population size via an option.

8) Results for this case will be just one value of function which does not deviate with no of iterations.

Code for optimization of stalagmite function using a genetic algorithm.

Program:

Stalagmite Function Code:

% stalagmite function

function z =stalagmite(input)

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

fx_1 = (sin((5.1*pi.*x)+0.5)).^6;
fx_2 = exp((-4*log(2).*((x-0.0667).^2))./0.64);
fy_1 = (sin((5.1*pi.*y) + 0.5)).^6;
fy_2 = exp((-4*log(2).*((y-0.0667).^2))./0.64);

z =(-fx_1 .* fx_2 .* fy_1 .* fy_2);
end

Main code:

%Genetic algorithm
clear all
close all
clc

% Creating 1D array
xi=linspace(0,0.6,150);
yi=linspace(0,0.6,150);

% Creating 2D array
[xx,yy]=meshgrid(xi,yi);

% Getting output from the stalagmite function and storing it
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

%study 1
iterations = 100;
tic
for i=1:iterations
      [input1,f_val1(i)]=ga(@stalagmite,2);
      x1(i)=input1(1);
      y1(i)=input1(2);
end
time1 = toc;

% plotting unbound iteration case
figure(1);
subplot(2,1,1);
surfc(xx,yy,-f);
shading interp; %makes the surface look more smoother
hold on
plot3(x1,y1,-f_val1,'marker','*');
title('Study1: unbound inputs values');
xlabel('x_input');
ylabel('y_input');
zlabel('Z Value');
subplot(2,1,2);
plot(-f_val1);
axis([0,100,0,1]);
xlabel('iterations');
ylabel('z_max_1');


%study 2
tic
for i=1:iterations
      [input2,f_val2(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
      x2(i)=input2(1);
      y2(i)=input2(2);
end
time2 = toc;

% plotting bound iteration case
figure(2);
subplot(2,1,1);
surfc(xx,yy,-f);
shading interp; %makes the surface look more smoother
hold on;
plot3(x2,y2,-f_val2,'marker','*');
title('Study2: unbound inputs values');
xlabel('x_input');
ylabel('y_input');
zlabel('Z Value');
subplot(2,1,2);
plot(-f_val2);
axis([0,100,0,1]);
xlabel('iterations');
ylabel('z_max_2');


% study 3 increasing the population size
% by doing so we are increasing the probability of the function
% to converge at global maximum
opti=optimoptions('ga');
opti=optimoptions(opti,'PopulationSize',350); %increasing the popolation size
tic;
for i=1:iterations
      [input3,f_val3(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],opti);
      x3(i)=input3(1);
      y3(i)=input3(2);
end
time3=toc;  %gives the time taken for study
time1;
time2;
time3;
x_optimum = x3(1);
y_optimum = y3(1);
z_optimum = -f_val3(1);
figure(3);
subplot(2,1,1);
surfc(xx,yy,-f); %creates a surface to visualise 3D
shading interp;
hold on;
plot3(x3,y3,-f_val3,'marker','*');
title('Study3: Bounded inputs with increased population size');
xlabel('x_inputs');
ylabel('y_inputs');
zlabel('Z Value');
subplot(2,1,2); plot(-f_val3) %
plot(-f_val3) %plotting -f vs number of iterations
xlabel('iterations')
ylabel('Z_max_3');

Output:

1. The optimization solution for unbounded inputs

>>In a case study-1, the GA doesn't know the search space(i.e input array doesn't define as a search space for a 'GA'). Therefore each time program is executed it gives different optimum solutions.

2. The optimization for bounded inputs.

>>In the case study-2, the lower bound and upper bounds are specified of a stalagmite function is mentioned. Hence, the maximum point obtained in each iteration is between the bound.

3. The optimization for bounded inputs with population size.

>>In a case study -3, initial population size is mentioned along with the bound conditions. The maximum value is more precise than the other two cases.

Error faced while programing:

1. Error in study 1, the graphical representation is inverse.

>> solved by correcting value of 'f' to '-f'.

2. Several spelling mistake was corrected by over viewing the program.

Conclusion:

Hence, we are able to optimise the stalagmite function and find the global maxima of the function.

The (GA) is only used for the minimum function therefore to Maximize the function we inversed the minimum function.

Referances:

1. https://en.wikipedia.org/wiki/Genetic_algorithm

2. https://www.youtube.com/watch?v=1i8muvzZkPw

3. https://www.youtube.com/watch?v=W-RVXiBYdAA

4. https://www.youtube.com/watch?v=tvau83TYOak