求解最大分散度問題的混合分布估計算法

李 濤，林 耿

(閩江學(xué)院 數(shù)學(xué)系，福建 福州 350108)

?

求解最大分散度問題的混合分布估計算法

李 濤，林 耿

(閩江學(xué)院 數(shù)學(xué)系，福建 福州 350108)

最大分散度問題是一個NP困難問題,提出了一個有效求解最大分散度問題的混合分布估計算法.該算法利用搜索過程中的全局和局部信息來構(gòu)造新解，提高了搜索的多樣性，避免早熟.根據(jù)最大分散度問題的特點，構(gòu)造局部搜索算法來改進(jìn)分布估計算法的局部搜索能力，采用18個標(biāo)準(zhǔn)測試?yán)訙y試本研究提出的算法,與其他算法比較的結(jié)果證明了本算法是有效的.

最大分散度問題; 進(jìn)化算法; 分布估計算法; 啟發(fā)式算法

給定一個集合N={e1,…,en}，其中的兩個元素ei和ej之間的距離為dij(dij=dji).如i≠j，則dij>0；否則，dij=0.最大分散度問題(Maximum Diversity Problem,MDP)是尋找集合N的一個具有m個元素的子集，使該子集中元素間的距離總和最大.引入n維0-1解向量x=(x1,…,xn)，xi=1表示ei被選中，否則ei沒有被選中.最大分散度問題可以描述為如下的0-1規(guī)劃問題：

最大分散度問題是一個典型的NP困難問題，在定位、生態(tài)系統(tǒng)、遺傳學(xué)、制造設(shè)計、課程設(shè)計等方面有著廣泛的應(yīng)用背景.由于精確算法只能求解較小規(guī)模的實例，近年來，元啟發(fā)式算法成為人們的研究熱點之一，如禁忌搜索[1-2]、貪心隨機自適應(yīng)搜索[3]、memetic算法[4]、變鄰域搜索[5]被應(yīng)用于求解大規(guī)模最大分散度問題，取得了較好的結(jié)果.

分布估計算法(Estimation of Distribution Algorithms,EDA)是一種基于統(tǒng)計原理的隨機優(yōu)化算法，它已經(jīng)成功應(yīng)用于求解許多組合優(yōu)化問題[6-8].然而，由于EDA過多側(cè)重于解空間宏觀的全局優(yōu)化，單純的EDA局部搜索能力有限，算法后期易陷入早熟收斂.

本研究根據(jù)最大分散度問題的特點，提出了一個混合分布估計算法(HEDA).該算法利用搜索到的解的局部信息和分布估計算法的全局信息來產(chǎn)生新的解向量，采用基于迭代改進(jìn)的局部搜索算法來改進(jìn)局部搜索能力.用一些國際標(biāo)準(zhǔn)測試?yán)訙y試本算法并與現(xiàn)存算法比較，證明了本算法的有效性.

1 混合分布估計算法的主要組成模塊

求解最大分散度問題的HEDA是一種將統(tǒng)計學(xué)習(xí)方法與進(jìn)化算法有機結(jié)合的種群算法，它主要包含3個基本子模塊：①概率模型；②新解的產(chǎn)生方法；③局部搜索算法.算法的基本步驟如下：首先，構(gòu)造多樣性較好的初始種群，通過對優(yōu)勢解集建立概率模型獲得候選解的分布特征，通過新解的產(chǎn)生方法構(gòu)造新的解向量.然后，采用局部搜索算法對新解進(jìn)行再優(yōu)化，用再優(yōu)化后得到的解對種群進(jìn)行更新.接下來，混合分布估計算法重復(fù)以上步驟，直到滿足算法的停止準(zhǔn)則.

下面對求解最大分散度問題的HEDA的3個子模塊——概率模型、新解的產(chǎn)生方法和局部搜索算法分別進(jìn)行詳細(xì)介紹.

1.1 概率模型

HEDA采用n維概率向量p=(p1,…,pn)來描述解空間分布的概率模型，其中pi表示第i個元素ei被選中的概率，即xi=1的概率.

