Week 5 - Genetic Algorithm

Try to understand the concept of genetic algorithm by referring to various sources before you attend this challenge. Look out for information regarding stalagmite function and ways to optimise it.

• Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.
• Clearly explain the concept of genetic algorithm in your own words and also explain the syntax for ga in MATLAB in your report.
• Make sure that your code gives the same output, even if it is made to run several times.
• Plot graphs for all 3 studies and for F maximum vs no. of iterations. Title and axes labels are a must, legends could be shown if necessary.

THEORY

Optimization

Optimization is a decision-making process, it helps to find the best results under a set of prioritized criteria or constraints. It is a procedure which is executed iteratively by comparing various solutions till an optimum or satisfactory solution is found. These include maximizing factors such as productivity, strength, reliability, efficiency, utilization, etc.

Techniques available to perform Optimization

Deterministic Method

They use specific rules for moving one solution to another. In this technique, the output of the model is fully determined by the parameter values and the initial conditions. Example - Stress analysis of the component.

Stochastic Method

These are gaining popularity due to certain properties which deterministic algorithms do not possess. Stochastic models possess some inherent randomness, it is a probabilistic approach.

The procedure followed by any Optimization process

Genetic Algorithm

The genetic algorithm is one of the optimization processes. A genetic Algorithm (GA) is a search–based optimization technique based on the principles of Genetics and natural selection. It is frequently used to find optimal or near-optimal solutions.

The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that are based on natural selection, the process that drives biological evolution. 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 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.

Function Code :

CODE AND EXPLANATION :

• Firstly creating the mesh from the two vectors which will be acting as a search space to find the maxima of the function.
• Creating the mesh of these two vectors using the 'mesh' command and defining the number of iterations as 'num_cases' to iterate the values of the optimum values of the function.
• Now calculating the values of fitness function at each point of the mesh grid formed.
• Now creating the values of fitness function at each point of the mesh grid formed.
• Now creating its surface through 'surfc' command which will also provide the contour of the generated surfaces.
• While using surf applying the -ve sign to the function will generate the surface upside down which will be quite good to get the maxima of the function, as it will provide positive value for the maxima using the -ve sign.

• First, Linspace command is used to define x & y with 150 elements between zero and 0.6 including the bounds.
• Then num_cases is set which will be used as counter for iteration to 50
• Then a 2D grid is made using meshgrid command is created from x & y input tobe output to xx & yy
• Then for loop is used to solve the genetic algorithm for every element in the 2D mesh grid
• The length of rows & column (which have equal length) are used as counters
• Then the input vector is declared as ga requires input vector which is each value in the mesh grid
• Then output of stalagmite function is stored in matrix

• Then tic command is used to start a timer
• Then for loop bounded by the number of iterations is formed
• Then ga code is entered for unbounded statistical study which have the following format :
• [inputs, fopt] = ga(fun, nvars)
• Inputs represent the values of parameters x & y for which the function has the least value (fopt)
• fun - the function tobe optimized, in this case stalagmit nvars - the number of design variables, in this case only x & y are the variables tobe plotted
• Then smallest (minimum) value of the function for each iteration is output & its x & y coordinates which are stored in seperate variables
• Then 'toc' command is used to stop the timer and the output is stored in study_time1
• Then figure1 is plotted by the following steps-
• First subplot command is used to partition the plot window in order to draw more than one plot in the same window, two rows and one column are specified and then the position of each plot is selected
• Then hold on command is used to prevent plot for being removed
• The surfc command is used to plot contour with xx & yy value from the mesh grid as input and negative optimum value is used because we need to maximize the function
• Then x,y,& z axis are labelled
• Then shading interp is used to smoothen the function plot and to remove the grid lines
• Then plot 3 command is used to plot a point in 3D, here it will plot- fopt because we need the maximum value of the function not the minimum
• Then the graph title is selected
• Then fopt value of the function is plotted on the second plot in the second row
• Then its x & y axis are labelled

• Then the same study is made but this time it is bounded (has lower & upper limit) which requires the same commands and step excepts the ga command which have the following format :

[input, fopt] = ga(fun, nvars, A, b, Aeq, beq, lb, ub)

Inputs, fopt, fun & nvars are the same as study-1

A - Linear inequality constraints : real matrix, if there are none, then []

b - Linear inequality constraints : real vector, if there are none, then []

Aeq - Linear equality constraints - :- real matrix, if there are none, then []

beq - Linear equality constraints - real vector, if there are none, then []

lb - lower bounds, specified as a real vector or array [0;0]

ub - upper bounds, specified as a real vector or array [0.6;0.6]

The range of the genetic algorithm is bounded by introducing values for lower and upper bounds and hence the values of global maxima and the values of x & y will be within the defined search space in inputs

• Then increasing population size study was done which is the same as before but it had different ga code of :

• [inputs, fopt] = ga(fun, nvars, A, b, Aeq, beq, lb, ub, nonlcon, IntCon, options)

inputs, fopt, fun and nvars, A, b, Aeq, beq, lb, ub are the same as study-1 and study -2 respectivelly

nonlcon - nonlinear constraints, specified as a function handle or function name. If there are none then []

IntCon - Integer variables, specified as a vector of positive integers, if there are none, then []

Options - Optimization options, specified as the output of optimoptions or a structure.

1. the range of the genetic algorithm is bounded as in study-2 but to improove the accuracy, the commands optimoptions is introduced to increase the Population Size
2. then total time is computed
3. then using fprintf command the results are printed in the command windows
4. then the study time is printed
5. then x, y coordinate of the maximum optimum values are printed
6. then the optimum values of the function (maximum value) is printed which is calculated from the (negative mean) of the all iterations of the output value and the negative sign is used to get the maximum value
7. then the study time of the whole 3 studies combined is printed.

OUTPUT EXPLANATION

The above results show that the bounded samples with population size have an accurate solution. This is because the code shows the random samples which can start and end at random points.

To overcome the issue, the bounded samples method is used giving the lower and upper limits. (Therefore, it will take the values which are greater than the upper bound or less than the lower bound.)

This loop gives an output with different local maxima with bounded inputs. To conquer this problem, we need to increase the population size as it increases the probability to converge to a global maximum.

The global maximum of a function can be found by inverting the function. Find the minimum value of the inverted function, the negative of the minimum value will give the global maximum of the function.