# Comparing Solutions under Uncertainty in Multiobjective Optimization

Authors: Miha Mlakar; Tea Tušar; Bogdan Filipič
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Due to various reasons the solutions in real-world optimization problems cannot always be exactly evaluated but are sometimes represented with approximated values and confidence intervals. In order to address this issue, the comparison of solutions has to be done differently than for exactly evaluated solutions. In this paper, we define new relations under uncertainty between solutions in multiobjective optimization that are represented with approximated values and confidence intervals. The new relations extend the Pareto dominance relations, can handle constraints, and can be used to compare solutions, both with and without the confidence interval. We also show that by including confidence intervals into the comparisons, the possibility of incorrect comparisons, due to inaccurate approximations, is reduced. Without considering confidence intervals, the comparison of inaccurately approximated solutions can result in the promising solutions being rejected and the worse ones preserved. The effect of new relations in the comparison of solutions in a multiobjective optimization algorithm is also demonstrated.


---

## Body

## 1. Introduction

Multiobjective optimization is the process of simultaneously optimizing two or more conflicting objectives. Problems with multiple objectives can be found in various fields, from product design and process optimization to financial applications. Their specificity is that the result is not just one solution, but a set of solutions representing trade-offs between objectives.Multiobjective evolutionary algorithms (MOEAs) are known for efficiently solving these kind of problems [1]. However, MOEAs can also be used for solving optimization problems with uncertain objective values. The reason for uncertainty can be noise, robustness, fitness approximations, or time-varying fitness functions. When solving uncertain optimization problems, it is better if the algorithm takes uncertainty into account.Uncertain solutions can be represented with approximated values and variances of these approximations. From the variance, the confidence interval of the approximation can be calculated. This interval indicates the region in which the exactly evaluated solution is most likely to appear. The confidence interval width indicates the certainty of the approximation. If the confidence interval is narrow, we can be more certain about the approximation and vice versa. Since the confidence intervals offer additional information on the approximations, they can be effectively used to compare solutions and an algorithm using confidence intervals can perform better by exploiting this additional information [2]. During optimization that does not consider confidence intervals, an approximated solution may be incorrectly identified as the better of the two compared solutions. Often the solution that is incorrectly determined as worse is then discarded. Similarly, a promising solution can get discarded if a worse solution is incorrectly determined as being better. In both cases good solutions are lost due to the comparison of solutions which only considers approximated values.To prevent these unwanted effects, we propose new relations for comparing solutions under uncertainty, where, in addition to the approximated values of a solution, their confidence intervals are considered. These relations cover all possible combinations that can occur when comparing solutions represented with confidence intervals. New relations also take into consideration the feasibility of solutions including the uncertainty of feasibility due to the uncertainty of solutions. During the optimization process some solutions are exactly evaluated and others approximated; therefore, the relations under uncertainty also cover the comparison of approximated solutions with exactly evaluated solutions. The relations under uncertainty can be used to compare solutions in any multiobjective optimization algorithm dealing with solutions represented with confidence intervals.The structure of this paper is as follows. In Section2 we describe the existing techniques for comparing solutions under uncertainty reported in the literature. In Section 3 we recall the Pareto dominance relations for comparing the exactly evaluated solutions in multiobjective optimization. In Section 4 we generalize these relations to solutions represented with approximated values and confidence intervals. Section 5 presents the possible use of new relations under uncertainty for comparing two solutions in any multiobjective optimization algorithm. Section 6 presents an empirical proof of concept of comparing solutions under uncertainty by demonstrating that the use of new relations under uncertainty reduces the number of incorrect comparisons. Section 7 concludes the paper with a summary of the work done.


## 2. Existing Techniques for Comparing Solutions

