论文标题
精英进化算法的剥削和探索分析：案例研究
Exploitation and Exploration Analysis of Elitist Evolutionary Algorithms: A Case Study
论文作者
论文摘要
广泛讨论了通过搜索，剥削和探索解决问题的两个基石，以实施和应用进化算法（EAS）。但是，只有少数研究专注于评估和剥削和探索的理论估计。考虑到剥削和探索是有关全球搜索和本地搜索的两个问题，本文提议通过成功概率和在不同集成领域计算的一步改进率进行评估。然后，通过分析（1+1）随机单变量搜索和（1+1）在球体函数和作弊问题上的进化编程来进行案例研究。通过严格的理论分析，我们证明了对所研究的ESIST EAS的剥削和探索都与问题维度$ n $呈指数式退化。同时，还表明，可以通过为高斯突变的标准偏差$σ$设置适当的值来实现剥削和勘探的最大化，这与从当前解决方案到有前途区域的中心的距离呈正相关。
Known as two cornerstones of problem solving by search, exploitation and exploration are extensively discussed for implementation and application of evolutionary algorithms (EAs). However, only a few researches focus on evaluation and theoretical estimation of exploitation and exploration. Considering that exploitation and exploration are two issues regarding global search and local search, this paper proposes to evaluate them via the success probability and the one-step improvement rate computed in different domains of integration. Then, case studies are performed by analyzing performances of (1+1) random univariate search and (1+1) evolutionary programming on the sphere function and the cheating problem. By rigorous theoretical analysis, we demonstrate that both exploitation and exploration of the investigated elitist EAs degenerate exponentially with the problem dimension $n$. Meanwhile, it is also shown that maximization of exploitation and exploration can be achieved by setting an appropriate value for the standard deviation $σ$ of Gaussian mutation, which is positively related to the distance from the present solution to the center of the promising region.
