人工蟻群覓食行為建模、仿真和分析

（北京航空航天大學 經濟管理學院， 北京 100083）

摘 要：在Wilensky蟻群覓食模型基礎之上，增加了多樣性、競爭機制和進化機制，提出了人工蟻群覓食行為仿真模型（AntcolonySim）。通過對該模型的仿真，分析了不同條件下的系統整體涌現屬性，包括最短覓食路徑、蟻群覓食優勢和競爭優勢。仿真結果及分析表明，AntcolonySim能夠比較逼真地模擬自然界蟻群的覓食行為，對研究如何通過多相互作用的agent來模擬和探索復雜系統中的整體涌現行為具有一定的參考價值。

關鍵詞：計算機仿真；復雜系統；蟻群；主體；涌現

中圖分類號：TP18 文獻標志碼：A

文章編號：10013695(2009)01020204

Artificial ant colony foraging behavior modeling， simulation and analysis

ZHANG Cheng，JIA Suling，WEI Fajie

(College of Management Science Economics， Beihang University， Beijing 100083， China)

Abstract:Based on Wilensky’s ant colony foraging model and considers additional nature rules including multispecies， competition and evolution mechanism，promoted AntcolonySim model.It carried out simulations based on AntcolonySim under different conditions as well as emergent properties including foraging predominance and analyzed competition predominance. The simulation result shows that AntcolonySim can simulate nature ant colony foraging realistically， which is also a reference for discussing emergent behavior in complex system through bottom interactional agents.

Key words:computer simulation; complex system; ant colony; agent; emergence

蟻群覓食模型是由Wilensky[1]基于NetLogo仿真軟件設計的，用來模擬自然界真實螞蟻覓食行為的多agent仿真模型。模型中的螞蟻個體（agent）行為極其簡單，但是由大量個體組成的蟻群整體卻能完成避開障礙物，找到最短覓食路徑等復雜任務。Wilensky通過對蟻群覓食模型的設計和仿真，驗證了復雜的、全局的、群體的行為可以源自簡單的、局部的、個體的規則這一復雜系統的核心內涵，從而豐富了人們對于復雜系統的認識。國內也有學者基于Bonabeau等人[2]提出的蟻群算法，設計并實現了蟻群覓食多主體仿真系統，并通過該系統驗證了蟻群算法的有效性和可適應性[3]。

本文設計的人工蟻群系統覓食行為仿真模型（AntcolonySim），以Wilensky蟻群覓食模型為原型，其創新之處在于引入了多樣性、競爭機制和進化機制等自然規則。

1）多樣性 不限于Wilensky模型中的單一種群、單一覓食規則，而是引入多種類型的蟻群，且不同類型的蟻群存在不同的覓食規則。

2）競爭機制 引入競爭、死亡、誕生等自然界客觀存在的生存法則。在覓食過程中，不同種類的蟻群可能發生競爭，優勝劣汰；表現出色的蟻群，將有機會誕生新的螞蟻等。

3）進化機制 較優的覓食規則有機會遺傳至下一代，低劣的覓食規則將被淘汰，體現適應和自然選擇的思想。

1 人工蟻群覓食行為仿真模型

11 環境

AntcolonySim中的人工蟻群生活在一個n×n的二維方格環境中，每只螞蟻占據一個方格(grid)。每個方格周邊包含了八個鄰近方格，按順時針方向分別用數字1~8表示，螞蟻只能感受到鄰近方格中所包含的信息，并且每次移動的范圍也僅限于鄰近方格中的某一格（圖1）。

整個環境包含了如下四類元素：

a)蟻群(antcolony)。存在四種類型的人工蟻群，用不同的顏色加以區分，分別為紅蟻群、藍蟻群、綠蟻群和黃蟻群，每種類型的蟻群包含了一定數量的人工螞蟻。

b)蟻巢(nest)。每種類型蟻群都擁有自己的蟻巢，人工螞蟻在尋覓到食物后，會設法將食物搬運回同類蟻群所在蟻巢。

c)信息素(pheromone)。螞蟻可以釋放信息素。信息素分為兩種，即找到食物后返回蟻巢的螞蟻釋放的食物信息素(food_pheromone)與從蟻巢出發尋找食物的螞蟻釋放的蟻巢信息素(nest_pheromone)。每類蟻群都可以感受到異類蟻群釋放的食物信息素，但不會感受到異類蟻群的蟻巢信息素，且信息素會按一定的速率從環境中消失。

