Week 4.1 - Genetic Algorithm

4. PHASES OF GENETIC ALGORITHM:

• Initialization of population:

The code generates its random population of defined size and from that population the code evaluates the fitness of the members of the population according to which it forms new population based on no. of iterations performed.

• Fitness Assignment:

It is that function which we have to optimize and its optimization is done with the help of number of generations which have been formed by the code accordance with the fitness value of each member generated, these fitness values are used for the reproduction of the children.

• Selection:

The idea of the selection phase is to select the fittest individuals and let them pass their genes to the next generation. The main goal of this phase is to find the region where the chances of getting the best solution are more. Inspiration for this is from the survival of the fittest. It should be a balance between exploration and exploitation of search space. GA tries to move the genotype to higher fitness in the search space. Too strong fitness selection bias can lead to sub-optimal solutions. Too little fitness bias selection results in unfocused search.

• Crossover:

Crossover is the most significant stage in the genetic algorithm. During crossover, a random point is selected while mating a pair of parents to generate offspring.

• Mutation:

In a few new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This indicates that some of the bits in the bit chromosome can be flipped. Mutation happens to take care of diversity among the population and stop premature convergence.

• Termination:

After a number of iterations through the phases of the algorithm, the process terminates based on certain defined termination criteria. at this stage the optimal solution is reached.

Syntax for ga:

fun Fitness function

nvars Number of design variables

Aineq A matrix for linear inequality constraints

Bineq b vector for linear inequality constraints

Aeq Aeq matrix for linear equality constraints

Beq Beq vector for linear equality constraints

1b Lower bound on x

ub Upper bound on x

FORMULA USED:

where , the above equations are used in the stalagmite function to plot the graph in the main functions.

5. PROGRAMS

code 1: Function program

function [f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
f1_x = (sin(5.1*pi*x+0.5))^6;
f1_y = (sin(5.1*pi*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);

f = -[f1_x,f1_y,f2_x,f2_y];

end

While using the function at the end as we are using the -ve sign so that the plot will be reversed as we have to find the maxima of the given function using ga.

code 2: Main program

clear all
close all
clc

%defining our search space

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

%creating a 2D mesh

[xx yy] = meshgrid(x,y);

%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(input_vector); %values of function in given search space
    end
end

%study1-statistical behaviour
%calculating the time for the study by placing tic and toc

tic
num_cases = 50; %Number of itreation for which the function will evaluate the fitness

for i=1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite,2); %calculating the optimized value of the function
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end

study1_time = toc %displaying the time taken to evaluate

%plotting the graph

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(-fopt)
xlabel('Iteration');
ylabel('Function-Maximum');

%study2- statistical behaviour - with upper and lower bounds

tic

for i = 1:num_cases;
    [inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end

study2_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(-fopt);
xlabel('Iteration');
ylabel('Function-Maximum');

%study3 - increasing GA iteration

tic

for i =1:num_cases;
    [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end

study3_time = toc

%plotting

figure(3)
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 with Increase Population Size');
subplot(2,1,2);
plot(-fopt);
xlabel('Iteration');
ylabel('Function-Maximum');

Error faced while proramming:

Reference:

• https://www.mathworks.in/help/gads/what-is-the-genetic-algorithm.html#:~:text=The%20genetic%20algorithm%20is%20a,a%20population%20of%20individual%20solutions.
• https://skill-lync.com/projects/week-4-1-genetic-algorithm-284