Week 4.1 - Genetic Algorithm

AIM

1. To Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.
2. To explain the concept of genetic algorithm in your own words and also explain the syntax for ga in MATLAB.

THEORY

Stalagmite and Stalactite functions

These functions are mathematical functions which represents shapes similar to that of the stalagmite and stalactite functions.

A stalagmite function generally refers to the function with which we are generating values over a stalagmite kind of surface for finding out the local and global maxima and minima of that particular given function. In MATLAB we will use 'optimization' method to find these values.

Genetic Algorithum

The genetic algorithum is a technique for solving both constrained and unconstrained optimization problems that are based on natural selection, the process that drives biological evolution. The GA constantly modifies the population size of individual solution.

Phases in Genetic Algoritham

• Initialization of Population (Coding)

The code generates its random population of defined size and from that population the code evaluates the fitness of the members of the population according to which it forms new population based on no. of iterations performed.

• Fitness Function

It is that function which we have to optimize and its optimization is done with the help of number of generations which have been formed by the code accordance with the fitness value of each member generated, these fitness values are used for the reproduction of the children.

• Selection

The idea of the selection phase is to select the fittest individuals and let them pass their genes to the next generation. The main goal of this phase is to find the region where the chances of getting the best solution are more.

Inspiration for this is from the survival of the fittest.

It should be a balance between exploration and exploitation of search space.

GA tries to move the genotype to higher fitness in the search space.

Too strong fitness selection bias can lead to sub-optimal solutions.

Too little fitness bias selection results in unfocused search.

• Reproduction

Generation of offspring happen in 2 way:

Crossover

Mutation

A) Crossover

Crossover is the most significant stage in the genetic algorithm. During crossover, a random point is selected while mating a pair of parents to generate offspring.

There are 3 major types of crossover.

Single Point Crossover:

A point on both parents’ chromosomes is picked randomly, and designated a ‘crossover point’.

Two-Point Crossover: Two crossover points are picked randomly from the parent chromosomes.

Unifofm Crossover: In a uniform crossover, typically, each bit is chosen from either parent with equal probability.

B) Mutation

In a few new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This indicates that some of the bits in the bit chromosome can be flipped. Mutation happens to take care of diversity among the population and stop premature convergence.

Syntax for GA

x= ga(fun,nvars) finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun.

x= ga(fun,nvars,A,b) finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').

x= ga(fun,nvars,A,b,Aeq,beq) finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[] and b=[] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').

x= ga(fun,nvars,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables, x, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[] and beq=[] if no linear equalities exist.)

x= ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon) subjects the minimization to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)

x= ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.

x= ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values.

Program for Stalagmite Function

function A = 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);
A = -(f1x*f2x*f1y*f2y);
end

Program for Genetic Algorithm

%program on Genetic Algorithm(GA)
clear all
close all
clc

x = linspace(0,0.6,200);
y = linspace(0,0.6,200);
limit=60;

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

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

% case_study-1:Unbounded condition
tic
for i=1:limit
    [inputs,fopt(i)]=ga(@Stalagmite,2);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study1_time=toc

figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('X-axis')
ylabel('Y-axis')
shading interp
hold on;
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,"MarkerFaceColor",'r')
title('Case study-1 (unbounded)')
subplot(2,1,2)
plot(-fopt)
xlabel('No of Iterations')
ylabel('Maximum Function minimum')

% case_study-2: Adding bounding box
tic
for i=1:limit
    [inputs,fopt(i)]=ga(@Stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study2_time=toc

figure(2)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('X-axis')
ylabel('Y-axis')
shading interp
hold on;
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,"MarkerFaceColor",'r')
title('case study-2')
subplot(2,1,2)
plot(-fopt)
xlabel('No of Iterations')
ylabel('Maximum Function minimum')

%case_study-3
options=optimoptions('ga');
options=optimoptions(options,'populationsize',150)

tic
for i=1:limit
    [inputs,fopt(i)]=ga(@Stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study3_time=toc

figure(3)
subplot(2,1,1)
surfc(xx,yy,-f)
xlabel('X-axis')
ylabel('Y-axis')
shading interp
hold on;
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,"MarkerFaceColor",'r')
title('case study-3')
subplot(2,1,2)
plot(-fopt)
xlabel('No of Iterations')
ylabel('Maximum Function Values')

Program Explanation

• Program starts with basic commands of 'clear all','close all' and 'clc', then it stores 200 values of 'x' and 'y' using linspace command.
• 'limit' variable is used for running the 'ga' for 60 times in order to global maxima.
• Creating 2-D array of 'x' and 'y' using meshgrid command.
• After creating 2-dimensional array of 'xx' and 'yy', we assign the values to the variable 'input(1)' and 'input(2)' by using 'for' loop. Starting for loop from 1 to length of 'xx' array using counter 'i'. Then nested loop is created using the counter 'j'. saving the vlaues of xx and yy in the variable 'input_vector(1)' and 'input_vector(2)'.
• Finally calling the function 'Stalagmite' that contains the code for evaluating the function.

Case study-1: Unbounded

• Here the procedure is same as case-1, but additionally the ga syntax is used for mentioning the upper bound and lower bound.'input' is the array to store optimum values of the variable.

• Here the procedure is same as case study-2, but additionally we are providing a parameter of 'population size' with a value of 150.
• After specifying the 'polulation size' the ga searches more in depth of the defined search space and with increase in polulation size the genetic algorithm takes more time to compile the data.

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

Results

Time taken

Errors

• While running the program i have encountered some typing error and overcomed the errors by cross checking the program.

References

• https://riadalam323.medium.com/aim-genetic-algorithm-write-a-code-in-matlab-to-optimise-the-stalagmite-function-and-find-the-9a4373ffee93
• https://in.mathworks.com/help/gads/ga.html