d)食物(food)。環境中分布了一定量的食物，各蟻群為了生存繁殖，共同尋覓這些食物，并為此展開競爭。

面向對象的編程技術已經被廣泛地應用于系統建模領域，以下是基于面向對象設計思想的偽代碼，用以描述環境及其中包含的蟻群：

//類Grid用來描述環境中的任一方格

class Grid{

int row;//方格所在行

int col;//方格所在列

int food;//方格中的食物數量

int food_pheromone;//食物信息素數量

int red_nest_pheromone;//紅蟻的蟻巢信息素

int blue_nest_pheromone;//藍蟻的蟻巢信息素

int green_nest_pheromone;//綠蟻的蟻巢信息素

int yellow_nest_pheromone;//黃蟻的蟻巢信息素

/*方格類型，取0，1，2，3，4，分別代表普通方格、紅蟻巢、藍蟻巢、綠蟻巢和黃蟻巢*/

int grid_type; 

//獲取鄰近方格中最濃食物信息素

float get_max_food_pheromone();

Grid(row，col);//構造函數，用于創建一個方格

}

//類Antcolony用來描述環境中的人工螞蟻

class Antcolony{

int color; //人工螞蟻的類型

int row;//人工螞蟻所在方格的行

int col;//人工螞蟻所在方格的列

int energy;//人工螞蟻擁有的能量

boolean carrying_food;//是否攜帶食物

void putup_food();//背起食物

void putdown_food();//放下食物

void search_food();//沿食物信息素尋找食物

void search_nest(int color);//沿相應類型的蟻巢信息素回巢

void spread_food_pheromone();//釋放食物信息素

//釋放相應類型的蟻巢信息素

void spread_nest_pheromone(int color); 

abstract void free_move();//自由移動規則

void move(int i); //移入數字i對應的鄰近方格

Antcolony(row， col);//構造函數，用來創建人工螞蟻

}

其中，類Antcolony中所描述的各項基本行為都很簡單。以下偽代碼分別用于實現“背起食物”和“移入鄰近方格”這兩項基本行為，其余行為的具體實現不再贅述。

//以下偽代碼用于實現背起食物

void putup_food(){

carrying_food = true;//設置攜帶食物狀態為真

Grid(row， col).food--;//減少螞蟻所在方格的食物數量

}

/*螞蟻根據不同數字移入不同的鄰近方格。例如，數字1對應螞蟻所在方格的左上方格*/

void move(int i){

switch(i){

case 1:left_up();break; 

case 2:up();break;

case 3:right_up();break;

case 4:left();break;

case 5:right();break;

case 6:left_bottom();break;

case 7:bottom();break;

case else:right_bottom();

}

}

12 覓食規則

人工螞蟻的覓食規則實際上就是Antcolony類中所描述的各項基本行為的組合，可以總結為以下兩條：

a)螞蟻處于攜帶食物的狀態。螞蟻會檢測自己是否位于蟻巢。如果已經位于蟻巢，則它會放下食物，從而轉入沒有攜帶食物的狀態；否則，攜帶該食物沿蟻巢信息素較濃的方向移動，同時釋放食物信息素。

b)螞蟻處于沒有攜帶食物的狀態。螞蟻會判斷此地是否有食物，如果有食物，則背起該食物，從而轉入攜帶食物的狀態；否則，螞蟻會判斷周圍是否存在食物信息素，如果有信息素存在，則沿信息素較濃的方向移動，同時釋放蟻巢信息素，否則執行自由移動策略。

以下偽代碼用于描述任意人工螞蟻Antcolony(row， col)的覓食規則：

if(carrying_food==true)

if(Grid(row，col).grid_type==color)

putdown_food();

else{

search_nest(color);

spread_food_pheromone();

}

else

if(Grid(row， col).food > 0)

putup_food();

else{

if(Grid(row， col). get_max_food_pheromone()>r)

search_food();

else

free_move();

spread_nest_pheromone(color);

}

13 自由移動規則

