选择超启发式七个关键组件在遗传算法超启发式中的实证分析

《Scientific Reports》：Empirical analysis of algorithmic components for improved performance in a baseline genetic algorithm selection hyper-heuristic

　　

摘要

选择超启发式是一类高层搜索算法，它们动态选择并应用低层启发式来解决各种优化问题。它们涵盖众多算法组件，例如启发式选择、移动接受、反馈和参数设置。这些组件中的每一个都提供多种实现方法，这给算法设计者带来了挑战，因为他们必须决定最适合其算法的方法。由于缺乏针对这些组件的公认最佳方法，这一问题变得更加严重。此外，关于这些组件实现方法有效性的全面实证研究尚缺乏，大多数既往研究仅关注启发式选择和移动接受。本文旨在填补这一空白，在基于种群的遗传算法超启发式（GAHH）的语境下，对七个关键的选择超启发式组件进行全面的实证分析，这些组件包括搜索点、搜索阶段、移动接受、反馈、禁忌机制、重启机制以及低层启发式参数。这些组件的实现方法源自使用 HyFlex 框架实现的 53 个算法，尤其是 2011 年跨域启发式搜索挑战（CDHSC）的 20 个入围方案。本研究采用分析方法比较其性能，并在评估设置中确定最有效的实现方法。分析结果表明，在有限的 12 个 HyFlex 调优实例中，多点搜索、迭代搜索阶段、非随机阈值移动接受、不从搜索反馈中学习、基于已访问解的禁忌机制、阈值重启机制以及自适应参数控制是 GAHH 表现最佳的策略。值得注意的是，“不学习”方法的性能受遗传算法进化算子的影响。研究结果提供了宝贵的见解，为未来算法开发奠定了坚实基础，并加深了对选择超启发式组件的理解，尤其是 GAHH 中的组件。