HEDA是一種種群進(jìn)化算法.從一個初始的概率向量開始，分布估計算法的每一代都通過種群中的優(yōu)勢解集來更新概率向量.假設(shè)當(dāng)前的種群包含s個解，記為S=(x1,…,xs).首先，HEDA從種群S中找出最好的t個解，記為{y1,…,yt}.然后，HEDA通過式(1)來更新概率向量：

(1)

式中：0≤λ≤1表示學(xué)習(xí)速率.

對于大部分組合優(yōu)化問題來說，它們的優(yōu)勢解具有相似的結(jié)構(gòu).利用式(1)來更新容易導(dǎo)致算法過早收斂.為了產(chǎn)生多樣性的解、避免早熟，HEDA對概率模型進(jìn)行了如下修正：

(2)

1.2 新解的產(chǎn)生方法

遺傳算法通過交叉和變異來構(gòu)造下一代解向量.交叉和變異操作都是隨機進(jìn)行的，可能無法繼承精英解的優(yōu)良結(jié)構(gòu).另外，由于沒有利用搜索到的全局信息，所以導(dǎo)致遺傳算法在一定程度上出現(xiàn)了退化.

分布估計算法有效利用了解空間的分布情況，通過概率模型來產(chǎn)生新的解向量.但是，分布估計算法沒有利用到搜索的局部信息，導(dǎo)致算法的局部搜索能力不足.

新解產(chǎn)生的具體步驟如下：

輸入相關(guān)參數(shù).

輸出新解x.

第1步 初始化i=1.

第2步 產(chǎn)生一個隨機數(shù)δ∈[0,1].

第4步 產(chǎn)生一個隨機數(shù)κ∈[0,1].如果κ≤pi，令xi=1；否則，令xi=0.

第5步 令i=i+1.如果i≤n，轉(zhuǎn)第2步；否則，轉(zhuǎn)第6步.

第8步 停機，輸出新產(chǎn)生的可行解x.

1.3 局部搜索算法

局部搜索算法是進(jìn)化算法求解過程中消耗時間最多的模塊.提高局部搜索算法的復(fù)雜度能夠有效減少整個算法的求解時間，故設(shè)計高效的局部搜索算法是一個非常重要的環(huán)節(jié).

HEDA通過局部搜索算法來有效提高算法的局部搜索能力.Kernighan和Lin[9]提出了一個求解劃分問題的高效局部搜索算法——KL算法.KL算法已經(jīng)被成功地應(yīng)用于求解許多NP困難問題，HEDA改進(jìn)KL算法為局部搜索算法，該局部搜索算法在提高解的質(zhì)量的同時還可保持解的可行性.

給定一個解x=(x1,…,xn)，設(shè)Z(x)={i|xi=1}表示選中的元素的集合，U(x)={i|xi=0}表示未選中的元素的集合.Z中的一個元素k與U中的一個元素j交換后，會產(chǎn)生一個新的可行解x′，將交換后目標(biāo)函數(shù)值的改變量定義為交換k與j的增益g(k,j)，即

g(k,j)=f(x′)-f(x).

(3)

局部搜索算法是一個迭代改進(jìn)算法，由一系列的pass組成.局部搜索算法從一個初始解x0開始，在每一個pass的開始階段，所有元素都能夠自由移動.設(shè)Zf和Uf分別表示選中和未選中的自由元素組成的集合.HEDA通過式(3)計算出所有自由元素交換后的增益，選擇增益最大的組合進(jìn)行交換，交換后的兩個元素在該pass中禁止再次移動.每個pass執(zhí)行以上交換σ次后停止，將該pass中找到的最好的解xb輸出.如果當(dāng)前pass能夠找到更好的解，HEDA以xb為初始解，繼續(xù)下一個pass；否則，局部搜索算法停止，將該過程中找到的最好的解輸出.

局部搜索算法的具體步驟如下：

輸入可行解x0.

輸出改進(jìn)后的解xb.

第1步 初始化x=x0，xb=x0.

第2步 令Zf=Z(x)，Uf=U(x)，初始化iter=0.

第3步 由式(3)計算出所有g(shù)(k,j)，κ∈Zf，j∈Uf.

