Week 5 - 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 the Genetic Algorithm Work?

The following outline summarizes how the genetic algorithm works:

1. The algorithm begins by creating a random initial population.

2. The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population. To create the new population, the algorithm performs the following steps:

• Scores each member of the current population by computing its fitness value. These values are called raw fitness scores.
• Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
• Selects members, called parents, based on their expectation.
• Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.
• Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.
• Replaces the current population with the children to form the next generation.

3. The algorithm stops when one of the stopping criteria is met.

Genetic Algorithm (ga) Syntax (used in our program):

1. x = ga (@func, nvars), where "func" is the function name and "nvars" is the number of variables.

2. x = ga (@func, nvars, A, B, Aeq, Beq), a set of lower and upper bounds is given so that the solution lies in that range.

3. x = ga (@func, nvars, A, B, Aeq, Beq, lb, ub, nonlcon, IntCon, options), where

A, B = linear inequality constraints

Aeq, Beq = linear equality constraints

lb = lower bound

up = upper bound

nonlcon = non-linear constraints

Intcon = vector of positve integers

options = optimisation options

Stalagmite Function:

What is a Stalagmite?

A stalagmite is a type of rock formation that rises from the floor of a cave due to the accumulation of material deposited on the floor from ceiling drippings. Stalagmites may be composed of lava, minerals, mud, peat, pitch, sand, sinter and amber.

Here, in this program, the graph we get looks like hanging stalagmites, that is why it is referred to as stalagmite function.

The equation of stalagmite function is:

program for a function:

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

Program for finding Global Maxima:

close all

clear all

clc

%Creating x and y array

x=linspace(0,0.6,150);

y=linspace(0,0.6,150);

num_cases=50;

%Creating two dimensional mesh

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

%Calculating the stalagmite function

for i=1:length(xx)

for j=1:length(yy)

a(1)=xx(i,j);

a(2)=yy(i,j);

f(i,j)=stalagmite(a);

end

end

%Study-1

tic

for i=1:num_cases

[inputs,fopt(i)]=ga(@stalagmite,2);

xopt(i)=inputs(1);

yopt(i)=inputs(2);

end

study1_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',6,'markerfacecolor','r')

subplot(2,1,2)

plot(fopt)

xlabel('Iterations')

ylabel('Function maximum')

%Study-2

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

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',6,'markerfacecolor','r')

subplot(2,1,2)

plot(fopt)

xlabel('Iterations')

ylabel('Function maximum')

%Study-3
options=optimoptions('ga')

options=optimoptions(options,'PopulationSize',170)

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

fopt=-fopt;

f=-f;

study3_time=toc

figure(3)

subplot(2,1,1)

hold on

surfc(xx,yy,f)

shading interp

xlabel('x values')

ylabel('y values')

plot3(xopt,yopt,fopt,'marker','o','markersize',6,'markerfacecolor','r')

subplot(2,1,2)

plot(fopt)

xlabel('Iterations')

ylabel('Function maximum')

max_value=fopt

Stalagmite function code:

function [F]=stalagmite(a)

x = a(1);

y = a(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

Output:

Study 1:

Study 2:

Study 3:

This point on the peak is called the global maxima.

Results and Conclusions:

Hence by using generic algorithm, we were able to find the Global maxima point of the stalagmite function.

By default in MATLAB, ga calculates the global minima. In order to make it show the global maxima, we add a -ve sign to 'f' and 'fopt' everywhere.

Initially, the time required to run the program is long. We can reduce this time by reducing the limits. Decreasing the population size will get more accurate results.