Week 5 - Genetic Algorithm

Introduction

Genetic algorithm optimization is a process that applies the principles of natural selection and evolution to find an optimal solution to a problem.

Yes, that is the general idea behind the genetic algorithm. By selecting individuals with high fitness scores to form the next generation and recombining their genetic material to produce offspring, the algorithm aims to generate solutions with even better fitness scores over time. Through repeated cycles of selection, recombination, and mutation, the genetic algorithm can converge on a population of highly fit individuals, which may represent near-optimal or optimal solutions to the problem.

The genetic algorithm is a versatile optimization method that can be applied to a wide range of problems, including those that are challenging for traditional optimization techniques. Its ability to explore a large, diverse search space and its ability to handle complex, non-linear objective functions make it a suitable method for solving many real-world optimization problems. Additionally, the genetic algorithm's probabilistic nature and its use of heuristics rather than derivatives or gradients can make it more robust and effective in handling problems with noisy, multi-modal, or non-differentiable objective functions. However, it's important to note that the genetic algorithm can be computationally intensive and may be less efficient than other optimization methods for simple or well-behaved problems.

Parent Selection

Parent selection refers to the process of choosing which individuals from a population will be used to produce offspring for the next generation. This is an important step in the algorithm because it determines the genetic diversity and overall quality of the population. Common methods for parent selection include tournament selection, roulette wheel selection, and rank selection. The choice of parent selection method can have a significant impact on the efficiency and convergence of the genetic algorithm.

Using the principles of natural selection and evolution to produce better and better individuals, the genetic algorithm aims to find a solution that optimizes a certain fitness function, and parent selection plays a crucial role in this process by preserving desirable traits and recombining them to create new, potentially better solutions. Through multiple generations, the genetic algorithm is able to explore the solution space and converge on the optimal solution.

The genetic algorithm is a global optimization method, which means that it searches the entire solution space for the best solution, rather than being stuck in a local optimum. This makes it well-suited for a wide range of problems, including optimization in machine learning, engineering design, financial planning, and many others.

STEPS

The main steps of the process are:

1. Initialization: randomly generating an initial population of solutions (individuals) to a problem.

2. Evaluation: assigning a raw fitness score to each individual in the population based on how well they solve the problem.

3. Scaling: converting the raw fitness scores into expectation values to represent the likelihood of an individual being selected for mating.

4. Selection: selecting individuals based on their expectation values to form a mating pool for the next generation.

5. Crossover: recombining the genetic material of the selected individuals to form new offspring solutions.

6. Mutation: introducing random variations in the offspring solutions to add diversity to the population.

7. Repeat steps 2 to 6 until a satisfactory solution is found or a termination condition is met.

8. Output: returning the best solution found as the result of the genetic algorithm.
   Genetic algorithm syntax:

1. [x, fval] = ga(fun, nvars, A ,b, Aeq, beq, Lb, Ub, nonlcon, IntCon, options)
2. The above syntax represents the Genetic algorithm syntax.
3. fun - represents the function to be optimized.
4. nvars - represents the number of variables of the function to be optimized.
5. A & b - Linear inequality constraints (A = Real Matrix, b = Real vector).
6. Lb & Ub - Linear equality constraints (A = Real Matrix, b = Real vector).
7. nonlcon - Ninlinear constraints.
8. options - Optimization options.
9. Intcon - Indices Integers variables.

INPUT FUNCTION

`f(x,y)=f_(1,x)*f_(2,x)*f_(1,y)*f_(2,y)`

`f_(1,x)=[sin(5.1pi*x+0.5)]^6`

`f_(1,y)=[sin(5.1pi*y+0.5)]^6`

`f_(2,x)=exp[-4ln(2)*(x-0.0667)^2/0.64]`

`f_(2,y)=exp[-4ln(2)*(x-0.0667)^2/0.64]`

Function Code for stalagmite function

function f= stalgamite_fun(input)
x=input(1);
y=input(2);

f1x=(sin(((5.1*pi).*x)+0.5)).^6;
f1y=(sin(((5.1*pi).*y)+0.5)).^6;

f2x=exp((((x-0.0667).^2).*(-4*log(2)))./0.64);
f2y=exp((((y-0.0667).^2).*(-4*log(2)))./0.64);

