期刊
THEORETICAL COMPUTER SCIENCE
卷 436, 期 -, 页码 106-117出版社
ELSEVIER
DOI: 10.1016/j.tcs.2012.01.010
关键词
Computational complexity; Evolutionary algorithms (EAs); Expected running time; Probable computational time (PCT); Randomized search heuristics (RSHs); Tail inequalities
资金
- National Natural Science Foundation of China [60774085, 61074116]
- Fundamental Research Funds for the Central Universities of China
For the purpose of analyzing the time cost of evolutionary algorithms (EAs) or other types of randomized search heuristics (RSHs) with certain requirements on the probability of obtaining a target solution, this paper proposes a new index, called the probable computational time (PCT), which complements expected running time analysis. Using simple tail inequalities, such as Markov's inequality and Chebyshev's inequality, we also provide basic properties of PCT, explicitly exhibiting the general relationships between the expected running time and the PCT. To present deeper estimations of the PCT for specific RSHs and problems, we demonstrate a new inequality that is based on the general form of the Chernoff inequality and previous methods such as fitness-based partitions and potential functions, which have been used to analyze the expected running time of RSHs. The precondition of the new inequality is that the total running time can be described as the sum of a linear combination of some independent geometrically distributed variables and a constant term. The new inequality always provides meaningful upper bounds for the PCT under such circumstances. Some applications of the new inequality for simple EAs, ant colony optimization (ACO) and particle swarm optimization (PSO) algorithms on simple pseudo-Boolean functions are illustrated in this paper. (C) 2012 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据