組合優(yōu)化中概率模因算法框架的個體間距離度量選擇研究

1、組合優(yōu)化中概率模因算法框架的個體間距離度量選擇研究重慶大學碩士學位論文（學術學位）學生姓名：葉振斌指導教師：沙行勉教授專業(yè)：計算機科學與技術學科門類：工學重慶大學計算機學院二O一七年四月萬方數(shù)據(jù)重慶大學碩士學位論文中文摘要I摘要模因算法（MemeticAlgithm，簡稱MA）是一種融合了群體全局搜索和個體生命周期學習（局部搜索）的啟發(fā)式搜索框架。在MA解決復雜優(yōu)化問題的過程中，全局搜索和局部搜索的計算資源分配很大程度上影響了算法的性能

2、。為了得到全局搜索和局部搜索的權衡依據(jù)，概率模因算法框架（ProbabilityMemeticFramewk，簡稱PMF）被提出。PMF把全局搜索和局部搜索分離，作為獨立的優(yōu)化行為，并且把MA建模為對全局搜索和局部搜索的選擇決策過程。PMF通過搜索過程中計算得到的局部搜索強度理論上界，控制每個個體的局部搜索強度，平衡全局搜索和局部搜索的計算資源消耗。根據(jù)Feng等學者的研究[1]，當使用PMF解決組合優(yōu)化問題的時候，恰當?shù)膫€體間距離度量

3、（相似度度量）選擇對局部搜索強度的估計起著極為關鍵的作用。然而，就目前最新的研究進展，幾乎沒有相應的工作研究關于PMF在解決組合優(yōu)化問題中個體相似度度量選擇的理論，我們的工作嘗試改進這一方面的不足。在本文中，我們對PMF在解決組合優(yōu)化問題時個體間距離度量的選擇進行了初步地分析和研究，并且在經(jīng)典組合優(yōu)化問題：限量弧路徑問題（CapacitatedArcRoutingProblem，簡稱CARP）和有時間窗車輛路徑問題（VehicleRou

4、tingProblemwithTimeWindows，簡稱VRPTW）上進行了實驗研究。我們首先分析在組合優(yōu)化問題中十分常用的4個距離度量被用來度量CARP候選解之間的相似度的可行性。接下來，我們提出一個基于鄰近候選解度量和適應度距離相關性度量的距離度量適合度評價策略，用于量化一個候選個體相似度度量被用在PMF中解決組合優(yōu)化問題時估計局部搜索強度的適合程度。最后，我們在egl的24個CARPbenchmark上進行的實驗研究表明：只有在

5、使用編輯距離時，PMF找到了4個目前最優(yōu)的解；對比改進Jaccard距離，當在PMF中使用編輯距離時得到了9個更優(yōu)的解。我們在Solomon的VRPTWbenchmark上的實驗研究表明：對比MA，使用編輯距離作為距離度量的PMF在24個VRPTWbenchmark中找到了10個更優(yōu)的解；對比改進Jaccard距離，當在PMF中使用編輯距離時得到了12個更優(yōu)的解。實驗研究結果強調了在使用PMF解決組合優(yōu)化問題時，恰當?shù)木嚯x度量選擇對PM