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

1、模因算法（Memetic Algorithm，簡稱MA）是一種融合了群體全局搜索和個(gè)體生命周期學(xué)習(xí)（局部搜索）的啟發(fā)式搜索框架。在MA解決復(fù)雜優(yōu)化問題的過程中，全局搜索和局部搜索的計(jì)算資源分配很大程度上影響了算法的性能。為了得到全局搜索和局部搜索的權(quán)衡依據(jù)，概率模因算法框架（Probability Memetic Framework，簡稱PMF）被提出。PMF把全局搜索和局部搜索分離，作為獨(dú)立的優(yōu)化行為，并且把MA建模為對(duì)全局搜索和局部

2、搜索的選擇決策過程。PMF通過搜索過程中計(jì)算得到的局部搜索強(qiáng)度理論上界，控制每個(gè)個(gè)體的局部搜索強(qiáng)度，平衡全局搜索和局部搜索的計(jì)算資源消耗。根據(jù)Feng等學(xué)者的研究[1]，當(dāng)使用PMF解決組合優(yōu)化問題的時(shí)候，恰當(dāng)?shù)膫€(gè)體間距離度量（相似度度量）選擇對(duì)局部搜索強(qiáng)度的估計(jì)起著極為關(guān)鍵的作用。然而，就目前最新的研究進(jìn)展，幾乎沒有相應(yīng)的工作研究關(guān)于PMF在解決組合優(yōu)化問題中個(gè)體相似度度量選擇的理論，我們的工作嘗試改進(jìn)這一方面的不足。在本文中，我們對(duì)

3、PMF在解決組合優(yōu)化問題時(shí)個(gè)體間距離度量的選擇進(jìn)行了初步地分析和研究，并且在經(jīng)典組合優(yōu)化問題：限量弧路徑問題（Capacitated Arc Routing Problem，簡稱CARP）和有時(shí)間窗車輛路徑問題（VehicleRouting Problem with Time Windows，簡稱VRPTW）上進(jìn)行了實(shí)驗(yàn)研究。我們首先分析在組合優(yōu)化問題中十分常用的4個(gè)距離度量被用來度量CARP候選解之間的相似度的可行性。接下來，我們提出

4、一個(gè)基于鄰近候選解度量和適應(yīng)度距離相關(guān)性度量的距離度量適合度評(píng)價(jià)策略，用于量化一個(gè)候選個(gè)體相似度度量被用在PMF中解決組合優(yōu)化問題時(shí)估計(jì)局部搜索強(qiáng)度的適合程度。最后，我們?cè)趀gl的24個(gè)CARP benchmark上進(jìn)行的實(shí)驗(yàn)研究表明：只有在使用編輯距離時(shí)，PMF找到了4個(gè)目前最優(yōu)的解；對(duì)比改進(jìn)Jaccard距離，當(dāng)在PMF中使用編輯距離時(shí)得到了9個(gè)更優(yōu)的解。我們?cè)赟olomon的VRPTW benchmark上的實(shí)驗(yàn)研究表明：對(duì)比MA