Week 4.1 - Genetic Algorithm

GENETIC ALGORITHM

The Genetic Algorithm (GA) is a optimization technique tp solve non linear optimization problems. It is used to find the global minima for optimising a problem. An initial set of solutions is tested against the objective function. Subsequent generations evolve through the processes in below.

GENERIC ALGORITHM IS DONE IN THREE STEPS

SELECTION : A Number of individuals is selected in the mating pool, the called parents who contribute to the population at the next generation.

CROSSOVER : This combines parents from different generations, by mutating the old generation parents. The new generation offspring comes carrying genes from both the parents. The genes carried by the offspring is random.

MUTATION : Mutation prevents the solution from falling into local minima.

EXPLANATION OF THE CODE

1) The random array of x and y was created and the corresponding 2D array was obtained using meshgrid function.

2) A Nested for loop array was used to assign the values from this array to an array names into input_vector.

3) This input_vector is the input to stalagmite function.

4) The stalagmite function is written seperately.

5) (-)Minus sign is given to the output of stalagmite function so after ga processes it we get the global maxima.

6) Tic Toc command is used to get the run time of each case.

7) In the first case the bounds were not defined and the plots were made.

8) Negative sign is given for f value inside surface function to get the stalagmite function upwards.

9) The bouncing is given in the next case so that the number of solution gives more accuracy.

10) The population is increaed in subsequent cases and the plotting is done.

11) The global maxima is found in the last case.

STOPPING CRITERIA

GENERATIONS : The algorithm stops when the number of generations reaches the values of generations.

TIME LIMIT : The algorithm stops after running for amount of time in seconds equal to time limit.

FITNESS LIMIT : The algorithm stops when the value of fitness function for the best point in the current population less than or equal to the fitness function.

MAIN PROGRAM

% main program

clear all 
close all
clc

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
limit = 50; 

% 2D array using meshgrid function
[xx yy] = meshgrid(x,y);

% array value input
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:limit
     [input,fval(i)] = ga(@stalagmite,2);
     x_out(i) = input(1);
     y_out(i) = input(2);
 end
 
 case_time_1 = toc
 
 figure(1)
 subplot(2,1,1)
 surfc(xx,yy,-f)
 xlabel('x')
 ylabel('y')
 title('case 1(Unbounded)','color','k')
 shading interp
 hold on;
 plot3(x_out,y_out,-fval,'marker','o','markersize',6,'markerfacecolor','r');
 subplot(2,1,2)
 plot(-fval);
 xlabel('No of iterations')
 ylabel('max function value')
 % case:2 Inserting bounding box
 tic
 for i = 1:limit
     [input,fval(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
     x_out(i) = input(1);
     y_out(i) = input(2);
 end
 
 case_time_2 = toc
 figure(2);
 subplot(2,1,1)
 hold on;
 surfc(xx,yy,-f)
 xlabel('x')
 ylabel('y')
 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('max function value')
 
 % case:3
 options = optimoptions('ga');
 options = optimoptions(options,'populationsize',100)
 
 tic
 for i = 1:limit
     [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_time_3 = toc
 figure(3);
 subplot(2,1,1)
 hold on;
 surfc(xx,yy,-f)
 xlabel('x')
 ylabel('y')
 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('max function value')
 
 % case:4
 options = optimoptions('ga');
 options = optimoptions(options,'populationsize',500)
 
 tic
 for i = 1:limit
     [input,fval(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.1;0.1],[],[],options);
     x_out(i) = input(1);
     y_out(i) = input(2);
 end
 
 case_time_4 = toc
 figure(4);
 subplot(2,1,1)
 hold on
 surfc(xx,yy,-f)
 shading interp
 xlabel('x')
 ylabel('y')
 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('max function value')

STALAGMITE 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;

f2x = exp((((input_vector(1)-0.0667).^2)/0.64).*(-4*log(2)));
f2y = exp((((input_vector(2)-0.0667).^2)/0.64).*(-4*log(2)));
f1 = f1x*f1y*f2x*f2y;
f = -f1;
end

ERRORS FACED IN PROGRAM

I made small mistake in inputs_vector instead of input_vector so that it was not recogonised.

The running time of the program was observed too long. The run time of each program was observed using tic toc command and number of iterations in each command is altered to reduce the running time without affecting the result.

RESULTS

CASE 1 UNBOUNDED :

CASE 2 BOUNDED :

CASE 3 BOUNDED WITH INCREASED POPULATION :

CASE 4 BOUNDED WITH MORE POPULATION :

REFERENCES

https://in.mathworks.com/help/gads/genetic-algorithm.html