Comparison of solutions is an essential step of the optimization process. Comparing solutions helps determine which solution is better and therefore appropriate to drive the optimization process further, and which one is worse and should be replaced with a better solution. The comparison of solutions in single objective optimization is straightforward. Either both solutions have the same objective values, or one solution is better than the other, which means that deciding which solution is better is trivial.In multiobjective optimization, we wish to simultaneously optimize several conflicting objectives. Here, one solution can be better in some objectives and worse in others. Consequently, the comparison of solutions and therefore the whole optimization process become more challenging.When solving real-world optimization problems, it is often not possible to determine the objective values without uncertainties. The nature of uncertainties depends on the problem. In [2], four types of uncertainty sources are mentioned. The first one is thenoisy fitness functions, where the same input parameters return different objective values. The second one is the requirement forsolution robustness, where the quality of the obtained optimal solutions should be robust against environmental changes or deviations from the optimal point. The third type is theapproximated fitness, where the fitness functions suffer from approximation errors. The fourth and final type is thetime-varying fitness functions, where the optimum of the problem to be solved changes over time and, thus, the optimizer should be able to track the optimum continuously.Regardless of the uncertainty origin, the techniques for comparing solutions under uncertainty and determining their domination status are similar. Two different approaches are used when comparing solutions under uncertainty. The first one is to take the approximated value and variance and transform them into one value and then compare these single values. The second approach is to calculate the confidence interval and then directly compare the solutions represented with confidence intervals.An example of the first approach can be found in [3], where probabilistic dominance is defined and, for comparing solutions, the probability of dominance is used rather than outright dominance. If the probability that one solution dominates the other is higher than the specified degree of confidence, then this solution is said to dominate the other. This probabilistic dominance allows the use of the usual deterministic elitist algorithms with certain degree of confidence in the results. The methods to calculate the probability of dominance vary, depending on the types of uncertainty.Similarly, in [4] the authors define the dominance relation between solutions based on the probabilities of one solution objective being better than the same objective of another solution. For solutions with more objectives, the hypercuboids are defined and, similarly, comparing their volume and the center point can determine the probability of one solution being better than the other. To select diverse solutions, the paper also redefines the crowding distance defined in [5] based on the location and the volume of the hypercuboids of these solutions.Another example of this approach is presented in [6], where each solution is inherently associated with a probability distribution over the objective space. A probabilistic model that combines quality indicators and uncertainty is created and then used to calculate the expected value for each solution.In the second approach, the solutions represented with approximated values and confidence intervals are compared to determine the relation between them.In [7, 8], the authors tackle a noisy optimization problem with an algorithm that evaluates every solution multiple times (and if necessary performs additional evaluations to reduce the uncertainty) and calculates the mean value and standard deviation for these evaluations. A modified Pareto dominance relation is defined for comparing solutions in uncertain environments. The Pareto dominance relation is modified in a way that the solution x dominates solution y if for every objective, the mean value plus standard deviation of x dominates the mean value minus standard deviation of y. If this is not the case, the solutions are nondominated. To avoid having too many nondominated solutions, the promising solutions are additionally evaluated to make the standard deviation smaller.In [9], a robust multiobjective evolutionary algorithm was developed for solving optimization problems in which solutions should be invariant to small input changes. The uncertain parameters are represented with intervals, which results in solution objectives also being represented with intervals. The algorithm for comparing solutions then compares worst-case scenario values of objectives, that is, the values at the border of an interval.In [10], the authors tackled noisy optimization problems with a modified NSGA-II algorithm [5] for handling solutions with uncertainty. The procedure for obtaining the rank of solutions is transformed so that it also considers the variance of solutions. Dominated solutions can also be ranked on the Pareto frontier, if the distance to any nondominated solution, calculated from the fitness values and variances of solutions, is smaller than the threshold called neighborhood restriction factor. During the optimization process, this factor becomes smaller and the number of evaluations taken for nondominated solutions increases, resulting in a smaller variance and a more precise set of nondominated solutions.A concept of comparing solutions with uncertain objectives represented with intervals is presented in [11]. The authors define the extension of Pareto dominance based on a theory of probabilistic dominance. They present a case where objective values are continuously and uniformly distributed inside the interval and by comparing the distributions the probability of dominance is calculated. The approach is then implemented in the modified SPEA [12] algorithm.Another concept of comparing solutions under uncertainty is presented in [13], where using a possibilistic framework the new Pareto relations are defined. The solutions characterized by a particularpossibility distribution are represented with triangular possibility distributions-triplet of values, most plausible value and lower and upper borders of distribution that represent the least plausible values. Based on this representation, the strong Pareto dominance, weak Pareto dominance, and indifference are defined and used on a vehicle routing problem with uncertain demands.A more theoretical approach to the solution comparison under uncertainty is presented in [14] for optimization problems where the uncertainty of the solutions cannot be reduced by the sampling methods. The solutions are represented with intervals, and new relations are defined for comparing those intervals. The authors define certain and uncertain domination criteria for comparing intervals. On this basis, they suggest a strong Pareto dominance relation in cases when the dominance relation can be determined and weak Pareto dominance relation when the domination relation cannot be determined because of uncertainty. In this case, the expected values for every solution are assumed and these values are then compared.In [15], a partial order approach is suggested to enable the comparison of solutions represented with confidence intervals. This approach does not differentiate between the cases in which the upper border of one interval dominates the lower border of another interval and the cases in which some part of intervals overlap. A very similar approach to handle solutions represented with intervals, called imprecise Pareto relations, is presented in [16].Bounding boxes representing multiobjective solutions with confidence intervals are defined in [17] (they are described in greater detail in Section 4). The authors presented various comparison strategies, but in all strategies the comparison of bounding boxes is simplified to the comparison of bounding box bounds. The individuals are compared to all solutions in the population and individuals with a small probability of being competitive are rejected, while individuals with a high probability of being better are exactly evaluated.To our knowledge, none of these methods systematically covers all cases that can occur when comparing (constrained) multiobjective solutions with confidence intervals, which is the main contribution of this paper.Because the comparison of solutions under uncertainty is based on the comparison of solutions without uncertainty, the latter concept is described first.


## 3. Relations without Uncertainty

A constrained multiobjective optimization problem (CMOP) consists of finding the minimum of the function:(1)f:X⟶Zf:(x1,…,xn)⟼(f1(x1,…,xn),…,fm(x1,…,xn)),
subject to(i) boundary constraints:(2)ximin⁡≤xi≤ximax⁡;(i=1,…,n),(ii) constraints on decision values:(3)gj(x)≤0;(j=1,2,…,k),(iii) constraints on objectives:(4)hj(f(x))≤0;(j=1,2,…,l),
where n is the number of variables, m is the number of objectives, k is the number of constraints on decision variables, and l is the number of constraints on objectives. Each solution x=(x1,…,xn)∈X is called adecision vector, while the corresponding element z=f(x)∈Z is anobjective vector.The boundary constraints define thesearch region of an optimization problem by setting lower bounds xmin⁡ and the upper bounds xmax⁡ for the variables. Inside the search region, the constraints on decision values further define the feasibility of solutions. An example of such constraint would be that the sum of two variables should not exceed a predefined value. Since these constraints can be complex, the region they define can also be complex. As a result, the red contour in Figure 1 that represents this region is drawn as a complex shape. The constraints on objectives limit the feasibility of the objective values. An example of constraint on objectives would be to set a maximum budget and a minimum top speed in the optimization problem of finding a fast and cheap car. The constraints on objectives are typically not very complex; hence the region defined by these constraints is fairly simple. We call this regionfeasible objective value region; in Figure 1 it is surrounded by the blue and green lines.Figure 1
The objective space of a constrained multiobjective optimization problem.If all constraints are satisfied, we say that the solution isfeasible; otherwise it isinfeasible. All feasible solutions in the decision space constitute thefeasible region. The mapping of this region in the objective space is calledfeasible region image and this region is marked with black hatching in Figure 1. The feasible solutions of an optimization problem that are the best with regard to all objectives create a front of solutions called thePareto optimal front, which is indicated by the green line in Figure 1.This problem formulation is used to describe the relations between the solutions without and with uncertainty. In this section we consider the case in which all solutions of a CMOP are exactly evaluated; that is, they are without uncertainty.Definition 1 (Pareto dominance).
The objective vectorz dominates the objective vector w, z≺w, if and only if zj≤wj for all j∈{1,…,m} and zk<wk for at least one k∈{1,…,m}.Definition 2 (weak Pareto dominance).
The objective vectorz weakly dominates the objective vector w, z⪯w, if and only if zj≤wj for all j∈{1,…,m}.Definition 3 (strict Pareto dominance).
The objective vectorz strictly dominates the objective vector w, z≺≺w, if and only if zj<wj for all j∈{1,…,m}.Whenz=f(x), w=f(y), and z (weakly or strictly) dominates w, we say that solution x (weakly or strictly) dominates solution y. In other words, solution x is equal to or better than solution y. The weak Pareto dominance is a natural generalization of the ≤ relation, and the strict Pareto dominance is the natural generalization of the < relation.Definition 4 (incomparability).
The objective vectorsz and w are incomparable, z∥w, if and only if z⋠w and w⋠z.Again, ifz and w are incomparable, solutions x and y are incomparable.The abovedefined relations are usually used only when solving problems without constraints where all solutions are feasible. For cases where the feasibility of solutions is unknown, the Pareto dominance relation is slightly modified, as suggested in [5].Definition 5 (constrained dominance).
The objective vectorz constrained-dominates the objective vector w, z≺cw, if any of the following conditions are true. (1)
Solutionz is feasible and solution w is not.(2)
Solutionsz and w are both infeasible, but solution z has a smaller overall constraint violation.(3)
Solutionsz and w are feasible and solution z Pareto dominates solution w.Whenz=f(x), w=f(y), and z constrained-dominates w, we say that solution x constrained-dominates solution y.The effect of using the constrained dominance principle is that any feasible solution is better than any infeasible solution and that of the two infeasible solutions the one closer to the feasibility region is better.


