A natural and simple function which is hard for all evolutionary algorithms

11 November 2002

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

Vol. 4, 2704-2709
https://doi.org/10.1109/iecon.2000.972425

Abstract

Evolutionary algorithms (EAs) are randomized search strategies that have turned out to be efficient for somewhat different optimization problems. In order to understand the behavior of EAs, one is also interested in examples where EAs need exponential time to find an optimal solution. Until now only artificial examples of this kind were known. An example with a clear and simple structure is presented. It can be described by a short formula, it is a polynomial of degree 3, and it is an instance of a well-known problem, the theoretically and practically important MAXSAT problem.

Keywords

This publication has 4 references indexed in Scilit:

A computational view of population genetics
Random Structures & Algorithms, 1998
On the optimization of unimodal functions with the (1+1) evolutionary algorithm
Published by Springer Nature ,1998
An Introduction to Kolmogorov Complexity and Its Applications
Published by Springer Nature ,1993
A guided tour of chernoff bounds
Information Processing Letters, 1990