林耿

（閩江學(xué)院數(shù)學(xué)與數(shù)據(jù)科學(xué)學(xué)院，福建福州350108）

0 引 言

圖的最大二等分問題是一類特殊的最大分割問題，已被證明是NP-困難的[1]。給定一個賦權(quán)簡單圖G=(V,E)，通過圖的最大二等分問題尋找圖G頂點集V的一個劃分(A,B)，滿足A∪B=V，A∩B=?，且|A|=|B|，使得2個頂點分別在A，B中的邊的權(quán)的和最大。該問題在許多工程領(lǐng)域，如大規(guī)模集成電路設(shè)計、網(wǎng)絡(luò)信道分配、數(shù)據(jù)劃分等有重要應(yīng)用。

針對圖的最大二等分問題，已有深入研究，提出了求解該問題的精確算法、近似算法和啟發(fā)式算法。基于分支定界[2]和半定規(guī)劃[3]的精確算法，雖然可以找到問題的最優(yōu)解，但算法具有指數(shù)時間復(fù)雜度，只適用于求解小規(guī)模問題。針對非負權(quán)圖，于力等[4]采用隨機擾動技巧，設(shè)計了近似比為0.488的近似算法。FRIEZE等[5]、YE[6]和 HALPERIN 等[7]推廣了GOEMANS等[8]的方法，通過求解最大二等分問題的半定規(guī)劃松弛問題，分別提出了近似比為0.651，0.699和0.7016的近似算法。由于利用內(nèi)點算法[9]求解大規(guī)模半定規(guī)劃的松弛問題比較耗時，因此,這些近似算法無法快速找到高質(zhì)量的解。

由于啟發(fā)式算法能在較短時間內(nèi)找到較高質(zhì)量的解，近年來越來越受學(xué)者們的關(guān)注。穆學(xué)文等[10]基于最大二等分問題的半定規(guī)劃松弛，提出了低秩可行方向算法。BURER等[11]和張芳等[12]結(jié)合半定規(guī)劃與秩二松弛方法的優(yōu)點，提出了秩二松弛算法。LING等[13]提出了求解最大二等分問題的變鄰域搜索算法。XU等[14]通過罰函數(shù)法將最大二等分問題化為一個無約束問題，并通過離散Hopfield神經(jīng)網(wǎng)絡(luò)求解該無約束問題，從而求解最大二等分問題。WU等[15]和LIN等[16]分別提出了求解最大二等分問題的Memetic算法。隨著規(guī)模的增大，局部最優(yōu)解的數(shù)量大大增加，許多啟發(fā)式算法容易陷入局部最優(yōu)解。最近，林耿等[17]提出了求解最大二等分問題的填充函數(shù)算法，實驗結(jié)果表明，該算法具有較強的局部搜索能力，并且能有效跳出局部搜索得到的解，但求解的質(zhì)量尚待提高。限制該算法性能的主要原因為其初始解不是利用先前搜索信息而是隨機產(chǎn)生的。

人工蜂群算法[18]具有多種群協(xié)同尋優(yōu)的特點，能利用搜索過程中找到的解產(chǎn)生新解。因人工蜂群算法簡單易實現(xiàn)，已成功應(yīng)用于求解各類優(yōu)化問題[19-20]。但在求解大規(guī)模組合優(yōu)化問題時，人工蜂群算法的局部搜索能力較弱，收斂速度慢。THAMMANO等[21]和 SINGHAL等[22]的研究結(jié)果表明，混合人工蜂群算法和局部搜索算法能有效加快人工蜂群算法的收斂速度，提高求解質(zhì)量。

