基于質(zhì)點(diǎn)模型的多智能體遺傳算法

張?chǎng)?許峰

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

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

DOIDOI：10.11907/rjdk.172216

中圖分類號(hào)：TP312

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

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

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

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

1.1質(zhì)點(diǎn)模型

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

1.2智能體

1.2.1智能體定義

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

1.2.2智能體能量

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

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

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

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

1.2.4智能體區(qū)域

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

1.3智能體的行為算子

1.3.1競(jìng)爭(zhēng)算子

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

1.3.2合作算子

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

1.3.3變異算子

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

1.3.4自學(xué)習(xí)算子

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

1.4算法原理與步驟

1.4.1算法原理

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

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

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

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

1.4.2算法步驟

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

2.2數(shù)值實(shí)驗(yàn)結(jié)果

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

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

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

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

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

3結(jié)語

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

參考文獻(xiàn)：

[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].自然科學(xué)進(jìn)展，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é)同進(jìn)化遺傳算法及其在優(yōu)化中的應(yīng)用[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]梁昌勇，陸青，張恩橋.基于均勻設(shè)計(jì)的多智能體遺傳算法研究[J].系統(tǒng)工程學(xué)報(bào)，2009，24（1）：109113.

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

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

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

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

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

[13]焦李成，劉靜，鐘偉才.協(xié)同進(jìn)化計(jì)算與多智能體系統(tǒng)[M].北京：科學(xué)出版社，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.

（責(zé)任編輯：杜能鋼）endprint