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

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

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

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

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

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

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

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

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

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

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

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

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

信息素蒸發(fā)完畢后，每只螞蟻會在經(jīng)過的路徑中釋放信息素，按公式（3）和（4）進行更新。公式（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é)語

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

[參考文獻]

[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].軟件學報，2016（4）：855-878.