Parameter-less population pyramid
Parameter-less population pyramid
复制标题
无参数人口金字塔
DOI：
10.1145/2576768.2598350
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
W. Punch
中科院分区：
文献类型：
--
作者：
B. Goldman;W. Punch
进化技术在现实世界中的应用常常因需要确定特定问题的参数设置而受阻。虽然一些先前的方法已经减少或消除了对参数调整的需求，但许多方法是以牺牲效率来换取普遍适用性的。无参数种群金字塔（P3）是一种不需要参数且仍然广泛有效的进化技术。P3在持续整合多样性和利用精英算子之间取得了平衡，使其能够快速解决简单问题，并最终解决困难问题。当与三种经过最优调整的最先进的优化技术进行比较时，在四个基准测试（欺骗性陷阱、欺骗性阶梯陷阱、层次分明的可分解函数（HIFF）、拉斯特里金函数（Rastrigin））中，P3总是至少以一个常数因子更快地找到最优解。更重要的是，在三个随机基准测试（NK景观、伊辛自旋玻璃、最大可满足性问题（MAX - SAT））中，通过评估衡量，P3具有较低阶的计算复杂度。我们还提供了P3预期运行时间分析的大纲，为未来基于理论的结论奠定了基础。基于超过1万亿次评估，我们的结果表明P3对广泛的一类问题具有广泛的适用性。
Real world applications of evolutionary techniques are often hindered by the need to determine problem specific parameter settings. While some previous methods have reduced or removed the need for parameter tuning, many do so by trading efficiency for general applicability. The Parameter-less Population Pyramid (P3) is an evolutionary technique that requires no parameters and is still broadly effective. P3 strikes a balance between continuous integration of diversity and exploitative elitist operators, allowing it to solve easy problems quickly and hard problems eventually. When compared with three optimally tuned, state of the art optimization techniques, P3 always finds the optimum at least a constant factor faster across four benchmarks (Deceptive Trap, Deceptive Step Trap, HIFF, Rastrigin). More importantly, on three randomized benchmarks (NK Landscapes, Ising Spin Glasses, MAX-SAT), P3 has a lower order of computational complexity as measured by evaluations. We also provide outlines for expected runtime analysis of P3, setting the stage for future theory based conclusions. Based on over 1 trillion evaluations, our results suggest P3 has wide applicability to a broad class of problems.