Week 4.1 - Genetic Algorithm

Genetic Algorithm using MATLAB

Aim:

To write code in MATLAB to optimize the stalagmite function and find the global maxima of the function.

Optimization and its purpose:

Optimization is an act or methodology of making something as fully perfect, functional or effective as possible. The purpose of optimization is to achieve the best design relative to a set of prioritized criteria or constraints. These includes maximizing factors such as productivity, strength, reliability, longevity, efficiency and utilization.

Mathematical Optimization:

Mathematical optimization or mathematical programming is the selection of a best element (with regard to some criteria) from some set of available alternatives. Optimization problems of sorts arise in all quantitative disciplines from computer and engineering to operation research and economics, and the development of solution methods has been of interest in mathematics for centuries.

In the simplest case, an optimization problem consists of maximizing or minimizing a real function by systematically choosing input values from within an allowed set and computing the value of the function. The generalization of optimization theory and techniques to other formulations constitutes a large area of applied mathematics. More generally, optimization includes finding "best available" values of some objective function given a defined domain (or input), including a variety of different types of objective functions and different types of domains.

What is Stalagmite function?

It is a function which contains the input parameters that to be given plot like stalagmite structure. Calling the function stalagmite that contains the code for evaluates the value of the function using the array input. For the study of the statistical behaviour of Genetic Algorithm, primarily a stopwatch is started.

It contains the following formulas to generate the data that causes to be plot,

F = (F₁x * F₁y * F₂x * F₂y)

F₁y = (sin (5.1*π*y1+0.05))⁶

F₂x = exp(-4*log(2)*((x1-0.0667)²)/0.64)

F₂y = exp(-4*log(2)*((y1-0.0667)²/0.64)

Stalagmite function generated plot

Genetic Algorithm

A genetic algorithm is a search method used in artificial intelligence and computing. It is used for finding optimized solutions to search problems based on the theory of natural selection and evolutionary biology.

ga is good for searching large and complex data sets

ga are most commonly used in optimization problems where we have to maximize a given objective function and set of constraints.

Working of Genetic Algorithm:

The algorithm begins by creating a random initial population.

The algorithm then creates a sequence of new populations

At each step, the algorithm uses the individuals in the current generation to create the next population

Then the sequence of points approaches an optimal solution

Genetic algorithm

A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

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 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 od solution 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

Initial Population

This 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 representing 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.

  

Fitness Function

The fitness function determines how fit an individual is (the ability of an individual to complete 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.

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 on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.

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.

Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

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.

Mutation occurs to maintain diversity within the population and prevent premature convergence.

Termination

The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). Then it is said that the generic algorithm has provided a set of solutions to our problem.

The population has a fixed size. As new generations are formed, individuals with least fitness die, providing space for new offspring

The sequence of phase is repeated to produce individuals in each new generation which are better than the previous generation

ga is function of MATLAB

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(___)

 

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.

Note

Passing Extra Parameters explains how to pass extra parameters to the objective function and nonlinear constraint functions, if necessary.

 

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.

Note

When there are integer constraints, ga does not accept linear or nonlinear equality constraints, only inequality constraints.

x = ga(problem) finds the minimum for problem, a structure described in problem.

 

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

 

MATLAB Program:

clear all

close all

clc

 

%Defining our search space

x=linspace(0,0.6,150);

y=linspace(0,0.6,150);

 

%Creating a 2D mesh

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

 

%Evaluating the 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_func(input_vector);

    end

end

 

figure(1)

surfc(xx,yy,-f)

shading interp

xlabel('x value')

ylabel('y value')

title('stalagmite_func')

 

%study 1

n_iteration = 50;

tic

for i = 1:n_iteration

    [inputs,fopt(i)] = ga(@stalagmite_func,2);

    xopt1(i) = inputs(1);

    yopt1(i) = inputs(2);

end

study_time1 = toc;

%plotting

figure(2)

subplot(2,1,1)

hold on

surfc(x,y,-f)

title('unbounded inputs')

xlabel('x value')

ylabel('y value')

shading interp

hold on

plot3(xopt1,yopt1,-fopt,'marker','o','markersize',5,'markerfacecolor','r')

subplot(2,1,2)

plot(-fopt)

xlabel('iteration')

ylabel('function minimum')

tic

 

%study2 - statistical behaviour with upper and lower bounds

for i=1:n_iteration

    [inputs,fopt(i)] = ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.6;0.6]);

    xopt(i) = inputs(1);

    yopt(i) = inputs(2);

end

study2_time=toc

%plotting

figure(3)

subplot(2,1,1)

surfc(x,y,-f)

shading interp

title('bounded inputs')

xlabel('x value')

ylabel('y value')

hold on

plot3(xopt1,yopt1,-fopt,'marker','o','markersize',5,'markerfacecolor','r')

subplot(2,1,2)

plot(-fopt)

xlabel('iteration')

ylabel('function minimum')

%study3 increasing the population size

options = optimoptions(@ga);

options = optimoptions(@ga,'populationsize',500)

tic

for i=1:n_iteration

    [inputs,fopt(i)]=ga(@stalagmite_func,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);

    xopt(i)=inputs(1);

    yopt(i)=inputs(2);

end

study3_time=toc;

figure(4)

subplot(2,1,1)

surfc(x,y,-f)

shading interp

title('bounded inputs with increased popu;ation size')

xlabel('x value')

ylabel('y value')

hold on

plot3(xopt1,yopt1,-fopt,'marker','o','markersize',5,'markerfacecolor','r')

subplot(2,1,2)

plot(-fopt)

xlabel('iteration')

ylabel('function minimum')

 

MATLAB Stalagmite function program:

function [f] = stalagmite_func(input_vector)

x1 = input_vector(1);

y1 = input_vector(2);

f1x = (sin(5.1*pi*x1+0.5))^6;

f1y = (sin(5.1*pi*y1+0.5))^6;

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

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

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

end

 

OUTPUTS:

1. Stalagmite Function:

2. Unbounded Inputs

3. Bounded Inputs

4. Bounded Inputs with Increase Population