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

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

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

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

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

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

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

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

雖然蟻群算法應(yīng)用如此廣泛，但其可視化研究卻非常鮮見(jiàn)。在中國(guó)知網(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é)果中排在前面的記錄顯然沒(méi)有與檢索關(guān)鍵字完全匹配，因此，可以斷定在Glgoo的數(shù)據(jù)庫(kù)中找不到與關(guān)鍵字完全匹配的記錄。

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

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

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

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

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

信息素蒸發(fā)完畢后，每只螞蟻會(huì)在經(jīng)過(guò)的路徑中釋放信息素，按公式（3）和（4）進(jìn)行更新。公式（5）中的Ck為第k只螞蟻?zhàn)咄暾麠l路徑后得到的總長(zhǎng)度。

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

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

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

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

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

4? ? 結(jié)語(yǔ)

針對(duì)蟻群算法的自適應(yīng)、自組織行為的透明性問(wèn)題，本文通過(guò)現(xiàn)代化可視化手段，基于經(jīng)典蟻群算法，設(shè)計(jì)和實(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]曾夢(mèng)凡，陳思洋，張文茜，等.利用蟻群算法生成覆蓋表：探索與挖掘[J].軟件學(xué)報(bào)，2016（4）：855-878.