Direkt zum InhaltDirekt zur Navigation

The role of selective pressure when solving symmetric functions in polynomial time

Lars Kaden, Nicole Weicker, Karsten Weicker
In: FOGA'11 Proc. of the 2011 ACM/SIGEVO Foundations of Genetic Algorithms XI, H.-G- Beyer, W. B. Langdon (eds.), ACM, pp. 105-118, 2011.

 

Abstract

This paper is concerned with the question to which extent a change in the selective pressure might improve the runtime of an optimization algorithm considerably. The subject of this examination is the class of symmetric functions, i.e. OneMax with a subsequent application of a real valued function. We consider an improvement in runtime as considerable if an exponential runtime becomes polynomial. The basis for this examination is a Markov chain analysis. An exact criterion for static selective pressure, telling which functions are solvable in polynomial time, is extended to a sufficient (but not necessary) criterion for chanigng selection pressure.

 

Download free at ACM website:

ACM DL Author-ize serviceThe role of selective pressure when solving symmetric functions in polynomial time
Lars Kaden, Nicole Weicker, Karsten Weicker
FOGA '11 Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms, 2011

[Contact author] 

Termine
24. Sitzung des Fakultätsrats 20.12.2017 12:30 - 14:00 — Z 417
Verteidigungen
Masterverteidigung Tim Menapace Raum: Gu 110
Beginn: 18.12.17 - 11:15