填充函數(shù)算法具有較強的局部搜索能力，但缺乏構(gòu)造初始解的有效方法，無法進一步提高搜索的效率。人工蜂群算法能夠有效利用找到的解構(gòu)造新的初始解，但局部搜索能力較弱，求解質(zhì)量欠高。本文將填充函數(shù)算法和人工蜂群算法的優(yōu)點相結(jié)合，根據(jù)最大二等分問題的特性，提出了一種求解最大二等分問題的混合二進制人工蜂群算法。前期研究表明，組合優(yōu)化問題高質(zhì)量解之間的相似度較高[15]。首先，混合二進制人工蜂群算法設(shè)計了新的食物源更新策略，利用已經(jīng)搜索到的高質(zhì)量解，產(chǎn)生新的食物源(初始解)。與填充函數(shù)算法采用隨機初始解相比，混合二進制人工蜂群算法新產(chǎn)生的解能有效繼承高質(zhì)量解的優(yōu)良結(jié)構(gòu)，提高求解效率。其次，通過填充函數(shù)算法對新產(chǎn)生的初始解進行再優(yōu)化，與其他人工蜂群算法相比，混合二進制人工蜂群算法提高了算法的局部搜索能力，有效提高了求解質(zhì)量。

為了驗證混合二進制人工蜂群算法的性能，采用常用的標準測試算例對其進行測試，測試算例數(shù)據(jù) 從 http://www.stanford.edu/～yyye/yyye/Gset/下載。將本文算法的結(jié)果與Lagrangian net、填充函數(shù)算法得到的結(jié)果進行比較，結(jié)果表明，混合二進制人工蜂群算法能找到更好的解。此外，還驗證了混合二進制人工蜂群算法中主要算子的有效性。

1 模型和填充函數(shù)算法

1.1 數(shù)學(xué)模型

給定一個無向圖G=(V,E)，其中，V={1,2,…,n}（n為偶數(shù)）是頂點集，E是邊集合。頂點i和頂點j之間的邊(i,j)∈E的權(quán)值為wij。由圖的最大二等分問題尋找頂點集V的一個劃分(A,B)，滿足A∪B=V，A∩B=?，且|A|=|B|，使得2個頂點分別在A，B中的邊的權(quán)的和最大。

引入分割向量x∈{-1,1}n，若i∈A，記xi=1，否則記xi=-1。令W=[wij]，Diag(x)表示以x的元素為對角元，其余元素為0的矩陣，e表示全1的n維向量表示Laplace矩陣，則圖的最大二等分問題可以建模為以下整數(shù)規(guī)劃問題[17]：

1.2 填充函數(shù)

文獻[17]提出了求解圖的最大二等分問題的填充函數(shù)算法。假設(shè)x*是當(dāng)前找到的最好解，首先構(gòu)造了問題(MB)在x*處的輔助函數(shù)：

其中，k＞0為參數(shù)，d(x,x*)是解x和x*間的距離，其次，將問題 (MB)等價轉(zhuǎn)化為無約束的輔助問題：

文獻[17]證明了當(dāng)k足夠大時，問題(MB)和(AMB)具有相同的全局最優(yōu)解。最后，設(shè)計了一個基于迭代改進的最大二等分問題局部搜索算法（FMMB）。FMMB由若干個迭代組成，在開始階段，所有頂點均能自由移動。每個迭代由若干個交換操作組成，每個交換操作包含2個步驟。FMMB從一個可行劃分(A,B)出發(fā)，第1步，將自由的且具有最大增益的頂點從一個子集移到另一個子集，并鎖定該頂點，即該頂點禁止在該迭代中繼續(xù)移動。頂點移動的增益定義為

填充函數(shù)算法是一種多起始點搜索算法。首先，從一個隨機的可行解出發(fā)，利用局部搜索算法FMMB找到1個可行解x*，在x*處構(gòu)造問題(MB)的填充函數(shù)F(x,x*)和輔助問題(AMB)。然后，從1個隨機可行解出發(fā)，利用FMMB搜索輔助問題(AMB)，當(dāng)找到 1個比x*更好的解時，更新x*，并重新構(gòu)造輔助問題(AMB)。重復(fù)以上步驟，直到滿足預(yù)設(shè)的終止條件。

2 人工蜂群算法