第4步 找出κ*，j*,使g(κ*,j*)最大.令xκ*=0，xj*=1.令Zf=Zf-{κ*}，Uf=Uf-{j*}.

第5步 如果 f(x)>f(xb)，則xb=x.

第6步 令iter=iter+1.如果iter≤σ，轉(zhuǎn)第3步；否則，轉(zhuǎn)第7步.

第7步 如果f(xb)>f(x0)，則x0=xb，轉(zhuǎn)第1步；否則，停機，輸出改進(jìn)后的可行解xb.

2 HEDA的算法描述

假設(shè)L為算法的最大迭代次數(shù)，下面給出了求解最大分散度問題的混合分布估計算法的具體步驟：

輸入相關(guān)參數(shù).

輸出近似最優(yōu)解x*.

第4步 從種群S中找出t個最好的解，利用式(1)和式(2)更新概率向量.

第5步 令g=g+1，如果g

3 實驗

為了檢驗HEDA算法的性能，本研究用C語言編寫算法的程序，在CPU主頻為3.40 GHz的計算機上測試.根據(jù)前期試驗結(jié)果，算法的參數(shù)設(shè)置如下：s=12，λ=0.7，α=0.7，σ=0.4m，L=200.

3.1 測試?yán)?/p>

采用2個數(shù)據(jù)集的18個國際標(biāo)準(zhǔn)測試?yán)觼頊y試提出的算法，測試?yán)拥囊?guī)模為400～2 000.

(1)集合1(Silva實例)：n∈[100,500]，m∈{0.1n,0.2n,0.3n,0.4n}，dij是從區(qū)間[0,9]中隨機產(chǎn)生的整數(shù).由于小規(guī)模的例子比較容易求解，故本研究采取n=400和n=500的8個例子來測試.

(2)集合2(隨機類型實例)：這些測試?yán)拥募嫌晌墨I(xiàn)[10]提出，本研究取其中規(guī)模最大的10個例子(n=2 000，m=200，dij∈(0,10))來測試算法.

3.2 實驗結(jié)果與分析

對于18個標(biāo)準(zhǔn)測試?yán)?，分別運行HEDA 5次.表1和表2分別給出了運行集合1和集合2的每個測試?yán)拥淖詈媒Y(jié)果和平均結(jié)果.為了與迭代禁忌搜索(ITS)、Macambira的禁忌搜索(MTS)、禁忌與GRASP混合算法(LS_TS[11]和GRASP-TS[12])、路徑重鏈算法(KLD+PR)、神經(jīng)網(wǎng)絡(luò)和變鄰域算法(DCHNN-VNS)比較，表1和表2也列出了這些啟發(fā)式算法的結(jié)果.

表1 HEDA與其他啟發(fā)式算法求解Silva實例的實驗結(jié)果比較Tab.1 Comparison results of HEDA with other heuristics on Silva instances

表2 HEDA與其他啟發(fā)式算法求解隨機類型實例的實驗結(jié)果比較Tab.2 Comparison results of HEDA with other heuristics on random instances

從表1給出的結(jié)果可以看出，ITS,DCHNN-VNS,GRASP-TS,HEDA在8個例子上都能找到最優(yōu)解，并且HEDA得到的平均結(jié)果優(yōu)于MTS,DCHNN-VNS,LS_TS和KDL+PR，但是比ITS差.

從表2給出的測試結(jié)果可以看出，HEDA在10個例子上都找到了比MTS和LS_TS更好的最優(yōu)解，分別在6個例子和7個例子上獲得了比ITS和DCHNN-VNS更好的最優(yōu)解.HEDA在10個例子上都獲得了比其他算法更好的平均解.

以上結(jié)果表明，從算法的求解結(jié)果來看，本研究提出的算法優(yōu)于MTS,DCHNN-VNS,LS_TS和KDL+PR，并且比其他算法穩(wěn)健.HEDA能夠有效地避免早熟，是求解最大分散度問題的有效算法.

4 結(jié)束語

