一種通用蟻群智能規(guī)劃器架構(gòu)設(shè)計與實現(xiàn)

鄧向陽，沈劍，方偉，方君

（1.海軍航空工程學(xué)院信息融合研究所，煙臺　264001；2.海軍裝備部軍械保障部，北京　100841）

一種通用蟻群智能規(guī)劃器架構(gòu)設(shè)計與實現(xiàn)

鄧向陽1，沈劍2，方偉1，方君1

（1.海軍航空工程學(xué)院信息融合研究所，煙臺264001；2.海軍裝備部軍械保障部，北京100841）

部委級預(yù)研基金（No.9140A04020213JB14046）、部委級預(yù)先研究項目（No.51304030205）、院校青年基金（No.HYQN201315）

0　引言

1997年，Wolpert[1]等針對進(jìn)化算法提出的 NFL（No Free Lunch）定理指出：對于任意的表現(xiàn)度量，當(dāng)對所有可能的目標(biāo)函數(shù)做平均時，所有搜索算法的表現(xiàn)是完全一樣的。任何搜索算法在求解性能和對問題的普適性上不可能兼顧，在面對不同的優(yōu)化問題時，往往得不到一般意義下同樣的求解性能，也就是每個算法在面對不同的問題時，一般都需要根據(jù)問題特征進(jìn)行一定的調(diào)整，才能夠發(fā)揮最優(yōu)的性能。因此，蟻群算法作為一種應(yīng)用廣泛的進(jìn)化算法同樣具有泛化計算能力問題，一般稱為欺騙性問題[2]，Blum等在文獻(xiàn)[3]中對蟻群系統(tǒng)的二階欺騙效應(yīng)進(jìn)行了研究，Montgomery等在文獻(xiàn) [4，5]中首次對蟻群欺騙性問題進(jìn)行了綜合性的分類，Chen等在文獻(xiàn)[6]中研究了基于信息素反饋的搜索偏離現(xiàn)象，并定義了第三類欺騙問題存在的情形。為了解決蟻群算法的泛化求解能力問題，許多學(xué)者嘗試采用認(rèn)知相關(guān)的理論來提高蟻群算法對具體問題的自適應(yīng)性，如陳崚引入了知覺相關(guān)理論定義了螞蟻的顯意識和潛意識[7]，蕭蘊(yùn)詩等建立了一種能夠進(jìn)行最佳模式記憶用以指導(dǎo)進(jìn)化的蟻群算法[8]，蘇淼等通過增加一個額外的記憶庫，利用免疫記憶和克隆選擇提出了改進(jìn)蟻群算法[9]，蔡文彬等通過引入心理學(xué)中的差別感覺閾限概念與蟻群算法進(jìn)行了結(jié)合研究[10]，郭禾等在算法中結(jié)合了視覺系統(tǒng)模型和記憶模型[11]，Deng等通過引入統(tǒng)計的方法建立了兩種蟻群初始化學(xué)習(xí)結(jié)構(gòu)，提高了對問題的自適應(yīng)能力[12-13]。

本文為了得到一種通用的蟻群智能規(guī)劃器，討論了蟻群計算方法的特點和結(jié)構(gòu)，通過泛化蟻群搜索行為和信息素更新的概念，研究了一種基于動作－反饋控制的基本蟻群計算結(jié)構(gòu)，將信息素矩陣設(shè)計為具有群體控制功能的“腦”模型，結(jié)合問題解決過程中的映射轉(zhuǎn)換，構(gòu)建了一個具有較好泛化求解性能的通用規(guī)劃器架構(gòu)，該架構(gòu)有簡單通用的概念模型，抽象良好的接口體系。

1　蟻群算法的計算結(jié)構(gòu)

蟻群算法是一種基于顯式表達(dá)解空間的啟發(fā)式搜索方法，它將優(yōu)化問題的解分解成一系列的組成單元，并將這些組成單元映射成解構(gòu)造圖中的節(jié)點，從而用解構(gòu)造圖來描述優(yōu)化問題的解空間。螞蟻的求解過程就是在解構(gòu)造圖中根據(jù)子路徑上存儲的信息隨機(jī)游走，逐步地遍歷各個節(jié)點構(gòu)造優(yōu)化問題的一個完整解，然后釋放信息素以引導(dǎo)其他螞蟻的進(jìn)一步搜索。螞蟻是通過在解構(gòu)造圖上遍歷所有節(jié)點的順序不同，從而實現(xiàn)對解空間的搜索，進(jìn)而比較獲得的不同解決方案，使方案得到不斷的進(jìn)化[14]。