不同類型蟻群的絕大多數行為都是一致的，但蟻群因感受不到信息素而采取的自由移動方式卻不盡相同。AntcolonySim模型在實際處理時，當鄰近方格中的食物信息素低于一定濃度r后，即認為各蟻群已經感受不到信息素的存在，進而采取自由移動規則。

紅蟻(redAntcolony)的自由移動規則最為簡單，它直接采用了隨機移動的方式，即當鄰近方格最濃食物信息素濃度低于r時，隨機移入鄰近方格中任一方格。偽代碼描述如下：

class RedAntcolony extends Antcolony {

void freemove(){

int i=random(1，8); //隨機產生一個1~8的整數

move(i);//移入該數字對應的鄰近方格

}

}

藍蟻(blueAntcolony)自由移動的原則是盡量避免移動到同類蟻群曾經到達過的方格，即藍蟻存在這樣一個信念：同類搜尋過的區域，不必重復搜尋。藍蟻在搜索食物過程中會遺留蟻巢信息素，因此藍蟻只需選擇蟻巢信息素最少的方向移動，就可以達到目的。相應的偽代碼描述如下：

class BlueAntcolony extends Antcolony{

void freemove(){

Grid［8］grids = Grid(row， col).get_neighbor_grids();

float min_pheromone = grids[1]. blue_nest_pheromone;

int index=1;

//獲得蟻巢信息素最少的鄰近方格

for(int i=2;i<=8;i++){

if(grids[i]. blue_nest_pheromone < min_pheromone){

index=i;

min_pheromone = grids[i]. blue_nest_pheromone;

}

}

move(index); //移入數字index對應的鄰近方格

}

}

綠蟻(greenAntcolony)的自由移動規則是紅蟻和藍蟻的組合，綠蟻以一定的概率p選擇紅蟻的隨機移動方式，以1-p的概率選擇藍蟻的自由移動方式。偽代碼描述如下：