本研究構(gòu)造了求解最大分散度問題的混合分布估計算法.該算法從一個隨機的初始種群開始，利用概率模型收集全局信息，與當(dāng)前最優(yōu)解的局部信息相結(jié)合來構(gòu)造新解.然后，根據(jù)最大分散度問題的特點，構(gòu)造局部搜索算法來提高局部搜索能力.最后，通過種群更新方法來保持種群的多樣性.這些策略有效地組成了一個有機的整體，提高了搜索的效率.與現(xiàn)存的一些算法比較，本研究提出的混合分布估計算法是一種求解最大分散度問題的有效算法.然而，局部搜索的算法復(fù)雜度比較高，求解速度較慢，課題將進(jìn)一步研究更加有效的局部搜索算法來提高算法的效率.

[1] PALUBECKIS G.Iterated tabu search for the maximum diversity problem[J].Applied Mathematics and Computation,2007,189(1):371-383.

[2] WANG Y,HAO J K,GLOVER F,et al.A tabu search based memetic algorithm for the maximum diversity problem[J].Engineering Applications of Artificial Intelligence,2014(27):103-114.

[3] SILVA G C,ANDRADE M,OCHI L S,et al.New heuristics for the maximum diversity problem[J].Journal of Heuristics,2007,13(4):315-336.

[4] DEFREITAS A R R,GUIMARAES F G,SILVA R C P,et al.Memetic self-adaptive evolution strategies applied to the maximum diversity problem[J].Optimization Letters,2014,8(2):705-714.

[5] 周雅蘭，王甲海，閉瑋，等.結(jié)合變鄰域搜索的競爭Hopfield神經(jīng)網(wǎng)絡(luò)解決最大分散度問題[J].計算機科學(xué),2010,37(3):208-211.

[6] 王勇臻，陳燕，李桃迎，等.元胞分布估計算法求解高維0/1背包問題[J].小型微型計算機系統(tǒng)，2015，36(6):1341-1346.

[7] 余娟，馮曉華，賀昱曜.求解多維背包問題的改進(jìn)分布估計算法[J].計算機仿真，2014,31(10):286-290.

[8] HAUSCHILD M,PELIKAN M.An introduction and survey of estimation of distribution algorithms[J].Swarm and Evolutionary Computation,2011(3):111-128.

[9] KERNIGHAN B W,LIN S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal,1970,49(2):291-307.

[10]MACAMBIRA E M.An application of tabu search heuristic for the maximum edge-weighted subgraph problem[J].Annals of Operations Research,2002(117):175-190.

[11]DUARTE A,MARTI R.Tabu search and GRASP for the maximum diversity problem[J].European Journal of Operational Research,2007,178(1):71-84.

[12]ARINGHIERI R,CORDONE R,MELZANI Y.Tabu search versus GRASP for the maximum diversity problem[J].40R,2008,6(1):45-60.

A hybrid estimation of distribution algorithm for solving the maximum diversity problem

LI Tao，LIN Geng

(DepartmentofMathematics,MinjiangUniversity,Fuzhou350108,China)

The maximum diversity problem is known to be NP-hard. In this paper,an efficient hybrid estimation of distribution algorithm is proposed to solve the maximum diversity problem. The proposed algorithm uses the local information and the global information to generate new solutions. It diversifies the search and prevents the premature convergence. According to the structure of the maximum diversity problem,a local search procedure is developed to enhance the exploitation of estimation of distribution algorithm. The experiments were done on 18 benchmark instances from the literature. Numerical results and comparisons with other existing algorithms indicate that the proposed algorithm is efficient.

maximum diversity problem; evolutionary algorithm; estimation of distribution algorithm; heuristic

2016-07-06

福建省自然科學(xué)基金項目(2016J01025);福建省高校新世紀(jì)優(yōu)秀人才支持計劃;大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項目(201510395049)

李濤(1994-)，男，廣東汕頭人，本科生，研究方向為應(yīng)用數(shù)學(xué)與人工智能.

林耿(1981-)，男，福建莆田人，副教授，博士，研究方向為組合優(yōu)化與人工智能.E-mail:lingeng413@163.com.

O221.4

A

1674-330X(2016)04-0069-05