Week 5 - Genetic Algorithm

Genetic algorithm (GA):- Genetic algorithm (GA) is a search based optimization technique based on the principles of genetic and natural selection. It is frequently used to find an optimal or near-optimal solution. It is frequently used to solve optimization problems in research and in machine learning.

How does GA work:-

Phases in Genetic Algoritham-

1. 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.

1.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.

1. 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.

1. Reproduction

Generation of offspring happen in 2 way:

Crossover

Mutation

1. 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.

1. 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

x = ga(fun,nvars)

x = ga(fun,nvars,A,b)

x = ga(fun,nvars,A,b,Aeq,beq)

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

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

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

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)

x = ga(problem)

[x,fval] = ga(___)

[x,fval,exitflag,output] = ga(___)

[x,fval,exitflag,output,population,scores] = ga(___)

Description

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.

x = ga(problem) finds the minimum for problem, a structure described in problem.

[x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.

[x,fval,exitflag,output] = ga(___) also returns exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.

[x,fval,exitflag,output,population,scores] = ga(___) also returns a matrix population, whose rows are the final population, and a vector scores, the scores of the final population.

Main code :-

close all
clear all
clc
%input
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_spaces=50;

%forming 2d array
[xx,yy]=meshgrid(x,y);
for i=1:length(x)
    for j=1:length(y)
        input_vector(1)=xx(i,j);
        input_vector(2)=yy(i,j);
        f(i,j)=stagalmite(input_vector);
    end
end
%study 1-unbounded
tic
for i=1:num_spaces
    [results,fopt(i)]=ga(@stagalmite,2)
    xopt(i)=results(1)
    yopt(i)=results(2)
end
study_time1=toc
figure(1)
subplot(2,1,1)
surf(x,y,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function maximum')
%study 2- bounded
tic
for i=1:num_spaces
    [results,fopt(i)]=ga(@stagalmite,2,[],[],[],[],[0;0],[0.6;0.6])
    xopt(i)=results(1)
    yopt(i)=results(2)
end
study_time2=toc
figure(2)
subplot(2,1,1)
surf(x,y,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function maximum')
%study3- increased initial population
tic
options=optimoptions('ga')
options=optimoptions(options,'populationsize',250)
for i=1:num_spaces
    [results,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options)
    xopt(i)=results(1)
    yopt(i)=results(2)
end
study_time3=toc
figure(3)
subplot(2,1,1)
surf(x,y,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function maximum')

function file (stalagmite) :-

function A = stalagmite(input_vector)
x=input_vector(1);
y=input_vector(2);
f1=(sin(5.1*pi*x+0.5)).^6;
f2=exp((-4*log(2)*((x-0.0667).^2))/0.64);
f3=(sin(5.1*pi*y+0.5)).^6;
f4=exp((-4*log(2))*((y-0.0667).^2)/0.64);
A =-(f1*f2*f3*f4);
end

Explaination : -

Took 'x' and 'y' as input matrix which are have 150 values from 0 to 0.6. Then made 2d array from x and y using meshgrid function.

Then started nested for loop to calculate stalagmite fuction fover each values and ended the for loop.

started study 1 for unbounded condition.

used tic toc command for finding a study time.

started a for loop for i= 1 to num_spaces (we had took num_spaces as 50 at starting of code)

used General algorythm to find fopt, xopt, yopt and then enf the loop.

took figure window 1 and plotted two plots in one figure using subplot command. plotted x,y and -f using surf function. we didn't want shading on surface plot so we used a shading interp. then hold on for another plot of xopt, yopt and -fopt. and also we use marker 'o' to show global maxima on the figure. Then another subplot in same figure window of -fopt with lable on x axis 'itretion' and y axis 'function maximum'.

we took -f (minus f) so we can show the maximum value because f is use for the optimum value.

and we create another fuction file for the stalagmite function. here we take the ouput as -f since ga only minimises a given function.so if -f is considered it automatically gives us the maxima.

we wrote code for study 2 bounded condition where we specify the lower and upper bounds of x and y and, study 3 for increased initial population we increase our initial population which is default as 50 to 250 and the rest part is same way as we write for the study 1.

Output :-

Study 1 :-

study_time1 =

3.5857

Study 2 :-

study_time2 =

4.2510

Study 3 :-

study_time3 =

12.7802