人工蜂群算法是受蜜蜂覓食行為啟發(fā)由KARABOGA[18]提出的。近年來，人工蜂群算法受到越來越多學(xué)者的關(guān)注。

應(yīng)用人工蜂群算法求解優(yōu)化問題時，食物源代表優(yōu)化問題的1個解。食物源的優(yōu)劣取決于優(yōu)化問題的適應(yīng)值，適應(yīng)值越高表示食物源越好。蜂群主要由兩大類人工蜂組成。一類是采蜜蜂(employed bees)，負責(zé)在當(dāng)前食物源附近搜索。另一類是特工蜂(unemployed bees)。特工蜂由跟隨蜂和偵察蜂組成。跟隨蜂負責(zé)在優(yōu)質(zhì)食物源附近搜索，進而提高算法的收斂速度；偵察蜂在解空間中隨機尋找新的食物源，提高搜索的多樣性。

傳統(tǒng)人工蜂群算法的主要步驟[23]如下：

算法1傳統(tǒng)二進制人工蜂群算法。

步驟1初始化。隨機產(chǎn)生NS個n維向量，令表示產(chǎn)生的第i個向量，每一維分量的生成公式為

其中，rand(0,1)是(0，1)間的隨機數(shù)；xmax,j和xmin,j表示第j維的上下界。用式(3)計算每只采蜜蜂對應(yīng)的食物源的適應(yīng)值：

其中fi是第i個食物源xi(針對求最小值的優(yōu)化問題)。記適應(yīng)值最大的食物源為gbest，其對應(yīng)的適應(yīng)值為fitbest。

步驟2循環(huán)階段。對食物源進行更新，直到滿足終止條件。

步驟2.1采蜜蜂階段：針對xi產(chǎn)生1個候選解vi：

其中，k∈{1,2,…,NS}且k≠i，φi,j是[-1,1]上的隨機數(shù)。比較vi和xi的適應(yīng)值，若vi的適應(yīng)值大于xi，令xi=vi。

步驟2.2跟隨蜂階段：利用適應(yīng)值計算每個食物源的被選擇概率pi:

跟隨蜂采用輪盤賭算子來決定xi是否進行更新。即隨機產(chǎn)生 1 個ri∈(0,1)，若ri＜pi，則用式(4)產(chǎn)生xi的一個候選食物源vi，若vi的適應(yīng)值優(yōu)于xi的適應(yīng)值，則用vi替換xi。

步驟2.3偵察蜂階段：如果有食物源xi在限定次迭代中無更新，那么放棄食物源xi，用式(2)隨機產(chǎn)生1個新的食物源替代xi。

步驟2.4更新gbest和fitbest。

步驟3停止，輸出gbest和fitbest。

3 混合二進制人工蜂群算法

3.1 適應(yīng)值和候選解

傳統(tǒng)人工蜂群算法已經(jīng)成功應(yīng)用于求解各種連續(xù)優(yōu)化問題。近年來，研究者根據(jù)傳統(tǒng)人工蜂群算法的框架，提出了各種版本的二進制人工蜂群算法。前期研究結(jié)果[24-25]表明，結(jié)合待求解的優(yōu)化問題的性質(zhì)能有效提高二進制人工蜂群算法的性能。本文根據(jù)最大二等分問題的性質(zhì)，提出了新的食物源更新策略，即候選解產(chǎn)生方法。

混合二進制人工蜂群算法直接將最大二等分問題的目標函數(shù)值f(x)作為解的適應(yīng)值。

文獻[15-16]的研究結(jié)果表明，最大二等分問題的高質(zhì)量解之間的距離較小，即解之間的相似度較高。為了提高候選解的質(zhì)量，用下式產(chǎn)生候選解：

