(Multimodal) Multi-Objective Optimization

The goal of multi-objective optimization is to optimize multiple objectives simultaneously. For instance, one might be interested in minimizing the time of travel (equivalent to maximizing the speed), minimizing the gas consumption (equivalent to maximizing the miles per gallon) and minimizing the CO2 emission. However, multi-objective optimization problems usually are extremely hard to understand - let alone visualize. Due to the limitations of our common visualization methods, and the corresponding poor understanding of multi-objective optimization problems (MOPs), people simply infer concepts (such as multimodality) from their experiences in the single-objective domain. Within this project, we started to shed light on this highly complex class of optimization problems - mainly with the help of seminal visualization techniques, which are capable of depicting local optima in MOPs - and used our insights to design powerful multi-objective optimization algorithms.

People

This projectly mainly is joint work between researchers from the TU Dresden and University of Münster in Germany as well as the Leiden Institute of Advanced Computer Science (LIACS), Leiden University in The Netherlands.

• Big Data Analytics in Transportation, TU Dresden (Germany):
• Pascal Kerschke, Professor (TU Dresden, Germany)
• Lennart Schäpermeier, Research Associate (TU Dresden, Germany)


• Statistics and Optimization, University of Münster (Germany):
• Pelin Aspar, Research Assistant (University of Münster, Germany)
• Jakob Bossek, Postdoctoral Researcher (University of Muenster, Germany)
• Christian Grimme, Postdoctoral Reseaercher (University of Münster, Germany)
• Vera Steinhoff, Graduate Student Assistant (University of Münster, Germany)
• Heike Trautmann, Professor (University of Muenster, Germany)


• Leiden Institute of Advanced Computer Science (LIACS), Leiden University (The Netherlands):
• Thomas Bäck, Professor (LIACS, The Netherlands)
• André H. Deutz, Lecturer (LIACS, The Netherlands)
• Michael T.M. Emmerich, Associate Professor (LIACS, The Netherlands)
• Mike Preuss, Assistant Professor (LIACS, The Netherlands)
• Hao Wang, Postdoctoral Researcher (LIACS, The Netherlands)

Visualization Tools

• R package mogsa [GitHub]
  Implementation of the Multi-Objective Gradient Sliding Algorithm (MOGSA), which efficiently exploits local efficient sets (i.e., local optima of multi-objective problems) to maneuver towards the problem's global efficient sets (= multi-objective global optima). Moreover, this package also contains functionalities to illustrate multi-objective local optima.


• R package moPLOT [GitHub]
  In an attempt to make multi-objective problems more conceivable, moPLOT provides the means to visualize bi- and tri-objective problems (i.e., problems with two or three objectives). This is achieved by plotting the landscapes of their multi-objective gradients using various visualization tools.

Problem Generator

• R package smoof [GitHub, CRAN]
  Provides generators for a high number of both single- and multi- objective test functions which are frequently used for the benchmarking of (numerical) optimization algorithms. Moreover, it offers a set of convenient functions to generate, plot and work with objective functions.


• Python package optproblems [GitHub]
  A collection of test problems for black-box optimization.

Algorithms

In the following we provide data used in our publications:

• HIGA-MO (Hypervolume Indicator Gradient Ascent Multi-objective Optimization)
• An optimization algorithm, which follows the steepest ascent of the Hypervolume indicator.
• For details, please refer to:
  

  Wang, Hao and Deutz, André H. and Bäck, Thomas H.W. and Emmerich, Michael T.M. (2017).
  Hypervolume Indicator Gradient Ascent Multi-objective Optimization.
  Proceedings of the 9th International Conference on Evolutionary Multi-Criterion Optimization (EMO), pp. 654-669. Springer.



• MOGSA (Multi-Objective Gradient Sliding Algorithm) [GitHub]
• A local search algorithm, which efficiently exploits the multi-objective gradient to maneuver along the (multi-objective) local optima.
• For details, please refer to:
  

  Grimme, Christian and Kerschke, Pascal and Trautmann, Heike (2019).
  Multimodality in Multi-Objective Optimization — More Boon than Bane?
  Proceedings of the 10th International Conference on Evolutionary Multi-Criterion Optimization (EMO), pp. 126-138. Springer.



• SOMOGSA
• A single-objective local search algorithm, which transfers a single-objective problem into a bi-objective problem (multiobjectivization), optimizes it using a modified version of MOGSA and returns the single-objective solution.
• For details, please refer to:
  

  Steinhoff, Vera and Kerschke, Pascal and Grimme, Christian (2020 ).
  Empirical Study on the Benefits of Multiobjectivization for Solving Single-Objective Problems
  arXiv:2006.14423.

Publications

Survey Article

