Challenge

Week 4.1 - Genetic Algorithm

RRishikesh Nanaware27 Aug 2023

AIM:To write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

THEORY:

1.Introduction to Optimization:

Optimization is the process of making something better. In any process, we have a set of inputs and a set of outputs as shown in the following figure.

Optimization refers to finding the values of inputs in such a way that we get the “best” output values. The definition of “best” varies from problem to problem, but in mathematical terms, it refers to maximizing or minimizing one or more objective functions, by varying the input parameters.

The set of all possible solutions or values which the inputs can take make up the search space. In this search space, lies a point or a set of points which gives the optimal solution. The aim of optimization is to find that point or set of points in the search space.

2.Genetic Algorithm:

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 to difficult problems which otherwise would take a lifetime to solve. It is frequently used to solve optimization problems, in research, and in machine learning.

What are GAs?

Nature has always been a great source of inspiration to all mankind. Genetic Algorithms (GAs) are search based algorithms based on the concepts of natural selection and genetics. GAs are a subset of a much larger branch of computation known as Evolutionary Computation.

GAs were developed by John Holland and his students and colleagues at the University of Michigan, most notably David E. Goldberg and has since been tried on various optimization problems with a high degree of success.

In GAs, we have a pool or a population of possible solutions to the given problem. These solutions then undergo recombination and mutation (like in natural genetics), producing new children, and the process is repeated over various generations. Each individual (or candidate solution) is assigned a fitness value (based on its objective function value) and the fitter individuals are given a higher chance to mate and yield more “fitter” individuals. This is in line with the Darwinian Theory of “Survival of the Fittest”.

In this way we keep “evolving” better individuals or solutions over generations, till we reach a stopping criterion.

Genetic Algorithms are sufficiently randomized in nature, but they perform much better than random local search (in which we just try various random solutions, keeping track of the best so far), as they exploit historical information as well.

Advantages of GAs:

GAs have various advantages which have made them immensely popular. These include −

Does not require any derivative information (which may not be available for many real-world problems).
Is faster and more efficient as compared to the traditional methods.
Has very good parallel capabilities.
Optimizes both continuous and discrete functions and also multi-objective problems.
Provides a list of “good” solutions and not just a single solution.
Always gets an answer to the problem, which gets better over the time.
Useful when the search space is very large and there are a large number of parameters involved.

Limitations of GAs:

Like any technique, GAs also suffer from a few limitations. These include −

GAs are not suited for all problems, especially problems which are simple and for which derivative information is available.
Fitness value is calculated repeatedly which might be computationally expensive for some problems.
Being stochastic, there are no guarantees on the optimality or the quality of the solution.
If not implemented properly, the GA may not converge to the optimal solution.

Basic Structure:

The basic structure of a GA is as follows −

We start with an initial population (which may be generated at random or seeded by other heuristics), select parents from this population for mating. Apply crossover and mutation operators on the parents to generate new off-springs. And finally these off-springs replace the existing individuals in the population and the process repeats. In this way genetic algorithms actually try to mimic the human evolution to some extent.

Each of the following steps are covered as a separate chapter later in this tutorial.

A generalized pseudo-code for a GA is explained in the following program −

GA()
initialize population
find fitness of population

while (termination criteria is reached) do
parent selection
crossover with probability pc
mutation with probability pm
decode and fitness calculation
survivor selection
find best
return best

GA Terminologies:

1.Fitness Function

The fitness function is the function you want to optimize. For standard optimization algorithms, this is known as the objective function. The toolbox software tries to find the minimum of the fitness function.

Write the fitness function as a file or anonymous function, and pass it as a function handle input argument to the main genetic algorithm function.

2.Indivisual:

An individual is any point to which you can apply the fitness function. The value of the fitness function for an individual is its score. For example, if the fitness function is

f(x1,x2,x3)=(2x1+1)2+(3x2+4)2+(x3−2)2,

the vector (2, -3, 1), whose length is the number of variables in the problem, is an individual. The score of the individual (2, –3, 1) is f(2, –3, 1) = 51.

An individual is sometimes referred to as a genome and the vector entries of an individual as genes.

3.Population:

A population is an array of individuals. For example, if the size of the population is 100 and the number of variables in the fitness function is 3, you represent the population by a 100-by-3 matrix. The same individual can appear more than once in the population. For example, the individual (2, -3, 1) can appear in more than one row of the array.

At each iteration, the genetic algorithm performs a series of computations on the current population to produce a new population. Each successive population is called a new generation.

4.Diversity

Diversity refers to the average distance between individuals in a population. A population has high diversity if the average distance is large; otherwise it has low diversity. In the following figure, the population on the left has high diversity, while the population on the right has low diversity.

Diversity is essential to the genetic algorithm because it enables the algorithm to search a larger region of the space.

5.Fitness Value

The fitness value of an individual is the value of the fitness function for that individual. Because the toolbox software finds the minimum of the fitness function, the best fitness value for a population is the smallest fitness value for any individual in the population.

6.Parents and Children:

To create the next generation, the genetic algorithm selects certain individuals in the current population, called parents, and uses them to create individuals in the next generation, called children. Typically, the algorithm is more likely to select parents that have better fitness values.

Syntax:

Following is the syntax used in GA.

1)x= ga(fun,nvars) finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun. where, fun- objective function and nvars-number of variables.

2) 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.)

3)x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values.

Where, A and b are A=[] and b=[] if no linear inequalities.

lb and ub are lower bound and upper bound. Lower bounds, and upper bound specified as a real vector or array of doubles.

nonlcon is a function that accepts a vector or array.

Intcon- integer variable vectors of positive integers.

options- Optimization options, specified as the output of optimoptions or a structure it helps in constraint tolerance by increasing the population size.

MATLAB CODE:

%Genetic Algorithm
close all
clear all
clc

�fining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[xx,yy] = meshgrid(x,y); 
num_cases = 80 ;

�lling stalagmite function 
for i = 1:length(xx)
    for j = 1:length(yy)
        input_vector(1) = xx(i,j);
        input_vector(2) = yy(i,j);
        f(i,j) = stalagmite(input_vector);
    end
end

%Study 1 - Statistical behavior
tic
for i=1:num_cases
    [inputs, fopt(i)] = ga(@stalagmite,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
 
end

study1_time = toc;
 
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title('Unbound inputs')
xlabel('X values')
ylabel('Y values')
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')

subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function maximum')

%Study 2 - Statistical behavior with upper and lower bounds
tic
for i=1:num_cases
    [inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end

 study2_time = toc;
 
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title('Bounded inputs')
xlabel('X values')
ylabel('Y values')
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function maximum')

%Study 3 - Increasing GA iterations
options = optimoptions('ga');
options = optimoptions(options,'populationSize',200);

tic
for i=1:num_cases
    [inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end

 study3_time = toc;
 
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
xlabel('X values')
ylabel('Y values')
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('Function maximum')

function [f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);

f1_x = (sin((5.1*pi*x)+0.5)).^6;
f1_y = (sin((5.1*pi*y)+0.5)).^6;

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

[f] = -(f1_x*f1_y*f2_x*f2_y);
end

EXPLANATIONS:

1.First we create our search space using linspace and meshgrid command. Then we call the stalagmite function using two for loops.

2.STUDY 1:-

After running ga function 80 times, we are getting the above plot. Notice that we are getting the optimum values of 'x' and 'y' outside the scope. Each iteration gives different optimum value. This is clearly not great solution.

Study 1 time:

In order to narrow down are search, we'll have to bound the values of x and y while using the ga function.

3.STUDY 2:-

Study 2 produces much better results than Study 1. It narrows down our search results to only 3 points. Still this is not the perfect solution. More number of iterations could produce better generation. Thus, in our next study, we will increase the number of iterations.

Study 2 time:

4.STUDY 3:-

Study 3 give us the best result of all three studies. The min. value is aprox -0.99999 .

Study 3 time:, nearly 4 times the study 1 time.

References:

https://in.mathworks.com/help/gads/some-genetic-algorithm-terminology.html

https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_quick_guide.htm

Week 4.1 - Genetic Algorithm

Ship work like this
in your own course.

Talk to a career counsellor

Ship work like thisin your own course.

Talk to a career counsellor

Ship work like this
in your own course.