基于質點模型的多智能體遺傳算法

張鑫+許峰

摘要：針對傳統遺傳算法優化高維函數效率不高的問題，借鑒質點間相互作用機制，提出了一種基于質點模型的多智能體遺傳算法。基本思想是：定義質點的質量表示智能體的歷史活動信息及具有的能量，通過質點間引力作用的特點，不斷提高智能體的自學習能力和自身的能量。該算法具有較高的優化效率，特別適合高維函數的優化。

關鍵詞：遺傳算法；多智能體；質點模型；算法效率

DOIDOI：10.11907/rjdk.172216

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2018）001008104

Abstract：A multi agent genetic algorithm based on particle model is proposed for the traditional genetic algorithm， which is prone to search efficiency is not high and precocious. The quality of the defined particle represents the historical activity information of the agent and its energy. Through the interaction between the particles， the selflearning ability and the energy of the agent are improved. The algorithm has higher optimization efficiency and is especially suitable for the optimization of highdimensional functions.

Key Words：genetic algorithm； multiagent； particle model； algorithm efficiency

0引言

遺傳算法是經過模擬生物在自然界的進化而產生的一種優化算法，應用廣泛。但傳統遺傳算法在優化高維甚至超高維函數時，效率不高，從而使其實用性大打折扣。基于智能體（Agent）的優化方法已廣泛應用于計算科學的各個領域，它們通過推理、學習、協作和協商能力感知環境并做出反應，可對復雜問題有效求解。多智能體系統的分布式并行布局有利于防止遺傳算法早熟，而智能體自身的鄰域結構有利于提高種群的局部搜索能力，由此產生了很多改進的遺傳算法[1]。鐘偉才[24]等將智能體與遺傳算法相結合，提出了多智能體進化算法，提升了算法的求解精度，但是消耗了大量時間；文獻[5]提出的協同進化遺傳算法收斂速度快，但它破壞了變量之間的相關性，導致搜索解的質量差；文獻[6]把智能體的動態鏈式網絡布局加入到遺傳算法中，削減了次優個體過早獲得“頂端優勢”，防止早熟，可以保持種群多樣性；文獻[7]把均勻設計方法加入到智能遺傳算法中，在某些方面避免了局部最優；文獻[8]將差分進化算子結合到多智能體遺傳算法上，提升了智能體的換代速度；文獻[9]提出了交互式多智能遺傳算法，增強了算法的全局收斂能力和局部搜索能力；文獻[10]把多種群的概念加入到遺傳算法中，考慮了種群數量對收斂速率的影響；文獻[11]創建了包括“智能體、環境、交互式規則”3個重要概念的AER模型，有效解決了多達7 000個皇后的問題和一些大規模著色問題；文獻[12]把均勻設計的思路、多智能體系統以及遺傳算法相結合，提出了高維多峰函數算法，擁有很好的全局搜索能力和較快的收斂速率。上述各種改進算法都在某些方面提高了算法的尋優能力和收斂速度。

為了提高遺傳算法高維優化的效率，本文將“理想化模型——質點”的思想引入到多智能體遺傳算法中，提出了一種基于質點模型的多智能體遺傳算法。算法采用多智能體相互作用的演化結構，各智能體分別與其它智能體

產生引力作用，通過矢量合成得到各智能體合力，相互進行比較、競爭、合作及自學習，實現自身能量的增加，向著群體最優的方向移動，各智能體定期通過引力作用操作進行信息交互。

1質點模型的多智能體遺傳算法

1.1質點模型

任何物體都具有尺寸、形狀、質量和空間特性，這些屬性混合在一起就很難確定物體的位置和研究對象的運動。假設物體是在一個很大的空間內，自身的體積遠遠小于空間范圍，則確定物體在空間的位置時，其自身因素對結果影響很小，這時就可以忽略物體的尺寸和形狀等特性，用一個具有質量的點去代替實際物體，在物理學中稱為質點。質點是科學概括的產物，是一個理想化模型，事實上不存在。質點并不是憑空想象出來的，它與實際物體有著密切關系，這種關系表現在：質點是以實際物體為基礎建立起來的，對質點的描述和探究的結果能夠代替實際結果。

1.2智能體

1.2.1智能體定義

將環境中的每個個體看作一個智能體，它具有自身的特征，可以了解周圍環境，也可以作用和改善環境。Agent具有3種基本狀態：信念、期望和意圖，分別代表知識、水平和目標。Agent具有強大的智能特征，以固定的方式響應環境的要求和變化，并且能根據自身狀態和學習的環境信息主動決定和控制狀態以及行為。Agent在了解環境并作出反應的同時，展示出應變行為，采取積極行動實現目標。

