Speeding Up Evolutionary Algorithms through Asymmetric Mutation Operators
Speeding Up Evolutionary Algorithms through Asymmetric Mutation Operators
复制标题
DOI：
10.1162/evco.2007.15.4.401
复制
发表时间：
2007-12
影响因子：
6.8
通讯作者：
Benjamin Doerr;Nils Hebbinghaus;F. Neumann
中科院分区：
文献类型：
--
作者：
Benjamin Doerr;Nils Hebbinghaus;F. Neumann
进化算法的成功应用表明，某些变异算子可以比其他算子更快地得到好的解。我们从理论的角度研究了在实践中观察到的这种行为，并研究了进化算法中的非对称突变算子对运行时行为的影响。考虑到欧拉循环问题，我们提出了运行时边界的进化算法使用的非对称运营商是远远小于一个更一般的最佳上限。在我们的分析中，事实证明，这两种算法都必须科普的高原改变了其结构，使算法能够更快地获得改进。此外，我们提出了一个下界的一般情况下，这表明，非对称运营商的计算速度至少有一个线性因素。
Successful applications of evolutionary algorithms show that certain variation operators can lead to good solutions much faster than other ones. We examine this behavior observed in practice from a theoretical point of view and investigate the effect of an asymmetric mutation operator in evolutionary algorithms with respect to the runtime behavior. Considering the Eulerian cycle problem we present runtime bounds for evolutionary algorithms using an asymmetric operator which are much smaller than the best upper bounds for a more general one. In our analysis it turns out that a plateau which both algorithms have to cope with changes its structure in a way that allows the algorithm to obtain an improvement much faster. In addition, we present a lower bound for the general case which shows that the asymmetric operator speeds up computation by at least a linear factor.