Week 4 - Genetic Algorithm

GENETIC ALGORITHM USING MATLAB

AIM- Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function. Explain the concept of genetic algorithm and the syntax for GA. Plot graphs for all 3 studies and for F maximum vs no. of iterations.

OBJECTIVES-

1. Explain the concept of genetic algorithm
2. Write a code in MATLAB to optimise the stalagmite function.
3. Find the global maxima of the function.
4. Plot graphs for all 3 studies and for F maximum vs no. of iterations.

THEORY-

The genetic algorithm is inspired by the process that drives biological evolution. The process of evolution starts with the selection of fittest individuals from a population. Then they produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found. And this is the main working principle for the algorithm because at each step, the genetic algorithm selects randomly 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 be applied to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear.

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.

Crossover rules combine two parents to form children for the next generation.

Mutation rules apply random changes to individual parents to form children.

PROCESS OF NATURAL SELECTION:

• This process starts with selection of fittest individual form a given set of population.
• They produce offsprings which inherit the characteristic of the parents and will be added to next generation.
• If the parents are fit enough, their offsprings will be better than their parents and will have better chances of surviving.
• This process keeps on iterating and at the end a generation of fittest individuals will be obtained.
• This whole notion can be helpful in search problems.
• We select a set of solutions to a problem and sort out a set of best ones out of them. This will eventually narrow down to one best solution that gives optimum results for the given problem.

There are five phases in gentic algorithm and are explained as below:

1. Initial population~ The problem intiates with a set of individuals which is called population. Each individual is a solution to the problem we want to solve. Each individual is characterized by a set of parameters called genes. Genes are joined into a string which yields us chromosome which is nothing but a solution.
2. FITNESS FUNCTION~ The fitness function determines how fit an individual is. It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on this score.
3. SELECTION PHASE~ The main objective of this phase is to select the fittest individual and let them pass their Gene onto the next generation.
4. CROSSOVER~ For each pair of parents to be mated, crossover point is chosen at random from within the genes. Offsprings are created by exchanging genes of parents among themselves until the crossover point is reached. The new offspring is then added to the population.
5. MUTATION~ In certain new offsprings formed, some of their genes can be subjected to mutation with low random probability. This implies that some of the bits in the bit string can be flipped.

TERMINATION- Finally, the algorithm terminates if the population has converged. Then, it is said that genetic algorithm has provided a set of solution to our problem.

PROCEDURE-

1. Write code for the stalagmite function.

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

2. Negative sign used maximizes the stalagmite function for our purpose of finding maxima with GA.
3. Write code to use stalagmite function defined to find the global maxima using MATLAB's in-built 'ga' function:

   clear all 
   close all
   clc 
   
   %defining the search space
   x = linspace(0,0.6,150);
   y = linspace(0,0.6,150);
   iterations = 50;
   [xx, yy] =meshgrid(x,y);
   
   %stalagmite function
   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
   
   %1st iteration - studying the statistical behaviour
   
   tic 
   for i=1:iterations
   [inputs , f_optimum(i)] = ga(@stalagmite,2);
   x_optimum(i) = inputs(1);
   y_optimum(i) = inputs(2);
   end
   
   iteration_1_time = toc
   
   %plotting
   
   figure (1)
   subplot(2,1,1)
   hold on
   surfc(xx,yy,f)
   shading interp
   plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
   title('Unbounded inputs')
   subplot(2,1,2)
   plot(f_optimum)
   xlabel('Iterations')
   ylabel('Function maximum')
   
   %2nd iteration with upper and lower limits
   
   tic
   for i=1:iterations
   [inputs , f_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
   x_optimum(i) = inputs(1);
   y_optimum(i) = inputs(2);
   end
   
   iteration_2_time = toc
   
   %plotting
   figure (2)
   subplot(2,1,1)
   hold on
   surfc(xx,yy,f)
   shading interp
   plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
   title('Bounded inputs')
   subplot(2,1,2)
   plot(f_optimum)
   xlabel('Iterations')
   ylabel('Function maximum')
   
   %3rd iteration - increasing the size of population
    
   options = optimoptions('ga');
   options = optimoptions(options,'populationsize',200)
   
   tic
   for i=1:iterations
   [inputs , f_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
   x_optimum(i) = inputs(1);
   y_optimum(i) = inputs(2);
   end
   
   iteration_3_time = toc
   
   %plotting
   figure (3)
   subplot(2,1,1)
   hold on
   surfc(xx,yy,f)
   shading interp
   plot3(x_optimum,y_optimum,f_optimum,'marker','o','markersize',5,'markerfacecolor','r')
   title('Bounded inputs with modified population size')
   subplot(2,1,2)
   plot(f_optimum)
   xlabel('Iterations')
   ylabel('Function maximum')​

4. The linspace command is used that defines x and y which vary from 0 to 0.6 with 150 divisions in between.
5. Meshgrid command is row vectors x and y are converted into matrices xx and yy.
6. For loop is used to define the input vectors required for stalagmite function.
7. Program is divided into three iterations and will be made to run individually.

1st iteration: The behaviour of the algorithm is studied by not defining the limits.

2nd iteration: The lower and upper limits are defined to find the boundaries within which the global maxima lies.

3rd iteration: the population size is increased to converge to the global maxima.

SYNTAX EXPLANATION FOR GA-

f_min = ga(@function,nvars,A,B,Aeq,Beq,LB,UB,nonlcon,intcon,options)

1. f_min is the local minima point.
2. @function is the stalagmite function to be called.
3. nvars shows the no of variables used.
4. A and B are used to indicate any kind inequalities that exist in the function. Aeq abd Beq are similar to it.
5. LB is lower bound, UB is upper bound.
6. nonlcon generates two vectors containing inequalities and equalities.
7. options is used to perform additional operations like increasing population size.