Non-dominated sorting genetic algorithm II

We use the widely applied multi-objective evolutionary algorithm NSGA II (Deb et al., 2002) for land conservation optimization under uncertainty. The first step of the NSGA II by Deb et al. (2002) is initializing the first generation of solutions. Here, solutions to the problem are created at random. All solutions are evaluated with the two objective functions described in Sec. Objective functions. In the NSGA II, the solutions get assigned a non-domination rank following the following domination principle: A solution A is dominated by a solution B if all objective values of solution A are better than the corresponding objective values of solution B. The ranks indicate which solutions are non-dominated and which are dominated by other solutions. Non-dominated solutions constitute the first rank and the Pareto front. First-rank solutions dominate all other solutions, and all solutions that are only dominated by the first-rank solutions belong to the second rank. This procedure continues until all solutions have a rank. Then, a density estimation called crowding distance quantifies how similar the objective values of one solution are to the objective values of neighboring solutions in the objective space.

In the tournament selection procedure, solutions are drawn randomly from the population into a tournament pool, where the tournament pool size is a parameter. The solutions of the tournament pool are compared by their ranks. Solutions of a better rank are selected over solutions of a lower rank. If solutions are of the same rank, the solutions with higher crowing distances are selected. The selected solutions proceed to the crossover. In every crossover operation, the genes of two selected solutions (parents) are combined to produce new solutions (offspring). Random genes of produced offspring are manipulated in the mutation to encourage population diversity until the number of offspring equals the number of parents. Hereafter, the offspring population and parent generation population are merged, and the solutions with the best ranks survive. When multiple solutions have the same rank and are more numerous than the population size, the solutions with the highest crowding distances survive.