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. © 1997-2012 IEEE.
| Original language | English |
|---|---|
| Article number | 6800034 |
| Pages (from-to) | 295-305 |
| Number of pages | 11 |
| Journal | IEEE Transactions on Evolutionary Computation |
| Volume | 19 |
| Issue number | 2 |
| Early online date | 17 Apr 2014 |
| DOIs | |
| Publication status | Published - Apr 2015 |
| Externally published | Yes |
Funding
Manuscript received June 27, 2013; revised November 21, 2013 and February 16, 2014; accepted March 27, 2014. Date of publication April 17, 2014; date of current version March 27, 2015. This work was supported by the EPSRC under Grants EP/I009809/1 and EP/I010297/1. The work of X. Yao was supported in part by a Royal Society Wolfson Research Merit Award and in part by the NSFC under Grant 61329302. The work of T. Chen was supported by the NSFC under Grants 61100163 and 61221062.
Keywords
- Algorithm analysis
- benchmark design
- evolutionary algorithm
- fitness landscape
- problem difficulty