在所有的ACO應(yīng)用中，在解構(gòu)造圖上的搜索過程，都是在信息素規(guī)則的引導(dǎo)下進(jìn)行的，不同的ACO會具有不同的信息素控制結(jié)構(gòu)。但是，對于通過在構(gòu)造圖上的游走來進(jìn)行求解的過程來說，其表達(dá)的是一種計算結(jié)構(gòu)，它對所有ACO算法來說都是一樣的，它們都具有共同的特點，總結(jié)起來，包括如下幾點[15]：

（1）搜索空間是離散的；

（2）具有一組有限的約束條件；

（3）具有一個代價函數(shù)，為搜索算法生成的解計算代價；解的每一部分都會對解的代價產(chǎn)生影響；

（4）具有一個有限的節(jié)點集合，用于構(gòu)造解；

（5）具有一個有限的節(jié)點間的可能轉(zhuǎn)移的集合；

（6）具有一個節(jié)點序列的有限集合，用于表示所有的有效組合，來定義完整的搜索空間；組合的有效性、可行性由約束條件決定。

以上的特點其實就構(gòu)建了一個蟻群算法的基本運(yùn)算結(jié)構(gòu)，結(jié)構(gòu)的重要性是不言而喻的，它對算法的通用性和工程化具有重要作用，是算法能夠應(yīng)用到不同領(lǐng)域解決不同類型問題的保證。Dorigo在文獻(xiàn)[16]中將蟻群算法形式化為{S，f，Ω}，其中S表示一系列的解，f是一個目標(biāo)函數(shù)，該函數(shù)可以為每一個解計算出 （或指定）一個值，Ω是定義在可行域上的約束。蟻群優(yōu)化的目標(biāo)就是搜索一個解s*，使得：

f（s）≤f（s*），s∈S∩s*∈S（1）

此外，Birattari等也定義了一類蟻群算法的形式化框架[17]，稱作螞蟻規(guī)劃，該框架將蟻群優(yōu)化的特征形式化為T={fr，π，v，σ}，其中fr表示生成函數(shù)，用于建立優(yōu)化問題對應(yīng)的圖表示，π，v，σ是定義特定蟻群算法相應(yīng)行為的算子。螞蟻規(guī)劃用Gr表示fr生成的圖，用fτ表示Gr中邊的傾向性信息。其中算子π用于如何利用fτ的值來構(gòu)建解，而算子v，σ則表示如何根據(jù)已產(chǎn)生的解的質(zhì)量來修改fτ。螞蟻規(guī)劃可以用于一類特定的優(yōu)化問題，并要求這些優(yōu)化問題的形式可以轉(zhuǎn)化為最短路問題，并可以通過一個多階段的決策過程對其建模。

聞育[14]根據(jù)對解構(gòu)造塊的分解方式以及與解構(gòu)造圖節(jié)點之間的映射方式的不同，分別定義了簡單解構(gòu)造圖、基本層狀解構(gòu)造圖及復(fù)合層狀解構(gòu)造圖。其中，簡單解構(gòu)造圖直接將解的構(gòu)造塊映射為解構(gòu)造圖中的節(jié)點，而兩種層狀解構(gòu)造圖則從螞蟻在解構(gòu)造圖中生成候選解的多階段決策過程的角度出發(fā)，將解構(gòu)造塊分別映射為螞蟻在解構(gòu)造圖中搜索并生成問題解的各個階段的容許節(jié)點集合。

2　蟻群智能規(guī)劃器

2.1形式化框架

