Challenge

Week 4.1 - Genetic Algorithm

SSujith Cn16 Feb 2022

MATLAB

GENETIC ALGORITHM

Aim:

To Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

Objectives:

Clearly explaining the concept of genetic algorithm.
Explaining the syntax for ga in Matlab.
Codes gives the same output even if it is made to run several times.
Plot graphs for all 3 studies and for F maximum vs no. of iterations.

Theory:

A genetic algorithm is a search heuristic that is inspired by Charles Darwin's theory of natural evolution. 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. Genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms. Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection.

Genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, non differentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.

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 it works:

In Genetic algorithm (GA), 'n' values form the function/problem are randomly selected (n is the population size). The values are selected after being sorted from the best to the worst ones first ('best' condition is subjected to the need). The GA selects the best and rejects the other values. Now, each selected value is mutated (n-1) times, i.e., some randomness is added to the values. Then, the mutated values are again checked against the minimum criteria condition. This iteration is continued up to the number of iterations decided.

1. Fitness function: It is the function that GA is trying to optimize.

2. Population of chromosome: It is the numerical values that represent all the solutions to the function. The selection operator chooses some of the chromosomes (with replacement) for reproduction based on probability distribution. fitter the chromosome more likely it is to be selected.

3. Cross over: This operator swaps in random a subsequence of two of the chosen chromosomes to create two offspring. Usually each chromosome is converted into binary code and then cross over is done from one parent chromosome into another.

4. Mutation: Mutation operator randomly flips individual bits in the new chromosomes.

The GA syntax in Matlab is given by :

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon,options)

fun = objective function

nvars= number of variables

A and B = subject to linear inequalities of the form A*x <=B

Aeq and Beq = subject to linear equalities of the form A*x = B

LB lower bound and UB = upper bound

nonlcon = non linear inequalities

intcon = integer constrained

options = helps to add contraint tolerance by increasing the population size.

Code For Stalagmite Function:

function y = 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));
y = -[f1_x*f1_y*f2_x*f2_y];
end

Code For Finding The Global Maxima Of The Stalagmite Function:

clear all
close all
clc

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

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

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

%study 1
tic
for i=1:num_case
    [inputs,Fopt(i)]=ga(@stalagmite,2);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end

Study_time_1 = toc

figure(1)
subplot(2,1,1);
hold on
surfc(xx,yy,F);
shading interp;
ylabel('y data');
xlabel('x data');
plot3(xopt,yopt,Fopt,'marker','o','markersize',5,'markerfacecolor','k');
title('unbounded inputs');
subplot(2,1,2);
plot (Fopt);
xlabel('iterations');
ylabel('Function maximum');

%study 2
tic
for i=1:num_case
    [inputs,Fopt(1)]=ga(@stalagmite,2,[],[],[],[],[0:0],[1:1]);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end

study_time_2=toc

figure (2)
subplot(2,1,1);
hold on
surfc(xx,yy,F) ;
shading interp;
ylabel('y data');
xlabel('x data');
plot3(xopt,yopt,Fopt,'marker','o','markersize',5,'markerfacecolor','k');
title('bounded inputs');
subplot(2,1,2);
plot(Fopt);
xlabel('iterations');
ylabel('Function maximum');

%study 3

options=optimoptions('ga');
options=optimoptions(options,'populationsize',450);
tic
for i=1:num_case
    [inputs,Fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0:0],[1:1],[],[],options);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study_time_3=toc

figure(3)
subplot(2,1,1);
hold on
surfc(xx,yy,F);
shading interp;
ylabel('y data');
xlabel('x data');
plot3(xopt,yopt,Fopt,'marker','o','markersize',5,'markerfacecolor','k');
title('bounded inputs with increase population size');
subplot(2,1,2);
plot(Fopt);
xlabel('iterations');
ylabel('Function maximum');

max_value=Fopt

Step-wise explanation of the codes:

The code starts with defining x and y as inputs using linspace command which gets values between 0 to 0.6
A function known as Stalagmite.m is defined as shown in the 2nd stage of codes.
Two for loops are incorporated in the main code so that all the combinations of x and y values is taken in the stalagmite function using the meshgrid command.
In the 1st study GA function runs for 50 iterations. Plots of the stalagmites 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 50 iterations. Plots of the stalagmites and maximum values generated in each iteration is shown.
In the 3rd study GA function is incorporated with lower and upper bounds along with the population size. Plots of the stalagmites and maximum values generated in each iteration is shown.

ERRORS FACED: