Week 4.1 - Genetic Algorithm

Introduction:

Genetic algorithms are search methods that employ processes found in natural biological evolution. These algorithms search or operate on a given population of potential solutions to find those that approach some specification or criteria. To do this, the algorithm applies the principle of survival of the fittest to find better and better approximations. At each generation, a new set of approximations is created by the process of selecting individuals according to their level of fitness in the problem domain and breeding them together using operators borrowed from natural genetics. This process leads to the evolution of populations of individuals that are better suited to their environment than the individuals that they were created from, just as in natural adaptation.

The GA will generally include the three fundamental genetic operations:

- Selection

- Crossover

- Mutation

These operations are used to modify the chosen solutions and select the most appropriate offspring to pass onto succeeding generations. GA considers many points in the search space simultaneously and have been found to provide a rapid convergence to a near optimum solution in many types of problems. They usually exhibit a reduced chance of converging to local minima. GA suffers from the problem of excessive complexity if used on problems that are too large.

Genetic algorithms work on populations of individuals rather than single solutions, allowing for parallel processing to be performed when finding solutions to the more large and complex problems.

Aim:

To optimise the stalagmite function and find the global maxima of the function.

Objective:

- To write a code to optimise the stalagmite function and find the global maxima of the function.

- To plot the graphs of three studies and for F maximum vs no. of iterations.

Formulae:

CODE:

%program to optimise the stalagmite function and find the global maxima of the function.
clear all
close all
clc

%Workspace definition
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%Number of cases/iterations:
num_cases = 50;

%General loop for studies
for i = 1:length(x)
    for j = 1:length(y)
        inputs(1)=x(i);
        inputs(2)=y(j);
        f(i,j) = stalagmitefunc(inputs);
    end
end


%Study1 Statistical Behaviour(Unbounded)
tic
for i = 1:num_cases
    [inputs,funopt(i)] = ga(@stalagmitefunc,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study1_time = toc

%Plot for study1
figure(1)
subplot(2,1,1)
hold on
surfc(x, y, -f)
shading interp  %Smoothens the figure
plot3(xopt,yopt,-funopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Study1- Unbounded Inputs')
subplot(2,1,2)
plot(-funopt)
xlabel('No. of Iteration')
ylabel('Function Minimum')

tic
%Study-2 Statistical Behaviour - with upper and lower Bounds
for i = 1:num_cases
    [inputs,funopt(i)] = ga(@stalagmitefunc,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study2_time = toc

%Plot for study2
figure(2)
subplot(2,1,1)
hold on
surfc(x, y, -f)
shading interp   %Smoothens the figure
plot3(xopt,yopt,-funopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Study2- Bounded inputs')
subplot(2,1,2)
plot(-funopt)
xlabel('No. of Iteration')
ylabel('Function Minimum')

tic
%Study3- Increasing the Genetic Algorithm Iterations
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',250);

for i = 1:num_cases
    [inputs,funopt(i)] = ga(@stalagmitefunc,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
study3_time = toc

%Plot for study3
figure(3)
subplot(2,1,1)
hold on
surfc(x, y, -f)
shading interp  %Smoothens the figure
plot3(xopt,yopt,-funopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Study3- Bounded inputs(Increased Population)')
subplot(2,1,2)
plot(-funopt)
xlabel('No. of Iteration')
ylabel('Function Minimum')

%End of program

Function Code:

function[v] = stalagmitefunc(input_vector)

%Inputs for the function
x = input_vector(1);
y = input_vector(2);

%Stalagmite equations
f1_x = sin((5.1*3.142*x)+0.5)^6;
f1_y = sin((5.1*3.142*y)+0.5)^6;

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

[v] = -(f1_x*f2_x*f1_y*f2_y);

end

Explanation of the Code:

Initially we define the workspace and set default population size to 50. A loop for the study of Statistical behaviour with no bounds is created for default population size.

We use the solver ‘ga’ to find the minimum of function using Genetic Algorithm.

x = ga(fun,nvars) : finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun.

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) : minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.

Another loop for study is created to study the Statistical behaviour with upper and lower bounds. A similar loop is created for the study of stasitical behaviour with increased genetic algorithm iterations.

To alter the population size and to create optimization options we use ‘optimoptions’ command.

options = optimoptions(SolverName) : returns a set of default options for the SolverName solver.

options = optimoptions(SolverName,Name,Value) : returns options with the named parameters altered with the specified values.

Graphs for all the above studies are plotted for Function Minimum vs. No. of iterations.

Time taken for each study is determined using the tic-toc commands.

Errors Occurred:

There was an error shown in the command window, the variables ‘xx’ and ‘yy’ were not assigned and were used in the loop. I changed the loop variables to ‘x’ and ‘y’ as they were already assigned in the program. Thus, solved the error.

Result:

The local maxima for stalagmite function and the graphs for all three studies are obtained.

Study-1 Result: