基于細(xì)菌覓食和免疫粒子群算法的Nash均衡求解

劉露萍 賈文生

摘要 免疫粒子群算法在優(yōu)化過程中通過免疫記憶性能和抗體濃度抑制機(jī)制來促進(jìn)種群的多樣性、但并不能實(shí)現(xiàn)每個粒子可以找到其所在鄰域內(nèi)的最優(yōu)位置，易陷入局部極值。針對免疫粒子群算法的缺陷，本文引入細(xì)菌覓食算法中趨向性運(yùn)動算子的思想來完成局部搜索功能，并據(jù)此提出了基于細(xì)菌覓食算法和免疫粒子群算法的BFA-IPSO混合算法。該算法既利用免疫粒子群算法的種群多樣性，又借助細(xì)菌覓食算中的趨化算子增強(qiáng)快速局部尋優(yōu)能力，很好將兩者優(yōu)勢混合。通過對N人有限非合作博弈Nash均衡數(shù)值算例求解的實(shí)驗(yàn)結(jié)果表明，BFA-IPSO混合算法很大程度上克服了粒子早熟現(xiàn)象，改進(jìn)了全局搜索能力和收斂速度。

【關(guān)鍵詞】免疫粒子群算法 細(xì)菌覓食算法 趨化算子 Nash均衡

群智能優(yōu)化算法主要通過模擬自然界中生物系統(tǒng)的行為，借助生物種群本能的尋優(yōu)行為來優(yōu)化其生存狀態(tài)以更好的適應(yīng)環(huán)境。20世紀(jì)70年代學(xué)者們受到達(dá)爾文自然選擇學(xué)說和孟德爾的遺傳變異理論啟發(fā)提出了遺傳算法。隨后，相繼出現(xiàn)了很多諸如蟻群算法、人工魚群算法、粒子群優(yōu)化算法、蜂群優(yōu)化算法、猴群算法等群智能算法。遺傳算法主要思想是模擬“優(yōu)勝劣汰”的基因自然選擇法則。蟻群算法主要利用蟻群覓食中“信息共享”機(jī)制確定決策點(diǎn)。魚群算法主要模擬魚群趨向食物濃度最高處聚集的行為。粒子群算法主要模擬鳥群覓食的群體信息交換行為。蜂群算法從蜂擁舞蹈中傳遞交換信息收到啟發(fā)等智能算法。2002年，Passion受大腸桿菌覓食行為啟發(fā)提出了細(xì)菌覓食優(yōu)化算法。Mori K等提出了基于免疫思想的免疫算法。隨后劉小龍等結(jié)合免疫算法提出了一種基于免疫算法的細(xì)菌覓食算法。楊萍等提出了一種基于細(xì)菌覓食趨化算子的粒子群算法。劉偉等結(jié)合細(xì)菌覓食機(jī)理提出了一種改進(jìn)粒子群算法。群智能算法為Nash均衡的計(jì)算提供了一種新的途徑和研究方法。受上述工作的啟發(fā)，本文提出了基于細(xì)菌覓食算法和免疫粒子群算法的混合算法，并將其應(yīng)用于求解n人有限非合作博弈Nash均衡問題，對比試驗(yàn)表明，該算法復(fù)雜度較低，全局搜索能力強(qiáng)，一定程度上克服了免疫粒子早熟的現(xiàn)象。

1 問題描述

2.3 細(xì)菌覓食算法

細(xì)菌優(yōu)化算法（BFOA）通過模擬大腸桿菌的行為，即根據(jù)趨化、繁殖和驅(qū)散這3個算子的迭代進(jìn)行優(yōu)化。在BFOA模型中，搜索空間中細(xì)菌的狀態(tài)對應(yīng)于所求解的優(yōu)化問題解。趨化算子主要是模擬細(xì)菌隨機(jī)性地向營養(yǎng)豐富區(qū)域集聚的過程，趨化算子的操作有翻轉(zhuǎn)和游動兩種。繁殖算子則主要遵循“優(yōu)勝劣汰，適者生存”的規(guī)則，在細(xì)菌更新的迭代過程中，以趨化過程各細(xì)菌適應(yīng)度值累加的和值作為標(biāo)準(zhǔn)，使能量較差的1/2數(shù)細(xì)菌死亡，能量較好1/2數(shù)細(xì)菌一分為二且對能量較低的另一半細(xì)菌進(jìn)行替換。經(jīng)過一定的周期繁殖之后，為減少陷入局部最優(yōu)值，此時引入驅(qū)散操作，設(shè)定一個驅(qū)散概率，然后使每個細(xì)菌都被隨機(jī)驅(qū)散到搜索空間，提高算法的全局尋優(yōu)能力。其中細(xì)菌覓食算法的趨化行為可具體描述如下：

