HypE

HypE: an algorithm for fast hypervolume-based many-objective optimization. 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/


References in zbMATH (referenced in 29 articles )

Showing results 1 to 20 of 29.
Sorted by year (citations)

1 2 next

  1. Feliot, Paul; Bect, Julien; Vazquez, Emmanuel: A Bayesian approach to constrained single- and multi-objective optimization (2017)
  2. Steponavičė, Ingrida; Hyndman, Rob J.; Smith-Miles, Kate; Villanova, Laura: Dynamic algorithm selection for Pareto optimal set approximation (2017)
  3. Ye Tian, Ran Cheng, Xingyi Zhang, Yaochu Jin: PlatEMO: A MATLAB Platform for Evolutionary Multi-Objective Optimization (2017) arXiv
  4. Zuo, Cili; Wu, Lianghong; Zeng, Zhao-Fu; Wei, Hua-Liang: Stochastic fractal based multiobjective fruit fly optimization (2017)
  5. Lei, Hongtao; Wang, Rui; Laporte, Gilbert: Solving a multi-objective dynamic stochastic districting and routing problem with a co-evolutionary algorithm (2016)
  6. Martí, Luis; García, Jesús; Berlanga, Antonio; Molina, José M.: MONEDA: scalable multi-objective optimization with a neural network-based estimation of distribution algorithm (2016)
  7. Cao, Yongtao; Smucker, Byran J.; Robinson, Timothy J.: On using the hypervolume indicator to compare Pareto fronts: applications to multi-criteria optimal experimental design (2015)
  8. Giagkiozis, Ioannis; Purshouse, Robin C.; Fleming, Peter J.: An overview of population-based algorithms for multi-objective optimisation (2015)
  9. Li, Miqing; Yang, Shengxiang; Liu, Xiaohui: Bi-goal evolution for many-objective optimization problems (2015)
  10. Wang, Rui; Purshouse, Robin C.; Fleming, Peter J.: Preference-inspired co-evolutionary algorithms using weight vectors (2015)
  11. Dai, Cai; Wang, Yuping; Ye, Miao: A new evolutionary algorithm based on contraction method for many-objective optimization problems (2014)
  12. Derbel, Bilel; Humeau, Jérémie; Liefooghe, Arnaud; Verel, Sébastien: Distributed localized bi-objective search (2014)
  13. Jiang, Siwei; Zhang, Jie; Ong, Yew-Soon: Multiobjective optimization based on reputation (2014)
  14. Lei, Yu; Gong, Maoguo; Zhang, Jun; Li, Wei; Jiao, Licheng: Resource allocation model and double-sphere crowding distance for evolutionary multi-objective optimization (2014)
  15. Liu, Ruochen; Chen, Yangyang; Ma, Wenping; Mu, Caihong; Jiao, Licheng: A novel cooperative coevolutionary dynamic multi-objective optimization algorithm using a new predictive model (2014) ioport
  16. Shang, Ronghua; Wang, Yuying; Wang, Jia; Jiao, Licheng; Wang, Shuo; Qi, Liping: A multi-population cooperative coevolutionary algorithm for multi-objective capacitated arc routing problem (2014)
  17. von Lücken, Christian; Barán, Benjamín; Brizuela, Carlos: A survey on multi-objective evolutionary algorithms for many-objective problems (2014)
  18. Wang, Rui; Fleming, Peter J.; Purshouse, Robin C.: General framework for localised multi-objective evolutionary algorithms (2014) ioport
  19. Bringmann, Karl; Friedrich, Tobias; Igel, Christian; Voß, Thomas: Speeding up many-objective optimization by Monte Carlo approximations (2013)
  20. Kim, Hyoungjin; Liou, Meng-Sing: New fitness sharing approach for multi-objective genetic algorithms (2013)

1 2 next