Challenge

Genetic Algorithm

AAamair Khan11 Jul 2022

Aim :

To find the global maxima for the stalagmite function using genetic algorithm in MATLAB.

Theory :

What is a Genetic Algorithm?

Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. It is frequently used to find optimal or near-optimal solutions to difficult problems which otherwise would take a lifetime to solve. It is frequently used to solve optimization problems, in research, and in machine learning.

The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:

• 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:

The algorithm begins by creating a random initial population.
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 the 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.
The algorithm stops when one of the stopping criteria is met.
The algorithm takes modified steps for linear and integer constraints.
The algorithm is further modified for nonlinear constraints.

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, lntCon, options), where

A, B= linear inequality constraints

Aeq, Beq= linear equality constraints

lb=lower bound

ub= upper bound

nonlcon=non-linear constraints

lntcon=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 celling 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 :

`f(x,y)=f_(1,x)f_(2,x)f_(1,y)f_(2,y)`

`f_(1,x)=[sin(5.1pix+0.5)]^6`

`f_(1,y)=[sin(5.1piy+0.5)]^6`

`f_(2,x)=exp[-4ln(2)((x-0.0667)^2)/0.64]`

`f_(2,y)=exp[-4ln(2)((y-0.0667)^2)/0.64]`

Program for Stalagmite Function :

% The stalagmite function

function f=stalagmite(input_vector)

x=input_vector(1);

y=input_vector(2);

f1x = (sin((5.1*pi*x)+0.5))^6; % term 1

f1y = (sin((5.1*pi*y)+0.5))^6; % term 2

f2x = exp((-4*log(2)*(x-0.0667)^2)/0.64); % term 3

f2y = exp((-4*log (2)*(y-0.0667)^2)/0.64); % term 4

f=-(f1x*f1y*f2x*f2y);

end

Program for finding Global maxima :

%Program to find global maxima using genetic algorithm.

close all

clear all

clc

%Defining search space

x=linspace(0,1,150);

y=linspace(0,1,150);

num_cases =50; %To run the ga 50 times

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

%Creating Data points of 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);

%stalagmite function takes in the data given inside parantheses and calculates f

end

surfc(xx,yy,f);

xlabel('x axis')

ylabel('y axis')

shading interp

tic

%study1 - unbound condition

for i=1:num_cases

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

% ga is an inbuilt function, it always minimises a function

% @ defines what function to minimize

% 2 denotes no. of variables in a function

xopt(i) = input_vector(1);

yopt(i) = input_vector(2);

end

study1_time=toc;

% tic toc is used to measure how long it takes to study

figure(1)

subplot (2,1,1) % to have multiple plots inside the same figure window

hold on

surfc(x,y,-f);

shading interp

plot3(xopt, yopt,-fopt, 'marker', 'o', 'markersize',5,'MarkerFaceColor','r')

title('Unbounded Inputs')

subplot(2,1,2)

plot(-fopt)

xlabel('Iterations');

ylabel('Function minimum');

tic

% study2 - Statistical Behaviour - with upper and lower bounds

for i=1:num_cases

[input_vector, fopt(i)]=ga(@stalagmite,2,[],[],[],[],(0:0),(1:1));

xopt(i)=input_vector(1);

yopt(i)=input_vector(2);

end

study2_time=toc;

figure(2)

subplot(2,1,1)

hold on

surfc(x,y,-f);

shading interp

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

title('Bounded Inputs')

subplot(2,1,2)

plot(-fopt)

xlabel('Iterations');

ylabel('Function minimum');

%Study 3 Increasing GA Iterations

options=optimoptions('ga');

options=optimoptions(options, 'PopulationSize',300);

tic

for i=1:num_cases

[input_vector, fopt(i)]=ga(@stalagmite,2,[],[],[],[],(0:0),(1:1),[],[],options);

xopt(i)=input_vector(1);

yopt(i)=input_vector(2);

end

study3_time=toc;

figure(3)

subplot(2,1,1)

hold on

surfc(x,y,-f);

shading interp

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

title('Bounded Inputs with Modified Population Size')

subplot(2,1,2)

plot(-fopt)

xlabel('Iterations');

ylabel('Function minimum');

Output :

Study 1:

Study 2:

Study 3:

This point on the peak is called the Global Maxima.

Results and Conclusions:

Hence by using genetic 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 negative 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.

Genetic Algorithm

Ship work like this
in your own course.

Talk to a career counsellor

Ship work like thisin your own course.

Talk to a career counsellor

Ship work like this
in your own course.