## 4. Relations under Uncertainty

In this section we consider the case where the objective values of the solutions are represented with the approximated values and confidence intervals for each approximation. In such a case, the standard relations described previously are not suitable and must be adapted to accommodate the uncertainty. Every solutionx is represented with a vector of approximated objective values z=f(x)=(z1,z2,…,zm) and a confidence vector ε=(ε1,ε2,…,εm). For the objective zi the confidence interval is equal to [zi-εi,zi+εi]. In order to be able to compare the solutions represented in this way, the relations between the solutions under uncertainty are defined on thebounding boxes (BBs) of their objective values. From the vectors of the approximated values and the confidence intervals, the bounding box of an objective vector z is designed as (Figure 2)
(5)BB(z,ɛ)=[z1-ε1,z1+ε1]×[z2-ε2,z2-ε2]×⋯×[zm-εm,zm-εm].Figure 2
The bounding box of an objective vector.This definition ofBB presumes that the confidence intervals are symmetric. This is not always the case, for example, because of nonsymmetric form of noise. Instead of considering just confidence vector ε, we could define lower-bound confidence vector ε_=(ε1_,ε2_,…,εm_) and upper-bound confidence vector ε¯=(ε1¯,ε2¯,…,εm¯). For the objective zi the confidence interval would then be equal to [zi-εi_,zi+εi¯], and the definition of the bounding box that considers the nonsymmetric uncertainty intervals would then be
(6)BB(z,ε_,ε¯)=[z1-ε1_,z1+ε1¯]×[z2-ε2_,z2+ε2¯]×⋯×[zm-εm_,zm+εm¯].
However, since the relations under uncertainty are indifferent to the shape and size of the bounding boxes, we can for the sake of simplicity presume that the confidence interval is always symmetric.In addition to bounding boxes, where every objective has its own confidence interval, multiobjective solutions with uncertainty can also be represented with ellipsoids. Representation with ellipsoids restricts all objectives from obtaining their worst-case values simultaneously. But since comparing multiobjective solutions is performed by comparing pairs of objectives, where the confidence of each objective is inspected, we adopt the approach with bounding boxes.We handle relations under uncertainty without constraints and with constraints separately.


### 4.1. Relations under Uncertainty without Constraints

Definition 6 (probable Pareto dominance).
The bounding boxBB(z,ɛ) probably dominates the bounding box BB(w,δ), BB(z,ɛ)≺uBB(w,δ), if and only if for every z′∈BB(z,ɛ) and every w′∈BB(w,δ): z′≺w′.Ifz=f(x) with confidence vector ɛ, w=f(y) with confidence vector δ, and BB(z,ɛ)≺uBB(w,δ), then solution x probably dominates solution y (x≺uy). In other words, x dominates y with (high) confidence (depending on ɛ and δ).To test whetherBB(z,ɛ) probably dominates BB(w,δ) it is enough to check if the corner point (z1+ε1,z2+ε2,…,zm+εm) dominates the corner point (w1-δ1,w2-δ2,…,wm-δm). If it does, then BB(z,ɛ)≺uBB(w,δ).Figure3 shows the objective values z1,…,z5 and their bounding boxes. We can see that z1 probably dominates solution z4 (z1≺uz4).Figure 3
Approximated solutions presented in the objective space using bounding boxes.Analogously, other relations under uncertainty can be defined.Definition 7 (probable Pareto nondominance).
The bounding boxBB(z,ɛ) is probably nondominated by the bounding box BB(w,δ), BB(z,ɛ)⊁uBB(w,δ), if and only if for every z′∈BB(z,ɛ) and w′∈BB(w,δ), z′≺w′ or z′∥w′.Several examples of probable Pareto nondominance can be seen in Figure3: z1⊁uz2, z1⊁uz3, z1⊁uz4, z1⊁uz5, z2⊁uz4, and z3⊁uz4.Ifz=f(x) with confidence vector ɛ, w=f(y) with confidence vector δ, and BB(z,ɛ)⊁uBB(w,δ), we say that solution x is probably nondominated by solution y (x⊁uy). This means that we expect that either x dominates y or that the solutions are incomparable.Definition 8 (probable incomparability).
The bounding boxBB(z,ɛ) is probably incomparable with the bounding box BB(w,δ), BB(z,ɛ)∥uBB(w,δ), if and only if for every z′∈BB(z,ɛ) and w′∈BB(w,δ), z′∥w′.Again, two solutionsx and y are probably incomparable when their corresponding bounding boxes are probably incomparable (x∥uy). In Figure 3, z2 is probably incomparable with z3.Finally, when none of the presented relations under uncertainty apply, two solutions are in an undetermined relation.Definition 9 (undetermined relation).
The bounding boxBB(z,ɛ) is in an undetermined relation with the bounding box BB(w,δ), BB(z,ɛ)~uBB(w,δ), if and only if BB(z,ɛ)∩BB(w,δ)≠∅.Ifz=f(x) with confidence vector ɛ, w=f(y) with confidence vector δ, and BB(z,ɛ)~uBB(w,δ), we say that solution x is in an undetermined relation with solution y (x~uy). This means it is expected that either one solution weakly dominates the other or that the solutions are incomparable. In Figure 3, z5 is in an undetermined relation with z2, z3, and z4.Two implications can be found between relations under uncertainty. If solutionx probably dominates solution y, then the solution x is also probably nondominated by the solution y:
(7)x≺uy⟹x⊁uy.
Similarly, probable incomparability implies probable Pareto nondominance
(8)x∥uy⟹x⊁uy.If all the solutions are exactly evaluated, that is, all their corresponding confidence interval widths equal zero, the relations presented in this section directly translate to those described in Section3.