class GreenAntcolony extends Antcolony {

void freemove(){

if(random(0，1)

RedAntColony.freemove();//紅蟻的自由移動方式

else

BlueAntColony.freemove();//藍蟻的自由移動方式

}

}

黃蟻（yellowAntcolony）存在一個根據遺傳算法產生的移動序列，由該序列決定黃蟻的自由移動方式。黃蟻一旦感受不到周圍有食物信息素的存在，就會按此移動序列移動，直到感受到食物信息素的存在或尋覓到食物。成功將食物搬運回巢穴的黃蟻，其相應的移動序列會被保存下來，模型自動保留最新的兩條移動序列，通過遺傳算法中的交叉運算[4]，將新的移動序列遺傳給新誕生的黃蟻。這種自由移動規則的設定，旨在繼承能夠將食物搬回巢穴的高效移動規則，淘汰低效的移動規則，體現自然選擇的基本原理。

黃蟻自由移動的規則用以下偽代碼描述：

class YellowAntcolony extends Antcolony{

/*成功搬運回食物的兩條最新移動序列，用長度為8的整數數組表示*/

static int［8］bettermovelist_1， bettermovelist_2; 

int movelist[8];//當前黃蟻的移動序列

int list_index=1;

/*構造函數，新的黃蟻誕生時，通過交叉運算自動繼承兩條最新的移動序列*/

public YellowAntcolony(){

for(int i=1;i<=8;i++)

if(i<=4)

movelist[i] = bettermovelist_1[i];

else

movelist[i] = bettermovelist_2[i];

}

void freemove(){

//按照移動序列移入相應的鄰近方格

move(movelist[list_index]); 

//確定下一次需要移入的鄰近方格

if(list_index ==8)

list_index = 1;

else

list_index ++;

}

}

14 競爭、死亡和誕生機制

模型為每只螞蟻賦予一定的初始能量值energy，螞蟻每移動一次，則energy減少一定數量，當energy=0時，螞蟻死亡。不同種類的螞蟻移動到同一方格時，按一定的概率f發生競爭，通過能量值energy進行比較，能量低者死亡，能量高者繼續存活并補充一定能量。

成功將一定數量的食物搬運回蟻巢的螞蟻，會誕生相應類型的新螞蟻。

2 仿真分析

21 仿真參數設定

基于AntcolonySim所述各項規則，設定各項仿真參數，如表1所示。

表1 AntcolonySim仿真參數設定

參數名稱取值參數名稱取值

環境規模n×n100×100人工螞蟻數量4×20

初始能量值energy500競爭概率f50%

移動一次能量減少值1誕生一只新螞蟻需要的食物量2

每次搬運的食物量1信息素衰減比例k5%、20%

22 模型仿真效果

圖2~4分別顯示了當信息素衰減比例k=5%時，所有人工螞蟻在模型運行次數step=1 315 035 000時的一次仿真效果。

圖5顯示的是信息素衰減比例k=20%，模型運行次數step=5 000時的另一次仿真效果。

圖6、7分別顯示了上述兩次仿真過程中各蟻群數量隨運行次數的變化情況。

23 涌現屬性分析

在系統科學中，涌現屬性被認為是無法從系統底層次行為或結構推導得出的系統高層次的新行為或新結構[5]，這些新行為或新結構通常被認為是系統整體大于部分之和的部分，如細胞自動機在演化時產生的滑翔機結構和振蕩等現象[6]。涌現是理解復雜系統的關鍵與核心，Holland[7]認為只有認清了涌現的本質，才能真正了解復雜系統。

在AntcolonySim中，如果沒有針對某屬性P進行硬編碼，但蟻群的個體行為卻直接或間接導致了P的產生，則P被認為是涌現屬性。AntcolonySim中的涌現屬性至少包括最短覓食路徑、蟻群各自的覓食優勢和蟻群各自的競爭優勢。

231 最短覓食路徑

AntcolonySim并沒有為任何蟻群設定沿最短路徑移動的算法，每只螞蟻的行為都是簡單的，甚至是隨機的，但每次仿真在運行一段時間后，都可以觀察到成群的螞蟻沿著一條近似直線的路徑在蟻巢和食物之間往返（見圖2~5中的信息素分布軌跡）。

螞蟻依靠釋放信息素這樣的簡單局部行為，不但能夠找到食物，而且還能夠吸引其他螞蟻的加入，直到最后涌現出一條最優覓食路徑被大多數螞蟻所共用。這種現象啟示人們，組成復雜系統的個體在一開始會由于信息的不完全而導致其行為在一定程度上表現出盲目性和隨機性， 但是這種盲目性和隨機性通過一段時間的相互作用與相互適應，就會演變成系統整體行為的秩序性和穩定性。這也驗證了，看似簡單的局部行為，其中很可能隱含了豐富的復雜特性，即簡單性可以造就復雜性。

232 蟻群各自的覓食優勢

由圖6和7不難看出，在四類蟻群各項初始條件完全一致而信息素消失比例k值較小時（k=5%），黃蟻的覓食方式逐漸占據了優勢，其結果是紅、綠、藍三類蟻群數量不斷降低，而黃蟻數量急劇上升，形成一枝獨秀的局面。當k值較大時(k=20%)，藍蟻和綠蟻的覓食方式開始顯示出明顯的優勢，而黃蟻原有的覓食優勢則逐漸喪失，最后形成的結果是藍蟻和綠蟻共同達到了較多的種群數量，而黃蟻和紅蟻則趨于消亡。

表2記錄了k=5%和k=20%時，任意10次仿真在模型運行次數step=5 000時各蟻群數量結果統計。

表2 任意10次仿真中，各蟻群數量結果統計(k=5%和20%，step=5000)

運行次數k=5%

紅蟻藍蟻綠蟻黃蟻

k=20%

紅蟻藍蟻綠蟻黃蟻

10201791087520

20001973223610

3020302084680

4000203465730

5049128675810

60091503148130

700033110251080

80013261359470

90241444159150

100002066106500

平均021.12.3186.68.883.156.80

表2中的蟻群數量統計結果以及圖6、7所反映出來的蟻群數量變化趨勢，所得出的結論是：黃蟻、藍蟻和綠蟻的覓食優勢與信息素消失比例k值緊密相關。k值越小，則黃蟻的覓食方式越有效，并且隨著時間的延續，其覓食優勢會越來越明顯；k值越大，則藍蟻和綠蟻的覓食方式越為有效，且隨著時間的延續，其覓食的優勢也會越來越明顯。

究其原因，蟻群系統是一個典型的非線性復雜系統，信息素衰減比例k的變化實際上改變了系統個體之間的局部作用規則，而復雜系統的特點之一就是小原因可能導致大結果[8]，底層次規則的簡單變化經過一段時間的演化，就可以導致系統高層次行為的質變。這也啟發人們，只需要找到類似信息素衰減比例這樣的杠桿參數，就有可能控制和改變復雜系統的整體行為。

233 蟻群各自的競爭優勢

異類蟻群在同時移入同一個方格時會按照一定的概率發生競爭，能量高者獲得勝利并繼續生存，能量低者死亡。為了比較這些競爭情況，筆者分別在不同k值的情況下對各蟻群的競爭勝負情況進行了統計。

設任一次仿真中的任一蟻群與異類蟻群共發生了n次競爭，其中有m次獲得勝利（0≤m≤n），則該蟻群的競爭勝率p可以表示為p=m/n。p代表的是在各項初始環境條件一致的情況下，各蟻群的競爭優勢，且p越大，說明蟻群的競爭優勢越明顯。

由表3的統計結果可以看出，無論k值取較小值或較大值，藍蟻的勝率總是最高的，而黃蟻則一直處于劣勢。

模型更多次的仿真結果表明，藍蟻在不同信息素衰減速率k的作用下均具有一定的競爭優勢，黃蟻則在競爭中屢次表現最差，即使黃蟻種群數量能夠維持在一個較高數目，其競爭優勢也很少出現。因此，藍蟻的覓食規則是一種有利于保持競爭優勢的規則，它能夠在較大程度上避免其在競爭中死亡，而黃蟻的覓食規則雖然可以在一定條件下保持種群的優勢，但這是一種競爭相對低效的覓食方式。

蟻群各自的競爭優勢啟示人們，計算機仿真雖然是研究復雜系統的有效方法，但僅僅依靠模擬仿真，并不一定能夠幫助人們發現那些隱藏的系統涌現屬性。一種更好的辦法是把仿真模擬和定量分析結合起來，這樣可以在較高層次上歸納出這些并非顯而易見的系統整體屬性。

3 結束語

AntcolonySim是一個規則簡單而又包含了豐富涌現屬性的復雜系統模型，這些涌現屬性無法直接從系統個體行為中直接觀察得出，也難以采用傳統的數學方法進行演繹。然而，通過基于agent的建模和仿真，就可以使個體行為中隱含的系統全局行為自發地涌現出來。這種自下而上的構建方法較傳統的形式化分析方法顯然更加形象直觀，它有助于人們更好地認識由簡單局部行為所產生的復雜整體行為，從而加深和豐富了人們對復雜現象本質的理解。

除此之外，AntcolonySim抓住了多樣性、競爭、適應性等真實復雜系統所具有的特征，對研究如何通過多交互作用的agent來描述、理解和控制真實世界中的復雜系統具有一定的參考價值，對研究如何通過基于人工系統的計算實驗方法[9]來歸納和評估復雜系統中的整體涌現屬性也具有一定的啟示意義。

參考文獻：

［1］

WILENSKY U. NetLogo ants model [EB/OL].(20030912) [20080403]. http://ccl.northwestern.edu/netlogo/models/Ants.

［2］BONABEAU E， DORIGO M， THERAULAZ G. Swarm intelligence:from natural to artificial systems [M].New York: Oxford University Press，1999.

［3］賀建民，閔銳.多agent系統中蟻群算法的設計與實現[J].微電子學與計算機，2006，23(10):3234.

［4］HOLLAND J.Adaptation in natural and artificial system[M].Michigan: University of Michigan Press，1975.

［5］BAAS N A. Emergence，hierarchies and hyperstructures[M]//LANGTON C G.Artificial life III.Red wood City，CA:AddisonWesley，1993.

［6］LANGTON C G. Studying artificial life with cellular automata[J].Physica D，1986，22:120149.

［7］HOLLAND J.Emergencefrom chaos to order[M]. USA: AddisonWesley， 1998.

［8］CILLIERS P.復雜性與后現代主義[M].曾國屏，譯.上海:上海科技教育出版社，2006.

［9］王飛躍.計算實驗方法與復雜系統行為分析和決策評估[J].系統仿真學報，2004，16(5):893897.