Evolutionary multiobjective optimization (EMO) is a vivid area of research with a plethora of various methods proposed. Although these methods differ in some aspects, they also share many common algorithmic procedures like:
• filtering nondominated solutions which is a typical step in many EMO algorithms with an external Pareto archive,
• quality indicators (contribution) calculation/estimation used in indicator-based EMO and in computational experiments,
• scalarizing functions optimization in a set of solutions used in some EMO methods and in hypervolume and other quality indicators estimation.
Thus, the progress in EMO may be obtained not only by developing new EMO methods but also by improving efficiency and/or accuracy of such typical algorithmic procedures. In this tutorial we cover some recent developments in efficient data structures and algorithms for EMO. Precisely, we will cover the following topics:
- ND-Tree data structure which may be used for:
• Efficient update of the Pareto archive, i.e. checking if a new solution is nondominated, if so, adding it to the Pareto archive and removing dominated solutions from the archive.
• Finding the solution minimizing/maximizing a (modified) Chebycheff scalarizing function over a set of solutions, which, in turn, may be applied for:
o Adapting Pareto local search (PLS) for more than two objectives – Many objective PLS,
o Improving efficiency of hypervolume or R2 (contribution) estimation.
- Improved quick hypervolume algorithm for exact hypervolume calculation and its extensions for:
• Finding guaranteed bounds of hypervolume (contribution).
• Improving accuracy of Monte Carlo hypervolume (contribution) estimation.
• Finding extreme (minimum or maximum) hypervolume contribution/contributor in a set of solutions.
• Solving hypervolume subset selection problem through the lazy incremental or decremental greedy approach.
• On-line update of hypervolume value.
- New algorithm for exact calculation of R2 quality indicator, which is the first such algorithm with publically available implementation and computational complexity analysis.
We will also discuss some promising directions for further research in this area.
References:
• Jaszkiewicz and T. Lust. ND-Tree-Based Update: A Fast Algorithm for the Dynamic Nondominance Problem. IEEE Transactions On Evolutionary Computation, 22(5):778–791, OCT 2018.
• Andrzej Jaszkiewicz. Many-Objective Pareto Local Search. European Journal of Operational Research, 271(3):1001–1013, 2018.
• Jaszkiewicz. Improved quick hypervolume algorithm. Computers and Operations Research, 90:72–83, 2018.
• Jaszkiewicz, R. Susmaga, and P. Zielniewicz. Approximate hypervolume calculation with guaranteed or confidence bounds. PPSN XVI, pages 215–228, 2020.
• Andrzej Jaszkiewicz and Piotr Zielniewicz. Quick Extreme Hypervolume Contribution Algorithm. GECCO ’21, page 412–420, 2021.
• Andrzej Jaszkiewicz and Piotr Zielniewicz. Greedy Decremental Quick Hypervolume Subset Selection Algorithms. PPSN XVII, 2022.
• Andrzej Jaszkiewicz and Piotr Zielniewicz. On-Line Quick Hypervolume Algorithm. GECCO ’23 Companion, page 371–374, 2023.
• Andrzej Jaszkiewicz and Piotr Zielniewicz. Exact calculation and properties of the R2 multiobjective quality indicator. IEEE Transactions on Evolutionary Computation, 2024 (early access).
• Andrzej Jaszkiewicz and Piotr Zielniewicz. Improving the efficiency of the distance-based hypervolume estimation using ND-tree. IEEE Transactions on Evolutionary Computation, 2024 (early access).