### 4.2. Relations under Uncertainty with Constraints

Similarly to the Pareto dominance relations (Section3), the relations under uncertainty without constraints (Section 4.1) are usually applied only if all solutions are feasible. To compare solutions represented with BBs where the feasibility of solutions is uncertain, we need to define a measure of feasibility for solutions represented with BBs. Since BBs are defined on the objective space, we only need to check the feasibility of BBs against constraints on objectives that define the feasible objective value region F. We assume that, before checking these constraints, the solution has already met constraints on decision values and boundary constraints.Definition 10 (probable feasibility).
The bounding boxBB(z,ɛ) is probably feasible if BB(z,ɛ)∩F=BB(z,ɛ), where F is the feasible objective value region of the problem.Definition 11 (probable infeasibility).
The bounding boxBB(z,ɛ) is probably infeasible if BB(z,ɛ)∩F=∅, where F is the feasible objective value region of the problem.Definition 12 (undetermined feasibility).
The bounding boxBB(z,ɛ) has undetermined feasibility if BB(z,ɛ)∩F≠BB(z,ɛ) and BB(z,ɛ)∩F≠∅, where F is the feasible objective value region of the problem.In the unlikely case of very complex constraints on objectives, it can be difficult to implement and calculate the intersection betweenBB and F. However, the procedure can be simplified by checking the feasibility only for the points on the vertices of the BB. If all points are feasible, we can say that the solution is probably feasible; if all points are infeasible, the solution is probably infeasible; and if some points are feasible and others are not, we can say the solution has undetermined feasibility. We can assume this simplification since the widths of the confidence intervals are relatively small and we can presume that the vertices represent the whole BB sufficiently well.To compare feasible and infeasible solutions represented withBBs, we define the following four relations under uncertainty with constraints.Definition 13 (probable constrained dominance).
The bounding boxBB(z,ɛ) probably constrained-dominates the bounding box BB(w,δ), BB(z,ɛ)≺ucBB(w,δ), if any of the following conditions is true. (1)
The bounding boxBB(z,ɛ) is probably feasible and the bounding box BB(w,δ) is probably infeasible.(2)
The bounding boxesBB(z,ɛ) and BB(w,δ) are both probably infeasible, but the objective vector z has a smaller overall constraint violation.(3)
The bounding boxesBB(z,ɛ) and BB(w,δ) are both probably feasible and BB(z,ɛ)≺uBB(w,δ).(4)
The bounding boxBB(z,ɛ) is probably feasible and the bounding box BB(w,δ) has undetermined feasibility and BB(z,ɛ)≺uBB(w,δ).Ifz=f(x) with confidence vector ɛ, w=f(y) with confidence vector δ, and BB(z,ɛ)≺ucBB(w,δ), then the solution x probably constrained-dominates the solution y (x≺ucy).Definition 14 (probable constrained nondominance).
The bounding boxBB(z,ε) is probably constrained-non-dominated by the bounding box BB(w,δ), BB(z,ε)⊁ucBB(w,δ), if any of the following conditions is true. (1)
The bounding boxesBB(z,ε) and BB(w,δ) are probably feasible and BB(z,ε)⊁uBB(w,δ).(2)
The bounding boxBB(z,ε) is probably feasible and the bounding box BB(w,δ) has undetermined feasibility and either BB(z,ε)⊁uBB(w,δ) or BB(z,ε)∥uBB(w,δ).Ifz=f(x) with confidence vector ε, w=f(y) with confidence vector δ, and BB(z,ε)⊁ucBB(w,δ), then the solution x is probably constrained-non-dominated by the solution y (x⊁ucy).Definition 15 (probable constrained incomparability).
The bounding boxBB(z,ε) is probably constrained-incomparable with the bounding box BB(w,δ), BB(z,ε)∥ucBB(w,δ), if any of the following conditions is true. (1)
The bounding boxesBB(z,ε) and BB(w,δ) are probably feasible and BB(z,ε)∥uBB(w,δ).(2)
The bounding boxesBB(z,ε) and BB(w,δ) are both probably infeasible, and both objective vectors z and w have the same overall constraint violation.Two solutionsx and y are probably constrained-incomparable when the corresponding bounding boxes are probably constrained-incomparable (x∥ucy).Definition 16 (undetermined constrained relation).
The bounding boxBB(z,ε) is in an undetermined constrained relation with the bounding box BB(w,δ), BB(z,ε)~ucBB(w,δ), if the two bounding boxes are not in any other constrained relation under uncertainty.Again, two solutionsx and y are in an undetermined constrained relation when the corresponding bounding boxes are in an undetermined constrained relation (x~ucy).When two solutions are in an undetermined constrained relation, the three following outcomes are possible:(1) the first solution dominates the second one, (2) the second solution dominates the first one, or (3) the solutions are incomparable. We present a possible scenario to clarify why the solutions can be in an undetermined constrained relation due to their feasibility. We compare solution x with undetermined feasibility and solution y with probable feasibility and x is probably nondominated by y. This means that if we were to exactly evaluate solution x and it would be infeasible, the solution y would dominate the solution x. This implies that the solutions can be in any relation; hence, by definition, they are in an undetermined constrained relation. Similarly, there are also other cases in which solutions are in an undetermined constrained relation and we need to exactly evaluate at least one of the solutions.All relations for comparing solutions mentioned in this paper are summarized in Tables1, 2, and 3.Table 1
Relations without uncertainty.
Relation name
Relation symbol
Comparison
Pareto dominance
z
≺
w
z dominates w
Weak Pareto dominance
z
≼
w
z weakly dominates w
Strict Pareto dominance
z
≺
≺
w
z strictly dominates w
Incompatibility
z
∥
w
z is incomparable with w
Constrained dominance
z
≺
c
w
z constrained-dominates wTable 2
Relations under uncertainty without constraints.
Relation name
Relation symbol
Comparison
Probable Pareto dominance
BB
(
z
,
ε
)
≺
u
BB
(
w
,
δ
)
BB
(
z
,
ε
) probably dominates BB(w,δ)
Probable Pareto nondominance
BB
(
z
,
ε
)
⊁
u
BB
(
w
,
δ
)
BB
(
z
,
ε
) is probably nondominated by BB(w,δ)
Probable incomparability
BB
(
z
,
ε
)
∥
u
BB
(
w
,
δ
)
BB
(
z
,
ε
) is probably incomparable with BB(w,δ)
Undetermined relation
BB
(
z
,
ε
)
~
u
BB
(
w
,
δ
)
BB
(
z
,
ε
) is in an undetermined relation with BB(w,δ)Table 3
Relations under uncertainty with constraints.
Relation name
Relation symbol
Comparison
Probable constrained dominance
BB
(
z
,
ε
)
≺
u
c
BB
(
w
,
δ
)
BB
(
z
,
ε
) probably constrained-dominates BB(w,δ)
Probable constrained nondominance
BB
(
z
,
ε
)
⊁
u
c
BB
(
w
,
δ
)
BB
(
z
,
ε
) is probably constrained-non-dominated by BB(w,δ)
Probable constrained incomparability
BB
(
z
,
ε
)
∥
u
c
BB
(
w
,
δ
)
BB
(
z
,
ε
) is probably constrained-incomparable with BB(w,δ)
Undetermined constrained relation
BB
(
z
,
ε
)
~
u
c
BB
(
w
,
δ
)
BB
(
z
,
ε
) is in an undetermined constrained relation with BB(w,δ)


