基于Unity 3D的蟻群算法仿真

程廷，潘耘，姜瑞娟

(中國傳媒大學 計算機學院，北京 100024)

基于Unity3D的蟻群算法仿真

程廷，潘耘，姜瑞娟

(中國傳媒大學 計算機學院，北京 100024)

基于Unity3D引擎對蟻群尋路覓食場景進行了建模，通過C#語言編寫信息素迭代機制、蟻群尋找最短路徑的算法，并以可視化手段顯示出最短路徑，最后對蟻群算法的各個參數(shù)設置進行了探究。仿真結果驗證了使用Unity3D進行算法仿真的可行性，直觀易懂地呈現(xiàn)出蟻群算法的基本過程與原理，具有參數(shù)易控、視覺直觀性強等優(yōu)點。

蟻群算法；Unity3D；計算機仿真

1 引言

蟻群算法(Ant Colony Algorithm)是受自然界蟻群覓食過程啟發(fā)而提出的一種智能優(yōu)化算法，具有離散性、并行性、正反饋機制等特點[1]。為了能夠清楚地表達基本蟻群算法的數(shù)學模型，通常借助經(jīng)典的TSP(traveling salesman problem)旅行商問題對其進行描述[2]。其中包含較多數(shù)學模型，對于理解有一定的難度。為了使算法原理更加直觀，可讀性更強，考慮以可視化的形式呈現(xiàn)蟻群算法的仿真過程。因此，本文使用Unity3D引擎進行蟻群算法的仿真與實現(xiàn)。

Unity引擎是一款流行的3D/2D綜合型游戲開發(fā)工具和引擎套件，其中包括圖形、UI、物理、動畫等多方面的引擎支持[3]。Unity內置的PhysX物理引擎可以高效、逼真地模擬出蟻群覓食尋路的運動狀態(tài)。

本文使用Unity3D引擎對蟻群算法進行仿真模擬。首先創(chuàng)建了仿真場景的基本模型，然后使用C#語言編寫信息素迭代機制、蟻群尋路行為相關算法。通過添加腳本，可以改變仿真參數(shù)，比較不同參數(shù)下的仿真結果及算法效率；在仿真過程中，還可以對環(huán)境中的物體進行實時控制，并且可以實時輸出時間等數(shù)據(jù)，不必等到仿真結束再查看結果，提高了仿真實驗的效率。與Matlab等算法仿真軟件相比，本方法更加直觀、易控，具有一定優(yōu)勢。

2 蟻群算法的基本原理

2.1 蟻群算法原理

自然界中，蟻群通過互相協(xié)作完成覓食等復雜的任務，并以此找到較短的路徑。那么視覺系統(tǒng)發(fā)育不全的螞蟻是如何完成覓食的呢？研究發(fā)現(xiàn)，螞蟻會釋放一種叫信息素的化學物質。螞蟻在覓食的時候，經(jīng)過一段時間，就能找到一條從巢穴到食物源的最短路徑。這是因為，螞蟻在爬行的路徑上會釋放信息素。同時，螞蟻會實時感知信息素濃度，選擇一條信息素濃度高的路徑。當這條路徑上的信息素濃度越高，螞蟻選擇該路徑的概率越大，這樣就會有更多的螞蟻選擇該條路徑；相反，對于信息素濃度越低的路徑，螞蟻選擇它的概率就越小，隨著時間的推移，信息素濃度會越來越低，則以后螞蟻選擇該路徑的可能性也變得更小。由于較短路徑上的信息素被更多地保留下來，從而讓更多螞蟻聚集到最優(yōu)路徑上，這就是蟻群算法的正反饋機制[2]。

同時，當外部環(huán)境發(fā)生變化時，螞蟻能夠用很短的時間來適應這種變化。當在爬行路線上遇到障礙物時，螞蟻能很快找到較好路徑[1]。

為了便于理解，使用圖1至圖4說明蟻群覓食原理：

圖1 無障礙物時的覓食情況

