Week 4 - Genetic Algorithm

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

OBJECTIVE:- Clearly expalin 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.

INTRODUCTION TO GENETIC ALGORITHM (GA):-

Optimization problems

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:

1. a genetic representationof the solution domain,
2. a fitness functionto 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.

Initialization

The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Often, the initial population is generated randomly, allowing the entire range of possible solutions (the search space). Occasionally, the solutions may be "seeded" in areas where optimal solutions are likely to be found. However, population sizes larger than necessary can waste valuable computational resources, and as such, several techniques have been proposed for selecting an appropriate number of individuals.^[3]

Selection

During each successive generation, a portion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected. Certain selection methods rate the fitness of each solution and preferentially select the best solutions. Other methods rate only a random sample of the population, as the former process may be very time-consuming.

The fitness function is defined over the genetic representation and measures the quality of the represented solution. The fitness function is always problem dependent. For instance, in the knapsack problem one wants to maximize the total value of objects that can be put in a knapsack of some fixed capacity. A representation of a solution might be an array of bits, where each bit represents a different object, and the value of the bit (0 or 1) represents whether or not the object is in the knapsack. Not every such representation is valid, as the size of objects may exceed the capacity of the knapsack. The fitness of the solution is the sum of values of all objects in the knapsack if the representation is valid, or 0 otherwise.

In some problems, it is hard or even impossible to define the fitness expression; in these cases, a simulation may be used to determine the fitness function value of a phenotype (e.g. computational fluid dynamics is used to determine the air resistance of a vehicle whose shape is encoded as the phenotype), or even interactive genetic algorithms are used.

Genetic operators

The next step is to generate a second generation population of solutions from those selected through a combination of genetic operators: crossover (also called recombination), and mutation.

For each new solution to be produced, a pair of "parent" solutions is selected for breeding from the pool selected previously. By producing a "child" solution using the above methods of crossover and mutation, a new solution is created which typically shares many of the characteristics of its "parents". New parents are selected for each new child, and the process continues until a new population of solutions of appropriate size is generated. Although reproduction methods that are based on the use of two parents are more "biology inspired", some research^[4][5] suggests that more than two "parents" generate higher quality chromosomes.

These processes ultimately result in the next generation population of chromosomes that is different from the initial generation. Generally the average fitness will have increased by this procedure for the population, since only the best organisms from the first generation are selected for breeding, along with a small proportion of less fit solutions. These less fit solutions ensure genetic diversity within the genetic pool of the parents and therefore ensure the genetic diversity of the subsequent generation of children.

Opinion is divided over the importance of crossover versus mutation. There are many references in Fogel (2006) that support the importance of mutation-based search.

Although crossover and mutation are known as the main genetic operators, it is possible to use other operators such as regrouping, colonization-extinction, or migration in genetic algorithms.

It is worth tuning parameters such as the mutation probability, crossover probability and population size to find reasonable settings for the problem class being worked on. A very small mutation rate may lead to genetic drift (which is non-ergodic in nature). A recombination rate that is too high may lead to premature convergence of the genetic algorithm. A mutation rate that is too high may lead to loss of good solutions, unless elitist selection is employed. An adequate population size ensures sufficient genetic diversity for the problem at hand, but can lead to a waste of computational resources if set to a value larger than required.^[3]

Heuristics

In addition to the main operators above, other heuristics may be employed to make the calculation faster or more robust. The speciation heuristic penalizes crossover between candidate solutions that are too similar; this encourages population diversity and helps prevent premature convergence to a less optimal solution.

Termination

This generational process is repeated until a termination condition has been reached. Common terminating conditions are:

• A solution is found that satisfies minimum criteria
• Fixed number of generations reached
• Allocated budget (computation time/money) reached
• The highest ranking solution's fitness is reaching or has reached a plateau such that successive iterations no longer produce better results
• Manual inspection
• Combinations of the above

PROBLEM STATEMENT:-

`f=f1*f2*f3*f4`

where

`f1=[sin(5.1*pi*x+0.5)]^6`

`f2=[sin(5.1*pi*y+0.5)]^6`

`f3=exp[-4*log(2)*((x-0.0667)^2/0.64)]`

`f4= exp[-4*log(2)*((y-0.0667)^2/0.64)]`

where x & y are the two variables

We have to maximize this function using matlab, for which we will be using the function

`F=1/(1+f)`

PROGRAM FOR PLOTTING MAXIMA:-

%Defining the workspace
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);

%Creating a 2 dimensional array
[xx yy]=meshgrid(x,y);

%Evaluating stalgamite 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)=stalgamite(input_vector);
    end
end

figure(1)
surf(xx,yy,F)
shading interp
[inputs,fval]=ga(@stalgamite,2);

% Case study 1
numcase=50
tic
for i=1:numcase
    [inputs,fopt(i)]=ga(@stalgamite,2)
    xopt(i)=inputs(1)
    yopt(i)=inputs(2)
end
study_time1=toc
%plotting
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,F)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',3,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iteration')
ylabel('F maximum')

%case_study2 giving the lower and upper bound conditions

tic
for i=1:numcase
    [inputs,fopt(i)]=ga(@stalgamite,2,[],[],[],[],[0;0],[1;1])
    xopt(i)=inputs(1)
    yopt(i)=inputs(2)
end
study_time2=toc
%plotting
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,F)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',3,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iteration')
ylabel('F maximum')

% study-3 Increasing the ga Iteration
options=optimoptions('ga')
options=optimoptions(options,'populationsize',170)

tic
for i=1:numcase
    [inputs,fopt(i)]=ga(@stalgamite,2,[],[],[],[],[0;0],[1,1],[],[],options)
    xopt(i)=inputs(1)
    yopt(i)=inputs(2)
end
study_time3=toc
%plotting
figure(4)
subplot(2,1,1)
hold on
surfc(x,y,F)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',3,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iteration')
ylabel('F maximum')

PROGRAM OF FUNCTION:-

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

GRAPH OF THE PROGRAM AND FOR ALL THE 3 STUDIES:-

STUDY 1

STUDY 2

STUDY 3

STEPWISE EXPLAINATION OF THE PROGRAM:-

Case study 1:- Here we will run the genetic algorithm number of times,(in this case 50 times) and will plot the ‘xopt’, ’yopt’ and ’fopt’ for each and every case.

The problem here is that the algorithm does not knows the boundary condition of our problem.

Here our ‘x’ and ‘y’ values ranges from 0-0.6. The algorithm does not knows whether to go beyond 0.6 or to go below 0.

It will perform the algorithm for any random values.

Case study 2:- From case study 1 we are getting the above graph. To make it more cleaner we will now define the boundary conditions.

[inputs,fopt(i)]=ga(@stalgamite,2,[],[],[],[],[0;0],[1,1],[],[],options)

Here the first two ‘[ ]’ are for the condition of inequalities of ‘A’ and ‘b’ and the other two ‘[ ]’ are for the condition of equalities of ‘A’ and ‘b’.

After that we will define the search space i.e for both ‘x’, ‘y’ it should be between 0-1.

Case study 3:- Here we will increase the size of the population so as to get the maximum value of the function and to reduce the fluctuation of the optimum function in the previous graph

REFERENCE:-

https://in.mathworks.com/help/gads/ga.html#mw_f8e8d81b-aba1-4254-9f1a-cf93ff0ccc2b

https://in.mathworks.com/help/gads/what-is-the-genetic-algorithm.html