基于蟻群算法的管道規劃改進方法探究

黃鋼忠 姜春濤 楊志鵠 黃澤斌 黃穎欣 馮櫻

摘 ?要： 傳統蟻群在區域規模較大時收斂速度逐漸減慢，會出現效率低、精準度下降、局部最優解概率高等弊端。文章針對傳統蟻群算法出現的這些問題進行改進，提出一種雙向蟻群算法，構造解空間時可以有效的降低數據規模。雙向蟻群算法起點和終點并行計算，使得蟻群算法的搜索效率得到了極大的提高，并且可避免算法陷入局部最優解，提高了結果的有效性和準確性。

關鍵詞： 傳統蟻群算法; 雙向蟻群算法; 并行計算; 管道規劃

中圖分類號：TP 301.6 ? ? ? ? ?文獻標志碼：A ? ? 文章編號：1006-8228（2019）10-40-03

Abstract： When the area scale of traditional ant colony is large， the convergence speed gradually slows down， resulting in the disadvantages of low efficiency， stagnation and high probability of local optimal solution. Aiming at the problems of traditional ant colony algorithm， this paper proposes a bidirectional ant colony algorithm， which can effectively reduce the size of data when constructing solution space. The parallel computation of the start and end points of the bidirectional ant colony algorithm greatly improves the search efficiency of ant colony algorithm， avoids the algorithm falling into the local optimal solution， and improves the accuracy of the results.

Key words： traditional ant colony algorithm; bidirectional ant colony algorithm; parallel computation; pipeline planning

0 引言

在城市進行基礎工程設施規劃加速建設時，原有的城市管網承載力會即將飽和，管網系統建設是城市建設至關重要的一環。所以管道路徑規劃作為城市建設的重要組成部分，國內外學者的研究方法主要有遺傳算法[1]、粒子群算法[2]、智能蟻群算法[3]、啟發式搜索方法[4]等。

蟻群算法是由意大利學者Dorigo等[5]提出的一種智能優化算法， 在解決路徑規劃問題上取得了不錯的效果。但是蟻群算法也存在易出現局部最優解、搜索時間長和陷入死鎖等問題。

本文針對蟻群算法易陷入局部最優解的問題和收斂速度慢的問題進行如下改進：1）改進概率選擇策略和雙向蟻群策略，提高算法收斂速度;2）雙向蟻群策略可以有效減少死鎖螞蟻數量;3）通過改進的啟發函數策略和信息素更新原則，防止陷入局部最優。

1 蟻群算法

昆蟲學家研究螞蟻的行為時，發現螞蟻的覓食行為雖然簡單，但卻有一定的智能表現。蟻群可以在不同的環境下，尋找到抵達食物源的最短路徑。因為蟻群內的螞蟻可以通過某種信息機制實現信息的傳遞。螞蟻會在其經過的路徑上釋放一種可以稱之為“信息素”的物質，蟻群內的螞蟻對“信息素”具有感知能力，它們會往“信息素”濃度較高的地方搜索，每一只覓食的螞蟻都會在其經過的路徑留下信息素，這種行為類似于正反饋機制。一段時間后，整個蟻群就會沿著最短路徑到達食物源，也便得到最終的最優或者次優路徑。

1.1 構造解空間

圖1為傳統蟻群算法流程圖。

蟻群算法的解空間為螞蟻可以行動的路徑或區間，在可行動的范圍中設置出發點和終點。

1.2 節點選擇

螞蟻從當前節點選擇下一節點的方法如公式⑴。

3 總結

傳統蟻群在區域規模較大時收斂速度逐漸減慢，會出現效率低、精準度下降、局部最優解概率高等弊端。本文針對傳統蟻群算法出現的這些問題進行改進，提出一種雙向蟻群算法，構造解空間時可以有效的降低數據規模，同時雙向蟻群算法起點和終點并行計算，可以非常有效的減少算法的運行時間，使得蟻群算法的搜索效率得到極大的提高，并且可避免算法陷入局部最優解，提高了結果的有效性和準確性。

參考文獻（References）：

[1] 劉二輝，姚錫凡，藍宏宇.基于改進遺傳算法的自動導引小車動態路徑規劃及其實現[J].計算機集成制造系統，2018.24（6）：1455-1467

[2] 許川佩，呂瑩，黃喜軍.基于粒子群算法的數字微流控芯片在線測試路徑優化[J].電子測量與儀器學報，2017.31（8）：1192-1199

[3] 劉浩然，孫美婷，李雷.基于蟻群節點尋優的貝葉斯網絡結構算法研究[J].儀器儀表學報，2017.38（1）：143-150

[4] 陳洋，譚艷平，程磊.領域約束下空地異構機器人系統路勁規劃方法[J].機器人，2017.39（1）：1-7

[5] DORIGO M， GAMBARDELLA L M.Ant colony system：A cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Conputation，1997.1（1）：53-66