實際上在ACO中，蟻群算法獲得進(jìn)化解的過程分為了兩層：螞蟻活動層和蟻群控制層。在螞蟻活動層中，螞蟻從初始節(jié)點出發(fā)，通過重復(fù)在源節(jié)點處選擇下一個要到達(dá)的目標(biāo)節(jié)點的操作，搜索到一條可行路徑，該路徑對應(yīng)問題的一個可行解。螞蟻在每個節(jié)點處都要隨機(jī)選擇下一個要到達(dá)的節(jié)點，選擇過程中螞蟻不會顧及別的螞蟻的行為，它只會根據(jù)周圍信息素的大小來做這個決定，這可以看作是一個多階段的隨機(jī)決策過程；在蟻群控制層中，彷佛是一個蟻后在全局控制所有蟻群的運(yùn)行，其“指揮棒”就是信息素構(gòu)建的控制網(wǎng)，它通過評估完成路徑構(gòu)建的螞蟻們的路徑，來調(diào)節(jié)網(wǎng)絡(luò)控制器的各連線的信息素強(qiáng)度，以影響在不同節(jié)點做選擇的螞蟻。

在該兩層結(jié)構(gòu)中，對信息素釋放進(jìn)行了抽象，剝離為控制層的一種行為，可以認(rèn)為控制層在每條子路徑上放置了傳感器，能夠感知每次迭代中經(jīng)過該子路徑的螞蟻數(shù)。圖1對這種框架進(jìn)行了描述。

圖1　智能蟻群規(guī)劃器兩層結(jié)構(gòu)

兩層的ACO框架是一種工程化的框架，其可以形式化為T={fe，π，fk，φ}，其fe代表初始化函數(shù)，主要用于生成蟻群系統(tǒng)環(huán)境，π為動作算子，表示蟻群怎么通過該算子進(jìn)行移動，構(gòu)建解路徑，fk則代表了評估函數(shù)，主要對蟻群的移動進(jìn)行評估，根據(jù)一定的規(guī)則確定蟻群移動的價值，φ則為控制算子，主要表示將評估結(jié)果轉(zhuǎn)化為信息素，并將信息素釋放到環(huán)境中，影響后代蟻群的進(jìn)一步搜索和求解。

2.2規(guī)劃器組成結(jié)構(gòu)

通過上述的分析，得到的整個蟻群算法解決規(guī)劃問題的過程包括：編碼、移動與控制的循環(huán)、解碼三個部分，移動與控制的循環(huán)就是蟻群算法的求解過程，在循環(huán)體內(nèi)部又可分為移動和控制兩個部分。

在這個自動規(guī)劃結(jié)構(gòu)中，首先通過編碼和解碼完成問題到解構(gòu)造圖的映射或逆映射，再進(jìn)入蟻群算法求解的循環(huán)結(jié)構(gòu)中構(gòu)建規(guī)劃問題的解，得到了一個通用的智能蟻群規(guī)劃器，如圖2所示。

圖2　蟻群智能規(guī)劃器

規(guī)劃器組成主要包括了四個部分：編碼器、動作器、控制器和解碼器。編碼器主要是基于解構(gòu)造圖的映射方法，實現(xiàn)將各種待規(guī)劃問題映射為圖論問題的過程，以形成蟻群算法求解的基本結(jié)構(gòu)；動作器是蟻群搜索行為仿真部分，主要功能就是在圖上搜索構(gòu)建路徑，有圖上可見該部分有兩個輸入，一個是有編碼器得到的解構(gòu)造圖，一個是由控制器提供的輸入，該部分的唯一動作就是“移動”，因此非常適合于并行化操作，被設(shè)計成可以放在CPU上實現(xiàn)，也可以放在GPU上實現(xiàn)，也可以通過并行機(jī)實現(xiàn)；控制器主要為螞蟻的移動構(gòu)建啟發(fā)式環(huán)境，它的責(zé)任在于兩個方面，一是收集蟻群移動的信息，而是釋放信息素指導(dǎo)蟻群移動；解碼器是解構(gòu)造圖的逆過程，完成將由蟻群得到的基于解構(gòu)造圖的結(jié)論轉(zhuǎn)化為原來的領(lǐng)域問題，為用戶實現(xiàn)可理解的輸出。

2.3編碼器與解碼器

編碼器是對問題轉(zhuǎn)化過程的抽象，本文將主要針對圖論中的路徑規(guī)劃問題進(jìn)行設(shè)計，因此，在編碼過程中，最重要的兩點是建立抽象的點和點之間的連線。這里的點就是所求解問題的一個部分或者一個階段，或者是任何一個集合，點之間的連線就是集合中元素之間的關(guān)系，因此，對問題的編碼流程如下：

