HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization
HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization
复制标题
DOI：
10.1162/evco_a_00009
复制
发表时间：
2011-03-01
影响因子：
6.8
通讯作者：
Zitzler, Eckart
中科院分区：
文献类型：
--
作者：
Bader, Johannes;Zitzler, Eckart
在进化多准则优化领域，超体积指标是已知的唯一在帕累托支配性方面严格单调的单集质量度量：每当一个帕累托集近似完全支配另一个帕累托集近似时，那么支配集的指标值也会更好。该属性对于涉及大量目标函数的问题具有很高的兴趣和相关性。然而，超体积计算所需的大量计算工作迄今为止阻碍了该指标潜力的充分利用；当前基于超体积的搜索算法仅限于只有几个目标的问题。本文解决了这个问题并提出了一种快速搜索算法，该算法使用蒙特卡洛模拟来近似精确的超体积值。主要思想不是实际的指标值很重要，而是由超容量指标引起的解决方案的排名很重要。具体来说，我们提出了 HypE，一种用于多目标优化的超体积估计算法，通过该算法可以在估计的准确性和可用的计算资源之间进行权衡；因此，基于超体积的搜索不仅使多目标问题变得可行，而且还可以灵活地调整运行时间。此外，我们展示了如何使用相同的原理来统计比较不同多目标优化器相对于超体积的结果，到目前为止，统计测试仅限于目标很少的场景。实验结果表明，与现有的多目标进化算法相比，HypE 对于多目标问题非常有效。HypE 可以从 http://www.tik.ee.ethz.ch/sop/download/supplementary/hype/ 下载。
In the field of evolutionary multi-criterion optimization, the hypervolume indicator is the only single set quality measure that is known to be strictly monotonic with regard to Pareto dominance: whenever a Pareto set approximation entirely dominates another one, then the indicator value of the dominant set will also be better. This property is of high interest and relevance for problems involving a large number of objective functions. However, the high computational effort required for hypervolume calculation has so far prevented the full exploitation of this indicator's potential; current hypervolume-based search algorithms are limited to problems with only a few objectives.This paper addresses this issue and proposes a fast search algorithm that uses Monte Carlo simulation to approximate the exact hypervolume values. The main idea is not that the actual indicator values are important, but rather that the rankings of solutions induced by the hypervolume indicator. In detail, we present HypE, a hypervolume estimation algorithm for multi-objective optimization, by which the accuracy of the estimates and the available computing resources can be traded off; thereby, not only do many-objective problems become feasible with hypervolume-based search, but also the runtime can be flexibly adapted. Moreover, we show how the same principle can be used to statistically compare the outcomes of different multi-objective optimizers with respect to the hypervolume so far, statistical testing has been restricted to scenarios with few objectives. The experimental results indicate that HypE is highly effective for many-objective problems in comparison to existing multi-objective evolutionary algorithms.HypE is available for download at http://www.tik.ee.ethz.ch/sop/download/supplementary/hype/.