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 NSGA-II ).
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.
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
Dominance — A point x dominates a point y for a vector-valued objective function f when:
fi(x) ≤ fi(y) for all i.
fj(x) < fj(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
kindividuals are dominated only by individuals in rank
k - 1or 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.
gamultiobjuses rank to select parents.
Crowding Distance — The crowding distance is a measure of the closeness of an individual to its nearest neighbors. The
gamultiobjalgorithm 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 the
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 dimension
mand sorted, scaled individual
distance(i) = sum_m(x(m,i+1) - x(m,i-1)).
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
@distancecrowdingfunction. 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 tie-breaker 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
gamultiobjalgorithm 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 minimum-value Pareto point for that index and the minimum point for that index in the previous iteration. The spread is then
spread= (μ + σ)/(μ + 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).
gamultiobjuses 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.
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.
The main iteration of the
gamultiobj algorithm proceeds as
Select parents for the next generation using the selection function on the current population. The only built-in selection function available for
gamultiobjis 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
PopulationSizeindividuals 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.
The following stopping conditions apply. Each stopping condition is associated with an exit flag.
|exitflag Value||Stopping Condition|
Geometric average of the relative change in value of the spread over
Maximum number of generations exceeded
Optimization terminated by an output function or plot function
No feasible point found
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:
mutationadaptfeasiblefor mutation, and
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.
 Censor, Y. “Pareto Optimality in Multiobjective Problems,” Appl. Math. Optimiz., Vol. 4, pp 41–59, 1977.
 Da Cunha, N. O. and E. Polak. “Constrained Minimization Under Vector-Valued Criteria in Finite Dimensional Spaces,” J. Math. Anal. Appl., Vol. 19, pp 103–124, 1967.
 Deb, Kalyanmoy. “Multi-Objective Optimization using Evolutionary Algorithms,” John Wiley & Sons, Ltd, Chichester, England, 2001.
 Zadeh, L. A. “Optimality and Nonscalar-Valued Performance Criteria,” IEEE Trans. Automat. Contr., Vol. AC-8, p. 1, 1963.