（1）分析領(lǐng)域問題和所求問題的解的形式

這個過程需要通過設(shè)計人員不斷提出問題，并把這種問題進(jìn)行分解，可以是動作序列的集合，也可以是階段性成果的集合，還可以是完成任務(wù)的部分的集合等等。

（2）分析集合中所有元素的關(guān)系

這主要也是業(yè)務(wù)領(lǐng)域的問題，按照各元素之間的不同關(guān)系構(gòu)建一個關(guān)系的集合，可以是動作之間的資源依賴或者順序關(guān)系，可以是行為之間的相繼關(guān)系，也可以是人員之間的合作關(guān)系等。

（3）以元素和元素的關(guān)系建立圖模型

以元素建立圖模型中的點，以元素之間的聯(lián)系構(gòu)建連接相關(guān)點之間的邊，就得到了一個完整的圖模型，圖模型的邊根據(jù)不同問題可以是有向或者是無向的，可以是加權(quán)的或者是不加權(quán)的，節(jié)點根據(jù)不同問題也可以是加權(quán)或不加權(quán)的，該模型就是下一步蟻群移動的環(huán)境。

解碼器是編碼器的逆映射，根據(jù)編碼過程采用的方法再映射回去就行。

2.4動作器與控制器

動作器和控制器是對群智能算法的抽象，可以理解為智能群體的行為器官和意識器官，智能群體就是一個智能聚集體，聚集體的行為器官不斷的對解結(jié)構(gòu)圖上的節(jié)點進(jìn)行組合，聚集體的意識器官通過分析不同組合的優(yōu)越性指導(dǎo)行為器官的動作。聚集體通過不斷地得到不同的解路徑，并充分利用組成解路徑的各階段之間的相關(guān)性，不斷地更新解路徑達(dá)到更優(yōu)。

動作器實現(xiàn)了以下幾部分功能：

（1）動作實體的初始化

動作實體就是智能群體的基本組成部分，所有的求解過程是以動作實體的行為為基礎(chǔ)產(chǎn)生的，動作實體的每一步動作就得到了解的一個部分，因此，雖然相對于群體變現(xiàn)出的高級智能這種動作是簡單的，但是確實高級智能行為得以涌現(xiàn)的本質(zhì)。在智能蟻群中，蟻群的初始化包括初始化一定數(shù)量的螞蟻，并根據(jù)問題要求將它們放置在一個節(jié)點上或任意的多個節(jié)點上。

（2）動作規(guī)則選擇

動作規(guī)則是智能個體一系列行為需要遵循的約束。在智能蟻群規(guī)劃器中，可能包括螞蟻選擇下一個移動點，螞蟻移動的禁忌規(guī)則，或者是對螞蟻是否移動的一些附加條件。

控制器是綜合了智能個體的評估，以及基于評估的一種控制規(guī)則的集合體。控制器的抽象是將智能群體作為一個整體考慮，分別對進(jìn)行動作的實體和進(jìn)行思維的對象進(jìn)行分離的結(jié)果。經(jīng)過抽象之后，動作器只進(jìn)行簡單的移動或選擇動作，不對動作產(chǎn)生的效果或者得出的結(jié)論負(fù)責(zé)；控制器則需要對智能個體的結(jié)果進(jìn)行分析評估，以賦予群體智能的某種認(rèn)知方式對需要解決的問題產(chǎn)生一個階段性的總結(jié)，并采用一種直接或間接的方式生成一種控制結(jié)構(gòu)，指導(dǎo)動作器進(jìn)行下一步的動作。

在智能蟻群規(guī)劃器中，其控制器完成的功能包括：

（1）評估螞蟻移動構(gòu)建的解的優(yōu)劣

螞蟻不斷移動，當(dāng)根據(jù)移動規(guī)則螞蟻走完全程或者是中途退出后，形成的解需要進(jìn)行評估，評估函數(shù)根據(jù)實際所解決的問題有所不同，即使中途死亡的螞蟻得到的部分解也可能需要進(jìn)行評估。評估之后可能形成一個排序的螞蟻序列，也可能按照不同的適應(yīng)度建立相應(yīng)的結(jié)果。

