On the Easiest and Hardest Fitness Functions

Research output: Contribution to journalArticle

Standard

On the Easiest and Hardest Fitness Functions. / He, Jun; Chen, Tianshi; Yao, Xin.

In: IEEE Transactions on Evolutionary Computation, Vol. 19, No. 2, 6800034, 01.04.2015, p. 295-305.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

He, Jun ; Chen, Tianshi ; Yao, Xin. / On the Easiest and Hardest Fitness Functions. In: IEEE Transactions on Evolutionary Computation. 2015 ; Vol. 19, No. 2. pp. 295-305.

Bibtex

@article{7da398abe718438da9adfb4e58fbcfe1,
title = "On the Easiest and Hardest Fitness Functions",
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.",
keywords = "Algorithm analysis, benchmark design, evolutionary algorithm, fitness landscape, problem difficulty",
author = "Jun He and Tianshi Chen and Xin Yao",
year = "2015",
month = apr,
day = "1",
doi = "10.1109/TEVC.2014.2318025",
language = "English",
volume = "19",
pages = "295--305",
journal = "IEEE Transactions on Evolutionary Computation",
issn = "1089-778X",
publisher = "Institute of Electrical and Electronics Engineers (IEEE)",
number = "2",

}

RIS

TY - JOUR

T1 - On the Easiest and Hardest Fitness Functions

AU - He, Jun

AU - Chen, Tianshi

AU - Yao, Xin

PY - 2015/4/1

Y1 - 2015/4/1

N2 - 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.

AB - 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.

KW - Algorithm analysis

KW - benchmark design

KW - evolutionary algorithm

KW - fitness landscape

KW - problem difficulty

UR - http://www.scopus.com/inward/record.url?scp=84926353181&partnerID=8YFLogxK

U2 - 10.1109/TEVC.2014.2318025

DO - 10.1109/TEVC.2014.2318025

M3 - Article

AN - SCOPUS:84926353181

VL - 19

SP - 295

EP - 305

JO - IEEE Transactions on Evolutionary Computation

JF - IEEE Transactions on Evolutionary Computation

SN - 1089-778X

IS - 2

M1 - 6800034

ER -