其中，k∈{1,2,…,NS}且k≠i，? 算子的操作如下：假設(shè)xi，xk和vi對應(yīng)的劃分分別為 (Ai,Bi)，(Ak,Bk)和 (Av,Bv)，首先令A(yù)v=Ai∩Ak，Bv=Bi∩Bk；接著將剩下的頂點V-(Av∪Bv)平均分配給Av和Bv；最后，為了增加多樣性，在Av和Bv中分別選擇0.1n（n表示圖的頂點數(shù)）個頂點進行對換，從而得到新的可行解vi。新產(chǎn)生的候選解vi繼承了xi和xk的優(yōu)良結(jié)構(gòu)，同時具有良好的多樣性，提高了算法的性能。

3.2 混合算法

針對最大二等分問題的性質(zhì)，結(jié)合離散填充函數(shù)算法和二進制人工蜂群算法，設(shè)計了求解最大二等分問題的混合二進制人工蜂群算法?；旌隙M制人工蜂群算法流程圖如圖1所示，其基本思想為：初始化參數(shù)首先，隨機生成NS個可行解xi,i=1,2,…,NS，每個解對應(yīng)一個食物源。記其中適應(yīng)值最大的為x*，在x*處構(gòu)造問題(MB)的填充函數(shù)F(x,x*)和輔助問題(AMB)。在采蜜蜂階段，對每個食物源xi，用式(6)產(chǎn)生候選解vi。為進一步提高算法的收斂速度，從當(dāng)前候選解vi出發(fā)，將利用FMMB優(yōu)化輔助問題(AMB)找到的解記為y。由文獻[17]的定理2和定義3得：f(y)＞f(x*)或y=x*。如果f(y)＞f(x*)，找到了更好的解，則用y替換當(dāng)前食物源xi，即令xi=y，并更新x*和輔助問題 (AMB)。否則，比較f(vi)和f(xi)，如果f(vi)＞f(xi)，更新食物源xi=vi。在偵察蜂階段，如果食物源xi在限定次迭代中無更新，那么，在此食物源附近很難再找到更好的解，需要更新食物源。由于最大二等分問題高質(zhì)量解間距離較小，用當(dāng)前最優(yōu)解x*附近的解來替換當(dāng)前食物源可以提高搜索速度。設(shè)x*對應(yīng)的劃分為(A*,B*)，在A*和B*中分別隨機選擇0.025n個頂點進行對換，產(chǎn)生新的食物源xi。混合二進制人工蜂群算法，一方面，用人工蜂群算法框架，充分利用先前搜索到的高質(zhì)量解的信息產(chǎn)生新的解，從而有效提高新解的質(zhì)量；另一方面，利用填充函數(shù)算法來提高局部搜索能力。

圖1 算法流程圖Fig.1 Algorithm flowchart

下面給出求解問題(MB)的混合二進制人工蜂群算法的具體步驟，其中max_generation為算法運行的最大迭代數(shù)。

算法2混合二進制人工蜂群算法。

步驟1初始化。隨機產(chǎn)生NS個初始可行解xi，i=1,2,…,NS。 記x*=argmax{f(xi),i=1,2,…,NS}，構(gòu)造問題(MB)在x*處的填充函數(shù)F(x,x*)和輔助問題(AMB)。初始化generation=0。

步驟2循環(huán)階段：對食物源進行更新，直到generation≥ max_generation。

步驟2.1采蜜蜂階段：針對xi，用式(6)產(chǎn)生候選解vi。再從vi出發(fā)，利用文獻[17]的局部搜索算法FMMB進一步優(yōu)化輔助問題(AMB)，找到的解記為y。若f(y)＞f(x*)，則令xi=y，x*=y，更新輔助問題 (AMB)；否則，若f(vi)＞f(xi)，則令xi=vi。

步驟2.2跟隨蜂階段：利用適應(yīng)值計算每個食物源的被選擇概率pi:

跟隨蜂采用輪盤賭算子決定xi是否更新。即隨機產(chǎn)生ri∈(0,1)，若ri＜pi，用式(6)產(chǎn)生xi的候選食物源vi，再從vi出發(fā)，利用文獻[17]的局部搜索算法FMMB進一步優(yōu)化輔助問題(AMB)，找到的解記為y若f(vi)＞f(xi)，用vi替換xi。 若f(y)＞f(x*)，則令x*=y，更新輔助問題。

