gamultiobj
Algorithm
Introduction
This section describes the algorithm that gamultiobj
uses to
create a set of points on the Pareto front. gamultiobj
uses a
controlled, elitist genetic algorithm (a variant of NSGAII [3]).
An elitist GA always favors individuals with better fitness value (rank). A
controlled elitist GA also favors individuals that can help increase the diversity
of the population even if they have a lower fitness value.
Multiobjective Terminology
Most of the terminology for the gamultiobj
algorithm is the
same as Genetic Algorithm Terminology. However, there are some additional terms, described
in this section. For more details about the terminology and the algorithm, see Deb
[3].
Dominance — A point x dominates a point y for a vectorvalued objective function f when:
f_{i}(x) ≤ f_{i}(y) for all i.
f_{j}(x) < f_{j}(y) for some j.
The term "dominate" is equivalent to the term "inferior:" x dominates y exactly when y is inferior to x.
A nondominated set among a set of points P is the set of points Q in P that are not dominated by any point in P.
Rank — For feasible individuals, there is an iterative definition of the rank of an individual. Rank 1 individuals are not dominated by any other individuals. Rank 2 individuals are dominated only by rank 1 individuals. In general, rank
k
individuals are dominated only by individuals in rankk  1
or lower.Individuals with a lower rank have a higher chance of selection (lower rank is better).
All infeasible individuals have a worse rank than any feasible individual. Within the infeasible population, the rank is the order by sorted infeasibility measure, plus the highest rank for feasible members.
gamultiobj
uses rank to select parents.Crowding Distance — The crowding distance is a measure of the closeness of an individual to its nearest neighbors. The
gamultiobj
algorithm measures distance among individuals of the same rank. By default, the algorithm measures distance in objective function space. However, you can measure the distance in decision variable space (also termed design variable space) by setting theDistanceMeasureFcn
option to{@distancecrowding,'genotype'}
.The algorithm sets the distance of individuals at the extreme positions to
Inf
. For the remaining individuals, the algorithm calculates distance as a sum over the dimensions of the normalized absolute distances between the individual's sorted neighbors. In other words, for dimensionm
and sorted, scaled individuali
:distance(i) = sum_m(x(m,i+1)  x(m,i1))
.The algorithm sorts each dimension separately, so the term neighbors means neighbors in each dimension.
Individuals of the same rank with a higher distance have a higher chance of selection (higher distance is better).
You can choose a different crowding distance measure than the default
@distancecrowding
function. See Multiobjective Options.Crowding distance is one factor in the calculation of the spread, which is part of a stopping criterion. Crowding distance is also used as a tiebreaker in tournament selection, when two selected individuals have the same rank.
Spread — The spread is a measure of the movement of the Pareto set. To calculate the spread, the
gamultiobj
algorithm first evaluates σ, the standard deviation of the crowding distance measure of points that are on the Pareto front with finite distance. Q is the number of these points, and d is the average distance measure among these points. The algorithm then evaluates μ, the sum over the k objective function indices of the norm of the difference between the current minimumvalue Pareto point for that index and the minimum point for that index in the previous iteration. The spread is thenspread
= (μ + σ)/(μ + Qd).The spread is small when the extreme objective function values do not change much between iterations (that is, μ is small) and when the points on the Pareto front are spread evenly (that is, σ is small).
gamultiobj
uses the spread in a stopping condition. Iterations halt when the spread does not change much, and the final spread is less than an average of recent spreads. See Stopping Conditions.
Initialization
The first step in the gamultiobj
algorithm is creating an
initial population. The algorithm creates the population, or you can give an initial
population or a partial initial population by using the
InitialPopulationMatrix
option (see Population Options).
The number of individuals in the population is set to the value of the
PopulationSize
option. By default,
gamultiobj
creates a population that is feasible with
respect to bounds and linear constraints, but is not necessarily feasible with
respect to nonlinear constraints. The default creation algorithm is
@gacreationuniform
when there are no constraints or only
bound constraints, and @gacreationlinearfeasible
when there are
linear or nonlinear constraints.
gamultiobj
evaluates the objective function and constraints for
the population, and uses those values to create scores for the population.
Iterations
The main iteration of the gamultiobj
algorithm proceeds as
follows.
Select parents for the next generation using the selection function on the current population. The only builtin selection function available for
gamultiobj
is binary tournament. You can also use a custom selection function.Create children from the selected parents by mutation and crossover.
Score the children by calculating their objective function values and feasibility.
Combine the current population and the children into one matrix, the extended population.
Compute the rank and crowding distance for all individuals in the extended population.
Trim the extended population to have
PopulationSize
individuals by retaining the appropriate number of individuals of each rank.
When the problem has integer or linear constraints (including bounds), the algorithm modifies the evolution of the population. See Integer and Linear Constraints.
Stopping Conditions
The following stopping conditions apply. Each stopping condition is associated with an exit flag.
exitflag Value  Stopping Condition 

1  Geometric average of the relative change in value of the spread over

0  Maximum number of generations exceeded 
1  Optimization terminated by an output function or plot function 
2  No feasible point found 
5  Time limit exceeded 
For exit flag 1, the geometric average of the relative change in spread has multiplier ½^{k} for the relative change in the kth previous generation.
Integer and Linear Constraints
When a problem has integer or linear constraints (including bounds), the algorithm modifies the evolution of the population.
When the problem has both integer and linear constraints, the software modifies all generated individuals to be feasible with respect to those constraints. You can use any creation, mutation, or crossover function, and the entire population remains feasible with respect to integer and linear constraints.
When the problem has only linear constraints, the software does not modify the individuals to be feasible with respect to those constraints. You must use creation, mutation, and crossover functions that maintain feasibility with respect to linear constraints. Otherwise, the population can become infeasible, and the result can be infeasible. The default operators maintain linear feasibility:
gacreationlinearfeasible
orgacreationnonlinearfeasible
for creation,mutationadaptfeasible
for mutation, andcrossoverintermediate
for crossover.
The internal algorithms for integer and linear feasibility are similar to those for
surrogateopt
. When a problem has integer and linear constraints,
the algorithm first creates linearly feasible points. Then the algorithm tries to satisfy
integer constraints by rounding linearly feasible points to integers using a heuristic that
attempts to keep the points linearly feasible. When this process is unsuccessful in
obtaining enough feasible points for constructing a population, the algorithm calls
intlinprog
to try to find more points that are feasible with
respect to bounds, linear constraints, and integer constraints.
Later, when mutation or crossover creates new population members, the algorithms ensure that the new members are integer and linear feasible by taking similar steps. Each new member is modified, if necessary, to be as close as possible to its original value, while also satisfying the integer and linear constraints and bounds.
Bibliography
[1] Censor, Y. “Pareto Optimality in Multiobjective Problems,” Appl. Math. Optimiz., Vol. 4, pp 41–59, 1977.
[2] Da Cunha, N. O. and E. Polak. “Constrained Minimization Under VectorValued Criteria in Finite Dimensional Spaces,” J. Math. Anal. Appl., Vol. 19, pp 103–124, 1967.
[3] Deb, Kalyanmoy. “MultiObjective Optimization using Evolutionary Algorithms,” John Wiley & Sons, Ltd, Chichester, England, 2001.
[4] Zadeh, L. A. “Optimality and NonscalarValued Performance Criteria,” IEEE Trans. Automat. Contr., Vol. AC8, p. 1, 1963.