## 4.1. Relations under Uncertainty without Constraints

Definition 6 (probable Pareto dominance).
The bounding boxBB(z,ɛ) probably dominates the bounding box BB(w,δ), BB(z,ɛ)≺uBB(w,δ), if and only if for every z′∈BB(z,ɛ) and every w′∈BB(w,δ): z′≺w′.Ifz=f(x) with confidence vector ɛ, w=f(y) with confidence vector δ, and BB(z,ɛ)≺uBB(w,δ), then solution x probably dominates solution y (x≺uy). In other words, x dominates y with (high) confidence (depending on ɛ and δ).To test whetherBB(z,ɛ) probably dominates BB(w,δ) it is enough to check if the corner point (z1+ε1,z2+ε2,…,zm+εm) dominates the corner point (w1-δ1,w2-δ2,…,wm-δm). If it does, then BB(z,ɛ)≺uBB(w,δ).Figure3 shows the objective values z1,…,z5 and their bounding boxes. We can see that z1 probably dominates solution z4 (z1≺uz4).Figure 3
Approximated solutions presented in the objective space using bounding boxes.Analogously, other relations under uncertainty can be defined.Definition 7 (probable Pareto nondominance).
The bounding boxBB(z,ɛ) is probably nondominated by the bounding box BB(w,δ), BB(z,ɛ)⊁uBB(w,δ), if and only if for every z′∈BB(z,ɛ) and w′∈BB(w,δ), z′≺w′ or z′∥w′.Several examples of probable Pareto nondominance can be seen in Figure3: z1⊁uz2, z1⊁uz3, z1⊁uz4, z1⊁uz5, z2⊁uz4, and z3⊁uz4.Ifz=f(x) with confidence vector ɛ, w=f(y) with confidence vector δ, and BB(z,ɛ)⊁uBB(w,δ), we say that solution x is probably nondominated by solution y (x⊁uy). This means that we expect that either x dominates y or that the solutions are incomparable.Definition 8 (probable incomparability).
The bounding boxBB(z,ɛ) is probably incomparable with the bounding box BB(w,δ), BB(z,ɛ)∥uBB(w,δ), if and only if for every z′∈BB(z,ɛ) and w′∈BB(w,δ), z′∥w′.Again, two solutionsx and y are probably incomparable when their corresponding bounding boxes are probably incomparable (x∥uy). In Figure 3, z2 is probably incomparable with z3.Finally, when none of the presented relations under uncertainty apply, two solutions are in an undetermined relation.Definition 9 (undetermined relation).
The bounding boxBB(z,ɛ) is in an undetermined relation with the bounding box BB(w,δ), BB(z,ɛ)~uBB(w,δ), if and only if BB(z,ɛ)∩BB(w,δ)≠∅.Ifz=f(x) with confidence vector ɛ, w=f(y) with confidence vector δ, and BB(z,ɛ)~uBB(w,δ), we say that solution x is in an undetermined relation with solution y (x~uy). This means it is expected that either one solution weakly dominates the other or that the solutions are incomparable. In Figure 3, z5 is in an undetermined relation with z2, z3, and z4.Two implications can be found between relations under uncertainty. If solutionx probably dominates solution y, then the solution x is also probably nondominated by the solution y:
(7)x≺uy⟹x⊁uy.
Similarly, probable incomparability implies probable Pareto nondominance
(8)x∥uy⟹x⊁uy.If all the solutions are exactly evaluated, that is, all their corresponding confidence interval widths equal zero, the relations presented in this section directly translate to those described in Section3.


