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

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

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

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

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

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

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

0　引言

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

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

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

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

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

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

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

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

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

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

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

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

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

此外，Birattari等也定義了一類蟻群算法的形式化框架[17]，稱作螞蟻規(guī)劃，該框架將蟻群優(yōu)化的特征形式化為T={fr，π，v，σ}，其中fr表示生成函數(shù)，用于建立優(yōu)化問題對(duì)應(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)化為最短路問題，并可以通過一個(gè)多階段的決策過程對(duì)其建模。

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

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

2.1形式化框架

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

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

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

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

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

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

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

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

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

2.3編碼器與解碼器

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

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

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

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

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

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

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

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

2.4動(dòng)作器與控制器

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

動(dòng)作器實(shí)現(xiàn)了以下幾部分功能：

（1）動(dòng)作實(shí)體的初始化

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

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

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

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

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

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

螞蟻不斷移動(dòng)，當(dāng)根據(jù)移動(dòng)規(guī)則螞蟻?zhàn)咄耆袒蛘呤侵型就顺龊螅纬傻慕庑枰M(jìn)行評(píng)估，評(píng)估函數(shù)根據(jù)實(shí)際所解決的問題有所不同，即使中途死亡的螞蟻得到的部分解也可能需要進(jìn)行評(píng)估。評(píng)估之后可能形成一個(gè)排序的螞蟻序列，也可能按照不同的適應(yīng)度建立相應(yīng)的結(jié)果。

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

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

3　計(jì)算實(shí)驗(yàn)與分析

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

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

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

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

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

4　結(jié)語

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

圖4　網(wǎng)絡(luò)成熟平臺(tái)實(shí)驗(yàn)結(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é)報(bào)，2003，15（10）:1418-1425.

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

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

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

[11]郭禾，程童，陳鑫，等.一種使用視覺反饋與行為記憶的蟻群優(yōu)化算法[J].軟件學(xué)報(bào)，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]聞?dòng)?復(fù)雜多階段動(dòng)態(tài)決策的蟻群優(yōu)化方法及其在交通系統(tǒng)控制中的應(yīng)用[D].浙江大學(xué)，2004.

[15]Andries P.Engelbrecht著.譚營等譯.計(jì)算群體智能基礎(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-），男，湖南桃江人，講師，博士，研究方向?yàn)檎J(rèn)知與智能計(jì)算、復(fù)雜系統(tǒng)仿真

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

方偉（1977-），男，安徽人，博士，副教授，研究方向?yàn)橄到y(tǒng)仿真

方君（1979-），男，安徽人，博士，講師，研究方向?yàn)橹悄鼙ι?/p>

2015-12-15

2016-01-02

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

蟻群算法；泛化；規(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.