On the Easiest and Hardest Fitness Functions

Jun He, Tianshi Chen, Xin Yao

Research output: Contribution to journalArticlepeer-review

30 Citations (Scopus)

Abstract

The hardness of fitness functions is an important research topic in the field of evolutionary computation. In theory, this paper can help with understanding the ability of evolutionary algorithms (EAs). In practice, this paper may provide a guideline to the design of benchmarks. The aim of this paper is to answer the following research questions. Given a fitness function class, which functions are the easiest with respect to an EA? Which are the hardest? How are these functions constructed? This paper provides theoretical answers to these questions. The easiest and hardest fitness functions are constructed for an elitist (1 + 1) EA to maximize a class of fitness functions with the same optima. It is demonstrated that the unimodal functions are the easiest and deceptive functions are the hardest in terms of the time-based fitness landscape. This paper also reveals that in a fitness function class, the easiest function to one algorithm may become the hardest to another algorithm, and vice versa.

Original languageEnglish
Article number6800034
Pages (from-to)295-305
Number of pages11
JournalIEEE Transactions on Evolutionary Computation
Volume19
Issue number2
DOIs
Publication statusPublished - 1 Apr 2015

Keywords

  • Algorithm analysis
  • benchmark design
  • evolutionary algorithm
  • fitness landscape
  • problem difficulty

ASJC Scopus subject areas

  • Software
  • Computational Theory and Mathematics
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'On the Easiest and Hardest Fitness Functions'. Together they form a unique fingerprint.

Cite this