Week 4 - Genetic Algorithm

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.

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.

Process of natural selection :

The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.

This notion can be applied for a search problem. We consider a set of solutions for a problem and select the set of best ones out of them.

Five phases are considered in a genetic algorithm.

1. Initial population
2. Fitness function
3. Selection
4. Crossover
5. Mutation

1. Initial Population : The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve. An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution). In a genetic algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, binary values are used (string of 1s and 0s). We say that we encode the genes in a chromosome.

2. Fitness Function : The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.

3. Selection : The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation. Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.

4. Crossover : Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.

5. Mutation : In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.

Syntax for Genetic Algorithm :

Description :

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.

x = ga(fun,nvars,A,b) finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').

x = ga(fun,nvars,A,b,Aeq,beq) finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[] and b=[] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').

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

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon) subjects the minimization to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist).

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.

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.

x = ga(problem) finds the minimum for problem, where problem is a structure.

Outputs from the function :

[x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.

[x,fval,exitflag,output] = ga(___) also returns exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.

[x,fval,exitflag,output,population,scores] = ga(___) also returns a matrix population, whose rows are the final population, and a vector scores, the scores of the final population.

Program to optimize stalagmite function with explanation :

clc
clear all
close all

%Input
%We initialize the value of x and y by taking 150 values between 0 and 0.6
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
%We consider no. of iterations as 50
num_spaces = 50;

%Forming a 2D array
[xx,yy] = meshgrid(x,y);
for i = 1:length(x)
    for j = 1:length(y)
        input_vector(1) = xx(i,j);
        input_vector(2) = yy(i,j);
        f(i,j) = stalagmite(input_vector);
    end
end

%Study1 - Unbounded

%Now, let us make our 1st study in which we use ga function to calculate the maxima of the function. We store the outputs into results which contains maximas and fopt which contain the value at which the maxima is obtained.

tic
for i = 1:num_spaces
    [results,fopt(i)] = ga(@stalagmite,2);
    xopt(i) = results(1);
    yopt(i) = results(2);
end

study_time1 = toc;
figure(1)
subplot(2,1,1)
surf(x,y,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function maximum')

%Study2 - Bounded

%Now, let us make our study having bounded values. Let us specify the lower and upper bounds of x and y in this case. The ga is initiated with random population only.

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

study_time2 = toc;
figure(2)
subplot(2,1,1)
surf(x,y,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function maximum')

%Study3 - Increased Initial Population

%In this case we increase our initial population which is 50 as default upto 250.

tic

options = optimoptions('ga');
options = optimoptions(options,'populationsize',250);

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

study_time3 = toc;
figure(3)
subplot(2,1,1)
surf(x,y,-f)
shading interp
hold on
plot3(xopt,yopt,-fopt,'marker','o')
subplot(2,1,2)
plot(-fopt)
xlabel('iteration')
ylabel('function maximum')

%Since we need to plot a 3D surface, we take the 2D array of x and y using meshgrid command and store them in input_vector array, so that it can be used as an argument to call the function stalagmite.

%Another function file is been created of stalagmite. Here, we take the output as 'f' as ga only minimizes a given function. So, if 'f' is considered, it automatically gives us the maxima.

function A = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
f1 = (sin(5.1*pi*x + 0.5)).^6;
f2 = exp((-4*log(2)*((x - 0.0667).^2))/0.64);
f3 = (sin(5.1*pi*y + 0.5)).^6;
f4 = exp((-4*log(2)*((y - 0.0667).^2))/0.64);
A = -(f1*f2*f3*f4);
end

Outputs of the program :

1. Study1 - Unbounded

In this result, we see that the optimal values went outside the values of x and y resulting in falling away from stalagmite surface. Hence, we failed to reach the global maxima in this case.

study_time1 = 6.2202sec

2. Study2 - Bounded

In this result, we see that the optimum values are within the limits but still, it could not give us the maxima value.

study_time2 = 7.6428 which is greater than the above case.

3. Study3 - Increased Initial Population

Though the time of execution is more in this case, we obtain correct value of maxima for the stalagmite function successfully.

So, we can say that by increasing the initial population size of the ga we can increase the accuracy of the algorithm.

study_time3 = 26.9431sec which is greater than both the above cases.

Result Table :

Errors faced during programming with its solution:

1. Error in calling the function - ga(@stalagmite,2)

An error was made as there wa no '@' sign while calling the function. Thus, to clear the error the mistake was rechecked and corrected.

2. Error made in the function program

An error was made in the function program as the 'input_vector' wasn't defined. So, to overcome this error the 'input_vector' was defined.

References :

1. https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_introduction.htm

2. https://en.wikipedia.org/wiki/Genetic_algorithm

3. https://in.mathworks.com/help/gads/ga.html#d120e41886