A natural and simple function which is hard for all evolutionaryalgorithms

摘要

Evolutionary algorithms (EAs) are randomized search strategiesthat have turned out to be efficient for somewhat different optimizationproblems. In order to understand the behavior of EAs, one is alsointerested in examples where EAs need exponential time to find anoptimal solution. Until now only artificial examples of this kind wereknown. An example with a clear and simple structure is presented. It canbe described by a short formula, it is a polynomial of degree 3, and itis an instance of a well-known problem, the theoretically andpractically important MAXSAT problem