Week 4.1 - Genetic Algorithm

Genetic Algorithm using Matlab to optimise the stalagmite function

Section 1 :

PROBLEM DEFINITION

To optimise the stalagmite function and find the maximum value of X and Y

Stalagmite Function :

Section 2 :

How the Genetic Algorithm Works?

A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.

Outline of the Algorithm

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:

   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.

3. The algorithm stops when one of the stopping criteria is met. See Stopping Conditions for the Algorithm.

4. The algorithm takes modified steps for linear and integer constraints. See Integer and Linear Constraints.

5. The algorithm is further modified for nonlinear constraints. See Nonlinear Constraint Solver Algorithms.

Above article available at the link given below :-

How the Genetic Algorithm Works

Section 3 :

GENETIC ALGORITHM IN ACTION

Program to perform Genetic Algorithm to optimise the stalagmite function :-

The Program has following three parts :-

Study 1 - Intial study

Study 2 - With Bounds

Study 3- With Larger Population

GA SYNTAX

clear all
close all
clc

%Generating X and Y values in the range of 0 to 0.6
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
%Generating 150 x 150 Matrix for xn and yn
[xn,yn]=meshgrid(x,y);
iteration_count=50;
% Start Stopwatch timer to clock the GA execution time
tic
% Study 1 - Initial Study
for i= 1:length(xn)
    for j=1:length(yn)
        input_vector(1)=xn(i,j);
        input_vector(2)=yn(i,j);
        f(i,j)=stalagmite(input_vector);
    end
end

for i=1:iteration_count
    [input,fval(i)]=ga(@stalagmite,2);
    x_out(i)=input(1);
    y_out(i)=input(2);
    % clc
end
% Stop Stopwatch timer to clock the GA execution time
Study_1_Time=toc
figure(1)
subplot(2,1,1)
surf(xn,yn,-f)
xlabel('X')
ylabel('Y')
title('Case 1:Initial Study')
shading interp
hold on;
plot3(x_out,y_out,-fval,'marker','o','MarkerFaceColor','k')
subplot(2,1,2)
plot(-fval);
xlabel('Iterations')
ylabel('Function Max')

tic
% Study 2 With Bounds
for i=1:iteration_count
    [input,fval(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    x_out(i)=input(1);
    y_out(i)=input(2);
    %clc
end
Study_2_Time=toc
figure(2);
subplot(2,1,1)
hold on;
surf(xn,yn,-f)
xlabel('x')
ylabel('y')
title('Case 2: With Bounds')
shading interp
plot3(x_out,y_out,-fval,'marker','o','MarkerFaceColor','k')
subplot(2,1,2)
plot(-fval);
xlabel('Iterations')
ylabel('Function Max')

tic
%Study 3 : With Increased Population = 300

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

for i=1:iteration_count
    [input,fval(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.1;0.1],[],[],options);
% ga syntax[x,fval]=ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon,options) 
% Using options in GA to define the population
    x_out(i)=input(1);
    y_out(i)=input(2);
    %clc
end
Study_3_Time=toc;
figure(3)
subplot(2,1,1)
hold on
surf(xn,yn,-f)
xlabel('x')
ylabel('y')
title('Case 3: With Increased Population =300','')
shading interp
plot3(x_out,y_out,-fval,'marker','o','MarkerFaceColor','k');
subplot(2,1,2)
plot(-fval);
xlabel('Iterations')
ylabel('Function Max')
Max_X=input(1)
Max_Y=input(2)
display(Study_1_Time)
display(Study_2_Time)
display(Study_3_Time)

Stalagmite Function

function[f]=stalagmite(input_vector)

x=input_vector(1);
y=input_vector(2);

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.*f1y.*f2x.*f2y);
% the value is negated to get the maximum value as the GA would find the minimum
end

Section 4 :

THE RESULTS!!

The Following are the results after running the above code :-

Output displayed on Command Window :-

Errors Faced:-

Error :-Stalagmite is not generated while running the function

Error due to typo in stalagmite equation coded in the Stalagmite function

Correction :-

Warnings Shown while executing GA :-

GA was running with the above warning but the program was executed.

Inference :-

You can apply the genetic algorithm to solve problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear.

Table1 : Comparison of Classical Algorithm vs Genetic Algorithm

Classical Algorithm	Genetic Algorithm
Generates a single point at each iteration. The sequence of points approaches an optimal solution.	Generates a population of points at each iteration. The best point in the population approaches an optimal solution.
Selects the next point in the sequence by a deterministic computation.	Selects the next population by computation which uses random number generators.

---------End--------