Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

External organisations

  • University of Southampton
  • Sobolev Insitute of Mathematics, Novosibirsk Russia

Abstract

It is largely unknown how the runtime of evolutionary algorithms depends on fitness landscape characteristics for broad classes of problems. Runtime guarantees for complex and multi-modal problems where EAs are typically applied are rarely available. We present a parameterised problem class SparseLocalOpt;", where the class with parameters ; 2 [0; 1] contains all fitness landscapes with deceptive regions of sparsity " and fitness valleys of density . We study how the runtime of EAs depends on these fitness landscape parameters. We find that for any constant density and sparsity ; " 2 (0; 1), SparseLocalOpt;" has exponential elitist (+) black-box complexity, implying that a wide range of elitist EAs fail even for mildly deceptive and multi-modal landscapes. In contrast, we derive a set of sufficient conditions for non-elitist EAs to optimise any problem in SparseLocalOpt;" in expected polynomial time for broad values of and ". These conditions can be satisfied for tournament selection and linear ranking selection, but not for (; )-selection.

Details

Original languageEnglish
Title of host publicationGECCO '21: Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion
Publication statusAccepted/In press - 26 Mar 2021
EventGenetic and Evolutionary Computation Conference -
Duration: 10 Jul 202114 Jul 2021

Conference

ConferenceGenetic and Evolutionary Computation Conference
Abbreviated titleGECCO 2021
Period10/07/2114/07/21