论文部分内容阅读
模因算法(Memetic Algorithm,简称MA)是一种融合了群体全局搜索和个体生命周期学习(局部搜索)的启发式搜索框架。在MA解决复杂优化问题的过程中,全局搜索和局部搜索的计算资源分配很大程度上影响了算法的性能。为了得到全局搜索和局部搜索的权衡依据,概率模因算法框架(Probability Memetic Framework,简称PMF)被提出。PMF把全局搜索和局部搜索分离,作为独立的优化行为,并且把MA建模为对全局搜索和局部搜索的选择决策过程。PMF通过搜索过程中计算得到的局部搜索强度理论上界,控制每个个体的局部搜索强度,平衡全局搜索和局部搜索的计算资源消耗。根据Feng等学者的研究[1],当使用PMF解决组合优化问题的时候,恰当的个体间距离度量(相似度度量)选择对局部搜索强度的估计起着极为关键的作用。然而,就目前最新的研究进展,几乎没有相应的工作研究关于PMF在解决组合优化问题中个体相似度度量选择的理论,我们的工作尝试改进这一方面的不足。在本文中,我们对PMF在解决组合优化问题时个体间距离度量的选择进行了初步地分析和研究,并且在经典组合优化问题:限量弧路径问题(Capacitated Arc Routing Problem,简称CARP)和有时间窗车辆路径问题(Vehicle Routing Problem with Time Windows,简称VRPTW)上进行了实验研究。我们首先分析在组合优化问题中十分常用的4个距离度量被用来度量CARP候选解之间的相似度的可行性。接下来,我们提出一个基于邻近候选解度量和适应度距离相关性度量的距离度量适合度评价策略,用于量化一个候选个体相似度度量被用在PMF中解决组合优化问题时估计局部搜索强度的适合程度。最后,我们在egl的24个CARP benchmark上进行的实验研究表明:只有在使用编辑距离时,PMF找到了4个目前最优的解;对比改进Jaccard距离,当在PMF中使用编辑距离时得到了9个更优的解。我们在Solomon的VRPTW benchmark上的实验研究表明:对比MA,使用编辑距离作为距离度量的PMF在24个VRPTW benchmark中找到了10个更优的解;对比改进Jaccard距离,当在PMF中使用编辑距离时得到了12个更优的解。实验研究结果强调了在使用PMF解决组合优化问题时,恰当的距离度量选择对PMF的重要影响,同时在一定程度上验证了我们提出的距离度量适合度评价策略在CARP和VRPTW上是有效的。