1.2.2智能體能量

一個智能體相當于質點模型多智能體遺傳算法中的一個質點，表示待優化函數的一個可能解。用質點的質量表示智能體的能量，能量越大，引力越強；反之，則弱。當引力較大時，自身的能量會不斷增加，而引力較小者將被淘汰。在求整體最優結果問題中，它的能量等于目標函數的結果。智能體的目的就是在滿足運行條件的情況下盡量增加其能量。endprint

1.2.3多智能體系統

與現實中的群體相同，Agent經常不是獨立存在的，在環境中會有許多Agent生存，構成一個大的群體。Agent不僅可以自主運行，還能和其它Agent相互協作，并能在遇到矛盾時通過協商消解沖突，隨著環境的不斷變化充實自身的學問和能力，提升整個系統的智能化和可靠性。這些Agent相互協作，達到共同的目標，這種系統叫作多智能體系統。就像人類合作的能力要遠大于個體一樣，MAS比單個Agent有更高的智能性和更強的解決問題能力。

多智能體模型主要針對系統內共同目標的實現，為多個智能體制定共同的規劃。每個Agent都有自己的求解目標，并且每個Agent都考慮其它Agent的行為和約束，并進行獨立規劃，稱為局部規劃。各個Agent以通信的方式進行協調，實現所有Agent都接受的全局規劃。

1.2.4智能體區域

簡單MAS的生存環境由一個網格組成，群體內共有N×M個Agent，稱為簡單智能體網格，記為A。每個Agent固定在一個位置上，第p行第q列的Agent表示為Ap，q， p=1，2，…，N；q=1，2，…，M；則智能體Ap，q的鄰域為Neighborsp，q={Ap1，q， Ap2，q，Ap，q1， Ap，q2}，p=1，2，…，N； q=1，2，…，M；分別是與Agent直接相連的上下左右的Agent，其中每個Agent只能與相鄰的Agent發生相互作用，無法與遠端以及其他區域的智能體發生相互作用，智能體網格表示成圖1的形式。每個圓圈為一個智能體，圓圈中的數字代表智能體在網格中的位置，相連的Agent可以直接發生相互作用。

1.3智能體的行為算子

1.3.1競爭算子

首先，找出智能體Ap，q=（a1，a2，…，an）的鄰域內能量最大的智能體Amaxp，q=（m1，m2，…，mn），如果Ap，q的能量大于Amaxp，q的能量，則繼續保留在網格上；否則，將被Amaxp，q替代，體現了智能體之間的競爭。

1.3.2合作算子

除了競爭，Agent之間還有合作關系。合作算子將利用彼此的信息去實現不同的Agent合作。算術交叉是一種常用方法，其優點是收斂速度快、性能穩定，但是只采用該算子時，產生的個體數值特性比較接近，對優化不利，會在該區域內過早收斂。因此，以增大選擇空間、加快進化速度為目的，采用混合交叉的方法得到新的Agent。

1.3.3變異算子

保留在網格上的智能體以概率P1進行變異，Agent利用自身知識獲得能量增加。以概率P1選取要進行變異的Agent a=（a1，a2，…，al，am，an，…，ak），隨機選擇其中的兩個分量al和an進行變異，變異產生新的Agent a′=（a1，a2，…，a′l，am，a′n，…，ak）。

1.3.4自學習算子

Agent不僅可以在局部環境與其它Agent進行競爭與合作，還能夠通過自身所擁有的知識進行自學習。生存在網格上的Agent以概率P2進行自學習操作，進一步提高求解問題的能力，使算法逐漸收斂。

1.4算法原理與步驟

1.4.1算法原理

多Agent系統模型應當將系統內的個體和環境作為一個整體來描述，包含多個智能體的系統用關系型網絡結構描述，如圖2所示。在圖中，有n個智能體，每個智能體都可以接受環境的任務輸入。任意兩個Agent之間連線上的字母rij代表它們之間的萬有引力。針對不同系統中Agent之間關系的復雜程度，在關系型網絡結構模型中，可以通過調整距離的大小對系統模型進行精確描述。

圖2多智能體關系結構

在實際應用中，有時無法精確描述Agent的關系，于是引入萬有引力概念，提出一種更實用的質點模型。各智能體之間引力的大小F=GMmR2，表示Agent之間的對立和合作關系以及相互影響程度的大小。其中G表示萬有引力常量，M、m表示兩個智能體的能量，R表示兩個智能體之間的距離。鄰域內任何兩個智能體可以計算出它們之間引力的大小。通過比較引力大小，保留優秀個體。