## 4.2. Relations under Uncertainty with Constraints

Similarly to the Pareto dominance relations (Section3), the relations under uncertainty without constraints (Section 4.1) are usually applied only if all solutions are feasible. To compare solutions represented with BBs where the feasibility of solutions is uncertain, we need to define a measure of feasibility for solutions represented with BBs. Since BBs are defined on the objective space, we only need to check the feasibility of BBs against constraints on objectives that define the feasible objective value region F. We assume that, before checking these constraints, the solution has already met constraints on decision values and boundary constraints.Definition 10 (probable feasibility).
The bounding boxBB(z,ɛ) is probably feasible if BB(z,ɛ)∩F=BB(z,ɛ), where F is the feasible objective value region of the problem.Definition 11 (probable infeasibility).
The bounding boxBB(z,ɛ) is probably infeasible if BB(z,ɛ)∩F=∅, where F is the feasible objective value region of the problem.Definition 12 (undetermined feasibility).
The bounding boxBB(z,ɛ) has undetermined feasibility if BB(z,ɛ)∩F≠BB(z,ɛ) and BB(z,ɛ)∩F≠∅, where F is the feasible objective value region of the problem.In the unlikely case of very complex constraints on objectives, it can be difficult to implement and calculate the intersection betweenBB and F. However, the procedure can be simplified by checking the feasibility only for the points on the vertices of the BB. If all points are feasible, we can say that the solution is probably feasible; if all points are infeasible, the solution is probably infeasible; and if some points are feasible and others are not, we can say the solution has undetermined feasibility. We can assume this simplification since the widths of the confidence intervals are relatively small and we can presume that the vertices represent the whole BB sufficiently well.To compare feasible and infeasible solutions represented withBBs, we define the following four relations under uncertainty with constraints.Definition 13 (probable constrained dominance).
The bounding boxBB(z,ɛ) probably constrained-dominates the bounding box BB(w,δ), BB(z,ɛ)≺ucBB(w,δ), if any of the following conditions is true. (1)
The bounding boxBB(z,ɛ) is probably feasible and the bounding box BB(w,δ) is probably infeasible.(2)
The bounding boxesBB(z,ɛ) and BB(w,δ) are both probably infeasible, but the objective vector z has a smaller overall constraint violation.(3)
The bounding boxesBB(z,ɛ) and BB(w,δ) are both probably feasible and BB(z,ɛ)≺uBB(w,δ).(4)
The bounding boxBB(z,ɛ) is probably feasible and the bounding box BB(w,δ) has undetermined feasibility and BB(z,ɛ)≺uBB(w,δ).Ifz=f(x) with confidence vector ɛ, w=f(y) with confidence vector δ, and BB(z,ɛ)≺ucBB(w,δ), then the solution x probably constrained-dominates the solution y (x≺ucy).Definition 14 (probable constrained nondominance).
The bounding boxBB(z,ε) is probably constrained-non-dominated by the bounding box BB(w,δ), BB(z,ε)⊁ucBB(w,δ), if any of the following conditions is true. (1)
The bounding boxesBB(z,ε) and BB(w,δ) are probably feasible and BB(z,ε)⊁uBB(w,δ).(2)
The bounding boxBB(z,ε) is probably feasible and the bounding box BB(w,δ) has undetermined feasibility and either BB(z,ε)⊁uBB(w,δ) or BB(z,ε)∥uBB(w,δ).Ifz=f(x) with confidence vector ε, w=f(y) with confidence vector δ, and BB(z,ε)⊁ucBB(w,δ), then the solution x is probably constrained-non-dominated by the solution y (x⊁ucy).Definition 15 (probable constrained incomparability).
The bounding boxBB(z,ε) is probably constrained-incomparable with the bounding box BB(w,δ), BB(z,ε)∥ucBB(w,δ), if any of the following conditions is true. (1)
The bounding boxesBB(z,ε) and BB(w,δ) are probably feasible and BB(z,ε)∥uBB(w,δ).(2)
The bounding boxesBB(z,ε) and BB(w,δ) are both probably infeasible, and both objective vectors z and w have the same overall constraint violation.Two solutionsx and y are probably constrained-incomparable when the corresponding bounding boxes are probably constrained-incomparable (x∥ucy).Definition 16 (undetermined constrained relation).
The bounding boxBB(z,ε) is in an undetermined constrained relation with the bounding box BB(w,δ), BB(z,ε)~ucBB(w,δ), if the two bounding boxes are not in any other constrained relation under uncertainty.Again, two solutionsx and y are in an undetermined constrained relation when the corresponding bounding boxes are in an undetermined constrained relation (x~ucy).When two solutions are in an undetermined constrained relation, the three following outcomes are possible:(1) the first solution dominates the second one, (2) the second solution dominates the first one, or (3) the solutions are incomparable. We present a possible scenario to clarify why the solutions can be in an undetermined constrained relation due to their feasibility. We compare solution x with undetermined feasibility and solution y with probable feasibility and x is probably nondominated by y. This means that if we were to exactly evaluate solution x and it would be infeasible, the solution y would dominate the solution x. This implies that the solutions can be in any relation; hence, by definition, they are in an undetermined constrained relation. Similarly, there are also other cases in which solutions are in an undetermined constrained relation and we need to exactly evaluate at least one of the solutions.All relations for comparing solutions mentioned in this paper are summarized in Tables1, 2, and 3.Table 1
Relations without uncertainty.
Relation name
Relation symbol
Comparison
Pareto dominance
z
≺
w
z dominates w
Weak Pareto dominance
z
≼
w
z weakly dominates w
Strict Pareto dominance
z
≺
≺
w
z strictly dominates w
Incompatibility
z
∥
w
z is incomparable with w
Constrained dominance
z
≺
c
w
z constrained-dominates wTable 2
Relations under uncertainty without constraints.
Relation name
Relation symbol
Comparison
Probable Pareto dominance
BB
(
z
,
ε
)
≺
u
BB
(
w
,
δ
)
BB
(
z
,
ε
) probably dominates BB(w,δ)
Probable Pareto nondominance
BB
(
z
,
ε
)
⊁
u
BB
(
w
,
δ
)
BB
(
z
,
ε
) is probably nondominated by BB(w,δ)
Probable incomparability
BB
(
z
,
ε
)
∥
u
BB
(
w
,
δ
)
BB
(
z
,
ε
) is probably incomparable with BB(w,δ)
Undetermined relation
BB
(
z
,
ε
)
~
u
BB
(
w
,
δ
)
BB
(
z
,
ε
) is in an undetermined relation with BB(w,δ)Table 3
Relations under uncertainty with constraints.
Relation name
Relation symbol
Comparison
Probable constrained dominance
BB
(
z
,
ε
)
≺
u
c
BB
(
w
,
δ
)
BB
(
z
,
ε
) probably constrained-dominates BB(w,δ)
Probable constrained nondominance
BB
(
z
,
ε
)
⊁
u
c
BB
(
w
,
δ
)
BB
(
z
,
ε
) is probably constrained-non-dominated by BB(w,δ)
Probable constrained incomparability
BB
(
z
,
ε
)
∥
u
c
BB
(
w
,
δ
)
BB
(
z
,
ε
) is probably constrained-incomparable with BB(w,δ)
Undetermined constrained relation
BB
(
z
,
ε
)
~
u
c
BB
(
w
,
δ
)
BB
(
z
,
ε
) is in an undetermined constrained relation with BB(w,δ)