步驟2.3偵察蜂階段：如果有食物源xi在限定次迭代中無更新，那么放棄食物源xi，x*對應(yīng)的劃分為(A*,B*)，選擇0.025n個頂點進行對換，產(chǎn)生一個新的食物源替代xi。

步驟2.4generation=generation+1。

步驟3停止，輸出x*。

4 仿真實驗與分析

為了驗證混合二進制人工蜂群算法的性能，采用C編程，對56個標準測試例子(從http://www.stanford.edu/～yyye/yyye/Gset/下 載)進 行 仿 真實驗。

4.1 與填充函數(shù)算法等實驗結(jié)果的比較

混合二進制人工蜂群算法中的參數(shù)設(shè)置：NS=8，限定迭代次數(shù)為3。其中涉及填充函數(shù)算法的參數(shù)直接沿用文獻[17]中的設(shè)置方法。圖2給出了算法的迭代次數(shù)與算法得到的解的質(zhì)量之間(在例子G1上)的關(guān)系圖。從圖2中可以看出，當(dāng)?shù)螖?shù)小于40時，解的質(zhì)量快速提升；當(dāng)max_generation＞40時，解的質(zhì)量已很難改進，算法基本收斂。故后續(xù)的實驗中取max_generation=40。

圖2 解的質(zhì)量與迭代次數(shù)關(guān)系圖Fig.2 The relationship between solution quality and number of iterations

為排除算法的偶然性，對每個測試例子進行10次計算。表1列出了混合二進制人工蜂群算法在10次運算中得到的最好結(jié)果(Cbest)、平均結(jié)果(Cavg)和算法運行的平均時間(tavg)，單位為s。為了與現(xiàn)存的Lagrangian net(LN)法[14]、填充函數(shù)算法[17]做比較，表1列出了LN和填充函數(shù)算法的結(jié)果，其中，LN列下的C和t分別表示算法得到的目標函數(shù)值和運行時間(s)。表1的最后一行給出了各列結(jié)果的平均值。從表1的結(jié)果中可以看出：

(1)在56個測試實例中，本文提出的混合二進制人工蜂群算法找到的平均結(jié)果都優(yōu)于文獻[14]中Lagrangian net算法得到的結(jié)果。

(2)與文獻[17]的填充函數(shù)算法相比，在56個測試實例中，混合二進制人工蜂群算法找到的最優(yōu)解有54個好于填充函數(shù)算法，找到的平均解全部優(yōu)于填充函數(shù)算法。

(3)Lagrangian net算法、填充函數(shù)算法、混合二進制人工蜂群算法的平均求解時間分別為65.84，49.078和49.163 s。填充函數(shù)算法和混合二進制人工蜂群算法消耗的求解時間大致相當(dāng)。

以上結(jié)果可見，與采用隨機初始解的填充函數(shù)算法相比，通過二進制人工蜂群算法框架構(gòu)造初始解，能有效提高填充函數(shù)算法的性能。

4.2 與改進的人工蜂群算法實驗結(jié)果的比較

2018年，HE等[26]提出了一類求解set-union背包問題的二進制人工蜂群算法(BABC)。根據(jù)最大二等分問題的特性，本文對HE等提出的二進制人工蜂群算法做了修改，修改后的算法記為MBABC。MBABC采用BABC的基本框架，將適應(yīng)值評價方法修改為最大二等分問題的目標函數(shù)；當(dāng)遇到不可行解時，采用隨機移動頂點的方法修復(fù)。

表1 實驗結(jié)果Table 1 Experimental results

續(xù)表1

圖3給出了混合二進制人工蜂群算法與MBABC在部分代表性例子上的計算結(jié)果。從圖3中可看出，混合二進制人工蜂群算法能找到比MBABC更好的結(jié)果，表明本文提出的算法性能優(yōu)于MBABC。