圖2 有障礙物時的初始情況

圖3 選擇較短路徑的螞蟻多

圖4 蟻群最終沿最短路徑覓食

2.2 蟻群算法的數(shù)學模型

蟻群算法的數(shù)學模型通常以旅行商問題(TSP)來建立。TSP問題是：在給定城市個數(shù)和各城市之間距離的條件下，找到一條經(jīng)過所有城市且每個城市只能訪問一次的最短路線[4]。下式為信息素強度以及第k只螞蟻選擇某個城市的概率：

上述公式中i、j分別為起點和終點，τij(t)為時間t時，i到j的信息素強度。m為螞蟻個數(shù)。ρ表示信息素的揮發(fā)率，如果它的值取得不恰當，得到的結果很可能是局部最優(yōu)解[4]。概率公式中，ηij為i、j距離的倒數(shù)。allowedk為尚未訪問過的節(jié)點集合。α值的大小表明留在每個結點上的信息素受重視的程度，α值越大，螞蟻選擇以前經(jīng)過的路線的可能性越大；β的大小表明啟發(fā)式信息受重視的程度。α和β兩個因子決定了蟻群算法的全局尋優(yōu)性能和快速收斂性能[5]。

由于蟻群搜索是一個正反饋的過程，所以螞蟻數(shù)量越多，搜索速度應該越快。但是，螞蟻數(shù)量越多意味著迭代次數(shù)越多，消耗的時間也越多[5]。因此，本文基于Unity3D的蟻群算法仿真通過設置不同螞蟻數(shù)量、信息素的揮發(fā)時間等參數(shù)研究其對算法效率的影響，尋找出較高效的參數(shù)設置方法。

3 基于Unity3D的蟻群算法仿真設計

3.1 蟻群算法的仿真流程

使用Unity3D引擎進行蟻群算法仿真的具體流程如下：

初始化場景信息，設置螞蟻數(shù)量、信息素揮發(fā)時間、螞蟻搜索半徑、螞蟻速度等參數(shù)。

按照設置的螞蟻數(shù)量生成蟻群。

所有螞蟻按照概率隨機分布到場景中進行尋路覓食，同時釋放信息素。信息素強度隨時間線性衰減。

螞蟻在尋路過程中，自動繞過障礙物。當少數(shù)螞蟻找到食物，取走食物塊后，返回巢穴，同時釋放信息素(信息素軌跡可見，隨時間揮發(fā))。

當其它螞蟻感知到信息素后，則趨向于信息素較濃的路徑，同時獲得信息素攜帶的食物坐標，沿著路徑找到食物，取走食物塊返回巢穴，同時釋放信息素。

通過迭代，最終大多數(shù)螞蟻聚集在信息素濃度最強的最短路徑上。圖5為蟻群算法仿真流程圖。

圖5 蟻群算法仿真流程圖

3.2 仿真場景設計

本次仿真建立了兩個場景：1、單一目的地的最短路徑尋找及避障場景；2、多目的地的尋路避障復雜場景。

為了模擬自然界中蟻群覓食的真實場景，需要建立的模型有：螞蟻巢穴、螞蟻、障礙物、食物。為簡單起見，這些模型均使用立方體代替。在初始化時獲取每類模型的材質分別設置為不同的顏色，用以區(qū)分各自類別。其中，螞蟻是核心模型，為其添加剛體和尋路組件，創(chuàng)建信息素和食物塊作為其子物體，然后將螞蟻模型做為預置體，方便在仿真過程中實例化生成。

此外，創(chuàng)建平面作為地面，信息素的可視化效果使用Unity自帶的粒子系統(tǒng)生成。UI方面，使用Unity的UGUI系統(tǒng)創(chuàng)建圖例和計數(shù)UI。

3.3 仿真實現(xiàn)

Unity3D引擎支持的編程語言是C#和JavaScript[6]。本次仿真的程序設計使用的是C#語言。

3.3.1 場景初始化

