基于细菌觅食和免疫粒子群算法的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次的结果。