 Computer Science and Application 计算机科学与应用, 2013, 3, 331-335 http://dx.doi.org/10.12677/csa.2013.38058 Published Online November 2013 (http://www.hanspub.org/journal/csa.html) Immune Multi-Direction Binary Particle Swarm Optimization Algorithm* Ziyuan Qi1,2, Jinqiu Zhang1, Jie Yue1, Chao Ma3 1Brigade of Equipment Trial and Training, Academy of Armored Forces Engineering, Beijing 2Department of Artillery Engineering, Ordnance Engineering College, Shijiazhuang 3Troop No.75134 of PLA, Chongzuo Email: jxxyqzy@126.com Received: Oct. 8th, 2013; revised: Oct. 29th, 2013; accepted: Nov. 7th, 2013 Copyright © 2013 Ziyuan Qi et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unre- stricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: A novel algorithm of BPSO is presented, which is named immune multi-direction binary particle swarm op- timization algorithm (IMBPSO). Operators including immune memory and clone selection of immune algorithm are introduced into BPSO in order to ensure the algorithm to find the best solution quickly and the diversity of colony. Fur- thermore, by modifying the formula of renewal of speed, the particle is translated from single direction into multi-di- rection. So it overcomes the disadvantages of BPSO algorithm, including falling into local best easily, low convergence speed as well as low quality in evolution evening. By testing and estimating with some standard functions, IMBPSO algorithm’s ability in finding the best solution is proved. Keywords: Binary Particle Swarm Optimization Algorithm (BPSO); Immune Operator; Clone Selection 免疫多向二进制粒子群优化算法* 齐子元 1,2，张进秋 1，岳 杰1，马 朝3 1装甲兵工程学院装备试用与培训大队，北京 2军械工程学院火炮工程系，石家庄 3中国人民解放军 75134 部队，崇左 Email: jxxyqzy@126.com 收稿日期：2013 年10 月8日；修回日期：2013年10月29 日；录用日期：2013 年11 月7日 摘 要：提出了一种新的 BPSO 改进算法——免疫多向二进制粒子群优化算法(IMBPSO)，算法中引入了免疫算 法的克隆选择算子和免疫系统的免疫记忆特性，保证了算法寻优的快速性以及群体的多样性。此外，通过修改 速度更新公式，把粒子群的搜索方向从单向变为多向，从而克服了BPSO 算法中易陷入局部最优，进化后期收 敛速度慢和精度不高等缺点。通过几个标准函数进行测试与评价，证明了 IMBPSO 算法具有良好的寻优性能。 关键词：二进制粒子群优化算法；免疫算子；克隆选择 1. 引言 粒子群优化算法(Particle Swarm Optimization, PSO)是由 Eberhart 博士和 Kennedy 博士在1995年提 出的一种新型全局优化进化算法[1]，该算法源于对鸟 类捕食行为的模拟。PSO同遗传算法类似，是一种基 于群体(population)的优化工具。系统初始化为一组随 机解，通过迭代搜寻最优值。但不同于遗传算法，PSO 没有采用复杂的交叉、变异算子和优胜劣汰的自然选 择过程，而是基于信息共享机制，通过粒子的自我学 习和向最佳个体学习的方法来实现对解空间的快速 *基金项目：军械工程学院科学研究基金资助项目(YJJXM11010)。 Open Access 331  免疫多向二进制粒子群优化算法 搜索。和其它优化算法相比，PSO 具有简单、快速、 调节参数少、易于实现等优点。Kennedy 和Eberhart 认为 PSO 算法应该是介于遗传算法和进化规划间的 一种算法，在编码方式上也较其它的算法简单。因此， PSO 一经提出，立刻引起了演化计算等领域的学者们 的广泛关注，并在短短的几年时间内出现了大量的研 究成果，形成了一个研究热点。 为解决离散问题，Kennedy 和Eberhart 等人[2]于 1997 年提出了一种二进制粒子群算法——BPSO，用 以求解离散优化问题。然而不管 PSO 算法还是 BPSO， 都存在易陷入局部极值点、进化后期收敛速度慢和精 度不高等缺点。本文针对粒子群算法这些缺点，提出 了一种改进 BPSO 算法——免疫多向二进制粒子群优 化算法(Immune Multi-direction Binary Particle Swarm Optimization, IMBPSO)，它以二进制粒子群算法的进 化框架为基础，主要从两个方面作以改进：1) 在算法 中引入免疫算法的克隆选择算子和免疫系统的免疫 记忆特性。克隆选择算子的引入可以提高算法寻优的 快速性，而记忆细胞的演化是用来保证群体的多样性 的。2) 通过修改速度更新公式，把粒子群的搜索方向 从单向变为多向，以提高搜索速度和精度。 2. 标准粒子群优化算法(SPSO) 1998 年Yuhuishi[3]提出了带带惯性权重的改进粒 子群算法。目前，有关 PSO 算法的研究大多以带惯性 权重的 PSO 算法为基础进行扩展和修改，为此将带惯 性权重的 PSO 算法称之为标准 PSO 算法(SPSO)。 SPSO 算法将每个粒子看作是在 n维搜索空间中的一 个没有重量和体积的微粒，每个微粒作为特征空间的 一个点，也就对应着一个特征子集。粒子群在特征空 间中以一定的速度“飞行”，该飞行速度由粒子的飞 行经验和群体的飞行经验进行动态调整，改变着位 置、进行相互交流，对单个粒子的最优位置和整个群 体的最优位置进行记忆。目的就是找到最优的特征子 集，这个特征子集具有最短的长度，而使用这些特征 进行分类却能得到最好的分类精度[4]。 对于任何一个粒子i都包含如下 3个向量： 12 ,,, iii in X txtxt xt 向量记录了粒子在搜索空间第 t次叠代时的位置； 12 ,,, iii in Vtvt vtvt 向量包含了粒子在不受干扰的情况 变，即粒子第t次叠代时的飞行速度； 下位置的改 12 ,,, iii in Ptp tptpt 向量记录了粒子所找到的当前最优解 置，即 个体极值 记为 P。 外，还有一个全体极值，即粒子群 到目前为 表示为 的位 (best) 除了个体极值 止找到的最优解，称为全局极值(记为 Gbest)， ： Ptpt ptpt 12 ,,, ggg gn 次叠代时 。在第 t + 1 ，粒子 i按照下面规则更新位置和速度： 11 1 ikikik ik vtvt crandptxt (1 22gk ik cr andptx t ) 11 ikik ik xtxtvt (2) 式中，ω为惯性权重，c1，c2为学习因子 为两个均匀分布在(0, 之间的 随机数；粒子 …N；搜索空间 k …t为迭 粒子通过不断学习更新， 中最优 解所在的位置，整个搜索过程结束，最后输出的G 就是算法找到的全局最优解。迭代终止条件根据具体 问题一般选为最大迭代次数或粒子群迄今为止搜索 到的最优位置满足预定最小适应阈值。 算法) 了解 决工程实际中 化问题，相对地，离散二进制 优化算法具有 ，首先对于纯组合优化问题的 表达浮点数，因此也同样适用于连续空间的问题求 解。 BPSO 算法中，每个粒子的位置使用二进制编码， 粒子的速 义为粒子位置改变的概率。 中，将每一维 x和pbest 限制为1或者 0，而速度 不作这种限制， v的位置 x更有可能选 1，v低 数就是模糊函 Sigmoid ，randl和rand2 l) 个数 I = 1,2, , 的维数 = 1,2,, n，代 次数。 最终飞至解空间 best 3. 二进制粒子群优化算法(BPSO 基本的 PSO 算法定义于连续的函数空间，为 的组合优 很多优势 表达形式要求优化算法离散的，其次二进制算法可以 度定 在BPSO ik ik 新位置时vik 。用速度来更 如果 ik 高一些，粒子 ik ik 一点则 xik选0，阈值在[0,1]之间，而有这种特点的函 数函数[5]： 1 1exp ik Sig vv ik (3) BPSO 的速度的计算公式与 SPSO 相同，如式 ik v Open Access 332  免疫多向二进制粒子群优化算法 (1)。粒子位置更新公式为： 其中，rand()为服从均匀分布的随机数。这样 xik被限 制在集合 中。 4. BPSO算法的改进 算法 入 是免疫系统的重要特性， 程中，高亲和力低浓度的抗体受到促进，而 到抑制，以此来保证抗体的 多样 1 ik xt 1, 1 0, ik if randsigvt 其他 0,1 4.1. 免疫 的引 抗体多样性和免疫记忆 在进化过 低亲和力高浓度的抗体受 性。免疫记忆是免疫系统将与入侵抗原反应部分 的抗体作为记忆细胞保留下来。对于同类抗原的再次 入侵，相应的记忆细胞被激活而产生大量的抗体。克 隆选择是在给定的选择率 ，01 ，在抗体群中 选择部分抗体的确定性映射，克隆选择仅选择群体中 亲和力较高的抗体参与繁殖及突变，而亲和力低的抗 体仍存在于免疫系统中，并逐渐 。 根据高浓度低亲和力的微粒(抗体)受到抑制，低 浓度高亲和力的微粒(抗体)受到促进这一免疫原理， 用基于浓度的选择概率来保证群体的多样性 被驱除 [6]。第 i 个微粒(抗体)的浓度和选择概率公式如下： 00 1 1 iN ii j N fX fX ) 1,2,,DXi (5 0 000 1 111 0 1 1 1, 2,, N ii j i iNNN ii iij i fx fx DX px f xfx Dx iN (6) 其中 ， 0,N roundN 满足 M为随机产生的新粒子 (抗体)，N为群体规模。 引入主 是保证粒子群中的粒 子的多样性，因此粒子群中 抗体作为初始化粒子。满 足约 中每个粒子仅根据自身的个体极值和 这两个信息量 新自己的速度和位置，并 ，粒子群在解空间的搜索是 单向 与BPSO 算法相比，IMBPSO 算法中的粒 最优的 m个个体极值、全局极值和其他的一些粒 信息来修正每个粒子下一次迭代的行动策略更新自 己的 IMBPSO算法的实现步骤： 的位置和速度； 算每个粒子的适应度值； 应值与所经历过的 最好 将其作为 当前 0 ,dNM N roun N， 免疫算法的要 为了 的初始化粒子不是随机产 生，而是由免疫算法产生的 束条件的最优解即是抗原；候选解即是抗体，抗 体和抗原之间的亲和力反映了候选解和最优解的接 近程度，也即反映候选解对约束条件和目标函数的满 足程度；抗体和抗体之间的亲和力反映了不同候选解 之间的异同，也即反映了抗体的多样性。在进化算法 中，保持抗体的多样性可以防止算法陷入局部最优 解。依据抗体和抗原之间的亲和力来选择有效抗体能 更好地体现“优胜劣汰”的原则，特别是当待选抗体 相差不大时，“优胜劣汰”的效果更明显，搜索效率 会更高[3]。 4.2. 速度更新的改进 BPSO 算法 全局极值 来更 没有考虑其他粒子的信息 的，因而精度不高。把粒子群的搜索方向从单向 变为多向是提高速度的一种有效方法。为此，将速度 更新公式(1)式修改成(7)式： 1 22 1 m ikikik ik i gk crand pt (7) 11 ik vtvtcrandpt xt x t 子根据 子的 速度和位置，从而考虑了更多粒子在迭代寻优过 程中包含的信息，整个粒子群在解空间的搜索是多方 向性的，搜索过程更均匀，能有效提高算法的精度和 全局收敛能力[7]。 4.3. 算法的实现流程 如图 1。 Step1：初始化粒子群 Step2：计 Step3：对于每个粒子，将其适 位置的适应度值进行比较，若较好。则 的粒子最好位置； Step4：对每个粒子，将其适应值与全局所经历的 最好位置的适应度值进行比较。若较好。则将其作为 当前的全局最好位置； Step5：根据式(4)和(7)更新粒子的速度和位置； Step6：产生记忆粒子(抗体)。将每一次迭代的 Gbest Open Access 333  免疫多向二进制粒子群优化算法 Open Access 334 Figure 1. Realization flow of IMBPSO 图1. IMBPSO算法的实现流程 作为记忆粒子放入记忆库中； Step7：当 Gbest连续进化若干代未有变化，如果 达到终止条件，则停 止进 据基于粒子(抗体)浓度的概率 选择 )。 达到终止条件，则结束；如果未 化，并按如下的方法更新粒子。否则转 Step2； Step8：更新粒子(抗体)。新粒子(抗体)由以下三 种方式来分别产生： a) 随机产生M个新粒子(抗体)。 b) 从记忆库中根 公式(5)和(6)，选出 0 N个粒子(抗体 c) 克隆选择。对当前的更新代按选择率 选择 round N 个较低适应度 (较高亲和力)的值 (抗 (round()函数 一代粒子(抗。然后，返回 Step2。 群算法(IMBPSO)的性能，选 著名的 benchmark 测试函数对 IMBPSO 和 行对比测试。四个测试函数如下： F1：Sphere函数，它在时达到最小值0。 BPSO 算法进 0 i x 2 1 1 100100 n ii i fx xx F2：Ackley 函数，在0x时达到最小值0。 i 1 exp c20 n i 2 4 0 1 1 20exp 0.2 os 2 30 30 n i i i i fx x n x e n x F3：Rastrigin函数，有很多正弦凸起的局部极小 点。在 粒子 0 体)。其中 round N 满足 roundNM NN 为就近取整数)。 形成新 体)群 5. 算法的性能评价 0 i x 处取到全局最小值0。 F4：Rosenbrock 函数。是一个经典的优化函数， 2 3 1 10 cos2π10 n ii i i fx xx x 5.12 5.12 为测试免疫多向微粒 择了四个  免疫多向二进制粒子群优化算法 Table 1. Test results of IMBPS 表1. IMBPSO与BPSO 的 达到精度时停止搜索 O and BPSO 测试结果 标准函数 算法 平均最优解 平均收敛代数 收敛率 最好解 BPSO 50/3.3675e−06 246 50 0 F1 IMBPSO 50/50 0 0 39 BPSO 2. F2 I 1.2.2 F3 I 0.0.3 F4 I 50/50 804e−084.5409e−06 395 MBPSO50/50 0 0 25 BPSO 9/50 4924 4843 937 MBPSO45/50 0.1932 0.4874 846 BPSO 18/50 2846 7502 145 MBPSO47/50 0 0.0247 510 在处取到全局最小。 测试条件：IBM笔记本 T1400 1.83 GHz，512 M 内存，Windows XP Processional, Matlab7.01 下编程运 行。 F1 和F2的误差设置为 ，F3和F4 的误 差为 1 i x值0 12 2 21 1 10 1 n ii i i fxx x 0x 2 30 30 i x 实验中种群规模为40，维数为 10，F1 和F2 的最 大进化代数是 1000 代，F3 和F4 的最大进化代数是 5000 代， 8 10 5 10，各函数的 max V取变量范围的上限。学习因 子C1 = C2 = 2.0，惯性权重 从0.9 到0.4 线性减少。 克隆选择率0.3 ，记忆粒子选为 0.7。每组参 数均重实验10 次，出相应参数下50 次实验的 收敛率、最好解、平均最优解、平均收敛代数。结果 如表 1所示。 从上面的实验结果可以看出，IMBPSO比BPSO 有着更好的搜索性能。对于较易收敛的 F1 和F2， IMBPSO在与BPSO 择率 复 并给 有着相同的收敛率和相近的平均 最优 ，而导 致收敛后期速度变慢， 优和收敛的精度 降低。IMBPSO 算法借 较好的多样性， 将每一进化代的Gbest 作为记忆细胞保存下来，并按基 于浓 [1] , J. and Eberhart, R.C. (1995) Parm optimiza- al Networks, Perth, 1942-1948. [2] Kennedy, J. and Eberhart, R.C. (1997) A discrete binary version of the particle swarm Proceedings of the World Multi- tics and Informatics, IEEE Ser- vice Center 环境污染与防治 , , 1-7. 解的情况下，收敛速度明显要好于 BPSO。而对 于较难收敛的F3 和F4，IMPSO 不管从收敛率还是收 敛速度和平均最优解上都明显优于BPSO。 6. 结论 BPSO 由于群体的多样性在进化后期变差 易陷于局部最 鉴免疫学习中 度的选择概率来更替部分微粒，使进化群体保持 了很好的多样性，有效地避免了算法陷于局部最优。 同时对更替当前代中适应值较好的微粒进行克隆选 择操作，从而加快了算法的收敛速度。测试结果也显 示，MPSO 算法具有精度高、收敛速度快的优点，为 解决最优问题提供了一条新的途径。 参考文献 (References) Kennedy ticle swar tion. IEEE International Conference on Neur algorithm. conference on Systemic, Cyberne , Piscataway, 4104-4109. [3] Shi, Y. and Eberhart, R. (1998) A modified particle swarm opti- mizer. IEEE World Congress on Computational Intelligence, 69- 73. [4] 郑洪英 (2007) 基于进化算法的入侵检测技术研究. 博士论 文, 重庆大学, 63-69. [5] 王新峰, 邱静, 刘冠军 (2005) 基于离散粒子群优化算法的 直升机减速器齿轮故障特征选择. 航空动力学报 , 6, 969-972. [6] 胡春霞 (2007) 免疫微粒群算法的研究. 硕士论文, 太原科 技大学, 16-21. [7] 曾慧娟, 潘文斌, 朱建全 (2008) 基于改进粒子群优化算法 的水质模型参数识别. 3 Open Access 335 |