在質點模型多智能體遺傳算法中，每個Agent就是一個質點，Agent的數量就是算法的群體規模。每個質點的鄰域就是每個Agent的鄰域，智能體網格中能量最大的Agent就是群體中的最優個體。在算法中，通過競爭算子和合作算子以及變異算子，分別實現Agent的競爭、合作、更新行為，通過自學習算子實現智能體利用自身知識。結合質點模型，與全局最優的Agent進行信息同享，并根據自身經驗來修正Agent的行動策略，使其可以更快、更精確地收斂到全局最優解。每個Agent利用固有的特征以及與鄰域內其它Agent的相互作用，再通過質點之間的引力算法的更新機制完成種群更替，實現每一代的進化。

1.4.2算法步驟

①設置算法參數，構造智能體環境；②初始化各質點位置，并計算每個質點的能量，找出全局最優智能體Ag；③對每個質點執行鄰域競爭算子；④對每個質點執行任意合作算子；⑤每個質點通過變異算子更新自己的狀態，并更新全局最優智能體Ag的狀態；⑥對全局最優質點執行自學習算子；⑦檢查終止條件，若條件成立，輸出最優解，算法終止；否則轉第③步。

2.2數值實驗結果

算法計算量主要體現在函數評價次數上。表1給出了優化10 000維函數時，AEA和MAGA評價次數和O（nα）的逼近結果。考慮到運算的隨機性，給出的是20次運算的平均結果。

為了直觀、形象地顯示函數維數對AEA和MAGA

的影響，圖3給出了這兩種方法的平均函數評價次數隨n的變化，及用函數O（nα）逼近評價次數的結果。

從表1及圖3中的O（nα）逼近結果來看，10個測試函數中有9個AEA的復雜度都劣于O（n），僅有f3的復雜endprint

度為O（n0.79）。而對于MAGA，除f2外均優于O（n）。在MAGA的逼近結果中，較差的是f1和f6，分別為O（n0.78）和O（n0.79），f3和f7～f10的復雜度僅為O（n0.1）左右。由此可見，基于質點模型的多智能體遺傳算法具有極低的復雜度，特別適宜于高維甚至超高維函數的優化。

3結語

本文將質點模型與多智能體遺傳算法相結合，提出了一種基于質點模型的多智能體遺傳算法。該算法將智能體的競爭、合作、變異以及自學習行為與質點間的引力關系相結合，提高了環境適應力。數值實驗表明，與其它改進的遺傳算法相比，該算法在進行高維函數優化時具有突出的搜索效率，特別適用于高維或超高維函數的優化。

參考文獻：

[1]SRINIVAS M， PATNAIK L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems， Man and Cybernetics，1994，24（4）：656667.

[2]鐘偉才，薛明志，劉靜.多智能體遺傳算法用于超高維函數優化[J].自然科學進展，2003，13（10）：10781083.

[3]ZHONG W C， LIU J， XUE M Z， et al. A multiagent genetic algorithm for global numerical optimization[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics，2004，34（2）：11281141.

[4]LIU J， ZHONG W C， JIAO L C. A multiagent evolutionary algorithm for constraint satisfaction problems[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics，2006，36（1）：11281141.

[5]孫曉燕，鞏敦衛.變種群規模合作型協同進化遺傳算法及其在優化中的應用[J].控制與決策，2004，19（12）：14371440.

[6]ZENG X P， LI Y M， JIAN Q. A dynamic chainlike agent genetic algorithm for global numerical optimization and feature selection [J].Neurocomputing，2009，72（46）：12141228.

[7]梁昌勇，陸青，張恩橋.基于均勻設計的多智能體遺傳算法研究[J].系統工程學報，2009，24（1）：109113.

[8]何大闊，高廣宇，王福利.多智能體差分進化算法[J].控制與決策，2011，26（7）：962972.

[9]黃永青，陸青，梁昌勇.交互式多智能體進化算法及其應用[J].系統仿真學報，2006，18（7）：20302055.

[10]姚志紅，趙國文.多種群變換遺傳算法及其在優化調度中的應用[J].控制理論與應用，2001，18（7）： 882886.

[11]韓靖，蔡慶生.AER模型中的智能涌現[J].模式識別與人工智能，2002，15（2）：134142.

[12]梁昌勇，陸青，張恩橋.基于均勻設計的多智能體遺傳算法研究[J].系統工程學報，2009，24（1）：109 113.

[13]焦李成，劉靜，鐘偉才.協同進化計算與多智能體系統[M].北京：科學出版社，2006.

[14]PAN Z， KANG L S. An adaptive evolutionary algorithm for numerical optimization[J]. In： Simulated Evolution and Learning， Lecture Notes in Artificial Intelligence. Heidelberg： SpringerVerlag，1997（1285）：2734.

（責任編輯：杜能鋼）endprint