在仿真初始時，為了生成相關參數(shù)，需要編寫Setup腳本。該腳本定義信息素產生間隔、信息素揮發(fā)時間、螞蟻移動速度、螞蟻搜索半徑、螞蟻數(shù)量等參數(shù)，并制作成可視化控制面板。圖6為Setup腳本生成的參數(shù)控制面板。

圖6 Setup控制面板

初始化參數(shù)后，會按照設置的螞蟻數(shù)量從巢穴生成相應數(shù)量的螞蟻。為此，編寫AntSetup腳本，獲取Setup面板中設置的螞蟻數(shù)量，在for循環(huán)體中使用Instantiate()函數(shù)實例化生成相應數(shù)量的螞蟻。

3.3.2 蟻群行為腳本與信息素迭代機制

生成一定數(shù)量的蟻群后，螞蟻開始隨機分布進行覓食并釋放信息素。為此，需編寫螞蟻尋路覓食的相關腳本。該腳本命名為AntBehavior，為蟻群算法核心腳本。

首先，螞蟻在尋路過程中會有三個狀態(tài)：尋路、跟隨信息素、運輸食物。每個狀態(tài)執(zhí)行相應的行為函數(shù)。因此，在腳本中利用枚舉結構定義這三個狀態(tài)。然后，設置不同的標簽，用以判斷螞蟻不同狀態(tài)的轉換，這里定義了3個布爾型標簽：是否找到食物、是否在運輸食物、是否找到信息素軌跡。在Update函數(shù)(Update函數(shù)是Unity提供的函數(shù)，其在每一幀被調用[6])中，使用switch選擇結構判斷螞蟻狀態(tài)，并執(zhí)行相應行為函數(shù)。偽代碼如下：

switch(當前狀態(tài))

{

case尋路：

explore()；//尋路函數(shù)

if(正在運輸食物)

{當前狀態(tài) = 運輸食物；}

if(找到信息素)

{當前狀態(tài) = 跟隨信息素路徑；}

break；

case跟隨信息素路徑：

followTrail()；//跟隨軌跡函數(shù)

if(正在運輸食物)

{當前狀態(tài) = 跟隨信息素路徑；}

if(!找到食物)

{當前狀態(tài) = 尋路；}

break；

case正在運輸：

transportFood()；//運輸函數(shù)

if(!正在運輸){

if(食物位置 != 初值)

{當前狀態(tài) = 跟隨信息素路徑；}

else

{當前狀態(tài) = 尋路；}

}

break；

}

螞蟻在不同狀態(tài)下會執(zhí)行相應的行為函數(shù)。圖7為螞蟻行為腳本的4個核心函數(shù)。分別為尋路函數(shù)、跟隨信息素軌跡函數(shù)、觸發(fā)函數(shù)和運輸函數(shù)。

圖7 螞蟻行為腳本的核心函數(shù)

生成蟻群后，每只螞蟻的初試狀態(tài)都為尋路，即執(zhí)行explore()函數(shù)。該函數(shù)實現(xiàn)了尋路算法，使螞蟻每1至2秒內重定向尋路。首先設置定時器timestamp用于計時。使用Random類的insideUnitSphere屬性隨機返回半徑為1的球體內的一個點的坐標，該坐標與螞蟻移動半徑相乘得到一個Vector3型的隨機方向變量。通過此變量實現(xiàn)螞蟻在尋路時隨機轉向的功能。使用導航網(wǎng)格類的SamplePosition()函數(shù)在導航網(wǎng)格上的指定范圍內尋找最近的點。該函數(shù)對網(wǎng)格進行采樣并尋找最近的點，采樣范圍從設置的第一個參數(shù)采樣起點開始到螞蟻運動半徑距離內。尋路目的地為碰撞信息類的碰撞位置。同時，信息素釋放并線性衰減。下面列出了尋路算法的關鍵代碼：