假設(shè)細(xì)菌每一個體代表搜索空間的一個解（粒子），P（i.j，k，l）為細(xì)菌i的空間位置向量。其中：j為第j代趨化循環(huán)，k為第k代繁殖循環(huán)，l為第1代驅(qū)散循環(huán)，用（4）更新細(xì)菌位置，用（5）式調(diào)整方向。

其中：C（i）表示己選定方向移動步長，△（i）表示變向中產(chǎn)生的任意向量，φ（i）表示進(jìn)行調(diào)整方向后選定的單位步長向量。細(xì)菌覓食優(yōu)化算法的趨化步驟實(shí)質(zhì)上就是細(xì)菌在解的空間中對可行解的鄰域進(jìn)行搜索，趨化算子保證了細(xì)菌個體總可以找到其所在鄰域內(nèi)的最優(yōu)值。

2.4 BFA-IPSO算法

2.4.1 基本思想

免疫粒子群算法在優(yōu)化過程中通過免疫記憶性能和抗體濃度抑制機(jī)制來促進(jìn)種群的多樣性、但并不能實(shí)現(xiàn)每個粒子可以找到其所在鄰域內(nèi)的最優(yōu)位置，易陷入局部極值。針對免疫粒子群算法的缺陷，通過引入細(xì)菌覓食算法中趨向性運(yùn)動算子在增強(qiáng)算法的局部搜索能力，并據(jù)此提出了基于細(xì)菌覓食算法和免疫粒子群算法的BFA-IPSO混合算法。該算法既利用免疫粒子群算法的種群多樣性，又借助細(xì)菌覓食算中的趨化算子增強(qiáng)快速局部尋優(yōu)能力，較好地將兩者優(yōu)勢混合，具體設(shè)計(jì)步驟如下：

2.4.2 BFA-IPSO算法步驟

Stepl：設(shè)置種群規(guī)模，精度和維數(shù)以及最大迭代次數(shù);

Step2：隨機(jī)生成初始種群;

Step3：用（1）（2）式分別更新種群中粒子的速度和位置，分別計(jì)算粒子的個體極值和全局極值以及適應(yīng)度值，并將全局極值g_best對應(yīng)的粒子位置存入記憶庫;

Step4：依次檢驗(yàn)粒子i的位置x^k+1_i≥0，否

3 數(shù)值算例

下面給出2個經(jīng)典的2x2的博弈（囚徒困境博弈、監(jiān)察博弈）和文獻(xiàn)[13]給出的一個經(jīng)典3x3博弈（mXn的博弈完全類似）的算例，用基于細(xì)菌覓食算法和免疫粒子群算法的BFA-IPSO混合算法分別對這3個算例進(jìn)行6次計(jì)算。其中，本文給出的BFA-IPSO混合算法中參數(shù)值事先設(shè)置為：群體l中規(guī)模N=20，群體2中規(guī)模M=10（計(jì)算抗體（粒子）概率濃度），最大迭代次數(shù)的參數(shù)是可以改變的，這里最大迭代次數(shù)設(shè)置為300，例1、例2精度￡設(shè)置為ε=10^-1，例3精度￡設(shè)置為ε=10^-4，計(jì)算結(jié)果如表l—3所示。

例1囚徒困境博弈г（X1，Y1，A1，B1）的Nash均衡點(diǎn)，支付矩陣如下：

如表1、表2、表3所示，利用BFO-IPSO算法求解例l，經(jīng)過6次計(jì)算，平均迭代8次得出精確解，雖然文獻(xiàn)[13]用免疫粒子群算法平均迭代7次，但其適應(yīng)度值的精確度低于10^-1。利用本文的BFO-IPSO算法求解例2，經(jīng)過6次計(jì)算，平均迭代3次，文獻(xiàn)[13]用免疫粒子群算法平均迭代3次，但其適應(yīng)度值的精確度低于l0^-1。例3中，利用BFO-IPSO求解，經(jīng)過6次計(jì)算，平均迭代120代就可以得到Nash均衡解，優(yōu)于文獻(xiàn)[13]用免疫粒子群算法平均迭代的288次的結(jié)果。