Week 4 - Genetic Algorithm

Genetic algorithm to predict maxima and minima of a stalagmite deposition.

“Stalagmite is an upward growing mound of mineral deposits that have precipitated from water dripping onto the floor of a cave.”

In this project we will try to define a function to plot the surface of a stalagmite deposition as well as use genetic algorithm to find the local maxima and minima of the points to find out where we have the highest and lowest amount of deposition in our defined area.

We start off with defining our ‘x’ and ‘y’ values to define an array of values that are input to our function. We then use the ‘meshgrid’ command to form a 2-D array to define our floor onto which the deposition has occurred.

We define a function named ‘stalagmite’ using the equation given below to form a general pattern of a stalagmite deposition.

Here f(x,y) defines the peak of deposition over a point (x,y).

We form a loop of values to run from the first to the last value of the complete array through the function, generate values and store them in a new array called ‘f(i,j)’.

Later we use the ‘surfc’ command to form a 3-D plot of out function and use the command ‘shading interp’ to make out surface smoother and remove the grids. The we use the ga command to perform a genetic algorithm solution to find local minima in our defined region.

As observed from the plot, we know out minima lies within the region where both x and y coordinated lie between 0.7 and 0.8.

Similarly we define another stalagmite function but we change the sign of the result to find the maxima of our point and we use that function again for our genetic algorithm solution.

After doing this and giving the limits again we run the function to find our plot and the values given below.

Genetic algorithm:

It is a method for solving constrained and unconstrained optimization problems that are based on natural selection (gaussian curve) which drives biological evolution.

It repeatedly modifies a population of individual solutions. At each step the genetic algorithm selects ‘parents’ at random which produce ‘children’. This is how they evolve into new values.

Used for discontinuous, non differential, stochastic or highly non linear problems.

the genetic algorithm works in three steps:

1. Selection process. (selecting parents)
2. Crossover rules. (combining parents to form children)
3. Mutation rules. (apple changes to parents to form children)

These take place the following way:

Selection process:

Create a random initial population.

Crossover:

• Compute raw fitness scores and scale them to usable values. (expectation values).
• Select parents based on expectations and select elites with the lowest fitness values to pass on to the next generation as is.
• Children are either produced by mutation of a single parent or combination of two vector elements of parents.
• Replace parents with children.

Stop:

The algorithm stops when one of the stopping criteria is met which could be anything from number of generations to constraint tolerance values.

Syntax:

[x fval]=Ga(func,vars,A,b,Aeq,beq,lb,ub,nonlcon)

X gives the coordinates of the minima found by ga function and fval gives the value of the minima at that point.

Func is the function that defines the whole plot.

Vars is the number of variables in our function.

A and b values are arrays that satisfy A*x<=b.

Aeq and beq are arrays that satisfy Aeq*x=beq.

Lb and ub are lower and upper bound for our coordinates to narrow down our search region.

Nonlcon is a function defining the non linear constraints in out plot (if any).

Stopping criteria:

1. When there has been no improvement in the population for X iterations.
2. When we reach an absolute number of generations.
3. When the objective function value has reached a certain pre-defined value.

Errors faced:

1. The function was not written properly which led to a miscalculation of values. This was countered by adding separate smaller variables to each part of the function and then multiplying them together to make everything cleaner and easier to debug.
2. The ga function was run as is without adding and variable values or bounds which led to calculation of minima in the wrong region where the operation used to be terminated at a wrong value because of function tolerance. This was countered by adding upper and lower bounds to the input variables so the algorithm is performed to find the minima in a specified region which is known to have the global minima.