基于最小生成樹扇度的蟻群算法

丁怡心 廖勇毅

(廣州民航職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)系，廣東 廣州 510800)

蟻群算法是一種尋找優(yōu)化組合的概率型算法，由Marco Dorigo在他的博士論文中提出[1,2]。蟻群算法本質(zhì)上是進(jìn)化算法中的一種啟發(fā)式全局優(yōu)化算法，該算法具有魯棒性強(qiáng)、并行計(jì)算和啟發(fā)式搜索等特征，并廣泛應(yīng)用于旅行商、網(wǎng)絡(luò)路由、任務(wù)調(diào)度等NP完全問(wèn)題。然而，蟻群算法存在收斂速度慢，容易陷入局部最優(yōu)解等問(wèn)題，對(duì)此眾多學(xué)者進(jìn)行了深入研究并提出了各種改進(jìn)方法[3,4,5,6]。

劉國(guó)寶等人提出精英蟻群算法[7,8]，此類算法的改良方法思路是：以某種策略選擇較優(yōu)的路徑，并在更新信息素時(shí)在這些路徑上增加額外的信息素，增強(qiáng)正反饋?zhàn)饔谩?/p>

Gambardella、王芳等人提出自適應(yīng)蟻群算法[9,10]，此類算法的改良思路是：動(dòng)態(tài)調(diào)整信息素?fù)]發(fā)因子，避免某些路徑因信息素過(guò)少導(dǎo)致算法陷入“早熟”。

Ciornei、鄧博等人提出智能融合算法[11,12]，此類算法的改良方法思路是：引入遺傳算法、人工免疫算法、模擬退火算法等智能啟發(fā)算法的優(yōu)點(diǎn)對(duì)蟻群算法進(jìn)行改良。

文章通過(guò)對(duì)TSPLIB已公布的最優(yōu)解做統(tǒng)計(jì)，發(fā)現(xiàn)單源邊與最優(yōu)解的吻合率約為91.14%，多源邊與最優(yōu)解吻合率約為64.14%，以此為依據(jù)提出基于最小生成樹扇度的蟻群算法。

1 蟻群算法

蟻群算法是一種模擬螞蟻覓食行為的模擬優(yōu)化算法，螞蟻會(huì)在其經(jīng)過(guò)的路徑上釋放信息素，蟻群內(nèi)的螞蟻對(duì)信息素具有感知能力，它們會(huì)沿著信息素濃度較高路徑行走，而每只路過(guò)的螞蟻都會(huì)在路上留下信息素，這就形成一種正反饋的機(jī)制，經(jīng)過(guò)一段時(shí)間后，整個(gè)蟻群就會(huì)沿著最短路徑到達(dá)食物源了。其基本工作原理如下：

（1）螞蟻在路徑上釋放信息素。

（2）碰到還沒走過(guò)的路口，就隨機(jī)挑選一條路走。同時(shí)釋放與路徑長(zhǎng)度有關(guān)的信息素。

（3）信息素濃度與路徑長(zhǎng)度成反比。后來(lái)的螞蟻再次碰到該路口時(shí)，就選擇信息素濃度較高路徑。

（4）信息素會(huì)隨著時(shí)間揮發(fā)，于是較差路徑上的信息素越來(lái)越淡，最優(yōu)路徑上的信息素越來(lái)越濃。

（5）最終蟻群找到最優(yōu)尋食路徑。

蟻群算法最核心的兩個(gè)問(wèn)題是路徑選擇和更新信息素。

1.1 選擇路徑

設(shè)螞蟻k當(dāng)前處于城市i，則其選擇城市j為下一個(gè)訪問(wèn)對(duì)象的概率計(jì)算見公式(1)。

其中， τ(i,j)為城市i和城市j之間的信息素濃度，η(i,j)為i和j之間距離的倒數(shù)。

α是信息素啟發(fā)因子，值越大信息素對(duì)路徑的選擇影響力越大，螞蟻選擇之前走過(guò)路徑的可能性越大，容易造成“早熟”。

β是期望啟發(fā)因子，值越大距離對(duì)路徑選擇的影響力越大，螞蟻選擇較短路徑的可能性越大，收斂速度變快，但是容易陷入局部相對(duì)最優(yōu)解。

1.2 信息素更新

所有螞蟻完成一輪迭代后需要對(duì)所有路徑的信息素進(jìn)行更新，首先把原來(lái)的信息素按一定比例揮發(fā)，然后加入最后一輪每只螞蟻產(chǎn)生的信息素.更新信息素計(jì)算見公式(3)。

其中，m為螞蟻個(gè)數(shù)，Ck為螞蟻k在本輪走完一圈的總距離。

