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

丁怡心 廖勇毅

(廣州民航職業技術學院 計算機系，廣東 廣州 510800)

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

劉國寶等人提出精英蟻群算法[7,8]，此類算法的改良方法思路是：以某種策略選擇較優的路徑，并在更新信息素時在這些路徑上增加額外的信息素，增強正反饋作用。

Gambardella、王芳等人提出自適應蟻群算法[9,10]，此類算法的改良思路是：動態調整信息素揮發因子，避免某些路徑因信息素過少導致算法陷入“早熟”。

Ciornei、鄧博等人提出智能融合算法[11,12]，此類算法的改良方法思路是：引入遺傳算法、人工免疫算法、模擬退火算法等智能啟發算法的優點對蟻群算法進行改良。

文章通過對TSPLIB已公布的最優解做統計，發現單源邊與最優解的吻合率約為91.14%，多源邊與最優解吻合率約為64.14%，以此為依據提出基于最小生成樹扇度的蟻群算法。

1 蟻群算法

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

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

（2）碰到還沒走過的路口，就隨機挑選一條路走。同時釋放與路徑長度有關的信息素。

（3）信息素濃度與路徑長度成反比。后來的螞蟻再次碰到該路口時，就選擇信息素濃度較高路徑。

（4）信息素會隨著時間揮發，于是較差路徑上的信息素越來越淡，最優路徑上的信息素越來越濃。

（5）最終蟻群找到最優尋食路徑。

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

1.1 選擇路徑

設螞蟻k當前處于城市i，則其選擇城市j為下一個訪問對象的概率計算見公式(1)。

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

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

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

1.2 信息素更新

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

其中，m為螞蟻個數，Ck為螞蟻k在本輪走完一圈的總距離。

ρ 是信息素揮發因子，(1- ρ)則為殘留因子，殘留因子值越大，路徑上殘留的信息素越多，導致無效的路徑繼續被搜索，影響算法的收斂速度。

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

2.1 名詞解析

最小生成樹節點扇度:對于最小生成樹上的一個節點，連接該節點的邊的數目稱為該節點的扇度。

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

圖1 最小生成樹

最小生成樹單源邊:對于最小生成樹上的一條邊，如果該邊的兩個節點扇度都小于或等于2，則該邊為單源邊。

最小生成樹多源邊：對于最小生成樹上的一條邊，如果該邊有一個節點扇度都大于2，則該邊為多源邊。

例如圖1中，邊ef的兩個節點的扇度都為2，所以為單源邊；對于邊ab，節點a的扇度為1，節點b的扇度為2，所以ab為單源邊；對于邊cd，節點c的扇度為3，所以cd為多源邊。

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

2.2 算法啟發

基于最小生成樹扇度的蟻群算法靈感源于以下統計數據的啟發。

文章作者統計了TSPLIB上已公布最優解的數據集，分析最小生成樹與最優解之間的吻合情況。圖2截取了部分統計實驗界面效果圖。

圖2 部分統計實驗效果截圖

見表1，統計結果如下：最小生成樹的邊與最優解的邊吻合率為75.76 %，其中單源邊吻合率為91.14 %，多源邊吻合率為64.14%。

表1 最小生成樹與最優解吻合統計

2.3 算法思想

以上統計結果表明最小生成樹的邊對最優解有很強的導向性，于是提出算法思想如下：通過初始化信息素實現對蟻群的導向，并且對單源邊、多源邊及其它邊初始化不同量的信息素，以體現不同強度的導向性。

最小生成樹單源邊的強導向性在一定程度上降低了問題的規模，同時一定程度上把原先的問題分割成若干個規模更小的問題，結合蟻群算法的全局搜索能力及對小規模問題良好解決能力，可以實現快速收斂并能得到較優的解。

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

圖3 單源邊降低問題規模

2.4 算法流程

圖4 算法流程

單源邊的強導向性可能會導致若干與最優解不吻合的單源邊被構建到最終路徑中，通過去交叉、點交換、點轉移等局部優化方法可以有效地優化最終解。

3 實驗

3.1 實驗一 參數調優

實驗目的是調整參數τsingle、τmulti及 τbase到適合的值，使算法效果最佳。

實驗選取數據集為ch150.tsp，蟻群算法的基本參數設置見表2。為了更純粹地比較蟻群的尋路能力，該實驗屏蔽了點交換、點轉移、去交叉等輔助優化方法。

表2 蟻群算法基本參數設置

表3 各組實驗參數設置

表4 第1組實驗數據

表5 第2組實驗數據

第3組實驗的10次測試數據見表6。

表6 第3組實驗數據

第4組實驗的10次測試數據見表7。

表7 第4組實驗數據

4組實驗結果表明，當最小生成樹邊的導向性較強時，算法收斂速度快，同時也會導致“早熟”，從而陷入局部最優解，如第1組實驗結果所示。當導向性比較弱時，算法收斂速度慢，蟻群的尋路表現起伏比較大，如第4組實驗結果所示。其中，第3組實驗中，蟻群尋路能力及收斂速度綜合表現最優，因此后面的實驗參數設置都參考第3組實驗的參數。

3.2 實驗二 對比精英螞蟻算法

精英螞蟻算法是綜合表現比較好的蟻群算法，該實驗目的是對比文章算法與精英螞蟻算法的效果。實驗同樣選取數據集ch150.tsp，用精英螞蟻算法進行10次測試。為了更純粹地比較蟻群的尋路能力，該實驗也屏蔽了點交換、點轉移、去交叉等輔助優化方法。

實驗的部分運行效果如圖5所示，10次測試結果見表8。

圖5 精英螞蟻算法部分實驗截圖

表8 精英螞蟻算法實驗數據

見表9，文章算法在實驗一第3組測試結果與精英螞蟻算法測試結果對比，兩種算法的尋路能力相當，文章提出算法則在收斂速度上有明顯優勢。

表9 改進蟻群算法vs精英螞蟻算法

3.3 實驗三 尋路能力測試

該實驗從TSPLIB中選取了若干數據集，測試算法在不同數據集中的表現，算法加入了點交換、點轉移、去交叉等輔助優化方法。

實驗共選取14個數據集，對每個數據集做10次測試，以下圖、表展示10次測試中最優的結果。

圖6-8展示程序運行界面，表10是測試數據匯總。

圖7 尋路能力測試界面截圖二

圖8 尋路能力測試界面截圖三

該實驗表明，算法在中小規模問題中尋路能力及收斂速度都表現非常優秀。

4 結論

文章對TSPLIB已公布的最優解進行統計，分析最優解路徑與最小生成樹邊之間的關系，以此為基礎提出基于最小生成樹扇度的蟻群算法。算法根據單源邊、多源邊及其它邊為路徑賦予不同量的信息素，為蟻群提供不同強度的導向作用，從而加快蟻群尋路速度及尋路精度。實驗表明算法在收斂速度及尋路能力方面都有顯著提高。下一步工作，針對最小生成樹邊的強導向作用引起的誤導問題進行改進。