The use of tail inequalities on the probable computational time of randomized search heuristics

详细信息	查看全文 | 推荐本文 |

• 作者：Dong Zhou^a ; Dan Luo^a ; Ruqian Lu^b ; Zhangang Han^a ; ^{zhan@bnu.edu.cn}
• 关键词：Computational complexity ; Evolutionary algorithms (EAs) ; Expected running time ; Probable computational time (PCT) ; Randomized search heuristics (RSHs) ; Tail inequalities
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：8 June, 2012
• 卷：436
• 期：Complete
• 页码：106-117
• 文件大小：288 K

摘要

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鈥檚 inequality and Chebyshev鈥檚 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 鈥渇itness-based partitions鈥?and 鈥減otential 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.