Multi-objective Evolutionary Algorithm under Uncertainty

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.

Since we propose an optimization under uncertainty, we now introduce the required adaptions to the NSGA II. Eskandari and Geiger (2009) proposed a nondomination-based ranking procedure of (Deb et al., 2002) that takes into account uncertainty in the objective values. Compared to the NSGA II, every solution has an ensemble of objective values. The selection and the recombination of the offspring and parent generation, also called survival, use the ensemble objective values. For the nondomination-based ranking procedure under uncertainty (Eskandari and Geiger, 2009), the solutions are assigned one of two ranks, the first rank with stochastically nondominated solutions and the second rank is formed by all dominated solutions. The following definition defines stochastic dominance between two solutions A and B: “Solution A stochastically dominates (is better than) solution B if f¯i(A) is less than f¯i(B) for each objective function i” (Eskandari and Geiger, 2009), where f¯ is the sample mean of the objective values per solution.

First rank

All solutions of the current generation are compared to each other. If a solution is not stochastically dominated by any other solution, it is added to the first rank. The crowding distances are computed as the fitness value for all identified solutions belonging to the first rank.

Second rank

The second rank combines all solutions dominated by the first-rank solutions. For the second-rank solutions, the summation of the probabilities that a solution dominates other solutions is computed, referred to as expected strength values E_S. To compute E_S, we define amongst all second-rank solutions whether or not a solution A dominates or is dominated under uncertainty by another solution B, where the following statement defines dominance under uncertainty: “Solution A significantly dominates (is better than) solution B with a confidence level of […](1 − α) if f¯i(A)+hwi(A) <f¯i(B)−hwi(B) for each objective function i” (Eskandari and Geiger, 2009), where f¯i(x) − hwi(x) and f¯i(x) + hwi(x) are the lower and upper bounds of the objective value interval at significance level α. Then, the probabilistic dominance P is computed with three possible cases of P (this definition holds only for minimization problems):

The probability P_A that objective values of solution A are lower than the objective values of B is computed with the following equation, which approximates the integral Q(x) using the suggestion of Borjesson and Sundberg (1979):

where

μ : mean of objective values,

σ : standard deviation of objective values,

erf(x) : Gaussian error function

The summed-up probabilities P values of every solution in the second rank of dominating the other solutions in the second rank (number of solutions are the same per generation) result in the expected strength value E_S. Lastly, we calculate the fitness value E_F for each solution in the second rank. For a solution A, the E_F is the sum of all E_S values solutions by which solution A is stochastically dominated minus the sum of all E_S values solution A stochastically dominates.

For the selection and survival under uncertainty, we use the ranks and computed fitness values E_F for the tournament selection (Sec. Non-dominated sorting genetic algorithm II). We use the tournament selection with a tournament pool size of two (binary tournament selection). Compared to the selection without uncertainty, the E_F are considered when two second-rank solutions are compared: If only one solution is of the first rank, it wins. If both solutions are of the first rank, the solution with the higher crowding distance wins. If both solutions are of the second rank, the solution with the higher E_F wins. The crossover and mutations produce offspring with the operators of the NSGA II. After that, the survival of solutions from the combined population of parents and offspring takes place. The ranks and fitness values are recomputed for the combined population. The crowding distance defines the order of the first-rank solutions, and the E_F values define the second-rank order. The best solutions are retrieved from the ordered population until meeting the population size limit.

We extend the described multi-objective optimization under uncertainty by seeding. Seeding is the injection of elite solutions into the initial population. We follow the method of Guariso and Sangiorgio (2020), who found that seeding the single objective optimal solutions benefits the spread and convergence of the Pareto fronts. Hildemann and Verstegen (2021) found that the findings hold for a multi-objective land use allocation optimization under uncertainty using the NSGA II. Therefore, the single objective extreme solutions are computed and injected into the initial population: The single objective extreme solution for minimizing the soil loss rates is to have every sub-watershed selected. The single objective extreme solution for minimizing the labor requirement is to omit SWC installations completely.