蟻群算法可視化軟件的設(shè)計和實現(xiàn)

陳嘉圣 李泓波 羅正德 李澤欽 彭攀宇 黃梓琛

摘? ?要：目前的蟻群算法一般都以數(shù)值形式展示結(jié)果，而蟻群自適應(yīng)、自組織的行為過程完全被掩蓋。對研究者和學(xué)習(xí)者來說，蟻群行為過程的透明性極易導(dǎo)致理解上的困難和偏差。針對這一問題，文章基于經(jīng)典蟻群算法，采用現(xiàn)代化可視化方法和技術(shù)，設(shè)計和實現(xiàn)了面向多種策略的蟻群算法可視化軟件。

關(guān)鍵詞：蟻群算法;可視化;人工智能

近幾年來，人工智能已經(jīng)成為學(xué)術(shù)界的研究熱點，得到越來越多學(xué)者的關(guān)注。人工智能的研究領(lǐng)域主要包括群體智能、機器人、語言識別、圖像識別、自然語言處理和專家系統(tǒng)等。AlphaGo、無人汽車駕駛、刷臉支付、智能搜索、定理證明、語言和圖像理解等都是人工智能的應(yīng)用實例[1]。

作為群體智能研究的重要研究內(nèi)容，蟻群算法近年來也得到廣泛關(guān)注和研究，其應(yīng)用領(lǐng)域目前已經(jīng)涵蓋了基因工程、作業(yè)調(diào)度、網(wǎng)絡(luò)路由、車輛路徑、機器人、電力系統(tǒng)、故障診斷、控制參數(shù)優(yōu)化、特征識別、聚類分析、數(shù)據(jù)挖掘、圖像處理、航跡規(guī)劃、空戰(zhàn)決策、化學(xué)工業(yè)、生命科學(xué)、布局優(yōu)化、模糊控制和云計算等多個學(xué)科和領(lǐng)域[2-3]。

目前的蟻群算法一般都以數(shù)值形式展示結(jié)果，而蟻群自適應(yīng)、自組織的行為過程完全被掩蓋。開展此項研究，有助于研究者和學(xué)習(xí)者克服蟻群行為過程透明性而導(dǎo)致的理解困難和偏差。

1? ? 相關(guān)研究工作

雖然蟻群算法應(yīng)用如此廣泛，但其可視化研究卻非常鮮見。在中國知網(wǎng)（China National Knowledge Infrastructure，CNKI）中以關(guān)鍵字“蟻群算法”+“可視化”進(jìn)行檢索，共檢索到相關(guān)文章0篇。在學(xué)術(shù)探索引擎Glgoo中以關(guān)鍵字“ACO”+“Visualization”進(jìn)行檢索，共檢索11 800條記錄。按Glgoo檢索算法，檢索出的最匹配記錄應(yīng)該排在最前。然而，在檢索結(jié)果中排在前面的記錄顯然沒有與檢索關(guān)鍵字完全匹配，因此，可以斷定在Glgoo的數(shù)據(jù)庫中找不到與關(guān)鍵字完全匹配的記錄。

2? ? 蟻群算法可視化算法

基于旅行商問題的蟻群算法可視化算法包含3個主要步驟，即螞蟻路徑的構(gòu)建、更新信息素、構(gòu)建可視化路徑和信息素。

在螞蟻路徑的構(gòu)建步驟中，算法將m只螞蟻隨機放置在不同的城市點中，然后根據(jù)公式（1）為每只螞蟻提供下一個城市的選擇，直至路徑構(gòu)建完畢。

在此公式中，Pijk表示位于城市i的螞蟻k到達(dá)城市j的概率，ηij=1/dij為啟發(fā)信息素，即兩個城市i和j之間距離的倒數(shù)，τij為城市i和j之間的信息素強度，α和β分別決定信息素和啟發(fā)信息素的相對影響力，allowedk為還未被螞蟻k訪問過的城市集合。

更新信息素步驟又分為信息素蒸發(fā)和螞蟻釋放信息素，在信息素蒸發(fā)過程中，當(dāng)所有螞蟻的路徑都構(gòu)建完畢后，各個城市之間的信息素將會減少一部分，按公式（2）執(zhí)行，其中，ρ為蒸發(fā)率。

信息素蒸發(fā)完畢后，每只螞蟻會在經(jīng)過的路徑中釋放信息素，按公式（3）和（4）進(jìn)行更新。公式（5）中的Ck為第k只螞蟻走完整條路徑后得到的總長度。

在可視化路徑和信息素中，使用C#的Graphics對象的DrawLine等方法將每一代螞蟻構(gòu)建的最佳路徑繪畫在顯示界面上，同時以表格形式顯示信息素強度。

3? ? 算法實現(xiàn)效果

一開始隨機創(chuàng)建10個城市，位置如圖1所示，此時的信息素各個邊的信息素強度都為0.002。

點擊下一次迭代按鈕后，算法找出一條螞蟻構(gòu)建的最佳路徑如圖2所示，其中的信息素強度如圖3所示。

繼續(xù)點擊下一次迭代按鈕后結(jié)果如圖4所示，此時再繼續(xù)多次點擊下一次迭代按鈕，不在圖4中顯示出來的邊的信息素強度趨向于0，算法結(jié)束。

4? ? 結(jié)語

針對蟻群算法的自適應(yīng)、自組織行為的透明性問題，本文通過現(xiàn)代化可視化手段，基于經(jīng)典蟻群算法，設(shè)計和實現(xiàn)了面向經(jīng)典蟻群、最大最小螞蟻、精英螞蟻等多種策略的蟻群算法可視化軟件。

[參考文獻(xiàn)]

[1]MARZBAND M，YOUSEFNEJAD E，SUMPER A，et al.Real time experimental implementation of optimum energy management system in standalone microgrid by using multi-layer ant colony optimization[J].International Journal of Electrical Power & Energy Systems，2016（75）：265-274.

[2]KPONYO J J，NWIZEGE K S，OPARE K A，et al.A distributed intelligent traffic system using ant colony optimization：a netlogo modeling approach[C].Hangzhou：International Conference on Systems Informatics，2017.

[3]曾夢凡，陳思洋，張文茜，等.利用蟻群算法生成覆蓋表：探索與挖掘[J].軟件學(xué)報，2016（4）：855-878.