• Grimme, Christian and Kerschke, Pascal and Aspar, Pelin and Trautmann, Heike and Preuss, Mike and Deutz, André and Wang, Hao and Emmerich, Michael (2021).
  Peeking Beyond Peaks: Challenges and Research Potentials of Continuous Multimodal Multi-objective Optimization.
  Computers & Operations Research (COR), Vol. 136, December 2021. Elsevier.
  [View Publication]

Algorithm Design

• Single-Objective Optimization

• Aspar, Pelin and Kerschke, Pascal and Steinhoff, Vera and Trautmann, Heike and Grimme, Christian (2021).
  Multi³: Optimizing Multimodal Single-Objective Continuous Problems in the Multi-Objective Space by Means of Multiobjectivization.
  Proceedings of the 11th International Conference on Evolutionary Multi-Criterion Optimization (EMO), pp. 311-322. Springer.
  [View Publication, BibTeX]

• Steinhoff, Vera and Kerschke, Pascal and Grimme, Christian (2020).
  Empirical Study on the Benefits of Multiobjectivization for Solving Single-Objective Problems
  arXiv:2006.14423.
  [Preprint available on arXiv]

• Steinhoff, Vera and Kerschke, Pascal and Aspar, Pelin and Trautmann, Heike and Grimme, Christian (2020).
  Multiobjectivization of Local Search: Single-Objective Optimization Benefits From Multi-Objective Gradient Descent.
  Proceedings of the IEEE Symposium Series on Computational Intelligence (SSCI), pp. 2445–2452. IEEE.
  [View Publication]



• Multi-Objective Optimization

• Grimme, Christian and Kerschke, Pascal and Trautmann, Heike (2019).
  Multimodality in Multi-Objective Optimization -- More Boon than Bane?
  Proceedings of the 10th International Conference on Evolutionary Multi-Criterion Optimization (EMO), pp. 126-138. Springer.
  [View Publication, BibTeX]

• Grimme, Christian and Kerschke, Pascal and Emmerich, Michael T.M. and Preuss, Mike and Deutz, André H. and Trautmann, Heike (2019).
  Sliding to the Global Optimum: How to Benefit from Non-Global Optima in Multimodal Multi-Objective Optimization.
  Proceedings of the International Global Optimization Workshop (LeGO 2018), pp. 020052-1-020052-4. AIP.
  [View Publication]

• Kerschke, Pascal and Wang, Hao and Preuss, Mike and Grimme, Christian and Deutz, André H. and Trautmann, Heike and Emmerich, Michael T.M. (2019).
  Search Dynamics on Multimodal Multi-Objective Problems.
  Evolutionary Computation (ECJ), Vol. 27(4):577-609. MIT Press.
  [View Publication]

• Wang, Hao and Deutz, André H. and Bäck, Thomas H.W. and Emmerich, Michael T.M. (2017).
  Hypervolume Indicator Gradient Ascent Multi-objective Optimization.
  Proceedings of the 9th International Conference on Evolutionary Multi-Criterion Optimization (EMO), pp. 654-669. Springer.
  [View Publication, BibTeX]

Visualizing and Understanding Multi-Objective Problem Landscapes

• Kerschke, Pascal and Grimme, Christian (2017).
  An Expedition to Multimodal Multi-Objective Optimization Landscapes.
  Proceedings of the 9th International Conference on Evolutionary Multi-Criterion Optimization (EMO), pp. 329-343. Springer.
  [View Publication, BibTeX]

• Kerschke, Pascal and Wang, Hao and Preuss, Mike and Grimme, Christian and Deutz, André H. and Trautmann, Heike and Emmerich, Michael T.M. (2016).
  Towards Analyzing Multimodality of Multiobjective Landscapes.
  Proceedings of the 14th International Conference on Parallel Problem Solving from Nature (PPSN XIV), pp. 962-972. Springer (Best Paper Award).
  [View Publication, BibTeX]

• Schäpermeier, Lennart and Grimme, Christian Kerschke, Pascal (2020).
  One PLOT to Show Them All: Visualization of Efficient Sets in Multi-Objective Landscapes.
  Bäck, Thomas and Preuss, Mike and Deutz, André and Wang, Hao and Doerr, Carola and Emmerich, Michael and Trautmann, Heike (Eds.),
  Proceedings of the 16th International Conference on Parallel Problem Solving from Nature (PPSN XVI), pp. 154-167. Springer.
  [View Publication, BibTeX]

• Schäpermeier, Lennart and Grimme, Christian Kerschke, Pascal (2021).
  To Boldly Show What No One Has Seen Before: A Dashboard for Visualizing Multi-objective Landscapes.
  Bäck, Thomas and Preuss, Mike and Deutz, André and Wang, Hao and Doerr, Carola and Emmerich, Michael and Trautmann, Heike (Eds.),
  Proceedings of the 11th International Conference on Evolutionary Multi-Criterion Optimization (EMO), pp. 632–644. Springer.
  [View Publication, BibTeX]