（2）選擇信息素釋放規(guī)則

信息素軌跡或者斑跡可能是網(wǎng)狀的，也可能是離散的點集。但是，信息素的作用是形成一層可以控制螞蟻移動的信息層，它不與螞蟻相關(guān)，而是直接與問題的部分解相關(guān)，是在思維器官經(jīng)過對不同的解的評價之后得到的一個整體認(rèn)知。

3　計算實驗與分析

為了驗證通用蟻群智能規(guī)劃器設(shè)計，選取魯中南地區(qū)的地圖（如圖3a），建立路網(wǎng)模型，采用本文規(guī)劃器求取從淄博市通過陸路至膠南市的最優(yōu)路徑，通過路網(wǎng)數(shù)據(jù)可知：該范圍主要由青銀高速、沈海高速等高速公路和 G15、G20、G2011、G22、G205、G1511、G2、G206等國道構(gòu)成，路況較好，路線較為明晰，通過建立關(guān)鍵點的經(jīng)緯度坐標(biāo)，對現(xiàn)有路網(wǎng)進(jìn)行近似，建立了測試路網(wǎng)數(shù)據(jù)庫。

選取典型的蟻群參數(shù)設(shè)置：α=2，β=3，ρ=0.8，Q=50，最大循環(huán)次數(shù)MaxCount=100，初始信息素c=1000。得到的結(jié)果如下（如圖3b）。

圖3　魯中南地區(qū)地圖及測試結(jié)果

為了檢驗實驗結(jié)果，下圖采用百度地圖和Google地圖進(jìn)行了同樣環(huán)境下的從淄博市至膠南市的路徑規(guī)劃，結(jié)果如下。

由于我們在模型建立時簡化了路網(wǎng)，所以求得的最優(yōu)路徑并不是絕對意義上的最優(yōu)路徑，例如從淄博到濰坊的路徑其實是包含青銀高速公路和國道兩條并行的道路，二者的里程不可能絕對相等，只能做到近似最優(yōu)，但是這對于檢驗規(guī)劃器的合理性不會產(chǎn)生影響，從這個角度可以認(rèn)為本文的通用蟻群規(guī)劃器是可行的。

4　結(jié)語

本文通過泛化蟻群算法的尋優(yōu)過程，建立了一種通用蟻群算法的概念模型體系，并以此對蟻群求解問題的過程進(jìn)行了分級抽象，設(shè)計了一種通用的規(guī)劃器結(jié)構(gòu)，并通過實際的路網(wǎng)最短路徑規(guī)劃問題檢驗了其合理性。未來將結(jié)合NP-hard問題的困難性，開展對框架自適應(yīng)的研究，進(jìn)一步提高通用蟻群框架的泛化求解能力。

圖4　網(wǎng)絡(luò)成熟平臺實驗結(jié)果

[1]Wolpert D H，Macready W G.No Free Lunch Theorems for Optimization[J].IEEE Transactions on Evolutionary Computation，1997，1 （1）:67-82.

[2]Blum C，Dorigo M.Deception in Ant Colony Optimization[M].Ant Colony Optimization and Swarm Intelligence.Springer Berlin Heidelberg，2004:118-129.

[3]Blum C，Dorigo M.Search Bias in Ant Colony Optimization:On the role of Competition-Balanced Systems[J].IEEE Transactions on Evolutionary Computation，2005，9（2）:159-174.

[4]Montgomery J，Randall M，Hendtlass T.Solution Bias in Ant Colony Optimization:Lessons for Selecting Pheromone Models[J].Computers&Operations Research，2008，35（9）:2728-2749.

[5]Montgomery J，Randall M，Hendtlass T.Structural Advantages for Ant Colony Optimization Inherent in Permutation Scheduling Problems[M].Innovations in Applied Artificial Intelligence.Springer Berlin Heidelberg，2005:218-228.

[6]Chen B，Chen L.A Method for Avoiding the Feedback Searching Bias in Ant Colony Optimization[M].Advances in Swarm Intelligence.Springer Berlin Heidelberg，2012:206-216.

