Efficient Computation of Probabilistic Dominance in Robust Multi-Objective Optimization

Real-world problems typically require the simultaneous op timization of several, often conflicting objectives. Many of these multi-objective optimization problems are characterized by wide ranges of uncertainties in their deci sion variables or objective functions, which further increases the complexity of optim ization. To cope with such uncertainties, robust optimization is widely studied aiming to distinguish candidate solutions with uncertain objectives specified by confidence intervals, probability distributions or sampled data. However, existing techniques most ly either fail to consider the actual distributions or assume uncertainty as instance s of uniform or Gaussian distributions. This paper introduces an empirical approac h that enables an efficient comparison of candidate solutions with uncertain objectiv es that can follow arbitrary distributions. Given two candidate solutions under compar ison, this operator calculates the probability that one solution dominates the other in terms of each uncertain objective. It can substitute for the standard comparison op erator of existing optimization techniques such as evolutionary algorithms to ena ble discovering robust solutions to problems with multiple uncertain objectives. Th is paper also proposes to incorporate various uncertainties in well-known multi-ob jective problems to provide a benchmark for evaluating uncertainty-aware optimization techniques. The proposed comparison operator and benchmark suite are integrated int o an existing optimization tool that features a selection of multi-objective optimiza tion problems and algorithms. Experiments show that in comparison with existing techniqu es, the proposed approach achieves higher optimization quality at lower overheads. The authors are with the Department of Computer Science, Friedr ich-Alexander-Universit at Erlangen-N urnberg (FAU), Erlangen 91058, Germany. A a candidate solution B a candidate solution B beta distribution C comparison operator c positive constant E expected value e approximation error f objective function N Gaussian distribution N number of samples or quantile cuts n number of decision variables m number of objective functions S sequence of samples s sample from an uncertain objective's distribution U uniform distribution u uncertainty added to an optimization problem V ar variance X random variable x decision variable γ comparison threshold δ tolerance (bound on an error) σ standard deviation ω interval width in a histogram 2 1 Introduction Real-world problems typically demand solutions that are optimized with respect to multiple criteria called objectives. In these so-called multi-objective optimization problems, the objectives often conflict with each other such that no single solution can b e found to be optimal in all objectives. Instead, one usually searches for a set of non-d ominated solutions known as Pareto front or Pareto set that provide decent tradeoffs among objectives.