论文部分内容阅读
现实世界中的大量优化问题都含有多个极优解(全局最优解或局部最优解)。面对这些优化问题,获得多个极优解往往比仅获得一个全局最优解更为有益。多模优化(Multimodal Optimization)寻找一个优化问题的多个极优解。作为一种通用的黑盒优化算法,演化算法(Evolutionary Algorithm, EA)在多模优化中应用广泛,并形成了演化多模优化这一独特的研究分支。物种分化(Speciation)是演化多模优化中的一项基础技术。通过将一个种群划分成物种(Species)的集合,该技术使得演化算法能够工作在较高的物种层次,以物种为单位进行操作,而不是局限于单个个体。目前,已有大量演化多模优化算法依赖于该技术。物种分化的效率和质量无疑将对这些算法的性能表现产生直接影响。因此,研究高性能的物种分化算法具有重要意义。物种分化技术的关键和难点为判断两个体是否属于同一物种。目前,主要有基于距离的和基于拓扑的两类算法。基于距离的算法根据两个个体间的距离判断它们是否属于同一物种,依赖设置困难的小生境(Niche)半径参数,对目标问题有较强假设。其优点在于无需在解空间中采样新的点,从而没有额外的适应度评估开销。基于拓扑的算法根据适应度地形的拓扑结构特征来判断两个个体是否属于同一物种,无需小生境半径参数,对目标问题假设较弱。然而,现有拓扑物种分化算法都需要采样新的点以捕获适应度地形的拓扑结构特征,从而造成额外的适应度评估开销。适应度评估是演化算法的核心资源。降低物种分化过程中的适应度评估消耗对于提升算法的整体性能具有非常积极的作用。本文研究无需消耗额外适应度评估的拓扑物种分化技术。基于随机采样的演化算法在执行过程中会产生大量历史信息。于是,提出仅通过历史信息来捕获适应度地形的拓扑结构特征。为此,首先从点序列的全新视角重新阐释了现有拓扑物种分化算法的基本思想,并将新思路的核心问题归结为构造一个仅由历史点构成的近似序列。将该问题形式化为了一个带约束的组合优化问题,并设计了一个专门的分治算法对其进行高效求解。最后,得到了一个新颖的基于历史信息的拓扑物种分化算法。本文详细阐述了新算法的设计思想和实现细节,理论分析了它的时间和空间复杂度,并通过和多个现有物种分化算法进行对比实验验证了其有效性。实验中,新算法的整体表现显著优于现有拓扑物种分化算法。此外,新算法是目前唯一的无参数物种分化算法,在实际使用中极为方便。