Week 5 - Genetic Algorithm

What is Genetic Algorithm?

• A genetic algorithm is a search-based algorithm used for solving optimization problems that solve difficult problems that would take a long duration to solve. It has been used in various real-life applications such as data centers, electronic circuit design, code-breaking, image processing, and artificial creativity.
• Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover, and selection.
• Genetic Algorithms are search-based algorithms based on the concepts of natural selection and genetics. It is a subset of a much larger branch of computation known as Evolutionary Computation.
• The genetic algorithm is based on the genetic structure and behavior of the chromosome of the population. The following things are the foundation of genetic algorithms.
• Each chromosome indicates a possible solution. Thus the population is a collection of chromosomes.
• A fitness function characterizes each individual in the population. Therefore, greater fitness better is the solution.
• Out of the available individuals in the population, the best individuals are used to reproduce the next generation's offspring.
• The offspring produced will have features of both the parents and is a result of mutation. A mutation is a small change in the gene structure.

(Flow chart outlines for the main algorithmic steps)

Phases of Genetic Algorithm

Below are the different phases of the Genetic Algorithm:

1. Initialization of Population

• 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.
• Order of genes on the chromosome matters.
• 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.
• 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 an unfocused search.
• Thus, Fitness proportionate selection is used, also known as roulette wheel selection, as a genetic operator used in genetic algorithms to select potentially useful recombination solutions.

4. Reproduction

Generation of offspring happens in 2 ways:

• Crossover
• Mutation

(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 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’. Bits to the right of that point are exchanged between the two parent chromosomes.
• Two-Point Crossover: Two crossover points are picked randomly from the parent chromosomes. The bits in between the two points are swapped between the parent organisms.
• Uniform 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 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.

Function Equation:

The syntax for Genetic Algorithm :

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

Finds a local minimum x to function, 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,non1con

Subjects the minimization to the constraints defined in non1con. The function non1con 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,non1con,options

Minimizes with the default optimization parameters replaced by values in options. Set non1con=[] if no nonlinear constraints exist. Create options using optimoptions.

• x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,non1con,intcon) or x=ga(fun,nvars,A,b,Aeq,beq,lb,ub,non1con,intcon,options

Requires that the variables listed in intcon take integer values.

• x= ga(problem)

Finds the minimum for the problem, a structure described in problem.

• [x,val] = ga

For any previous input arguments, also returns fval, the value of the fitness function at x.

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

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(___)

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

Matlab code for Stalagmite Function:

Matlab code for Genetic Algorithm:

Outputs / Results:

Code Explanation:

• Firstly we start with creating a function file for the stalagmite function where we have four unknown variables f1x,f2x,f1y,f2yf1x,f2x,f1y,f2y. These variables are multiplied to obtain the value of f and a negative sign is used because the function has to be maximized,
• Now we input three basic commands i.e. clear all, close all, clc which clears all the previous data stored.
• Define the values of x and y from 0 to 0.6 with 150 values in between by using linspace command.
• As we need to plot a 3d plot we take the 2-dimensional array by using meshgrid command for x and y.
• Then a for loop is used for calculating the genetic algorithm for a every element in 2-dimensional meshgrid.
• Figure has to be plotted for stalagmite function by using surfc command a surface and contour plot is created which uses the column and row indices of the elements.
• Now for the first case study of unbounded statistical behavior we use a syntax for ga is [inputs,fopt]= ga(func,nvars). where func is function and nvars is no. of variable i.e x and y.
• Tic-Toc command is used to calculate the study time, Now before the for loop we provide the tic command which is used to start the timer.
• For loop is bounded by no. of iteration and the minimum value for the function of each iteration is obtained which is stored in separate variable.
• After completing the for loop (Toc) command is used to stop the timer and the study time is stored is stored in variable name study1.
• Subplot command is used in order to draw more than one figure in the same window
• Now a surfc command is used for plotting 3d plot with the xx and yy values from meshgrid and the negative fopt value to maximise the function and a shading interp command is used to obtain a smooth plotwhich removes the grid lines on the plot.
• By using xlablel,ylabel and zlabel command the axis name in denoted and using a title command a title is given to the plot.
• Now a plot3 command is used to plot the coordinates in the 3d space.
• Then again the the subplot and plot command is used to obtain the -fopt in the second plot of the same window.
• Now we have second study which is same as that of first study only the change is that in this study it is bounded with upper and lower bounds and the ga syntax used for this study is [inputs,fopt]=ga(func,nvars,A,b,Aeq,Beq,lb,ub)

Where A = Linear inequality constraints: real matrix

b = Linear inequality constraints: real vector

Aeq = Linear equality constraints: real matrix

beq = Linear equality constraints: real vector

lb = Lower Bound

ub = Upper Bound

• The upper and lower bounds are bounded in this ga of bounded statistical study and hence the value of global maxima will be within the given bounds.
• Now the third study is carried out by modifying the size of the population and the ga syntax used [inputs,fopt]= ga(func,nvars,A,b,Aeq,Beq,lb,ub,non1con,intcon,options) here non1con = Non linear constraints which are specified as a function handle or function name, intcon=is a function that accepts a vector or array x and returns two arrays.
• Here after increasing the size of the population using option command we get the more accurate value of global maxima.

Conclusion:

• It can be concluded that by bounding the limits and increasing the population size we can increase the accuracy of genetic algorithm.
• An optimised stalagmite function and Global Maxima of the function is obtained by using Matlab.