Week 4.1 - Genetic Algorithm

• Selection rules select the individuals, called parents, that contribute to the population at the next generation.

• Crossover rules combine two parents to form children for the next generation.

• Mutation rules apply random changes to individual parents to form children.

HOW DOES A GENETIC ALGORITHM WORKS ?

Initialization

The evolutionary process begins with initialization, wherein an initial population of candidate solutions is generated. There are many different methods of initializing populations, but with Genetic Algorithms the most popular method of initialization is simply to create a population of randomly initialized binary strings. Once the initial population has been created, the evolutionary generational cycle begins.

Selection

At each generational step, a pool of parents is chosen from the parent population based on the fitness values of each individual using a selection mechanism, such that the fittest individuals will have a greater probability of passing on genetic material to subsequent generations. This selected population (known as the “parent” population) then forms the basis for all subsequent optimizations during the generational step.

Variation

Once the parent population is fully populated via the selection process, a child population is created which will form the basis of the next generation. This child population is generated by variation operators, which are performed on individuals from the parent population. The most prominent such methods are crossover and mutation.

Crossover

Crossover takes pairs of parents from the parent population (usually random selection with replacement, such that the same parent can be selected multiple times to produce children). These parents then have some of their genetic information swapped between them. Crossover of two parent chromosomes is usually done in a single-point manner, where a single crossover point on both chromosomes is randomly selected and then all subsequent genetic information is swapped between individuals, as shown in Fig. 2:

Crossover is typically performed on randomly selected pairs of parents from the parent population until the new “child” population reaches the same size as the original parent population.

Mutation

While crossover simply swaps pre-existing information between pairs of candidate solutions, mutation in Evolutionary Algorithms is typically the standard method of introducing “new” genetic material into the population. Once the child population has been created via crossover, mutation in canonical Genetic Algorithms then occurs on all children in a “bit-flip” fashion by randomly changing codons on the chromosome between 0 and 1 (as shown in Fig. 3).

Evaluation

Once the child population has been created, all children then need to be evaluated in order to assign a fitness value by which they can be judged against their peers. This fitness is used to sort/rank a population and to impose probabilities for both selection and replacement phases of the search process, such that the fittest members of the population have a higher probability of passing on genetic material.

Replacement

The final act of the generational step is to replace the old “N” population with the new “N+1” child population. While many methods exist, the most typical replacement method is Generational Replacement, wherein the entire previous generation is replaced with the newly generated child population.

Termination

A Genetic Algorithm will typically terminate after a predefined number of generations, or if some stopping criterion has been met (e.g. fitness is above some threshold, error rate is below some threshold, etc). The fittest solution in the population is then returned as the overall best solution.

CODE :

Function Code :

clear all
close all
clc
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))*(x-0.0667).^2)/0.64);

[f] = -(f1_x.*f1_y.*f2_x.*f2_y);
end

MAIN CODE:

close all
clear all
clc
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
[xx,yy] = meshgrid(x,y);
num_cases=80;

%calling 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

%study1- statistical behaviour
for i= 1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2);
xopt(i)=inputs(2);
yopt(i)=inputs(2);
end
study_time= toc;
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title('unbounded inputs')
xlabel('x values')
ylabel('y values')
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(fopt)
xlabel('literations')
ylabel('function minimum')
tic
%study2- statistical behaviour with upper and lower bounds
for i= 1:num_cases
[inputs,fopt(i)]= ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study2_time= toc
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title('bounded inputs')
xlabel('x values')
ylabel('y values')
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(fopt)
xlabel(iterations')
ylabel('function minimum')

%study3 - increasing ga iterations
options= optimoptions('ga');
options= optimoptions(options,'population size',200);
tic
for i= 1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end
study3_time= toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title('bounded inputs')
xlabel('x values')
ylabel('y values')
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(fopt)
xlabel(iterations')
ylabel('function minimum')

STEPS:

• The code starts with defining x and y as inputs using linspace.
• The function known as stalagmite_func is defined as shown in the 2nd stage of codes.
• Two for loops are incorporated in the main code so that all combination of x and y values taken in the stalagmite_func function
• In the 1st study GA function runs for 80 iterations. Plots stalagmite and maximum values generated in each iteration is shown.
• In the 2nd study GA function is incorporated with lower and upper bounds and runs for 80 iterations.Plots stalagmite and maximum values generated in each iteration is shown.
• In the 3rd study GA function is incorporated with lower and upper bounds with the population size of 200.Plots stalagmite and maximum values generated in each iteration is shown.

OUTPUT:

STUDY 1 :

STUDY 2:

STUDY 3: