Direkt zum InhaltDirekt zur Navigation

Metropolis and Symmetric Functions: A Swan Song

Lars Kaden, Nicole Weicker, Karsten Weicker
In: Evolutionary Computation in Combinatorial Optimization, 9th European Converence EvoCOP 2009, Hrsg: Carlos Cotta, Peter Cowling, Berlin: Springer, pp. 204-215, 2009.

 

Abstract

The class of symmetric functions is based on the OneMax function by a subsequent application of a real valued function. In this work we derive a sharp boundary between those problem instances that are solvable in polynomial time by the Metropolis algorithm and those that need at least exponential time. This result is both proven theoretically and illustrated by experimental data. The clasification of functions into easy and hard problem instances allows a deep insight into the problem solving power of the Metropolis algorithm and can be used in the process of selecting an optimization algorithm for a concrete problem instance.

 

[Download PDF]

Nachrichten RSS
  • 22.02.2017
    Kompilation von Constraint-Programmen: Erfolgreicher Abschluß eines kooperativen Promotionsverfahrens
    Herr Diplom-Informatiker (FH) Alexander Bau, Absolvent unserer ...
    Weiterlesen
Termine
JUG Saxony Camp 2017 an der HTWK 31.03.2017 09:00 - 18:00 — NIEPER-Bau der HTWK Leipzig
SKILL 2017 / Call for Papers 30.04.2017 - 30.09.2017
Verteidigungen
Masterverteidigung Anne Schüßler Raum: Z 417
Beginn: 10.03.17 - 10:00
Masterverteidigung Jonny Rillich Raum: Z 417
Beginn: 10.03.17 - 11:30
Masterverteidigung Gregor Schuldt Raum: Raum A3 01 (Sophus-Lie-Seminarraum), Max-Planck-Institut für Mathematik in den Naturwissenschaften, Inselstraße 22, 04103 Leipzig
Beginn: 22.03.17 - 14:00