f=-(f1x.*f1y.*f2x.*f2y);
end.

Main Code

clear all
close all
clc

%defining working space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_cases=50;

% creating 2d mesh
[xx,yy]=meshgrid(x,y);

for i=1:length(xx) %150 times
    for j=1:length(yy)
        input_vector(1)=xx(i,j);
        input_vector(2)=yy(i,j);
        f(i,j)=stalgamite_fun(input_vector);
    end
end

 surfc(x,y,f)
 %contour(x,y,f)
 shading interp
 % Study1- Unbounded statistical behaviour
 
 tic

for i = 1:num_cases
    [input1, fopt1(i)] = ga(@stalgamite_fun, 2);
    xopt1(i) = input1(1);
    yopt1(i) = input1(2);
end


figure(2)
subplot(2,1,1)
hold on
surfc (x,y,-f)
shading interp
plot3(xopt1,yopt1,-fopt1,'marker','o','markersize',5,'markerfacecolor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(-fopt1)
xlabel('no. of iterations');
ylabel('function max');
study_time1=toc;

% second case (bounded inputs)
tic
for i = 1:num_cases
    [input2,fopt2(i)]= ga(@stalgamite_fun, 2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt2(i)=input2(1);
    yopt2(i)=input2(2);
end

figure(3)
subplot(2,1,1)
hold on
surfc (x,y,f)
shading interp
plot3(xopt2,yopt2,fopt2,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(fopt2)
xlabel('no. of iterations');
ylabel('function max');

study_time2=toc;

% third case ( increasing iterations) 
tic
options=optimoptions('ga');
options=optimoptions(options,'populationsize',170);
for i = 1:num_cases
    [input3,fopt3(i)]= ga(@stalgamite_fun, 2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt3(i)=input3(1);
    yopt3(i)=input3(2);
end

figure(4)
subplot(2,1,1)
hold on
surfc (x,y,f)
shading interp
plot3(xopt3,yopt3,fopt3,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(fopt2)
xlabel('no. of iterations');
ylabel('function max');

study_time3=toc;

Now calling the stalagmite function with 2D matrix grid as a input.

• Creating the two for loops so to traverse through each row providing the present values as an input to the stalagmite function.
• The x and y values at the particular grid points are taken as the inputs for the stalagmite function.
• The x and y values are assigned to the variable 'input vector( )'.

Case-1 Unbounded:

There are no upper and lower constraints in this case, as it results in the values being chosen at random, which may even be further than the region under examination.

1. The num_case represents the number of times the for loop is repeated to increase the chances of getting desired results with lower error or deviation.
2. The inputs_u in the LHS of the command represents the x and y values of the optimized output.
3. The optimal values from the stalagmite function are represented by fopt_u.
4. The x and y coordinates for the 50 examples are stored inside the xt() and yt() parameters which are utilized to generate the graphs.
5. There are two variables in the stalagmite function so the ga has 2 in its syntax.
6. Tic before the loop and toc after the loop are added to output the time taken by the part of the program to execute.
7. Using the ga( ) the genetic algorithm is called for the stalagmite function with two variables.
8. Now the output are plotted using the plot3( ) and plot commands with the subplot option so to arrange the plots in single figure with m/n rows(2/1).
9. 
10. The first plot represents the xt along x-axis, yt along y-axis and optimized maximized output along z-axis.
11. The second plot represents the optimized values along y-axis for the 50 number of iteration along x-axis.
12. The respective labelling are made.
13. The marker in the plot syntax is used to add the markers at the value options.
14. Markersize defines the size of the marker i.e. 5.
15. xlabel, ylabel and zlabel are for labelling the respective axis.
16. tilte command is used for adding the title to the plot.
17. The outline body of this code remains same while the syntax of the GA has some additional inputs.

-----------------------------------------------------------------------------------------------------

Case-2 Bounded:

1. In this case the lower and upper bounds are defined so as to define the selection workspace which compared to previous one was a random selection.
2. Here we can consider the case to be more practically confined to the area under research.
3. This is done to narrow the initial selection area.
4. This case is very similar to the case-1 but only differs in the area of selecting the random population.
5. This code is also much similar to the case-1 but differs in the syntax extension of the genetic algorithm command function, as here the upper and lower bounds are also defined.
6. 
7. The yellow marking represents the syntax of Genetic algorithm defining the lower and upper bounds in format ([lower x;lower y], [Upper x; Upper y]).
8. Here as we know the x and y-values start from zero and end at 0.6 so the upper and lower bounds are defined in a way to fully cover the area of the meshgrid generated.
9. Here the coding is similar as that of the case-1 but differ only in the above defined terms.

-----------------------------------------------------------------------------------------------------

Case-3 Bounded with modified population size:

1. Here along defining the lower and upper bounds the size of the random selection of the population is redefined.
2. This is done so to have more number of initial samples which will inturn results in having the higher chance of getting the more accurate optimized output.
3. Here the options command is used in altering the inbuilt default settings of the genetic algorithm function.
4. First the options command is used to define the Function which is being altered, here as genetic algorithm is being altered adding it to the options syntax.
5. Second time the option command is used to define the parameter that need to changed in predefined function, here the population size needs to be altered with new value as 170 which is defined in the second part of second option command.
6. Now the changed settings needs to be used in the GA so to specify in which the case it should be used the options command is used in the syntax of the GA representing that this case needs to consider the altered default settings and no the other, this is highlighted in the code below.
7. 

Results and discussion:

1. Output of the stalagmite function (Actual and Inverted):
2. 
   
   1. Used to find the global minima by using the genetic algorithm.
3. Case-1 Unbounded Optimized output:
   1. 
   2. Here in this case the algorithm choses random population without any boundaries resulting in more dispersed output.
   3. Here the optimized values are ranging from 0-1 which is not at all accurate.
   4. This case types cannot be used for this kind of function/problems.
   5. Here the algorithm is run for 50 times.
4. Case-2 Bounded Optimized output:
   1. 
   2. Here the algorithm selects the population in the region defined in the upper and lower bounds.
   3. Here the output/optimized results are more confined and near to the optmized value compared to case-1.
   4. It can be seen that the optimized values are much closer to the actual maximum value (0.7 - 1) compared to case-1 (subplot - 2).
   5. Here the algorithm is run for 50 times.
5. Case-3 Bounded with population modification Optimized output:
   1. 
   2. Here algorithm selects the population in the confined region with defined population size to improve the optimized value.
   3. By selecting more population we have higher chance of getting to the optimized solution as the population will cover more region or points in the confined region, which will be processed to achieve the optimized results.
   4. Here it can be seen that the obtained optimized results are very closer to the real maximum value (0.99999976-0.99999986).
   5. The values are very near to the optimized values compared to any of the previous cases.
   6. Here the algorithm is run for 50 times.
   7. The algorithm is run for 50 times because to ensure there is no variation in the output optimized values.
6. Stopping criteria:
   1. The stopping criterias for our function of Genetic algorithum are:
      1. Optimization terminated: maximum number of generations exceeded.
      2. Optimization terminated: average change in the fitness value less than options.FunctionTolerance.
   2. 

Conclusions:

1. The program is executed successfully to obtain the optimized result for the given Stalagmite function.
2. Three cases are into consideration for the study/execution:
   
   1. Case-1 Unbounded:
   2. Here the results obtained are completely random and out of the research space.
   3. Here the solution is improper as the algorithum selects the populations randomly which may even be outside the area under study.
   4. So this is not the proper way to use the Genertic algorithm as it does not provide any accurate optimized output.
   5. Case-2 Bounded:
   6. Here the results are significantly improved as compared to the unbounded case beacause the upper and lower bounds are defined so the population selected is in the area under study which enhances the chances of getting the optimized output too the function.
   7. But this is also not much efficient way to optimize the function even though it is much closer to the optimized values compared to the case-1.
   8. Case-3 Boundded with modified population size:
   9. Here the results are significantly accurate with 0.000014% Error.
   10. Here we get the Global maxima of 0.85.
3. As the case-3 is giving the most accurate result it may be concluded that, to obtain the more accurate solution we must have higher population and the bounds depecting the boundaries of the area under study/interest must be defined properly.
4. Also defining more boundary constraints is helpful in many of the cases.