Project

Genetic Algorithm

RRahul Date9 May 2020

Project Title: writing code to calculate the global maxima of a stalagmite function.

Objective:

1. Study the genetic algorithm.

2. Study the stalagmite function.

3. Write code with unbounded inputs, bounded inputs and with population number.

Theory

Genetic Algorithm

Genetic algorithms (GA) are a method of optimization involving iterative search procedures based on an analogy with the process of natural selection (Darwinism) and evolutionary genetics. Genetic algorithms (GA) like neural networks are biologically inspired and represent a new computational model having its roots in evolutionary sciences. Usually GAs represent an optimization procedure in a binary search space, and unlike traditional hill climbers, they do not evaluate and improve a single solution but a set of solutions or hypotheses, a so-called population. The GAs produce successor hypotheses by mutation and recombination of the best currently known hypotheses. Thus, at each iteration, a part of the current population is replaced by offspring of the fittest hypotheses. In other words, a space of candidate hypotheses is searched in order to identify the best hypothesis, which is defined as the optimization of a given numerical measure, the so-called hypothesis fitness. Consider the case of function approximation based on given input-output samples: The fitness is the accuracy of the hypothesis (solution) over the training set.

The strength of this parallel process is enhanced by the mechanics of population modification, making GAs adequate candidates even for NP-hard problems. Mathematically, they are function optimizers and they encode a potential solution based on chromosome-like data structures. The critical information is preserved by applying a recombination operator to these structures. Their most interesting properties are:

Efficiency.

Simple programability.

Extraordinary robustness regarding the input data.

The most important property is robustness, and this represents an emulation of nature’s adaptation algorithum of choice. Mathematically, it means that it is possible to find a solution even if the input data do not facilitate finding such a solution. GAs are mostly applied to nondifferentiable functions and functions with many local optima. Besides the above-mentioned advantages, there is one major disadvantage: GAs have to be carefully designed. An unfavourable choice of operators might affect the outcome of the application. Therefore, a precise knowledge of the basics and the context is crucial for any problem solution based on GAs.

Usually, the implementation of a GA starts with the random definition of a chromosome population. The structures are evaluated and then better reproductive opportunities are allocated for those chromosomes, leading to better solutions. The adequacy of a solution is typically related to the current population average or the median population.

Let us look again at the definition of a GA. In a strict sense, the GA defines a model introduced and investigated by John Holland. This computational paradigm—known also as the canonical genetic algorithm—is still a relevant research topic. In a more detailed sense, the GA represents a population-based model, which employs selection and recombination operators to generate new data points in a search space. There are several GA models known in the literature, most of them designed as optimization tools for several applications.

GAs differ from classical optimization and search procedures: (1) direct manipulation of a coding, (2) search from a population of points and not a single solution, (3) search via sampling, a so-called blind search, and (4) search using stochastic operators, not deterministic rules.

What is stalagmite?

Calcium carbonate deposition as a stalagmite occurs when the solution carries the calcium laden leachate solution to the ground under the concrete structure. Carbon dioxide is absorbed into the alkaline leachate solution, which facilitates the chemical reactions to deposit calcium carbonate as a stalagmite.

Genetic Algorithum Syntax

x = ga(fun,nvars)
x = ga(fun,nvars,A,b)
x = ga(fun,nvars,A,b,Aeq,beq)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)
x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)
x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)
x = ga(problem)
[x,fval] = ga(___)
[x,fval,exitflag,output] = ga(___)
[x,fval,exitflag,output,population,scores] = ga(___)

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 nonlconaccepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such thatC(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 usingoptimoptions (recommended) or gaoptimset.

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)

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.

[x,fval] = ga(___)

for any previous input arguments, also returnsfval, 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.

Code

clear all 
close all
clc

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

[xx,yy] = meshgrid(x,y);

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

x = linspace(0,0.6,150);
y = linspace(0,0.6,150); //Define search space for function.

[xx,yy] = meshgrid(x,y); //mesh generation

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 // with thehelp of search space we calculate the function value at every mesh point. for that for loop is used.

surf(xx,yy,f)
xlabel(\'x value\')
ylabel(\'y value\') // ploting command

shading interp // command for hiding the lines on the surface

[inputs, fval] = ga(@stalagmite,2) // Direct genetic algorithm function used to calculate inputs and function values

Function

function[f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
a1 = (sin(5.1*pi*x+0.5))^6;
a2 = exp(-4*log(2)*(((x-0.0667)^2)/0.64));
a3 = (sin(5.1*pi*y+0.5))^6;
a4 = exp(-4*log(2)*(((y-0.0667)^2)/0.64));
f = -(a1*a2*a3*a4);
end

Function Explanation

the function is of stalagmite function. it consist four terms as shown in fig. we have to find local maxima of stalagmite function so that at the end we have to change the function value so that ga will calculate the maximum value of the function.

$\"\"$

Output

$\"\"$

Unbounded, Bounded, and population count code

clear all 
close all
clc

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num = 50;

[xx,yy] = meshgrid(x,y);

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
tic
for i = 1:num
    [inputs,fval(i)] = ga(@stalagmite,2);
    xopt(i) = inputs(1);
    yopt(i) = inputs(2);
end
time = toc
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title(\'Statistical behaviour of unbounded input\')
plot3(xopt,yopt,fval,\'marker\',\'o\')
subplot(2,1,2)
plot(fval)
xlabel(\'Number of iterations\')
ylabel(\'Maximum points on the function\')

%Case2 (bounding the value of x from 0-1)
tic
for i = 1:num
    [inputs,fval2(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt2(i) = inputs(1);
    yopt2(i) = inputs(2);
end
time2 = toc
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title(\'Bounded values\')
plot3(xopt2,yopt2,fval2,\'marker\',\'o\')
subplot(2,1,2)
plot(fval2)
xlabel(\'Number of iterations\')
ylabel(\'Maximum points on the function\')


%Case (bounding the value of x and y from 0-1 and increasing the population by 500)
options=optimoptions(\'ga\');
options=optimoptions(options,\'populationsize\',500);
tic
for i = 1:num
    [inputs,fval3(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt3(i) = inputs(1);
    yopt3(i) = inputs(2);
end
time3 = toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
title(\'Bounded values with increase population\')
plot3(xopt3,yopt3,fval3,\'marker\',\'o\')
subplot(2,1,2)
plot(fval3)
xlabel(\'Number of iterations\')
ylabel(\'Maximum points on the function\')

Output

$\"\"$