Challenge

Week 4 - Genetic Algorithm

AAbdullah Quadri31 May 2020

Genetic Algorithm (GA):

Genetic Algorithm is inspired by Charles Darwin's theory of natural evolution.. Genetic algorithm is an optimization method that mimics natural process of evolution .GA is a solver and it is totally based upon random sampling i.e. it starts with random number of inputs and and based upon input it evaluates function and pick some random natural selections (2 elements) and mate them and also do cross over and at last create new generation which is hopefully better.

For Ex:

This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

Fitness Function
The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.

Selection
The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.
Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.

Crossover
Crossover 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.
For example, consider the crossover point to be 3 as shown below.

Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

Exchanging genes among parents

The new offspring are added to the population.

Mutation
In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.

Mutation occurs to maintain diversity within the population and prevent premature convergence.
Termination:
The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). Then it is said that the genetic algorithm has provided a set of solutions to our problem.

The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that are based on natural selection, the process that drives biological evolution. It is inspired by Charles Darwin's theory of natural evolution. Here genetic algorithm is used to find the global maxima of the stalagmite function.

Stalagmite Function:

Stalagmites represents the 3D pointed formations that arises from the floor. Like cones but may or may not be pointed always. With refrence to data here, Stalagmites are the 3D curves formations because of data we gave and it helps finding the threshold value of a parametres.

It creates local maxima and local minimas for data and also helps in finding best design characteristics for a product.

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:
1. Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
2. Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
3. Selects members, called parents, based on their expectation.
4. 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.
5. 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.
6. Replaces the current population with the children to form the next generation.
The algorithm stops when one of the stopping criteria is met.

Three Behaviours Genetic Algorithm

Unbounded Statistical Behaviour

SYNTAX: [inputs,fopt] = ga(fun,nvars)

Where:

Inputs represent the values of parameters x and y for which the function has the least value (fopt)

fun - The function to be optimized, in this case Stalagmite

nvars - the number of design variables, in this case only x and y are the variables

2. Bounded Statistical Behvaiour:

Syntax: [inputs,fopt] = ga(fun,nvars,A,b,Aeq,beq,lb,ub)

Inputs, fopt,fun and nvars are the same as Study 1
A - Linear inequality constraints : real matrix, if there are none, then [ ]
b - Linear inequality constraints : real vector, if there are none, then [ ]
Aeq - Linear equality constraints : real matrix, if there are none, then [ ]
beq - Linear equality constraints : real vector, if there are none, then [ ]
lb - Lower bounds, specified as a real vector or array
ub - Upper bounds, specified as a real vector or array

3. Bounded Statistical Behvaiour with increased population:

Syntax: [inputs,fopt]=ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options)

inputs, fopt,fun and nvars,A,b,Aeq,beq,lb,ub are the same as Study 1 and Study 2 respectively)

nonlcon - Nonlinear constraints, specified as a function handle or function name. If there are none,then [ ]
IntCon - Integer variables, specified as a vector of positive integers, if there are none, then [ ]
Options - Optimization options, specified as the output of optimoptions or a structure

Main Code:

clear all
close all 
clc
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases=25;
% Creating a 2D Mesh
[xx yy] = meshgrid(x,y);

% Evaluating Stalagmite Function
for i = 1 : length(xx)
    for j = 1 : length(yy)
        input_value(1)= xx(i,j);
        input_value(2) = yy(i,j);
        f(i,j) = stalagmite(input_value);
    end
end
%unbounded statistical behaviour
%tic
for i=1:num_cases;
    [inputs1,fopt1(i)]=ga(@stalagmite,2);
    xoutput(i)=inputs1(1);
    youtput(i)=inputs1(2);