## 5. Comparing Solutions under Uncertainty

In iterative optimization algorithms, the process of gradual solution improvement is based on solution comparisons. By comparing solutions, the algorithm finds which solutions are better and promotes them further, while those that are found worse are discarded.In this section, we show the use of constrained relations under uncertainty for comparing two solutions represented withBBs. This comparison can be implemented in any multiobjective optimization algorithm. However, since every algorithm applies a specific search strategy, we present how the relations under uncertainty can be used instead of Pareto dominance relations.Nevertheless, it is to be noted that straightforward use of relations under uncertainty instead of Pareto dominance relations is not always possible. When the confidence intervals (at least one) are overlapping, confidence interval reduction procedures have to be applied in order to be able to determine the result of comparison. These additional procedures can, for example, be exact evaluations, in the case of surrogate-based optimization and in the case of optimization with noisy objectives additional evaluations that result in reducing the width of the confidence interval. In cases where the width of the confidence interval cannot be changed and the relations between solutions are unknown, another approach needs to be taken, for example, comparison of the approximated values instead of comparingBBs.When comparing solutionp with confidence vector ε and solution q with confidence vector δ, we consecutively check the four possibilities listed below.(1) Ifp≺ucq, we can consider p and q to be in the Pareto dominance relation (p≺q).Here the solutionp is probably better than the solution q; therefore, no confidence interval reduction is necessary as it would probably not change the dominance relation.(2) Ifp∥ucq, we can consider p and q to be incomparable (p∥q).In this case, solutionsp and q are probably constrained-incomparable. Even if both solutions were exactly evaluated, they would probably still be incomparable and the algorithm would probably still keep both solutions. Hence, no confidence interval reduction is needed in this case.(3) Ifp⊁ucq, the algorithm checks ε. If ε≠0, the algorithm performs confidence interval reduction on p and compares the solutions again. If ε=0, the algorithm performs confidence interval reduction on solution q and compares the solutions again.In this case, the solutionp is probably better in at least one objective and probably not worse in the others. In order to determine whether either solution p dominates solution q or they are incomparable, (at least) for one solution the confidence interval reduction needs to be performed. Because p is more promising, its confidence intervals are checked. If their widths are different from zero, which means that the solution is approximated, the algorithm performs confidence interval reduction on p and then compares the solutions again. If the confidence interval widths are equal to zero, which means that solution p is exactly evaluated, then, in order to be able to compare the solutions, the algorithm performs confidence interval reduction on q and compares the solutions again.(4) Ifp~ucq, the algorithm checks the feasibility of solutions. If both solutions have undetermined feasibility, the algorithm randomly chooses one solution and performs confidence interval reduction on it. If one solution has undetermined feasibility, the algorithm performs confidence interval reduction on that solution and compares the solutions again. If both solutions are probably feasible, the algorithm checks the confidence vector of a randomly picked solution. If it is not equal to zero, the algorithm performs confidence interval reduction on this solution and compares the solutions again. If the confidence vector is equal to zero, the algorithm performs confidence interval reduction on the other solution and compares the solutions again.In this case, the only way to find out which solution is better is to perform confidence interval reduction on (at least) one solution. Because solutions near the borders of the feasibility region are usually better, the algorithm first checks and performs confidence interval reduction on these solutions. If both solutions are probably feasible, the algorithm checks whether the first solution is exactly evaluated. If it is not, the algorithm performs confidence interval reduction on it. If it is, the algorithm performs additional confidence interval reduction on the other solution and then compares the solutions again.


## 6. Empirical Proof of Concept

