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

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

關鍵詞： 傳統(tǒng)蟻群算法; 雙向蟻群算法; 并行計算; 管道規(guī)劃

中圖分類號：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 引言

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

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

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

1 蟻群算法

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

1.1 構造解空間

圖1為傳統(tǒng)蟻群算法流程圖。

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

1.2 節(jié)點選擇

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

3 總結

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

參考文獻（References）：

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

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

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

[4] 陳洋，譚艷平，程磊.領域約束下空地異構機器人系統(tǒng)路勁規(guī)劃方法[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