Challenge

Week 4 - Genetic Algorithm

RRohit Bhargava3 Dec 2020

AIM:- To write a matlab programme to optimize the stalagmite function and find the global maxima of the function.

INTRODUCTION:- genetic algorithm (GA) is a high level process of natural selection that belongs to the larger class of evolutionary algorithms (EA). 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.

THEORY:-Optimization is the process that we will reference most often here. The optimizer operates similarly to a chess (or any gaming) computer. It needs to consider an immense number of possible moves as quickly as possible, remove the poor choices, and finish with the best possible move. At any point in time, there may be millions of combinations of moves available for the computer to consider, of which only a handful will be the best possible moves. Anyone that has played chess against a computer knows that the less time the computer has, the more likely it is to make an error.

In a genetic algorithm, a population of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotype) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.[2]

The evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated; the fitness is usually the value of the objective function in the optimization problem being solved. The more fit individuals are stochastically selected from the current population, and each individual's genome is modified (recombined and possibly randomly mutated) to form a new generation. The new generation of candidate solutions is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.

A typical genetic algorithm requires:

a genetic representation of the solution domain,
a fitness function to evaluate the solution domain.
A standard representation of each candidate solution is as an array of bits.[2] Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple crossover operations. Variable length representations may also be used, but crossover implementation is more complex in this case. Tree-like representations are explored in genetic programming and graph-form representations are explored in evolutionary programming; a mix of both linear chromosomes and trees is explored in gene expression programming.

Once the genetic representation and the fitness function are defined, a GA proceeds to initialize a population of solutions and then to improve it through repetitive application of the mutation, crossover, inversion and selection operators.

HOW GA WORKS:-

Outline of the Algorithm

The following outline summarizes how the genetic algorithm works:

The algorithm begins by creating a random initial population.
The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population. To create the new population, the algorithm performs the following steps:
1. Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
2. Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
3. Selects members, called parents, based on their expectation.
4. Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.
5. Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.
6. Replaces the current population with the children to form the next generation.
The algorithm stops when one of the stopping criteria is met.

Initial Population

The algorithm begins by creating a random initial population, as shown in the following figure.

In this example, the initial population contains 20 individuals. Note that all the individuals in the initial population lie in the upper-right quadrant of the picture, that is, their coordinates lie between 0 and 1. For this example, the InitialPopulationRange option is [0;1].

If you know approximately where the minimal point for a function lies, you should set InitialPopulationRange so that the point lies near the middle of that range. For example, if you believe that the minimal point for Rastrigin's function is near the point [0 0], you could set InitialPopulationRange to be [-1;1]. However, as this example shows, the genetic algorithm can find the minimum even with a less than optimal choice for InitialPopulationRange.

Creating the Next Generation

At each step, the genetic algorithm uses the current population to create the children that make up the next generation. The algorithm selects a group of individuals in the current population, called parents, who contribute their genes—the entries of their vectors—to their children. The algorithm usually selects individuals that have better fitness values as parents. You can specify the function that the algorithm uses to select the parents in the option.

The genetic algorithm creates three types of children for the next generation:

Eliteare the individuals in the current generation with the best fitness values. These individuals automatically survive to the next generation.
Crossover are created by combining the vectors of a pair of parents.
Mutation children are created by introducing random changes, or mutations, to a single parent.

The following schematic diagram illustrates the three types of children.

Mutation and Crossover explains how to specify the number of children of each type that the algorithm generates and the functions it uses to perform crossover and mutation.

The following sections explain how the algorithm creates crossover and mutation children.

Crossover Children

The algorithm creates crossover children by combining pairs of parents in the current population. At each coordinate of the child vector, the default crossover function randomly selects an entry, or gene, at the same coordinate from one of the two parents and assigns it to the child. For problems with linear constraints, the default crossover function creates the child as a random weighted average of the parents.

Mutation Children

The algorithm creates mutation children by randomly changing the genes of individual parents. By default, for unconstrained problems the algorithm adds a random vector from a Gaussian distribution to the parent. For bounded or linearly constrained problems, the child remains feasible.

The following figure shows the children of the initial population, that is, the population at the second generation, and indicates whether they are elite, crossover, or mutation children.

OBJECTIVE:-

1)To undertstand the concept of genetic algorithm.

2)To understand the syntax "ga" in matlab.

3) to find the global maxima of the stalagmite function in matlab.

MATLAB PROGRAMME:-

1) FUNCTION CODE:-

function [f]=stalagmite(inputs)
f1x=(sin(5.1*pi*inputs(1)+0.5)).^6;
f1y=(sin(5.1*pi*inputs(2)+0.5)).^6;
f2x=exp((-4*log(2)*(inputs(1)-0.0667)^2)/(0.64));
f2y=exp((-4*log(2)*(inputs(2)-0.0667)^2)/(0.64));
f=-(f1x*f1y*f2x*f2y);
end

2) MAIN CODE:-

close all
clear all
clc
%CONDITIONS
num_cases=50 
%1-d array
x=linspace(0,0.6,150);    % defining search space
y=linspace(0,0.6,150);
%2-d array
[xx, yy]=meshgrid(x,y);
%evaluating stalagmite func.
for i=1:length(xx)
 for j=1:length(yy)
    inputs(1)=xx(i,j);
    inputs(2)=yy(i,j);
%     inputs=[inputs(1),inputs(2)];
f(i,j)=stalagmite(inputs);          %calling of function
end
end

% case 1-statical behaviour| in unbounded condition 
       %time ga works
tic

for i=1:num_cases                      
    [input,fopt(i)]=ga(@stalagmite,2)   %tic-toc command for calculating the time
    xopt(i)=input(1)
    yopt(i)=input(2)
