Week 4 - Genetic Algorithm
AIM: To write code in MATLAB to optimize the stalagmite function and find the global maxima of the function.
DESCRIPTION
Genetic Algorithm
The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed-integer programming, where some components are restricted to be integer-valued.
The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:
- Selection rules select the individuals, called parents, that contribute to the population at the next generation.
- Crossover rules combine two parents to form children for the next generation.
- Mutation rules apply random changes to individual parents to form children.
Genetic Algorithm Terminology
Fitness Functions
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.
Individuals
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.
Populations and Generations
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.
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.
Figure 1: Diversity is essential to the genetic algorithm because it enables the algorithm to search for a larger region of the space.
Fitness Values and Best Fitness Values
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.
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.
How the Genetic Algorithm Works
Outline of the Algorithm
The following outline summarizes how the genetic algorithm works:
- 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. To create a new population, the algorithm performs the following steps:
- Scores each member of the current population by computing its fitness value. These values are called raw fitness scores.
- Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
- Selects members, called parents, based on their expectations.
- Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.
- It produces children from their parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.
- Replaces the current population with the children to form the next generation.
- The algorithm stops when one of the stopping criteria is met.
Initial Population
The algorithm begins by creating a random initial population, as shown in the following figure.
Figure 2: random initial population
In this example, the initial population contains 20 individuals. Note that all the individuals in the initial population lie in the upper-right quadrant of the picture, that is, their coordinates lie between 0 and 1. For this example, the Initial range in the Population options is [0;1].
Creating the Next Generation
At each step, the genetic algorithm uses the current population to create the children that make up the next generation. The algorithm selects a group of individuals in the current population, called parents, who contribute their genes—the entries of their vectors—to their children. The algorithm usually selects individuals that have better fitness values as parents. You can specify the function that the algorithm uses to select the parents in the Selection function field in the Selection options.
The genetic algorithm creates three types of children for the next generation:
- Eliteare the individuals in the current generation with the best fitness values. These individuals automatically survive to the next generation.
- Crossover is created by combining the vectors of a pair of parents.
- Mutationchildren are created by introducing random changes, or mutations, to a single parent.
The following schematic diagram illustrates the three types of children.
Figure 3: Three types of children.
Mutation and Crossover explains how to specify the number of children of each type that the algorithm generates and the functions it uses to perform crossover and mutation.
The following sections explain how the algorithm creates crossover and mutation of children.
Crossover Children
The algorithm creates crossover children by combining pairs of parents in the current population. At each coordinate of the child vector, the default crossover function randomly selects an entry, or gene, at the same coordinate from one of the two parents, and assigns it to the child. For problems with linear constraints, the default crossover function creates the child as a random weighted average of the parents.
Mutation Children
The algorithm creates mutation children by randomly changing the genes of individual parents. By default, for unconstrained problems, the algorithm adds a random vector from a Gaussian distribution to the parent. For bounded or linearly constrained problems, the child remains feasible.
The following figure shows the children of the initial population, that is, the population at the second generation, and indicates whether they are elite, crossover, or mutation children.
Figure 4: children of the initial population.
The following figure shows the populations at iterations 60, 80, 95, and 100.
Figure 5: As the number of generations increases, the individuals in the population get closer together and approach the minimum point [0 0].
Stopping Conditions for the Algorithm
The genetic algorithm uses the following conditions to determine when to stop:
- Generations— The algorithm stops when the number of generations reaches the value of Generations.
- Time limit— The algorithm stops after running for an amount of time in seconds equal to the Time limit.
- Fitness limit— The algorithm stops when the value of the fitness function for the best point in the current population is less than or equal to the Fitness limit.
- Stall generations— The algorithm stops when the average relative change in the fitness function value over Stall generations is less than Function tolerance.
- Stall time limit— The algorithm stops if there is no improvement in the objective function during an interval of time in seconds equal to the Stall time limit.
- Stall test— The stall condition is either average change or geometric weighted. For geometric weighted, the weighting function is 1/2n, where n is the number of generations prior to the current. Both stall conditions apply to the relative change in the fitness function over Stall generations.
- Function tolerance— The algorithm runs until the average relative change in the fitness function value over Stall generations is less than Function tolerance.
- Constraint tolerance— Constraint tolerance is not used as a stopping criterion. It is used to determine the feasibility with respect to nonlinear constraints. Also, max(sqrt(eps), Constraint Tolerance) determines feasibility with respect to linear constraints.
The algorithm stops as soon as anyone of these conditions is met.
Selection
The selection function chooses parents for the next generation based on their scaled values from the fitness scaling function. The scaled fitness values are called expectation values. An individual can be selected more than once as a parent, in which case it contributes its genes to more than one child. The default selection option, Stochastic uniform, lays out a line in which each parent corresponds to a section of the line of length proportional to its scaled value. The algorithm moves along the line in steps of equal size. At each step, the algorithm allocates a parent from the section it lands on.
A more deterministic selection option is Remainder, which performs two steps:
- In the first step, the function selects parents deterministically according to the integer part of the scaled value for each individual. For example, if an individual's scaled value is 2.3, the function selects that individual twice as a parent.
- In the second step, the selection function selects additional parents using the fractional parts of the scaled values, as in stochastic uniform selection. The function lays out a line in sections, whose lengths are proportional to the fractional part of the scaled value of the individuals, and moves along the line in equal steps to select the parents.
Reproduction Options
Reproduction options control how the genetic algorithm creates the next generation. The options are
- Elite count— The number of individuals with the best fitness values in the current generation that are guaranteed to survive to the next generation. These individuals are called elite children. The default value of Elite count is 5% of the population size, rounded up.
When Elite count is at least 1, the best fitness value can only decrease from one generation to the next. This is what you want to happen since the genetic algorithm minimizes the fitness function. Setting Elite count to a high value causes the fittest individuals to dominate the population, which can make the search less effective.
- Crossover fraction— The fraction of individuals in the next generation, other than elite children, that are created by crossover. Setting the crossover fraction describes how the value of Crossover fraction affects the performance of the genetic algorithm.
Because elite individuals have already been evaluated, ga does not re-evaluate the fitness function of elite individuals during reproduction. This behavior assumes that the fitness function of an individual is not random, but is a deterministic function. To change this behavior, use an output function
Mutation and Crossover
The genetic algorithm uses the individuals in the current generation to create the children that make up the next generation. Besides elite children, which correspond to the individuals in the current generation with the best fitness values, the algorithm creates
- Crossover children by selecting vector entries, or genes, from a pair of individuals in the current generation and combines them to form a child
- Mutation children by applying random changes to a single individual in the current generation to create a child
Both processes are essential to the genetic algorithm. Crossover enables the algorithm to extract the best genes from different individuals and recombine them into potentially superior children. Mutation adds to the diversity of a population and thereby increases the likelihood that the algorithm will generate individuals with better fitness values.
It can be specified how many of each type of children the algorithm creates as follows:
- Elite count, in Reproductionoptions, specifies the number of elite children.
- Crossover fraction, in Reproductionoptions, specifies the fraction of the population, other than elite children, that are crossover children.
ga
It is used to find a minimum of a function using genetic algorithm
Syntax
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,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.
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.
[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.
OBJECTIVE
- Explanation of the concept of genetic algorithm and syntax for ga in MATLAB.
- Plotting the graphs for all 3 studies and for F maximum vs no. of iterations.
- To write code in MATLAB to optimize the stalagmite function and find the global maxima of the function.
Figure: Flow of the project.
CODE
f(x,y)=f_(1,x) f_(2,x) f_(1,y) f_(2,y)
f_(1.x)=[sin(5.1πx+0.5)]^6
f_(1.y)=[sin(5.1πy+0.5)]^6
f_(2.x)=exp[-4 ln(2) (x-0.0667)^2/0.64 ]
f_(2.y)=exp[-4 ln(2) (y-0.0667)^2/0.64 ]
Function code
function [f] = stalgamite_function(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)*(x - 0.0667)^2/0.64);
f = -(f1x*f1y*f2x*f2y);
end
Main code
clear all
close all
clc
x = linspace(0,2,150);%creating an array
y = linspace(0,2,150);%creating an array
number_of_iterations = 200;%total number of iterations are 200
[xx yy] = meshgrid(x,y);
for m = 1:length(xx)
for n = 1:length(yy)
input_vector(1) = xx(m,n);
input_vector(2) = yy(m,n);
f(m,n) = stalgamite_function(input_vector);% calling the stalgamite function
end
end
figure
surfc(x,y,-f)%plotting the 3D plot
colorbar
xlabel('values of x')
ylabel('values of y')
zlabel('function values')
title('stalagmite function')
shading interp
[x_output , fval] = ga(@stalgamite_function,2)
%First STUDY
tic
for m = 1:number_of_iterations
[inputs , fopt(m)] = ga(@stalgamite_function,2);
xopt1(m) = inputs(1);
yopt1(m) = inputs(2);
end
time_1 = toc %calculating the time of study using tic and toc commands
figure
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt1,yopt1,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('unbounded input')
subplot(2,1,2)
plot(-fopt)
xlabel('number of iterations')
ylabel('function maximum')
%Second study with upper and lower bonds
tic
for m = 1:number_of_iterations
[inputs , fopt(m)] = ga(@stalgamite_function,2,[],[],[],[],[0;0],[1;1]);
xopt2(m) = inputs(1);
yopt2(m) = inputs(2);
end
time_2 = toc
figure
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt2,yopt2,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('unbounded input')
subplot(2,1,2)
plot(-fopt)
xlabel('number of iterations')
ylabel('function maximum')
%third study: increasing ga iterations
options = optimoptions('ga')
options = optimoptions(options , 'populationsize', 200)
tic
for m = 1:number_of_iterations
[inputs , fopt(m)] = ga(@stalgamite_function,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt3(m) = inputs(1);
yopt3(m) = inputs(2);
end
time_3 = toc
figure
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt3,yopt3,-fopt, 'marker' , 'o' ,'markersize' ,3, 'markerfacecolor' ,'g')
title('unbounded input')
subplot(2,1,2)
plot(-fopt)
xlabel('number of iterations')
ylabel('function maximum')
Explanation of the code
- A function is created to solve the given formula expressions in the stalagmite function:
`f(x,y)=f_(1,x) f_(2,x) f_(1,y) f_(2,y)`
`f_(1.x)=[sin(5.1πx+0.5)]^6`
`f_(1.y)=[sin(5.1πy+0.5)]^6`
`f_(2.x)=exp[-4 ln(2) (x-0.0667)^2/0.64 ]`
`f_(2.y)=exp[-4 ln(2) (y-0.0667)^2/0.64 ]`
- The linspace command is used to create an array defining 150 values between 0 to 2.
- Number of iterations are 200.
- The meshgrid command is used to mesh the x and y arrays.
- For loop is used for solving 200
- The surfc command is used for showing the graphs as surface view in 3D.
- The colorbar command is used to show the graph variations in different colours.
- The subplot command is used to show the two plots in a single figure.
- The plot3 command is used for plotting the graphs un 3-Dimensions
- The labels, titles, etc are added using xlabels, ylabels , and title commands.
- The tic and toc command is used to calculate the study time.
OUTPUTS
Figure: values of parameters
Figure: time to calculate study 1
Figure: Time to calculate second study
Figure: Genetic algorithm parameters
Figure: Time to calculate study 3
RESULTS
REFERENCES