gamultiobj Algorithm

`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 NSGA-II [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 vector-valued 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 rank k - 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 the DistanceMeasureFcn 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 dimension m and sorted, scaled individual i:
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 @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 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 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 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).
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 built-in 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 `options.MaxStallGenerations` generations is less than `options.FunctionTolerance`, and the final spread is less than the mean spread over the past `options.MaxStallGenerations` generations
`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 or gacreationnonlinearfeasible for creation, mutationadaptfeasible for mutation, and crossoverintermediate 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 Vector-Valued Criteria in Finite Dimensional Spaces,” J. Math. Anal. Appl., Vol. 19, pp 103–124, 1967.

[3] Deb, Kalyanmoy. “Multi-Objective Optimization using Evolutionary Algorithms,” John Wiley & Sons, Ltd, Chichester, England, 2001.

[4] Zadeh, L. A. “Optimality and Nonscalar-Valued Performance Criteria,” IEEE Trans. Automat. Contr., Vol. AC-8, p. 1, 1963.