ρ 是信息素?fù)]發(fā)因子，(1- ρ)則為殘留因子，殘留因子值越大，路徑上殘留的信息素越多，導(dǎo)致無(wú)效的路徑繼續(xù)被搜索，影響算法的收斂速度。

2 基于最小生成樹扇度的蟻群算法

2.1 名詞解析

最小生成樹節(jié)點(diǎn)扇度:對(duì)于最小生成樹上的一個(gè)節(jié)點(diǎn)，連接該節(jié)點(diǎn)的邊的數(shù)目稱為該節(jié)點(diǎn)的扇度。

如圖1所示，由于連接節(jié)點(diǎn)c的邊有3條，則節(jié)點(diǎn)c的扇度為3，同理節(jié)點(diǎn)g的扇度為4，節(jié)點(diǎn)a的扇度為1。

圖1 最小生成樹

最小生成樹單源邊:對(duì)于最小生成樹上的一條邊，如果該邊的兩個(gè)節(jié)點(diǎn)扇度都小于或等于2，則該邊為單源邊。

最小生成樹多源邊：對(duì)于最小生成樹上的一條邊，如果該邊有一個(gè)節(jié)點(diǎn)扇度都大于2，則該邊為多源邊。

例如圖1中，邊ef的兩個(gè)節(jié)點(diǎn)的扇度都為2，所以為單源邊；對(duì)于邊ab，節(jié)點(diǎn)a的扇度為1，節(jié)點(diǎn)b的扇度為2，所以ab為單源邊；對(duì)于邊cd，節(jié)點(diǎn)c的扇度為3，所以cd為多源邊。

通俗地說(shuō)，單源邊意味著從兩個(gè)方向進(jìn)入該邊的路都只有一條或沒有；多源邊則表示從某個(gè)方向至少有2條路進(jìn)入該邊。

2.2 算法啟發(fā)

基于最小生成樹扇度的蟻群算法靈感源于以下統(tǒng)計(jì)數(shù)據(jù)的啟發(fā)。

文章作者統(tǒng)計(jì)了TSPLIB上已公布最優(yōu)解的數(shù)據(jù)集，分析最小生成樹與最優(yōu)解之間的吻合情況。圖2截取了部分統(tǒng)計(jì)實(shí)驗(yàn)界面效果圖。

圖2 部分統(tǒng)計(jì)實(shí)驗(yàn)效果截圖

見表1，統(tǒng)計(jì)結(jié)果如下：最小生成樹的邊與最優(yōu)解的邊吻合率為75.76 %，其中單源邊吻合率為91.14 %，多源邊吻合率為64.14%。

表1 最小生成樹與最優(yōu)解吻合統(tǒng)計(jì)

2.3 算法思想

以上統(tǒng)計(jì)結(jié)果表明最小生成樹的邊對(duì)最優(yōu)解有很強(qiáng)的導(dǎo)向性，于是提出算法思想如下：通過(guò)初始化信息素實(shí)現(xiàn)對(duì)蟻群的導(dǎo)向，并且對(duì)單源邊、多源邊及其它邊初始化不同量的信息素，以體現(xiàn)不同強(qiáng)度的導(dǎo)向性。

最小生成樹單源邊的強(qiáng)導(dǎo)向性在一定程度上降低了問(wèn)題的規(guī)模，同時(shí)一定程度上把原先的問(wèn)題分割成若干個(gè)規(guī)模更小的問(wèn)題，結(jié)合蟻群算法的全局搜索能力及對(duì)小規(guī)模問(wèn)題良好解決能力，可以實(shí)現(xiàn)快速收斂并能得到較優(yōu)的解。

如圖3所示，bayg29.tsp是規(guī)模為29的TSP問(wèn)題，確定單源邊后規(guī)模近似地降至16，同時(shí)單源邊近似地把它們分割成A、B、C和D 4個(gè)規(guī)模分別為3、4、4和5的問(wèn)題。

圖3 單源邊降低問(wèn)題規(guī)模

2.4 算法流程

圖4 算法流程

單源邊的強(qiáng)導(dǎo)向性可能會(huì)導(dǎo)致若干與最優(yōu)解不吻合的單源邊被構(gòu)建到最終路徑中，通過(guò)去交叉、點(diǎn)交換、點(diǎn)轉(zhuǎn)移等局部?jī)?yōu)化方法可以有效地優(yōu)化最終解。

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

3.1 實(shí)驗(yàn)一 參數(shù)調(diào)優(yōu)

