针对具有布尔输入的可分离函数的(1 + 1)进化算法的严格复杂度分析。
A rigorous complexity analysis of the (1 + 1) evolutionary algorithm for separable functions with Boolean inputs.
作者信息
Droste S, Jansen T, Wegener I
机构信息
FB Informatik, Univ. Dortmund, Germany.
出版信息
Evol Comput. 1998 Summer;6(2):185-96. doi: 10.1162/evco.1998.6.2.185.
Evolutionary algorithms (EAs) are heuristic randomized algorithms which, by many impressive experiments, have been proven to behave quite well for optimization problems of various kinds. In this paper a rigorous theoretical complexity analysis of the (1 + 1) evolutionary algorithm for separable functions with Boolean inputs is given. Different mutation rates are compared, and the use of the crossover operator is investigated. The main contribution is not the result that the expected run time of the (1 + 1) evolutionary algorithm is theta (n ln n) for separable functions with n variables but the methods by which this result can be proven rigorously.
进化算法（EAs）是启发式随机算法，通过许多令人印象深刻的实验已证明，它们在解决各类优化问题时表现出色。本文对具有布尔输入的可分离函数的(1 + 1)进化算法进行了严格的理论复杂度分析。比较了不同的变异率，并研究了交叉算子的使用。主要贡献不在于(1 + 1)进化算法对于具有n个变量的可分离函数的预期运行时间为θ(n ln n)这一结果，而在于能够严格证明该结果的方法。
Zotero 插件