The role of selective pressure when solving symmetric functions in polynomial time
Lars Kaden, Nicole Weicker, Karsten Weicker · 2011
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 changing selection pressure.