end
%study1_time=toc;
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
xlabel('x-value')
ylabel('y-value')
zlabel('function value')
shading interp
plot3(xoutput,youtput,fopt1,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded Statistical Behvaiour')
subplot(2,1,2)
plot(fopt1)
xlabel('iterations')
ylabel('function maximum')



%statastical behaviour with upper and  lower bound
%tic;
for i=1:num_cases;
    [inputs2,fopt2(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xoutput(i)=inputs2(1);
    youtput(i)=inputs2(2);
end
%study2_time=toc;
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
xlabel('x-value')
ylabel('y-value')
zlabel('function value')
shading interp
plot3(xoutput,youtput,fopt2,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Statistical Behvaiour')
subplot(2,1,2)
plot(fopt2)
xlabel('iterations')
ylabel('function maximum')


%increasing Ga population size
options=optimoptions('ga');
options=optimoptions(options,'populationsize',350);
%tic
for i=1:num_cases;
    [inputs3,fopt3(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xoutput(i)=inputs3(1);
    youtput(i)=inputs3(2);
end
%study3_time=toc;
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
xlabel('x-value')
ylabel('y-value')
zlabel('function value')
shading interp
plot3(xoutput,youtput,fopt3,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded Statistical Behvaiour with Increased Population Size')
subplot(2,1,2)
plot(fopt3)
xlabel('iterations')
ylabel('function maximum')

fprintf ('\n Study 1 : Unbounded Statistical Behvaiour\n')
fprintf ('\n The Co-ordinates of x and y for the Global Maxima of the Function are : %f,%f\n',inputs1(1),inputs1(2))

fprintf ('\n Study 2 : Bounded Statistical Behvaiour\n')
fprintf ('\n The Co-ordinates of x and y for the Global Maxima of the Function are : %f,%f\n',inputs2(1),inputs2(2))

fprintf ('\n Study 3 : Bounded Statistical Behvaiour with Increased Population Size\n')
fprintf ('\n The Co-ordinates of x and y for the Global Maxima of the Function are : %f,%f\n',inputs3(1),inputs3(2))

Stalagmite Function code:

function f = stalagmite(input_vector)
  
  x = input_vector(1); linspace(0,0.6,150);
  y = input_vector(2); linspace(0,0.6,150);
  
  f1x = (sin(5.1*pi*x + 0.5))^6;
  f1y = (sin(5.1*pi*y + 0.5))^6;
  f2x = exp(-4*log(2)*(x-0.0667)^2/0.64);
  f2y = exp(-4*log(2)*(y -0.0667)^2/0.64);
  f = f1x.*f2x.*f1y.*f2y;
  
  end

results and plot:

code explanation:

First, Linspace command is used to for x and y with 150 elements ranging from 0 to 0.6

x = linspace(0,0.6,150);

y = linspace(0,0.6,150);

counter is set to 20 iterartion value

num_cases=25;

meshgrid command is used with x and y as input to form a output 2D grid [xx yy]

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

Two for loop are used to solve the genetic algorithm for every element in the 2D mesh grid using the the length of rows and columns as iteration values
Then output of stalagmite function is stored in matrix termed as input_value

for i = 1 : length(xx)

for j = 1 : length(yy)

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

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

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

end

Then for loop bounded by the number of iterations as num_cases is formed
Then ga code is entered for unbounded statistical study which have the following format :

[inputs,fopt] = ga(fun,nvars)

Inputs represent the values of parameters x and y for which the function has the least value (fopt)

fun - The function to be optimized, in this case Stalagmite

nvars - the number of design variables, in this case only x and y are the variables to be plotted

First subplot command is used to draw two plots in same window as two rows and one column
Then Hold on command is used to prevent plot from being removed
The surfc command is used to plot contour with xx value and yy value from the mesh grid and fopt as input.
Then shading interp is used to smoothen the function plot and to remove the grid lines
Then plot 3 command is used to plot a point in 3 dimensions, Then the graph title is selected
Then fopt value of the function is plotted on the second plot

figure(1)

subplot(2,1,1)

hold on

surfc(xx,yy,f)

xlabel('x-value')

ylabel('y-value')

zlabel('function value')

shading interp

plot3(xoutput,youtput,fopt1,'marker','o','markersize',5,'markerfacecolor','r')

title('Unbounded Statistical Behvaiour')

subplot(2,1,2)

plot(fopt1)

xlabel('iterations')

ylabel('function maximum')

ga code for Bounded Statistical Behvaiour:

Syntax: [inputs,fopt] = ga(fun,nvars,A,b,Aeq,beq,lb,ub)

The range of the genetic algorithm is Bounded by introducing values for lower and upper bounds and hence the values of global maxima and the values of x and y will be within the defined search space in inputs.

ga code for Bounded Statistical Behvaiour with increased population:

Syntax: [inputs,fopt]=ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon,options)

inputs, fopt,fun and nvars,A,b,Aeq,beq,lb,ub are the same as Study 1 and Study 2 respectively)

to increase the Population Size optimoptions command is used.
fprintf command is used to print the results in the command windows.

parallely plots are drawn for each condition and results are generated.

errors:

error1: unreconized function or vaiable 'o'

solution: typing fault in plot command

error2:unable to execute meshgrid command

solution: already a program called 'meshgrid' was present in my files. it was considering meshgrid as a function call

Week 4 - 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.