基于免疫网络的粒子群算法及其性能分析

摘要：针对粒子群算法存在进化后期收敛速度变慢且易陷入早熟收敛的缺点，提出了一种免疫网络粒子群算法（Immune Network Particle Swarm Optimization，INPSO）。新算法提高了动态寻优能力和问题的求解精度，有效克服了粒子群算法易出现早熟收敛与进化后期收敛速度慢等缺点。

关键词：粒子群算法 免疫网络 控制器优化

中图分类号：TP18 文献标识码：A 文章编号：1007-9416（2013）09-0110-04

1 引言

粒子群优化算法（Particle Swarm Optimization，PSO）是Kennedy与Eberhart提出的一种全局优化算法[1]，现已广泛应用于科学与工程领域。然而，粒子群算法随着问题规模的增大，在进化后期算法收敛速度变慢且易陷入早熟收敛。近年来，相关学者提出了许多改进算法以改善粒子群算法的性能。如Chia-Feng Juang将遗传算法的交叉与变异机制引入粒子群算法，提出了一种混合粒子群优化算法（HGAPSO）[2]。文献[3]提出了一种自适应粒子群算法（APSO），比较PSO该算法改善了收敛速度、增加了收敛精度和可靠性。文献 [4]提出了一种自适应综合学习粒子群算法（A-CLPSO），该算法减少了陷入局部最优的可能。然而，这些改进都只在一定程度上改善了PSO的性能，早熟收敛仍是粒子群算法的一大难题，尤其是对于复杂高维及多模态优化问题更是如此。

通过分析粒子群算法的特性，寻找其早熟收敛的原因，本文提出了一种新的免疫网络粒子群算法（Immune Network Particle Swarm Optimization，INPSO）。经过经典测试函数的测试表明，INPSO算法明显提高了粒子群体的多样性和算法的求解精度，有效避免了粒子群算法易出现早熟收敛和进化后期收敛速度慢的缺点。

2 算法改进基础

2.1 标准粒子群算法

粒子群优化算法通过粒子间的协作与竞争来进行迭代优化。假设在维搜索空间中群体由个粒子组成，即 。粒子的当前位置为，当前飞行速度为。为粒子的历史最优位置（）。为群体中的全局最优位置（）。粒子的速度更新公式如下：

（2-1）

其中，惯性权重。随着进化代数的增长，从0.9线性减少至0.4。粒子的位置更新公式如下：

（2-2）

2.2 改进的克隆选择算法

克隆选择算法是由L.N.De Castro提出[5]，算法中变异算子主要是高斯变异与柯西变异，变异空间比较固定，不利于免疫克隆选择算法的动态寻优。而小波变异的变异空间可变，且具有微调能力，有利于提高算法的动态优化性能。基于小波变异的克隆操作步骤如下：

Step 1 各个粒子的个体极值生成一个临时克隆种群。将临时克隆种群中的每个粒子视为抗体， 克隆规模与亲和度成正比，克隆倍数如下：

（2-3）

其中，为种群规模，。另外，为了保证每个抗体都有一定的克隆数量，因此加上了的整数常量。经过克隆扩增后，生成新群体Sub。

Step 2 对群体Sub中的每个个体实施高频变异， 其方法为自适应Morlet小波变异。受自然生物进化思想启发，算法在进化初期以一定的变异概率采用较大的小波变异幅值以保持粒子群体的多样性，而到进化后期小波变异幅值逐渐缩小以提高算法的局部微调能力。其变异算子如下：

（2-4）

其中，。。

Step 3免疫选择操作，从克隆变异后的个体中选择亲和度最高的个体进入下一代。通过局部择优实现了种群的压缩，同时保证了抗体群中的最优解不会变差。

2.3 免疫网络

受独特型免疫调节网络的启发，De Castro构造了一种aiNet算法，来模拟免疫网络对抗原刺激的应答过程[6]，有效地维持了抗原-抗体、抗体-抗体之间的动态稳定平衡，保持了抗体的多样性。aiNet新生成的网络细胞群如下。

（2-5）

其中是网络细胞群，是抗原细胞，是学习率或者成熟率。的取值根据网络单元与抗原的亲和度而定，亲和度高则的取值小，使抗体将朝着识别抗原的方向进化。

利用免疫网络及柯西变异扰动可有效克服粒子群算法早熟收敛，增强粒子种群的多样性，提高算法的收敛速度及全局搜索能力。因此，文中采用了柯西免疫网络来生成下一代群体，其新种群个体的生成公式如下。

（2-6）

其中，，为区间之间的随机数，密度函数的表达式如下。

（2-7）

3 免疫网络粒子群算法及流程

本文将克隆选择、免疫网络与粒子群算法进行了有机结合，提出了一种新的免疫网络粒子群算法（INPSO）。算法的基本流程如图1所示。

免疫网络粒子群算法的基本流程如下：

（1）随机初始化个粒子的位置与速度，并初始化相关参数。

（2）评价各粒子的初始适应度值，并保存相应粒子初始最优位置以及初始最优适应度值。While（不满足退出条件）do//退出条件为找到相应的全局最优解或达到设定的截止代数。

（3）根据式（2-1）（2-2）对粒子的速度和位置进行更新，并计算各粒子的适应度值，如果各粒子适应度值优于相应粒子历史最优适应度值，则粒子的更新。