[7]陳崚，秦玲，陳宏建，等.具有感覺和知覺特征的蟻群算法[J].系統(tǒng)仿真學(xué)報，2003，15（10）:1418-1425.

[8]蕭蘊(yùn)詩，李炳宇，吳啟迪.求解TSP問題的模式學(xué)習(xí)并行蟻群算法[J].控制與決策，2004，19（8）:885-888.

[9]蘇淼，錢海，王煦法.基于免疫記憶的蟻群算法的WTA問題求解[J].計算機(jī)工程，2008，34（4）:215-217.

[10]蔡文彬，朱慶保.具有感覺適應(yīng)功能蟻群算法的機(jī)器人路徑規(guī)劃[J].計算機(jī)工程與應(yīng)用，2010，46（31）:215-218.

[11]郭禾，程童，陳鑫，等.一種使用視覺反饋與行為記憶的蟻群優(yōu)化算法[J].軟件學(xué)報，2011，22（9）:1994-2005.

[12]Deng X，Zhang L，Luo L.An Improved Ant Colony Optimization Applied in Robot Path Planning Problem[J].Journal of Computers，2013，8（3）:585-593.

[13]Deng X，Zhang L，Lin H，et al.Pheromone Mark Ant Colony Optimization with a Hybrid Node-Based Pheromone Update Strategy[J]. Neurocomputing，2015，148:46-53.

[14]聞育.復(fù)雜多階段動態(tài)決策的蟻群優(yōu)化方法及其在交通系統(tǒng)控制中的應(yīng)用[D].浙江大學(xué)，2004.

[15]Andries P.Engelbrecht著.譚營等譯.計算群體智能基礎(chǔ)[M].北京，清華大學(xué)出版社，2009.

[16]Marco Dorigo，Thomas Stützle.Ant Colony Optimization[M].MIT Press，2004.

[17]Birattari M，DiCaro G，Dorigo M.Toward the Formal Foundation of Ant Programming.Lecture Notes in Computer Science，Berlin Springer-Verlag，2002，2463:188-201.

Ant Colony Optimization（ACO）;Generalized;Planning Program;Swarm Intelligence

Design and Implementation of a Generalized ACO-Based Planning Program Framework

DENG Xiang-yang1，SHEN Jian2，F(xiàn)ANG Wei1，F(xiàn)ANG Jun1
（1.Institute of Information Fusion，Naval Aeronautical and Astronautical University，Yantai264001；2.Ordance Support Dept.of NED，Beijing 100841）

鄧向陽（1981-），男，湖南桃江人，講師，博士，研究方向為認(rèn)知與智能計算、復(fù)雜系統(tǒng)仿真

沈劍（1981-），男，湖南湘鄉(xiāng)人，講師，碩士，研究方向為裝備保障與優(yōu)化

方偉（1977-），男，安徽人，博士，副教授，研究方向為系統(tǒng)仿真

方君（1979-），男，安徽人，博士，講師，研究方向為智能兵力生成

2015-12-15

2016-01-02

蟻群算法已經(jīng)成為解決各種困難問題的常用方法，在很多工程化系統(tǒng)中得到成功應(yīng)用，但是其對具體問題的依賴性強(qiáng)、泛化求解能力弱等特點嚴(yán)重制約其工程化推廣。分析幾種常用的蟻群算法計算架構(gòu)，通過對蟻群尋優(yōu)過程的分段概念化抽象，建立編碼、求解和解碼的三段式結(jié)構(gòu)，從群體認(rèn)知的角度，通過信息素更新機(jī)制建立蟻群集中控制模型，實現(xiàn)一種通用的智能蟻群規(guī)劃器架構(gòu)，并通過實例分析，驗證其有效性。

蟻群算法；泛化；規(guī)劃器；群智能

Ant colony optimization(ACO)has become an effective solution to a series of NP-hard problems,and has been widely applied in various engineering systems,but its generalized capability is so far an unsolved problem for the dependence on the type of problem.Based on the analysis of three common computational frameworks of ACO,gives an abstraction of ants’foraging behaviors modeled as three processes of coding,solving and decoding.Considering the solving process,discusses a centralized controlling model with a pheromone updating strategy,and presents a type of general ACO planning program framework.Tests and verifies its effectiveness by a roads network planning problem.