張鑫+許峰

摘要：針對傳統(tǒng)遺傳算法優(yōu)化高維函數(shù)效率不高的問題，借鑒質(zhì)點間相互作用機制，提出了一種基于質(zhì)點模型的多智能體遺傳算法?；舅枷胧牵憾x質(zhì)點的質(zhì)量表示智能體的歷史活動信息及具有的能量，通過質(zhì)點間引力作用的特點，不斷提高智能體的自學習能力和自身的能量。該算法具有較高的優(yōu)化效率，特別適合高維函數(shù)的優(yōu)化。

關(guān)鍵詞：遺傳算法；多智能體；質(zhì)點模型；算法效率

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引言

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

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

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

1質(zhì)點模型的多智能體遺傳算法

1.1質(zhì)點模型

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

1.2智能體

1.2.1智能體定義

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

1.2.2智能體能量

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

1.2.3多智能體系統(tǒng)

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

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

1.2.4智能體區(qū)域

簡單MAS的生存環(huán)境由一個網(wǎng)格組成，群體內(nèi)共有N×M個Agent，稱為簡單智能體網(wǎng)格，記為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發(fā)生相互作用，無法與遠端以及其他區(qū)域的智能體發(fā)生相互作用，智能體網(wǎng)格表示成圖1的形式。每個圓圈為一個智能體，圓圈中的數(shù)字代表智能體在網(wǎng)格中的位置，相連的Agent可以直接發(fā)生相互作用。

1.3智能體的行為算子

1.3.1競爭算子

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

1.3.2合作算子

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

1.3.3變異算子

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

1.3.4自學習算子

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

1.4算法原理與步驟

1.4.1算法原理

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

圖2多智能體關(guān)系結(jié)構(gòu)

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

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

1.4.2算法步驟

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

2.2數(shù)值實驗結(jié)果

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

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

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

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

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

3結(jié)語

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

參考文獻：

[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]鐘偉才，薛明志，劉靜.多智能體遺傳算法用于超高維函數(shù)優(yōu)化[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]孫曉燕，鞏敦衛(wèi).變種群規(guī)模合作型協(xié)同進化遺傳算法及其在優(yōu)化中的應用[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].系統(tǒng)工程學報，2009，24（1）：109113.

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

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

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

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

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

[13]焦李成，劉靜，鐘偉才.協(xié)同進化計算與多智能體系統(tǒng)[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