李 濤，林 耿

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

?

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

李 濤，林 耿

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

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

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

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

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

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

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

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

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

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

1.1 概率模型

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

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

(1)

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

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

(2)

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

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

分布估計(jì)算法有效利用了解空間的分布情況，通過概率模型來產(chǎn)生新的解向量.但是，分布估計(jì)算法沒有利用到搜索的局部信息，導(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)化算法求解過程中消耗時(shí)間最多的模塊.提高局部搜索算法的復(fù)雜度能夠有效減少整個(gè)算法的求解時(shí)間，故設(shè)計(jì)高效的局部搜索算法是一個(gè)非常重要的環(huán)節(jié).

HEDA通過局部搜索算法來有效提高算法的局部搜索能力.Kernighan和Lin[9]提出了一個(gè)求解劃分問題的高效局部搜索算法——KL算法.KL算法已經(jīng)被成功地應(yīng)用于求解許多NP困難問題，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開始，在每一個(gè)pass的開始階段，所有元素都能夠自由移動(dòng).設(shè)Zf和Uf分別表示選中和未選中的自由元素組成的集合.HEDA通過式(3)計(jì)算出所有自由元素交換后的增益，選擇增益最大的組合進(jìn)行交換，交換后的兩個(gè)元素在該pass中禁止再次移動(dòng).每個(gè)pass執(zhí)行以上交換σ次后停止，將該pass中找到的最好的解xb輸出.如果當(dāng)前pass能夠找到更好的解，HEDA以xb為初始解，繼續(xù)下一個(gè)pass；否則，局部搜索算法停止，將該過程中找到的最好的解輸出.

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

輸入可行解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ù)，下面給出了求解最大分散度問題的混合分布估計(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語言編寫算法的程序，在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)觼頊y(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è)例子來測(cè)試.

(2)集合2(隨機(jī)類型實(shí)例)：這些測(cè)試?yán)拥募嫌晌墨I(xiàn)[10]提出，本研究取其中規(guī)模最大的10個(gè)例子(n=2 000，m=200，dij∈(0,10))來測(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ī)類型實(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é)果來看，本研究提出的算法優(yōu)于MTS,DCHNN-VNS,LS_TS和KDL+PR，并且比其他算法穩(wěn)健.HEDA能夠有效地避免早熟，是求解最大分散度問題的有效算法.

4 結(jié)束語

本研究構(gòu)造了求解最大分散度問題的混合分布估計(jì)算法.該算法從一個(gè)隨機(jī)的初始種群開始，利用概率模型收集全局信息，與當(dāng)前最優(yōu)解的局部信息相結(jié)合來構(gòu)造新解.然后，根據(jù)最大分散度問題的特點(diǎn)，構(gòu)造局部搜索算法來提高局部搜索能力.最后，通過種群更新方法來保持種群的多樣性.這些策略有效地組成了一個(gè)有機(jī)的整體，提高了搜索的效率.與現(xiàn)存的一些算法比較，本研究提出的混合分布估計(jì)算法是一種求解最大分散度問題的有效算法.然而，局部搜索的算法復(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é)合變鄰域搜索的競(jìng)爭(zhēng)Hopfield神經(jīng)網(wǎng)絡(luò)解決最大分散度問題[J].計(jì)算機(jī)科學(xué),2010,37(3):208-211.

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

[7] 余娟，馮曉華，賀昱曜.求解多維背包問題的改進(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