end
study_1_time=toc
 
%plotting
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('func_max')

%case 2-statical behaviour in bounded condition
tic

for i=1:num_cases
    [input,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
         xopt(i)=input(1)
    yopt(i)=input(2)
end
study_2_time=toc

    figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(fopt)
title('bounded inputs')
xlabel('iteration')
ylabel('func_max')


%case 3-statical behaviour in bounded condition with increased population size
options=optimoptions('ga')%calculating the optimum solution for 'ga' and saving in option(variable)
options=optimoptions(options,'populationsize',240)% increasing population size
    
tic

for i=1:num_cases
    [input,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
         xopt(i)=input(1)
    yopt(i)=input(2)
end
study_3_time=toc


    figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(fopt)
title('bounded inputs')
xlabel('iteration')
ylabel('func_max')

PROCEDURE:-

Step 1- Start with usual Clear and closing command to clear memory. than defines the search space with 2 variable x & y. For that, creates 1-dimensional array for x,y & use linspace command to provide 150 value between 0 to 0.6. After that I creates 2-dimensional array based on our 1-dimension array

Step 2- In next step, by using 'for loop', I define the Than I am creating an array called input_vectort input_vector2 (row vectors) for each value of x,y and save these value in

input_vector.

Step 3- Now, to calculate maxima, I am typing a new function in @stalagmite, by using the below formula-

And stored its value in 'GA' Function.

Than this function, is called in for loop & passing the number of variable as input. So, that 'for loop' will generate the data for plot.

NOTE:- Genetic Algorithm is actually based on Random sample, means it will start with random sample of inputs & based on inputs we evaluate the function, than comes on some natural selection & do mates & also cross-over & than creates a new generation which is better."But every time we run 'ga' code we get different results, which is not useful. 'To get beneficial results i am doing some changes in inputs and check compare the results.

I am doing three Studies to get desired output(maxima)

Step 4-

Study1- Statistical Behaviour After creating x,y variable(input variable), as it does not define the search space for 'ga',"ga' does not know its actual space and the value for x,y go beyond or below to 0.6 or 0.

For that I use num_cases=50, means I am going to run it 50 times.

Sub-Step 1- I use 'for loop' and run the code from 1 to 50 times. After that I call ga & use the new function which I created @stalagmite, pass 2 variable as input and store the output in GA_opt. And than I store the value of ix &y' in 'xopt & yopt'

Sub-Step 2- Now to visualize my output, i use surface command(surfc), shading command(shading interp) is used to get smooth plot(without grid lines). in new figure window(figurel), I also use tic-toc command to calculate the time taken for evaluation. I use subplot command for multiple plotting, 1st plot to show stalagmite function, and plotting the minimum value that 'ga' trying to predict, over 50 studies. 2nd plot for showing the number of iteration at x-axis and during each iteration value changes which represents as Function maxima on y-axis.

Results for study-1

Here on plotting stalagmite function, I am plotting the minimum value that 'ga' predicts, which is all over the place on graph, it happens due to random sample during each iteration the value changes. Also in command window, we can observe the time taken for iteration is (study_1_time = 4.6723)sec

Step 5- Study2- Statistical Behaviour(with upper & lower bound) Sub-Step 1- In this study, I setup the bound condition for the variables x&y, as it is going above & below the 0 & 0.6.

By using syntax 'ga' I am giving x&y the upper limit and lower limit to 0 to 1. I a doing so, because in previous study, it was observed from the graph that the optimum output lies all over the graph, so make it more clear and optimum, I am applying the boundary condition.

Results for study-2

Here from the graph, it is observed that the function predict minimum points is between 3peaks, it is much clear than Styudy-1 If look at graph y-axis minimum values lies between 0.4 & 0.6, it is much accurate, but still not clear. Also , we can observe the time taken for iteration is (study 2_time=6.1982)sec, which is more than the study-1

Study3 - Increasing GA Iterations Sub-Step 1- In addition with specifying bounds, I am also increasing initial population size. If population size is too small, we cannot find the global maxima, but we can find only local maxmia, which happens in study2. Following the same procedure as in study-2, and increase the population size to 240 and applying the constraint 'optimoptions' and save its values in variable 'options' to allow the ga to predict the optimum solution from 240 population size.

And plot graph for visual result

Results for study-3

Here from subblot-1, it shows maxima only lies around 1 peak Maxima lies at around the value 0.85 that ga predicts In this study it giving the optimum value, on increasing the number Of iteration and applying constraints, but it has its drawbacks, as ga slows down as it have more number of samples, to process and evaluate them for the function. It takes (study_3_time =22.5917)sec, which is 6times higher than the study.

Based on the research answer for following questions are:-

Stopping criteria-When there has been no improvement in the population for X iterations.

When we reach an absolute number of generations.

When the objective function value has reached a certain pre-defined value

Syntax for ga- ga(@stalagmite,2,[],[],[],[],[0;0],[11],[],[],options)

ga(fun,nvars,A,b,Aeq,beq,11),tibinonlcon,options)

ga - To find the minimum of function using Genetic Algorithm

fun - finds a local minimum to function

nvars - number of variables.

A - Linear Inequality Constraints,specified as a real matrix

b - Linear Inequality Constraints,specified as a real vector

Aeq - Linear equality Constraints,specified as a real matrix

beq - Linear equality Constraints,specified as a real matrix

lb - Lower Bound

ub- Upper Bound

nonlcon - Nonlinear Constraints, specified as function handle

options- Optimization options, specified as the output

Significance of running multiple iterations -

We do Multiple iteration is to get the Global maxima in desired range. The main motive of doing so is to get the only 1 desired optimum output which is required for given problem. .