圖3 本文算法與MBABC的比較Fig.3 Comparison between the method and the MBABC

4.3 算法主要創(chuàng)新點及有效性分析

混合二進制人工蜂群算法的主要創(chuàng)新點有：（1）根據(jù)最大二等分問題的特征，結(jié)合傳統(tǒng)人工蜂群算法框架，設(shè)計了新的食物源更新策略。（2）針對傳統(tǒng)人工蜂群算法局部搜索能力較弱的缺點，利用填充函數(shù)算法中的局部搜索算法FMMB來提高局部搜索能力。（3）在式(6)?算子的最后一步，將得到的劃分，隨機選擇0.1n個頂點進行對換，從而增加算法搜索的多樣性。

4.3.1 實驗結(jié)果表明，混合二進制人工蜂群算法的性能優(yōu)于填充函數(shù)算法，證明采用人工蜂群算法構(gòu)造初始解比直接采用隨機產(chǎn)生的初始解[17]好，本文設(shè)計的食物源更新策略能有效利用已經(jīng)找到的高質(zhì)量解產(chǎn)生新解，指導(dǎo)搜索。

4.3.2 考慮混合二進制人工蜂群算法的2種變形。第1種記為HABC1，HABC1將混合二進制人工蜂群算法中的局部搜索算法FMMB去掉，其他步驟不變；第2種記為HABC2，HABC2將混合二進制人工蜂群算法中?算子的最后一步對換0.1n個頂點去掉，其他步驟保持不變。表2記錄了用混合二進制人工蜂群算法、HABC1和HABC2求解一些代表性例子10次得到的最好結(jié)果(Cbest)、平均結(jié)果(Cavg)和算法運行的平均時間(tavg)。

從表2的對比數(shù)據(jù)中可以看出，在所有測試例子中，混合二進制人工蜂群算法和HABC2都能找到較HABC1好很多的最優(yōu)解和平均解?？梢?，局部搜索算法FMMB大大提高了人工蜂群算法的局部搜索能力。但是，混合二進制人工蜂群算法和HABC2的求解時間較HABC1大大增加了，說明局部搜索算法消耗了大部分求解時間。

4.3.3 與HABC2相比較，在14個代表性測試例子中，混合二進制人工蜂群算法在其中的10個例子上找到了更好的最優(yōu)解，在13個例子上找到了更好的平均解，但求解時間稍長，說明?算子中的頂點對換能增加搜索的多樣性，可避免過早收斂。

5 結(jié) 語

設(shè)計了求解最大二等分問題的混合二進制人工蜂群算法。該算法根據(jù)最大二等分問題的特點，采用傳統(tǒng)人工蜂群算法框架，重新定義了食物源更新方法，用當(dāng)前蜂群中高質(zhì)量的解來構(gòu)造新的解，繼承了高質(zhì)量解的優(yōu)良結(jié)構(gòu)。用填充函數(shù)算法中的局部搜索算法來提高人工蜂群算法的局部搜索能力。采用56個標準測試例子測試本文提出的混合二進制人工蜂群算法，結(jié)果表明，該算法優(yōu)于填充函數(shù)算法。還對算法主要創(chuàng)新點的有效性進行了驗證，實驗結(jié)果表明，局部搜索算法能有效提高二進制人工蜂群算法的求解質(zhì)量，但也增加了求解時間。本文的不足之處是未能有效利用最大二等分問題的結(jié)構(gòu)來構(gòu)造填充函數(shù)。進一步工作為：設(shè)計更加有效且運算量較低的填充函數(shù)，指導(dǎo)搜索方向，盡快跳出局部最優(yōu)解；設(shè)計速度更快的局部搜索算法，提高算法的求解速度；將本文的混合二進制人工蜂群算法推廣應(yīng)用于求解其他組合優(yōu)化問題。

表2 不同版本人工蜂群算法的實驗結(jié)果Table 2 Experimental results of different versions of artificial bee colony algorithms