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

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

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

4、tingProblemwithTimeWindows，簡(jiǎn)稱VRPTW）上進(jìn)行了實(shí)驗(yàn)研究。我們首先分析在組合優(yōu)化問(wèn)題中十分常用的4個(gè)距離度量被用來(lái)度量CARP候選解之間的相似度的可行性。接下來(lái)，我們提出一個(gè)基于鄰近候選解度量和適應(yīng)度距離相關(guān)性度量的距離度量適合度評(píng)價(jià)策略，用于量化一個(gè)候選個(gè)體相似度度量被用在PMF中解決組合優(yōu)化問(wèn)題時(shí)估計(jì)局部搜索強(qiáng)度的適合程度。最后，我們?cè)趀gl的24個(gè)CARPbenchmark上進(jìn)行的實(shí)驗(yàn)研究表明：只有在

5、使用編輯距離時(shí)，PMF找到了4個(gè)目前最優(yōu)的解；對(duì)比改進(jìn)Jaccard距離，當(dāng)在PMF中使用編輯距離時(shí)得到了9個(gè)更優(yōu)的解。我們?cè)赟olomon的VRPTWbenchmark上的實(shí)驗(yàn)研究表明：對(duì)比MA，使用編輯距離作為距離度量的PMF在24個(gè)VRPTWbenchmark中找到了10個(gè)更優(yōu)的解；對(duì)比改進(jìn)Jaccard距離，當(dāng)在PMF中使用編輯距離時(shí)得到了12個(gè)更優(yōu)的解。實(shí)驗(yàn)研究結(jié)果強(qiáng)調(diào)了在使用PMF解決組合優(yōu)化問(wèn)題時(shí)，恰當(dāng)?shù)木嚯x度量選擇對(duì)PM