Genetic Algorithm

AIM: To write the code to calculate the Global Maxima of the Stalagmite function

GENETIC ALGORITHM :

The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.

Five phases are considered in a genetic algorithm.

1] Initial Population 2] Fitness Function 3] Selection 4] Cross Over 5] Mutation

Initial Population: The set of individuals involved in the process is called as Population. Each individual is a solution to the problem you want to solve.

Fitness Function: The Function which determines how fit an individual is to compete with oothers.

Selection: The phase of selecting the more fittest individual. Individuals with high fitness have more chance fo getting to be selected.

Cross Over: It 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.

Mutation: Mutation occurs to maintain diversity within the population and prevent premature convergence.

Stalagmite function is the Mathematical model that actually helps us to gain Local maximas and minimas. A stalagmite is the type of Rock formation that rises from the floor of the cave due to the accumulation of materials deposited on the floor from ceiling drippings. Stalagmite may be composed of lava, minerals, sand etc.

Stalagmite can be plotted as a function which is defined as :

%stalagmite function

function [F] = stalagmite(input_vector)
 x = input_vector(1);
 y = input_vector(2);

 f1=(sin(5.1*pi*x + 0.5)).^6;
 f2=(sin(5.1*pi*y + 0.5)).^6;
 f3= exp((-4*log(2)*(x-0.0667).^2)/(0.64));
 f4= exp((-4*log(2)*(y-0.0667).^2)/(0.64));
 F = -f1*f2*f3*f4;
end


%Main function

clear all 
close all
clc 

%defining the search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
iterations = 50;
[xx, yy] =meshgrid(x,y);

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

%1st iteration - studying the statistical behaviour

tic 
for i=1:iterations
[inputs , f_optimum(i)] = ga(@stalagmite,2);
x_optimum(i) = inputs(1);
y_optimum(i) = inputs(2);
end

iteration_1_time = toc

%plotting

figure (1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded inputs')
subplot(2,1,2)
plot(f_optimum)
xlabel('Iterations')
ylabel('Function maximum')

%2nd iteration with upper and lower limits

tic
for i=1:iterations
[inputs , f_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
x_optimum(i) = inputs(1);
y_optimum(i) = inputs(2);
end

iteration_2_time = toc

%plotting
figure (2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(f_optimum)
xlabel('Iterations')
ylabel('Function maximum')

%3rd iteration - increasing the size of population
 
options = optimoptions('ga');
options = optimoptions(options,'populationsize',200)

tic
for i=1:iterations
[inputs , f_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
x_optimum(i) = inputs(1);
y_optimum(i) = inputs(2);
end

iteration_3_time = toc

%plotting
figure (3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(x_optimum,y_optimum,f_optimum,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs with modified population size')
subplot(2,1,2)
plot(f_optimum)
xlabel('Iterations')
ylabel('Function maximum')

f_min = ga(@function,nvars,A,B,Aeq,Beq,LB,UB,nonlcon,intcon,options)

Explaination of terms involved:

1. f_min is the local minima point.
2. @function is the function to be called.(In our case, its the stalagmite function)
3. nvars indicates the no of variables used.
4. A and B are used to indicate any kind inequalities that exist in the function.
5. Same goes with Aeq and Beq.
6. LB = lower bound.
7. UB = upper bound.
8. nonlcon gives a two vectors representing inequalities and equalities.
9. options is used to perform additional operations like increasing population size. This is done with the help of optimooptions