In this section we test the hypothesis that by using the new relations under uncertainty the number of incorrect comparisons is reduced. In the following experiment we compared multiobjective solutions with uncertainty where the uncertainty comes from solution approximations gained with surrogate models. To be able to compare the number of incorrect comparisons, every solution comparison was performed with relations under uncertainty and with Pareto dominance relations. In addition to comparing approximated solution values, we also compared the exact solution values. This allowed us to monitor the accuracy of comparison of uncertain solutions.Since we did not want to use random solutions for comparisons, we decided to perform solution comparisons as executed by the NSGA-II algorithm [5]. In every generation the NSGA-II algorithm creates a new set of solutions, adds them to the current ones, and then performs selection on the union to select the most promising solutions. The selection procedure includes comparing every solution with all other solutions to determine its dominance status. On these comparisons we compared the relations under uncertainty with the Pareto dominance relations.The comparison was performed on three benchmark problems. One is Poloni optimization problem [18] and two are from [1], called OSY and SRN. All of them are two-objective problems.Gaussian process (GP) modeling [19] was used to build surrogate models for solution approximations. For the confidence interval width of the approximation we used the two standard deviations (2σ), which corresponds to about 95% of the normal distribution of the approximations. To test the correlation between the surrogate model accuracy and the incorrect comparisons, five different models of increasing accuracy were built—each on larger number of solutions.The algorithm parameter values used for testing were the same for all three problems. They were set as follows:(i)
population size: 100,(ii)
number of generations: 100,(iii)
number of runs: 30.For every problem and for every model we calculated the number of incorrect comparisons for each comparison technique. In addition, we calculated the average confidence interval width and for relations under uncertainty also the number of cases where, in order to be able to compare the solutions, confidence interval reduction procedures (in our case exact evaluations of approximated solutions) were performed.The results averaged over 30 runs are presented in Tables4, 5, and 6. These results show that by increasing the number of solutions used for building the surrogate model the accuracy of the model increases and the number of incorrect comparisons decreases. The reason for the high number of incorrect comparisons using the models built on smaller number of solutions is in the fact that the solutions used for building the surrogate models do not cover the decision space well enough. Due to the lack of information, the solution approximations can be incorrect by a large margin. This can also result in the exact solution values falling out of the bounding boxes. This reflects in some incorrect comparisons also encountered with the relations under uncertainty.Table 4
Comparison of newly defined relations with Pareto dominance relations on the Poloni problem (average values over 30 runs).
Relation type
Solutions used for surrogate model
Number of comparisons
Incorrect comparisons
Number of comparisons with confidence interval reductions
Proportion of confidence interval reductions
Confidence interval width
Relations under uncertainty
20
3,940,200
1,515
3,635,805
92%
26.25
30
682
3,152,124
80%
15.41
50
138
1,218,337
31%
1.29
100
65
672,384
17%
0.012
200
13
549,380
14%
0.002
Pareto dominance relations
20
3,940,200
367,684
/
/
26.25
30
159,945
/
/
15.41
50
22,032
/
/
1.29
100
2,309
/
/
0.012
200
1,219
/
/
0.002Table 5
Comparison of newly defined relations with Pareto dominance relations on the OSY problem (average values over 30 runs).
Relation type
Solutions used for surrogate model
Number of comparisons
Incorrect comparisons
Number of comparisons with confidence interval reductions
Proportion of confidence interval reductions
Confidence interval width
Relations under uncertainty
20
3,940,200
74,181
2,289,682
58%
42.81
30
21,861
1,934,212
49%
25.98
50
19,342
1,426,775
36%
25.05
100
144
712,298
18%
0.07
200
152
271,821
7%
0.03
Pareto dominance relations
20
3,940,200
336,049
/
/
42.81
30
136,357
/
/
25.98
50
49,790
/
/
25.05
100
1,736
/
/
0.07
200
1,453
/
/
0.03Table 6
Comparison of newly defined relations with Pareto dominance relations on the SRN problem (average values over 30 runs).
Relation type
Solutions used for surrogate model
Number of comparisons
Incorrect comparisons
Number of comparisons with confidence interval reductions
Proportion of confidence interval reductions
Confidence interval width
Relations under uncertainty
20
3,940,200
7407
2,703,783
69%
50.03
30
16
2,338,535
59%
0.074
50
2
749,258
19%
0.099
100
3
359,952
9%
0.022
200
11
183,625
5%
0.009
Pareto dominance relations
20
3,940,200
188,401
/
/
50.03
30
161
/
/
0.074
50
543
/
/
0.099
100
645
/
/
0.022
200
648
/
/
0.009With the increasing number of solutions used for building the surrogate model the average confidence interval width also gets narrower. The narrower the confidence intervals, the smaller the bounding boxes and the number of required additional confidence interval reductions.Examining the number of incorrect comparisons for the two relation types, we can see that by using the Pareto dominance relations the number of incorrect comparisons is from 3 to 243 times higher than by using relations under uncertainty. Regardless of the accuracy of the surrogate model, we can conclude that by using relations under uncertainty the number of incorrect comparisons is reduced.As we can see, in order to reduce the number of incorrect comparisons, we have to perform additional confidence interval reductions. This in turn increases the total optimization time; hence a balance between the number of incorrect comparisons and the time spent performing additional confidence interval reductions needs to be found.


## 7. Conclusion

In this paper we have presented new relations for comparing solutions under uncertainty. The uncertainty can derive from noisy fitness functions, requirement for robust solutions, surrogate approximations, or time-varying fitness functions. The relations under uncertainty are defined on bounding boxes that are based on approximated values and confidence intervals. These relations extend the Pareto dominance relations and, in addition to the confidence intervals, also consider the feasibility of solutions. Comparing solutions using the proposed relations reduces the likelihood of incorrect comparisons and prevents the inaccurate approximations from spoiling the results. We have also shown how the new relations under uncertainty can be used for solution comparison in an arbitrary multiobjective optimization algorithm. In addition, the relations under uncertainty also offer the possibility of determining the dominance status of solutions without necessarily knowing their exact values first.



---

*Source: 817964-2014-05-18.xml*