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 and also explain the syntax for ga in MATLAB
3. Plot graphs for all 3 studies and for F maximum vs no. of iterations.

Objective:-

Write the given function with the name Stalagmite to optimize it and find its maximum value using genetic algorithm and make 3 cases:

1) Unbounded region

2) Bounded region

3) Increase in size of population.

Theory:-

Stalagmite :-

1. Stalagmites are thin piles of mineral deposits that have fallen from the roof to the floor of a cave. They're sometimes connected to the stalactites that dangle down from the top.
2. Stalagmite function are those function with which we find maximum values over stalagmite type of surface using optimization.
3. In MATLAB genetic algorithm (ga) is used to optimize the function.

Genetic Algorithm :-

Genetic Algorithm is a search based optimization technique based on Charles Darwin ‘s Genetic and natural selection Theory. Optimization techniques are the techniques used to discover the best solution out of all the possible solutions available under the constraints present. The genetic algorithm is one such optimization algorithm built based on the natural evolutionary process of our nature.

The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals 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. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.

This flow chart outlines the main algorithmic steps.

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. The selection is generally stochastic, and can depend on the individuals' scores.
• Crossover rules combine two parents to form children for the next generation.
• Mutation rules apply random changes to individual parents to form children.

Below are the different phases of the Genetic Algorithm:

1. Initialization of Population(Coding)

• Every gene represents a parameter (variables) in the solution. This collection of parameters that forms the solution is the chromosome. Therefore, the population is a collection of chromosomes.

Chromosomes are often depicted in binary as 0’s and 1’s, but other encodings are also possible.

2. Fitness Function

• We have to select the best ones to reproduce offspring out of the available chromosomes, so each chromosome is given a fitness value.
• The fitness score helps to select the individuals who will be used for reproduction.

3. Selection

• This phase’s main goal is to find the region where getting the best solution is more.
• Inspiration for this is from the survival of the fittest.

Fitness Values and Best Fitness Values

The fitness value of an individual is the value of the fitness function for that individual. The best fitness value for a population is the smallest fitness value for any individual in the population.

4. Reproduction

Generation of off springs happen in 2 ways:

• Crossover
• Mutation

1. a) Crossover

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

1. b) Mutation

In a few new offspring formed, some of their genes can be subjected to a low random probability mutation. 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.

5. Convergence (when to stop)

Few rules which are followed which tell when to stop is as follows:

• When there is no improvement in the solution quality after completing a certain number of generations set beforehand.
• When a hard and fast range of generations and time is reached.
• Till an acceptable solution is obtained.

Syntax for Genetic Algorithm:-

• 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,Aeq,beq,lb,ub,nonlcon,intcon) or x = ga(fun,nvars,A,b,Aeq,beq,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.

MATLAB Code:-

STALAGMITE FUNCTION:-

Explanation:-

Writing Stalagmite function by giving input vector in x and y and at last “f” have negative sign because “ga” finds minimum value so by reversing the function we can find maximum value of the function.

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

PROGRAM FOR FINDING OPTIMUM VALUE OF STALAGMITE FUNCTION BY 3 DIFFERENT CASES

Explanation:-

Preparing the data by giving the inputs in x and y ranging from 0 to 0.6 with 150 difference between them. Running the “ga” for 50 times to get the optimum result. And mesh of these two vectors is prepared using mesh command.

clear all
close all
clc
 
% input
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_space = 50;
 
% forming 2d array
[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

Explanation:-

• Case 1 is statical study with unbounded inputs i.e.,there is no search space is defined.
• Plotting meshgrid with stalagmite function, here stalagmite function is plotted with negative sign to plot the surface upside down to get maxima of function.
• tic/toc command is used to get search time for result.
• Shading interp is used to remove lines of meshgrid.

%Case1:- Unbounded
tic
for i=1:num_space
    [results,fopt(i)]=ga(@stalagmite,2)
    xopt(i) = results(1)
    yopt(i) = results(2)
end
study_time1=toc
figure(1)
subplot(2,1,1)
surfc(xx,yy,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',4,'markerfacecolor','r');
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('f maximum')
title('Unbounded inuts')

Explanation:-

Case 2 is statical study with bounded inputs i.e.,search space is defined to ‘ga’ by providing upper and lower limit. Syntax for ‘ga’ for limits has been given above. And plotting the surface as above.

%Case2:- Statical study with bounded inputs
 
tic
for i=1:num_space
    [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(xx,yy,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('f maximum')
title('bounded inputs')

Explanation:-

Case 3 is statical study with increase in size of population using optimoptions command. Here, large search space is provided which increases possibility to find maximum value of function but it increases time for evaluation.

%Case3:- Statical study with increase in size of population.
 
tic
options=optimoptions('ga')
options=optimoptions(options,'populationsize',250)

for i=1:num_space    [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(xx,yy,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('f maximum')
title('increase in size of population')

Result:-

• Matlab Code for stalagmite function and for finding its maximum value has been written and shown above.
• Syntax for Genetic Algorithm and its explanation has been given above.
• Plots of 3 different cases:-

Case 1:- Unbounded inputs

Time taken for searching in case 1:-

Case2:- Bounded inputs

Time taken for study in case2:-

Case 3:- Increase in size of population

Time taken for study in case 3:-