實(shí)驗(yàn)?zāi)康氖钦{(diào)整參數(shù)τsingle、τmulti及 τbase到適合的值，使算法效果最佳。

實(shí)驗(yàn)選取數(shù)據(jù)集為ch150.tsp，蟻群算法的基本參數(shù)設(shè)置見表2。為了更純粹地比較蟻群的尋路能力，該實(shí)驗(yàn)屏蔽了點(diǎn)交換、點(diǎn)轉(zhuǎn)移、去交叉等輔助優(yōu)化方法。

表2 蟻群算法基本參數(shù)設(shè)置

表3 各組實(shí)驗(yàn)參數(shù)設(shè)置

表4 第1組實(shí)驗(yàn)數(shù)據(jù)

表5 第2組實(shí)驗(yàn)數(shù)據(jù)

第3組實(shí)驗(yàn)的10次測(cè)試數(shù)據(jù)見表6。

表6 第3組實(shí)驗(yàn)數(shù)據(jù)

第4組實(shí)驗(yàn)的10次測(cè)試數(shù)據(jù)見表7。

表7 第4組實(shí)驗(yàn)數(shù)據(jù)

4組實(shí)驗(yàn)結(jié)果表明，當(dāng)最小生成樹邊的導(dǎo)向性較強(qiáng)時(shí)，算法收斂速度快，同時(shí)也會(huì)導(dǎo)致“早熟”，從而陷入局部最優(yōu)解，如第1組實(shí)驗(yàn)結(jié)果所示。當(dāng)導(dǎo)向性比較弱時(shí)，算法收斂速度慢，蟻群的尋路表現(xiàn)起伏比較大，如第4組實(shí)驗(yàn)結(jié)果所示。其中，第3組實(shí)驗(yàn)中，蟻群尋路能力及收斂速度綜合表現(xiàn)最優(yōu)，因此后面的實(shí)驗(yàn)參數(shù)設(shè)置都參考第3組實(shí)驗(yàn)的參數(shù)。

3.2 實(shí)驗(yàn)二 對(duì)比精英螞蟻算法

精英螞蟻算法是綜合表現(xiàn)比較好的蟻群算法，該實(shí)驗(yàn)?zāi)康氖菍?duì)比文章算法與精英螞蟻算法的效果。實(shí)驗(yàn)同樣選取數(shù)據(jù)集ch150.tsp，用精英螞蟻算法進(jìn)行10次測(cè)試。為了更純粹地比較蟻群的尋路能力，該實(shí)驗(yàn)也屏蔽了點(diǎn)交換、點(diǎn)轉(zhuǎn)移、去交叉等輔助優(yōu)化方法。

實(shí)驗(yàn)的部分運(yùn)行效果如圖5所示，10次測(cè)試結(jié)果見表8。

圖5 精英螞蟻算法部分實(shí)驗(yàn)截圖

表8 精英螞蟻算法實(shí)驗(yàn)數(shù)據(jù)

見表9，文章算法在實(shí)驗(yàn)一第3組測(cè)試結(jié)果與精英螞蟻算法測(cè)試結(jié)果對(duì)比，兩種算法的尋路能力相當(dāng)，文章提出算法則在收斂速度上有明顯優(yōu)勢(shì)。

表9 改進(jìn)蟻群算法vs精英螞蟻算法

3.3 實(shí)驗(yàn)三 尋路能力測(cè)試

該實(shí)驗(yàn)從TSPLIB中選取了若干數(shù)據(jù)集，測(cè)試算法在不同數(shù)據(jù)集中的表現(xiàn)，算法加入了點(diǎn)交換、點(diǎn)轉(zhuǎn)移、去交叉等輔助優(yōu)化方法。

實(shí)驗(yàn)共選取14個(gè)數(shù)據(jù)集，對(duì)每個(gè)數(shù)據(jù)集做10次測(cè)試，以下圖、表展示10次測(cè)試中最優(yōu)的結(jié)果。

圖6-8展示程序運(yùn)行界面，表10是測(cè)試數(shù)據(jù)匯總。

圖7 尋路能力測(cè)試界面截圖二

圖8 尋路能力測(cè)試界面截圖三

該實(shí)驗(yàn)表明，算法在中小規(guī)模問(wèn)題中尋路能力及收斂速度都表現(xiàn)非常優(yōu)秀。

4 結(jié)論

文章對(duì)TSPLIB已公布的最優(yōu)解進(jìn)行統(tǒng)計(jì)，分析最優(yōu)解路徑與最小生成樹邊之間的關(guān)系，以此為基礎(chǔ)提出基于最小生成樹扇度的蟻群算法。算法根據(jù)單源邊、多源邊及其它邊為路徑賦予不同量的信息素，為蟻群提供不同強(qiáng)度的導(dǎo)向作用，從而加快蟻群尋路速度及尋路精度。實(shí)驗(yàn)表明算法在收斂速度及尋路能力方面都有顯著提高。下一步工作，針對(duì)最小生成樹邊的強(qiáng)導(dǎo)向作用引起的誤導(dǎo)問(wèn)題進(jìn)行改進(jìn)。