论文标题
多模式优化的自我调整的进化算法
Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
论文作者
论文摘要
最近的理论研究表明，在二元搜索空间的进化算法中，自我调整和自适应机制可以超过静态设置。但是，这些研究中的绝大多数都集中在单峰功能上，这些功能不需要算法同时翻转几个位以取得进展。实际上，现有的自我调整算法并非旨在检测本地最佳选择，并且没有明显的跨越大锤间隙的好处。 我们提出了一种称为停滞检测的机制，可以作为现有进化算法的模块添加（无论是有或没有以前的自我调整算法）。在简单的（1+1）EA中，我们证明了在众所周知的跳跃基准上的预期运行时，该运行时间与渐近的最佳参数设置相对应，并且优于其他机制，以进行多模式优化，例如重尾突变。我们还在自调整（1+$λ$）ea的背景下研究了该模块，并表明它结合了该算法对单峰问题的先前好处，并结合了更有效的多模式优化。 为了探索方法的局限性，我们还提供了一个例子，其中两种自我调整机制（包括停滞检测）都无助于找到突变率的有益环境。最后，我们通过实验研究了停滞检测的模块。
Recent theoretical research has shown that self-adjusting and self-adaptive mechanisms can provably outperform static settings in evolutionary algorithms for binary search spaces. However, the vast majority of these studies focuses on unimodal functions which do not require the algorithm to flip several bits simultaneously to make progress. In fact, existing self-adjusting algorithms are not designed to detect local optima and do not have any obvious benefit to cross large Hamming gaps. We suggest a mechanism called stagnation detection that can be added as a module to existing evolutionary algorithms (both with and without prior self-adjusting algorithms). Added to a simple (1+1) EA, we prove an expected runtime on the well-known Jump benchmark that corresponds to an asymptotically optimal parameter setting and outperforms other mechanisms for multimodal optimization like heavy-tailed mutation. We also investigate the module in the context of a self-adjusting (1+$λ$) EA and show that it combines the previous benefits of this algorithm on unimodal problems with more efficient multimodal optimization. To explore the limitations of the approach, we additionally present an example where both self-adjusting mechanisms, including stagnation detection, do not help to find a beneficial setting of the mutation rate. Finally, we investigate our module for stagnation detection experimentally.
