On the Easiest and Hardest Fitness Functions
On the Easiest and Hardest Fitness Functions
复制标题
DOI：
10.1109/tevc.2014.2318025
复制
发表时间：
2012-03
影响因子：
14.3
通讯作者：
Jun He;Tianshi Chen;X. Yao
中科院分区：
文献类型：
--
作者：
Jun He;Tianshi Chen;X. Yao
适应度函数的硬度是进化计算领域的一个重要研究课题。从理论上讲，本文可以帮助理解进化算法（EA）的能力。在实践中，本文可以为基准测试的设计提供指导。本文旨在回答以下研究问题。给定一个适应度函数类，对于EA，哪些函数是最简单的？哪个最难？这些功能是如何构建的？本文从理论上回答了这些问题。最简单和最困难的适应度函数构造的精英（1 + 1）EA最大化具有相同的最优值的一类适应度函数。结果表明，单峰函数是最简单的和欺骗性的功能是最困难的基于时间的适应度景观。本文还揭示了在一个适应度函数类中，对一个算法来说最容易的函数可能对另一个算法来说最难，反之亦然。
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.