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

劉露萍 賈文生

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

【關鍵詞】免疫粒子群算法 細菌覓食算法 趨化算子 Nash均衡

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

1 問題描述

2.3 細菌覓食算法

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

假設細菌每一個體代表搜索空間的一個解（粒子），P（i.j，k，l）為細菌i的空間位置向量。其中：j為第j代趨化循環，k為第k代繁殖循環，l為第1代驅散循環，用（4）更新細菌位置，用（5）式調整方向。

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

2.4 BFA-IPSO算法

2.4.1 基本思想

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

2.4.2 BFA-IPSO算法步驟

Stepl：設置種群規模，精度和維數以及最大迭代次數;

Step2：隨機生成初始種群;

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

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

3 數值算例

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

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

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