Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables*
研究了进化算法在机会约束优化问题中的理论表现，发现单目标算法在均匀约束下可能陷入局部最优，而多目标算法能高效找到所有置信水平下的最优解，并在最小生成树和最小支配集问题上验证了有效性。
Chance-constrained optimization problems allow us to model problems where constraints involving stochastic components should be violated only with a small probability. Evolutionary algorithms have been applied to this scenario and shown to achieve high-quality results. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for chance-constrained optimization. We study the scenario of stochastic components that are independent and normally distributed. Considering the simple single-objective (1+1) EA, we show that imposing an additional uniform constraint already leads to local optima for very restricted scenarios and an exponential optimization time. We therefore introduce a multiobjective formulation of the problem which trades off the expected cost and its variance. We show that multiobjective evolutionary algorithms are highly effective when using this formulation and obtain a set of solutions that contains an optimal solution for any possible confidence level imposed on the constraint. Furthermore, we prove that this approach can also be used to compute a set of optimal solutions for the chance-constrained minimum spanning tree problem. In order to deal with potentially exponentially many trade-offs in the multiobjective formulation, we propose and analyze improved convex multiobjective approaches. Experimental investigations on instances of the NP-hard stochastic minimum weight dominating set problem confirm the benefit of the multiobjective and the improved convex multiobjective approach in practice.