（4）将所有粒子按适应度排序，对中间个粒子根据式（2-6）进行柯西免疫网络操作，并重新初始化最后个粒子，如果各粒子适应度值优于相应粒子历史最优适应度值，则粒子的更新。

（5）对前面个粒子的进行克隆选择操作，如果所有粒子中最优粒子适应度值优于历史全局最优粒子适应度值，则更新。

End While

（6）输出结果，算法运行结束。

4 算法性能分析

为了验证本文提出的免疫网络粒子群算法（Immune Network Particle Swarm Optimization，INPSO）的收敛速度以及全局优化能力，用本算法对表1所示函数进行测试，其中f1～f4为单模态函数，f5～f8为多模态函数。并将INPSO与其它混合粒子群算法进行比较，充分考察免疫网络粒子群算法对不同类型问题的优化性能。

实验仿真环境为Windows 7系统，AMD Athlon （tm） II X2 255处理器，2.0GB内存，仿真软件为Microsoft Visual C++ 6.0，绘图软件为MATLAB 7.0。

实验参数设置：对于所有函数，INPSO的加速因子 ，惯性权重在区间内线性递减，且克隆变异概率为0.8。对于所有算法，设置粒子个数为40，问题维数为30，算法迭代次数为1000，运行次数为30。

4.1 算法精度比较

本节将免疫网络粒子群算法（INPSO）分别与混合遗传粒子群算法（HGAPSO）[7]、自适应粒子群算法（APSO）[8]以及自适应综合学习粒子群算法（A-CLPSO）[9]进行比较，对于表1中所列的8个经典测试函数，各算法30次独立运行结束后的均值（Mean）和均方差（Std.Dev）如表2所示，而图2则分别比较了各算法在进化过程中的收敛性能。

从表2和图2中可以看出，无论是对于单模态函数还是对于多模态函数， INPSO算法的收敛速度以及收敛精度都明显优于其它3种改进粒子群算法，而且具有更强大的搜索能力。

4.2 高维函数实验

从表1中选取两个单模态函数（f1、f3）和两个多模态函数（f5、f7），将函数维数分别取100维、500维、1000维与5000维来对算法进行测试，函数维数对算法性能的影响及函数维数与适应度值关系分别如表3、图3所示。

从表3与图3中可以看出，在其它参数不变的情况下，免疫网络粒子群算法（Immune Network Particle Swarm Optimization，INPSO）的优化能力并没有随着函数维数的增大而减弱，算法所需时间正常增长，这说明INPSO 在高维函数优化方面有明显优势。由于INPSO很好地保持了群体的多样性，对超高维函数也几乎能够在相同的代数下找到理想的全局最优值。

5 结语

本文提出了一种免疫网络粒子群算法。在标准粒子群算法的基础上，引入了克隆选择机制与免疫网络思想，并将克隆变异算子加以改进，提高了算法的动态寻优能力。实验结果表明，改进后的算法明显提高了算法的求解精度，有效克服了粒子群算法易出现早熟收敛与进化后期收敛速度慢等缺点。同时表明INPSO算法在求解多模态问题及高维优化问题上优势明显，可以预见INPSO算法在复杂系统控制器优化与设计领域有着较好的应用前景。

参考文献

[1] Eberhart R，Kennedy J A.New optimizer using particle swarm theory[C] //Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Piscataway， NJ，USA： IEEE， 1995： 39-43.

[2] Chia F J.A Hybrid of Genetic Algorithm and Particle Swarm Optimization for Recurrent Network Design.IEEE TRANSACTIONS ON SYSTEMS，MAN， AND CYBERNETICS—PART B：CYBERNETICS，2004， 34（2）：997-1006.

[3] Zhi H Z，Jun Z，Yun L H，Shu H C.Adaptive Particle Swarm Optimization.IEEE TRANSACTIONS ON SYSTEMS，MAN， AND CYBERNETICS—PART B：CYBERNETICS， 2009， 39（6）：1362-1381.

[4] Ho S Y，Lin H S，Liauh W H，et al.OPSO：Orthogonal particle swarm optimization and its application to task assignment problems[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part A： System and Humans， 2008， 38（2）： 288-298.

[5] De L N，Castro F，Zuben J V.Learning and optimization using the clonal selection principle. IEEE Trans. puter，2002， 6（3）： 239-251.

[6] De L N，Castro F Zuben J V.An evolutionary immune network for data clustering.Proceedings Sixth Brazilian Symposium on Neural Networks，2000，84-89.

[7] Chia F J.A Hybrid of Genetic Algorithm and Particle Swarm Optimization for Recurrent Network Design.IEEE TRANSACTIONS ON SYSTEMS， MAN，AND CYBERNETICS—PART B：CYBERNETICS， 2004， 34（2）：997-1006.

[8] Zhi H Z，Jun Z，Yun L H， Shu H C.Adaptive Particle Swarm Optimization.IEEE TRANSACTIONS ON SYSTEMS， MAN， AND CYBERNETICS—PART B：CYBERNETICS，2009，39（6）：1362-1381.

[9] Hao W，Junping G.An Improved Comprehensive Learning Particle Swarm Optimization and Its Application to the Semiautomatic Design of Antennas[J].IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION， 2009， 57（10）：3018-3028.