License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-2465
URL: http://drops.dagstuhl.de/opus/volltexte/2005/246/
Go to the corresponding Portal


Laumanns, Marco ; Thiele, Lothar ; Zitzler, Eckart

An Adaptive Scheme to Generate the Pareto Front Based on the Epsilon-Constraint Method

pdf-format:
Document 1.pdf (360 KB)


Abstract

We discuss methods for generating or approximating the Pareto set of multiobjective optimization problems by solving a sequence of constrained single-objective problems. The necessity of determining the constraint value a priori is shown to be a serious drawback of the original epsilon-constraint method. We therefore propose a new, adaptive scheme to generate appropriate constraint values during the run. A simple example problem is presented, where the running time (measured by the number of constrained single-objective sub-problems to be solved) of the original epsilon-constraint method is exponential in the problem size (number of decision variables), although the size of the Pareto set grows only linearly. We prove that --- independent of the problem or the problem size --- the time complexity of the new scheme is O(k^{m-1}), where k is the number of Pareto-optimal solutions to be found and m the number of objectives. Simulation results for the example problem as well as for different instances of the multiobjective knapsack problem demonstrate the behavior of the method, and links to reference implementations are provided.

BibTeX - Entry

@InProceedings{laumanns_et_al:DSP:2005:246,
  author =	{Marco Laumanns and Lothar Thiele and Eckart Zitzler},
  title =	{An Adaptive Scheme to Generate the Pareto Front Based on the Epsilon-Constraint Method},
  booktitle =	{Practical Approaches to Multi-Objective Optimization},
  year =	{2005},
  editor =	{J{\"u}rgen Branke and Kalyanmoy Deb and Kaisa Miettinen and Ralph E. Steuer},
  number =	{04461},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/246},
  annote =	{Keywords: Multiple objective optimization, non-dominated set, Pareto set, epsilon-constraint method, generating methods}
}

Keywords: Multiple objective optimization, non-dominated set, Pareto set, epsilon-constraint method, generating methods
Seminar: 04461 - Practical Approaches to Multi-Objective Optimization
Issue Date: 2005
Date of publication: 10.08.2005


DROPS-Home | Fulltext Search | Imprint Published by LZI