mco (version 1.17)

nsga2: NSGA II MOEA

Description

The NSGA-II algorithm minimizes a multidimensional function to approximate its Pareto front and Pareto set. It does this by successive sampling of the search space, each such sample is called a population. The number of samples taken is governed by the generations parameter, the size of the sample by the popsize parameter. Each population is obtained by creating so called offspring search points from the best individuals in the previous population. The best individuals are calculated by non-dominated sorting breaking ties using the crowding distance. The total number of function evaluations used is $$n_eval = popsize * (generations + 1)$$ when generations is a single number and $$n_eval = popsize * (max(generations) + 1)$$ when generations is a vector of numbers. Note the additional generation of evaluations in the above equation. These stem from the initial population which must be evaluated before the algorithm can start evolving new individuals.

While the algorithm supports unbounded minimization, it will throw a warning and best results are obtained when a sensible upper and lower bound are given. No attempt is made to find such a sensible region of interest, instead if any element of the upper or lower bound is infinite, it is replace with a very large number (currently +/-.Machine$double.xmax/4).

Usage

nsga2(fn, idim, odim, ...,
        constraints = NULL, cdim = 0,
        lower.bounds = rep(-Inf, idim), upper.bounds = rep(Inf, idim),
        popsize = 100, generations = 100,
        cprob = 0.7, cdist = 5,
        mprob = 0.2, mdist = 10,
        vectorized=FALSE)

Value

If generation is an integer, a list describing the final population with components par, value and pareto.optimal. If generations is a vector, a list is returned. The i-th element of the list contains the population after generations[i] generations, this is not necessarily the set of new individuals that were evaluated in this generation. Some of the new individuals might have been eliminated in the selection phase.

Arguments

fn

Function to be minimized

idim

Input dimension

odim

Output dimension

...

Arguments passed through to 'fn'

constraints

Constraint function

cdim

Constraint dimension

lower.bounds

Lower bound of parameters

upper.bounds

Upper bound of parameters

popsize

Size of population

generations

Number of generations to breed. If a vector, then the result will contain the population at each given generation.

cprob

Crossover probability

cdist

Crossover distribution index

mprob

Mutation probability

mdist

Mutation distribution index

vectorized

If TRUE, the objective and constraint functions must be vectorized, i.e. accept a matrix instead of a vector and return a matrix instead of a vector. The matrix is structured such that one individual parameter combination is contained in each row (the matrix has shape popsize * idim) and each objective is stored in a row of the returned matrix (the returned matrix must have shape odim * popsize).

A vectorized of a function fn should behave like apply(x, 1, f for a population stored in the matrix x.

Author

Heike Trautmann , Detlef Steuer and Olaf Mersmann

References

Deb, K., Pratap, A., and Agarwal, S.. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6 (8) (2002), 182-197.

See Also

zdt1 for more examples and a list of multiobjective test functions.

Examples

## Binh 1 problem:
binh1 <- function(x) {
  y <- numeric(2)
  y[1] <- crossprod(x, x)
  y[2] <- crossprod(x - 5, x - 5)
  return (y)
}
r1 <- nsga2(binh1, 2, 2,
           generations=150, popsize=100,
           cprob=0.7, cdist=20,
           mprob=0.2, mdist=20,
           lower.bounds=rep(-5, 2),
           upper.bounds=rep(10, 2))
plot(r1)

## VNT problem:
vnt <- function(x) {  
  y <- numeric(3)
  xn <- crossprod(x, x)
  y[1] <- xn/2 + sin(xn);
  y[2] <- (crossprod(c(3, -2), x) + 4)^2/8 + (crossprod(c(1, -1), x) + 1)^2/27 + 15
  y[3] <- 1/(xn + 1) - 1.1*exp(-xn)
  return (y)
}

r2 <- nsga2(vnt, 2, 3,
           generations=150, popsize=100,
           lower.bounds=rep(-3, 2),
           upper.bounds=rep(3, 2))
plot(r2)

## Example using constraints:
## minimize     f(x) = (x[1]^2, x[2]^2)
## subject to   g(x) = (sum(x) - 5) >= 0
f <- function(x) { x^2 }
g <- function(x) { sum(x) - 5 }
res <- nsga2(f, 2, 2, generations=500,
             lower.bounds=c(0, 0), upper.bounds=c(10, 10),
             constraints=g, cdim=1)
opar <-par(mfrow=c(1,2))
plot(res, xlab="y1", ylab="y2", main="Objective space")
plot(res$par, xlab="x1", ylab="x2", main="Parameter space")
par(opar)