李 濤，林 耿

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

?

求解最大分散度問(wèn)題的混合分布估計(jì)算法

李 濤，林 耿

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

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

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

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

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

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

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

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

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

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

1.1 概率模型

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

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

(1)

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

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

(2)

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

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

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

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

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

輸出新解x.

第1步 初始化i=1.

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

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

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

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

1.3 局部搜索算法

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

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

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

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

(3)

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

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

輸入可行解x0.

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

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

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

第3步 由式(3)計(jì)算出所有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ī)，輸出改進(jìn)后的可行解xb.

2 HEDA的算法描述

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

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

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

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

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

3 實(shí)驗(yàn)

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果與分析

對(duì)于18個(gè)標(biāo)準(zhǔn)測(cè)試?yán)?，分別運(yùn)行HEDA 5次.表1和表2分別給出了運(yùn)行集合1和集合2的每個(gè)測(cè)試?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實(shí)例的實(shí)驗(yàn)結(jié)果比較Tab.1 Comparison results of HEDA with other heuristics on Silva instances

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

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

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

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

4 結(jié)束語(yǔ)

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

[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é)合變鄰域搜索的競(jìng)爭(zhēng)Hopfield神經(jīng)網(wǎng)絡(luò)解決最大分散度問(wèn)題[J].計(jì)算機(jī)科學(xué),2010,37(3):208-211.

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

[7] 余娟，馮曉華，賀昱曜.求解多維背包問(wèn)題的改進(jìn)分布估計(jì)算法[J].計(jì)算機(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é)基金項(xiàng)目(2016J01025);福建省高校新世紀(jì)優(yōu)秀人才支持計(jì)劃;大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項(xiàng)目(201510395049)

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

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

O221.4

A

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