Week 4.1 - Genetic Algorithm

genetic algorithm


clear all
close all
clc

%input parameters (1d array)
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_spaces=50;

%creating 2 d array
[xx,yy]=meshgrid(x,y);

%stalagmite function
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)=stalagmite(input_vector);
    end
end

%study 1 unbounded
tic
for i=1:num_spaces
    [results,fopt(i)]=ga(@stalagmite,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 bound
tic
for i=1:num_spaces
    [results,fopt(i)]=ga(@stalagmite,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')

%study 3 increased initial position
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')








stalagmite function:::


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

Aim:

to write the code in matlab to optimize the stalagmite function and find the global maxima of the function .

theory:

GA is a search based optimization technique based on the principle of genetic and natural selection.

optimization:

the action of making the best or most effective use of situation or resources. mathematically, speaking optimization is the minimization or maximization of the function subject to constraint on its variale.

the purpose of optimization is to achieve the best design relative is a set of criteria.

stalagmite function:

generally, refers to the functions with which we are generating values over a stlagmite kind of surface for finding out the local and global maxima and minima of the particular given function.

genetic algorithm (GA):

the genetic algorithm is a method of solving both constraint and un constraint optimization problem that is based on natural selection, the process that is derived from biological evolution.

it is commomly used to generate high quality solutions to optimization and search problem by solving on biologically inspired operations such as mutation, crossover and selection.

GA are search algorithm inspire by charles darwin theory of evloution in nature by the process of natural selection ,reproduction and mutation.

process of natural selection:

it start with the selection of fittest individual from a population. they produce offspring which inherit. the characteristics of parents as will be added to the next generations.

if the parents have better fitness,their offspring will be better than parents and a better chance of survive.

five phase are considered for GA:

1.initial population

the process begins with a set of individual which is called as population. each individual is a solution to the problem you want to solve.

2.fitness function

it is also know as evaluation function. it is evaluates how close a given solution is to the optimum solution of the desired problem. it determines the how fit a solution is.

3.selection:

the selection is based on the fitness score. individual with high fitness have more chance to be selected for reproduction.

4.crossover:

it is a important phase in the GA . for each pair of parents to be mated. offspring are created by exchanging the parents among themselves untill the crossover point is reached.

5.mutation:

a mutation is a change inthe sequence of algorithm. if the probability is very high the GA gets reduced to a random search. mutation is the part of the GA which is related to the exploration at the search space.

SYNTAX OF GA

1.x=ga(fun,nvars)

find the local unconstraint minimum , x is objective;fun,nvars is the dimension.

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

find the local minimum x to fun subject to a linear inequalities A*x=b.

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

find the local minimum x to fun subjects to a linear inequalities Aeq*x=beq and A*b<=b.

4.x=ga(fun,nvars,A,B,Aeq,beq,1b,ub)

5.x=ga(fun,nvars,A,B,Aeq,beq,1b,ub,non1con)

it subjects the minimization to constraints defines in non1con.the function accept x and returns vector c and ceq.

6.x=ga(fun,nvars,A,B,Aeq,beq,1b,ub,non1con,options)

it minimizes with the defaults optimizations parameter replaced by values in options.

7.x=ga(fun,nvars,A,B,Aeq,beq,1b,ub,non1con,intcon)

8.x=ga(fun,nvars,A,B,Aeq,beq,1b,ub,non1con,intcon,options)

it requires that the variables listed in intcon take integer values.

9.x=ga(problem)

it find the minimum for problem. where problem is in structure.

outputs:

10.[x,fval]=ga(_)

for any input argument, also returns the fval, the value of the fitness function at x.

11.[x,fval,exitfag,output]=ga(_)

an integer identifying the reason the algorithm terminates.

12.[x,fval,exitflag,output,population,stores]=ga(_)

whose rows are the final population and vector scores, the scores of the final population.

genetic algorithm procedures:

first we have to open the matlab and create a newscrpit for code. then write clear all, close all, clc to close and clear the previous work.

we have to initialize the value of x and y taking 150 values between the interval of 0 to 0.6. we also consider no of iterations num space=50.

we take a 2d array of x and y using a meshgrid command and store in input vectors.

now execute the another function with the help of for loop to produce the value. the function is stalagmite function.

now let us make our first study ;

we take number of iteration=num_space and we use the genetic algorithmfunction to calculate maxima of function. we store the output into results. here a GA is intialised in random population.

now we store the results in xopt and yopt. we need to plot the surface of x,y,-f to get the 3 d plot.

we use plot3 command to make a plot of optimum maxima.

to get a time bound we use tic toc command.

now let us make a study on bounded values;

let us specify the lower and upper bound of x and y in this case. GA is intialised withrandom population only.

then the same procedure is followed as first study with the change GA only.

let us make a third study with initial population and bounded values;

in this case, let us initial population which is default as 50 to 250.

then the same procedure is followed as first study with the change in GA only.

stalagmite function procedure:

we create another function called stalagmite function. here we take the output as -f. since GA minimize a given function. if -f is considered it automatically gives maxima.

time recorded:

study_time1=6.9870

study_time2=6.4756

study_time3=21.6163

study 1 output

study 2 output

study 3 output