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.



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]

Workshop Haskell in Leipzig - mit Hackathon 26.10.2017 - 28.10.2017 — N001
Stipendientag an der HTWK, 07.11.2017 07.11.2017 11:00 - 14:30 — Foyer des Nieper-Baus der HTWK
World Usability Day 09.11.2017, HTWK-Veranstaltung 09.11.2017 09:00 - 17:00 — HTWK Leipzig, Gutenberg-Bau
14. WIK-Leipzig 2017 an der HTWK Leipzig 29.11.2017 10:00 - 16:00 — Foyer des Nieper-Baus der HTWK
Bachelorverteidigung Eric Müller Raum: Z 417
Beginn: 20.10.17 - 13:00
Bachelorverteidigung Jeremias Deck Raum: *** Gu 115 ***
Beginn: 23.10.17 - 09:00
Bachelorverteidigung Martin Kolbe Raum: Z 417
Beginn: 23.10.17 - 12:00
Bachelorverteidigung Laura Heyne Raum: Z 417
Beginn: 23.10.17 - 13:30
Bachelorverteidigung Pascal Parussudis Raum: Z417
Beginn: 24.10.17 - 11:00