一種通用蟻群智能規劃器架構設計與實現

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

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

一種通用蟻群智能規劃器架構設計與實現

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

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

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

0　引言

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

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

1　蟻群算法的計算結構

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

在所有的ACO應用中，在解構造圖上的搜索過程，都是在信息素規則的引導下進行的，不同的ACO會具有不同的信息素控制結構。但是，對于通過在構造圖上的游走來進行求解的過程來說，其表達的是一種計算結構，它對所有ACO算法來說都是一樣的，它們都具有共同的特點，總結起來，包括如下幾點[15]：

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

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

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

（4）具有一個有限的節點集合，用于構造解；

（5）具有一個有限的節點間的可能轉移的集合；

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

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

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

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

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

2　蟻群智能規劃器

2.1形式化框架

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

在該兩層結構中，對信息素釋放進行了抽象，剝離為控制層的一種行為，可以認為控制層在每條子路徑上放置了傳感器，能夠感知每次迭代中經過該子路徑的螞蟻數。圖1對這種框架進行了描述。

圖1　智能蟻群規劃器兩層結構

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

2.2規劃器組成結構

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

在這個自動規劃結構中，首先通過編碼和解碼完成問題到解構造圖的映射或逆映射，再進入蟻群算法求解的循環結構中構建規劃問題的解，得到了一個通用的智能蟻群規劃器，如圖2所示。

圖2　蟻群智能規劃器

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

2.3編碼器與解碼器

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

（1）分析領域問題和所求問題的解的形式

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

（2）分析集合中所有元素的關系

這主要也是業務領域的問題，按照各元素之間的不同關系構建一個關系的集合，可以是動作之間的資源依賴或者順序關系，可以是行為之間的相繼關系，也可以是人員之間的合作關系等。

（3）以元素和元素的關系建立圖模型

以元素建立圖模型中的點，以元素之間的聯系構建連接相關點之間的邊，就得到了一個完整的圖模型，圖模型的邊根據不同問題可以是有向或者是無向的，可以是加權的或者是不加權的，節點根據不同問題也可以是加權或不加權的，該模型就是下一步蟻群移動的環境。

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

2.4動作器與控制器

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

動作器實現了以下幾部分功能：

（1）動作實體的初始化

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

（2）動作規則選擇

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

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

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

（1）評估螞蟻移動構建的解的優劣

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

（2）選擇信息素釋放規則

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

3　計算實驗與分析

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

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

圖3　魯中南地區地圖及測試結果

為了檢驗實驗結果，下圖采用百度地圖和Google地圖進行了同樣環境下的從淄博市至膠南市的路徑規劃，結果如下。

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

4　結語

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

圖4　網絡成熟平臺實驗結果

[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].系統仿真學報，2003，15（10）:1418-1425.

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

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

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

[11]郭禾，程童，陳鑫，等.一種使用視覺反饋與行為記憶的蟻群優化算法[J].軟件學報，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].浙江大學，2004.

[15]Andries P.Engelbrecht著.譚營等譯.計算群體智能基礎[M].北京，清華大學出版社，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，FANG Wei1，FANG Jun1
（1.Institute of Information Fusion，Naval Aeronautical and Astronautical University，Yantai264001；2.Ordance Support Dept.of NED，Beijing 100841）

鄧向陽（1981-），男，湖南桃江人，講師，博士，研究方向為認知與智能計算、復雜系統仿真

沈劍（1981-），男，湖南湘鄉人，講師，碩士，研究方向為裝備保障與優化

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

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

2015-12-15

2016-01-02

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

蟻群算法；泛化；規劃器；群智能

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.