if(timestamp

{

Vector3randomDirection=Random.insideUnitSphere*setup.moveRadius；

randomDirection+=transform.position；

NavMeshHitnavMeshHit；

NavMesh.SamplePosition(randomDirection，

outnavMeshHit，setup.moveRadius，1)；

Vector3finalPosition=navMeshHit.position；

navMeshAgent.destination=finalPosition；

timestamp+=Random.Range(1f，2f)；

}

trailRenderer.time=Mathf.Lerp(trailRenderer.time，0f，0.01f)；// 信息素強度線性衰減

螞蟻在尋路過程中，如果找到信息素，就會執(zhí)行followTrail()函數(shù)。該函數(shù)使螞蟻沿著信息素軌跡找到食物。

螞蟻跟隨信息素路徑找到食物后，會執(zhí)行transportFood()函數(shù)，此函數(shù)設置了尋路的目的地為巢穴位置。螞蟻會取走食物塊并返回巢穴，且此時信息素渲染可見，返回的路徑將以可視化的手段顯示。

觸發(fā)算法也是核心之一。本仿真中，可能會與螞蟻發(fā)生觸發(fā)事件的對象有三類：食物、巢穴、信息素。要觸發(fā)碰撞，首先應給螞蟻、食物、信息素和巢穴這4類對象添加碰撞體。

Unity引擎提供了碰撞體和觸發(fā)器組件，碰撞體是物理組件的一類，它要與剛體一起添加到游戲對象上才能觸發(fā)碰撞[6]。本仿真基于Unity自帶的進入觸發(fā)和持續(xù)觸發(fā)函數(shù)，編寫了觸發(fā)算法。根據(jù)觸發(fā)者的不同，螞蟻執(zhí)行不同的行為。圖8為觸發(fā)算法流程圖：

圖8 觸發(fā)算法流程圖

綜上完成了蟻群行為的相關算法。

每只螞蟻在尋路過程的同時釋放信息素，信息素根據(jù)初始化場景時設置的信息素揮發(fā)時間進行線性衰減，直至消失。隨著時間推移，最優(yōu)路徑上的信息素越來越多，會有更多的的螞蟻跟隨信息素軌跡聚集到最優(yōu)路徑上，這就是本仿真使用的信息素迭代機制。

3.3.3 其他仿真細節(jié)

在本仿真中，食物由食物塊組成，當食物塊被螞蟻運輸完畢，食物自動消失。因此，所有食物預置體都添加碰撞體組件。當觸發(fā)者是螞蟻時，如果食物剩余且螞蟻狀態(tài)為正在運輸，則螞蟻取走食物塊，食物體積相應減少直至消失。食物新的體積使用冪函數(shù)進行求解。

自然界中，螞蟻實時連續(xù)釋放信息素。在本次仿真中，為了節(jié)省資源，設置計時器，實現(xiàn)每隔n幀釋放信息素的功能，n的具體數(shù)值由設置的信息素速率參數(shù)決定。以幀為單位是由于Unity的Update函數(shù)執(zhí)行單位是幀[6]。當信息素揮發(fā)完畢時，使用Destroy()方法銷毀信息素。

仿真結果與分析

本仿真所用的計算機配置為英特爾酷睿i3處理器，4G內存，NvidiaGeForceGT620顯卡，64位Windows7操作系統(tǒng)。使用的Unity版本為5.4.1f1(64bit)。

為了研究不同參數(shù)下本算法仿真的效率，使用Time類計時，所消耗的時間位于截圖最下方。螞蟻數(shù)量初值設為70。

圖9至圖11是場景一(單一目的地的最短路徑尋找及避障場景)蟻群尋路的仿真過程截圖，圖12為場景二(多目的地的避障尋路場景)的仿真截圖。

圖9 仿真初期蟻群生成

圖10 中期蟻群分布

圖11 終期蟻群聚集到信息素濃的最短路徑

圖12 場景二(多目的地的避障尋路場景)

本次仿真基于場景一，比較了不同螞蟻數(shù)量、信息素揮發(fā)時間參數(shù)下，蟻群找到最短路徑所花的時間。

表1 不同螞蟻數(shù)量的蟻群找到最短路徑的時間

表2 不同信息素揮發(fā)時間下，蟻群找到最短路徑的時間

表1至表2為不同螞蟻數(shù)量、信息素揮發(fā)時間參數(shù)下，蟻群找到最短路徑的時間。分析發(fā)現(xiàn)這些參數(shù)設置過大過小時都會導致算法效率下降。當螞蟻數(shù)量過小時，算法全局搜索能力差，收斂時間長；而螞蟻數(shù)量過大時，迭代次數(shù)增多，系統(tǒng)資源占用增多，也會導致效率下降。當信息素揮發(fā)完的時間過快時，信息素累積時間慢，收斂時間長；而信息素揮發(fā)完的時間過慢時，易造成局部收斂，降低算法結果精確性。

4 總結

本文基于Unity3D引擎，進行蟻群尋路覓食場景建模，通過C#語言編寫了蟻群尋找最短路徑等算法，最后對蟻群算法的各個參數(shù)設置進行了探究，探究發(fā)現(xiàn)螞蟻數(shù)量、信息素揮發(fā)時間等參數(shù)過大過小時都會導致算法效率下降。仿真結果驗證了使用Unity3D進行算法仿真的可行性，以可視化的方式直觀易懂地呈現(xiàn)出蟻群算法的基本過程與原理，為算法的仿真提供了一種較好的方法。

本文以可視化的形式實現(xiàn)了蟻群算法的仿真過程，但仍存在可改進的方面。在本仿真中，蟻群算法是通過信息素的累積和更新收斂于最優(yōu)路徑上的。但是，在求解初期，螞蟻釋放的信息素匱乏，求解速度慢，而一旦信息素積累到一定程度，就能夠快速收斂到最優(yōu)解。針對蟻群算法在初期求解速度慢這一缺點，可考慮結合遺傳算法進行組合優(yōu)化。遺傳算法在種群進化前期具有快速隨機的全局搜索能力[7]，與蟻群算法結合可以彌補前期求解慢的缺點。

[1]何小虎. 基于改進蟻群算法的圖像邊緣檢測[D]. 西北大學，2015.

[2]段海濱，王道波，于秀芬. 蟻群算法的研究現(xiàn)狀及其展望[J].中國工程科學，2007，9(2)：98-102.

[3]丁明華，李允旺，王勇. 基于Unity3d的麥克納姆輪移動平臺避障算法仿真[J].中國科技論文，2016，11(10)：1191-1195.

[4]葉志偉，鄭肇葆. 蟻群算法中參數(shù)α、β、ρ設置的研究——以TSP問題為例[J]. 武漢大學學報(信息科學版)，2004，29(7)：597-601.

[5]段海濱，王道波. 一種快速全局優(yōu)化的改進蟻群算法及仿真[J].信息與控制，2004，33(2)：241-244.

[6 ]陳泉宏. Unity API解析[M].北京：人民郵電出版社，2014.

[7]何娟，涂中英，牛玉剛. 一種遺傳蟻群算法的機器人路徑規(guī)劃方法[J].計算機仿真，2010，27(3)：170-174.

(責任編輯：宋金寶)

Simulation of Ant Colony Algorithm Based on Unity 3D

CHENG Ting，PAN Yun，JIANG Rui-juan

(Computer Science School，Communication University of China，Beijing 100024，China)

Based on Unity3D engine，this simulation creates scenes and designs ant colony algorithm through the c# script，and the shortest path is visible.Finally，the parameters of ant colony algorithm are researched.The results verify the feasibility of using Unity3D for algorithm simulation，being straightforward to show the basic process and principle of ant colony algorithm，with the advantage of visualization and easy control.

ant colony algorithm；Unity3D；computer simulation

2016-12-24

程廷(1994-)，男(漢族)，浙江衢州人，中國傳媒大學計算機學院研究生.E-mail：ct_cuc@163.com

TP

A

1673-4793(2017)03-0057-06