基于自适应搜索的免疫粒子群算法

工程科学学报，第39卷，第1期：125-132.2017年1月 Chinese Journal of Engineering,Vol.39,No.1:125-132,January 2017 DOI:10.13374/j.issn2095-9389.2017.01.016;http://journals.ustb.edu.cn 基于自适应搜索的免疫粒子群算法 张超)，李擎)四，王伟乾)，陈鹏)，冯毅南) 1)北京科技大学自动化学院，北京1000832)中国电子科技集团第二研究所.太原030024 ☒通信作者，E-mail:liqing@ics.usth.cdu.cn 摘要经典粒子群算法由于多样性差而陷入局部最优，从而造成早熟停滞现象.为克服上述缺点，本文结合人工免疫算 法，提出一种基于自适应搜索的免疫粒子群算法.首先，该算法改善了浓度机制：然后由粒子最大浓度值来控制子种群数目 以充分利用粒子种群资源：最后对劣质子种群进行疫苗接种，利用粒子最大浓度值调节接种疫苗的搜索范围，不仅避免了种 群退化现象，而且提高了算法的收敛精度和全局搜索能力.仿真结果表明该算法求解复杂函数优化问题的有效性和优越性 关键词粒子群算法：人工免疫算法；自适应搜索；海明距离 分类号TP18 Immune particle swarm optimization algorithm based on the adaptive search strategy ZHANG Chao,LI Qing),WANG Wei-gian?),CHEN Peng),FENG Yi-nan) 1)School of Automation and Electrical Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)The Second Research Institute of China Electronics Technology Group Corporation,Taiyuan 030024,China Corresponding author,E-mail:liging@ies.ustb.edu.cn ABSTRACT The particle swarm algorithm is often trapped in a local optimum due to poor diversity,resulting in a premature stagna- tion phenomenon.In order to overcome this shortcoming,an immune particle swarm optimization algorithm based on the adaptive search strategy was proposed in this paper.Firstly,the concentration mechanism was improved.Secondly,in order to make full use of the resources of the particle population,the number of particles of sub-populations was controlled by the maximum concentration of particles.Finally,the inferior sub-populations were vaccinated,and the maximum concentration of particles was used to control the search range of the vaccine,so the population degradation was avoided,and the convergence accuracy and the global search ability of the algorithm were improved.Simulation results show the effectiveness and superiority of the proposed algorithm in solving the complex function optimization problems. KEY WORDS particle swarm optimization;artificial immune algorithm;adaptive search;Hamming distance 粒子群优化算法(particle swarm optimization,应用过程中往往会出现陷入局部最优而导致的早熟停 PS0))是模仿鸟类飞行觅食过程的算法，以其速度更滞现象，造成算法得不到理想最优解，尤其是在解决复 新公式使种群中的粒子迅速向种群历史最优值靠拢， 杂的多峰多谷问题时更为突出2-).因此，研究者开始 搜索速度快、效率高且算法简单，适合处理实数编码问 尝试将一些其他智能仿生算法与经典粒子群优化算法 题.该算法一经提出，便受到众多学者的关注和研究. 相融合，以弥补粒子群优化算法多样性不足的缺点. 目前已被广泛应用于工程技术、科学研究等领域.但 如蚁群粒子群算法[]、遗传粒子群算法[]和免疫粒子 是粒子群优化算法与其他群智能算法类似，算法后期 群算法[6] 多样性差，进化速度大幅降低，容易出现停滞现象，在 人工免疫优化算法(artificial immune algorithm, 收稿日期：2016-01-29 基金项目：国家自然科学基金青年基金资助项目(61603362,61603034)

工程科学学报,第 39 卷,第 1 期:125鄄鄄132,2017 年 1 月 Chinese Journal of Engineering, Vol. 39, No. 1: 125鄄鄄132, January 2017 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2017. 01. 016; http: / / journals. ustb. edu. cn 基于自适应搜索的免疫粒子群算法 张 超1) , 李 擎1) 苣 , 王伟乾2) , 陈 鹏1) , 冯毅南1) 1) 北京科技大学自动化学院, 北京 100083 2) 中国电子科技集团第二研究所, 太原 030024 苣 通信作者, E鄄mail: liqing@ ies. ustb. edu. cn 摘 要 经典粒子群算法由于多样性差而陷入局部最优,从而造成早熟停滞现象. 为克服上述缺点,本文结合人工免疫算 法,提出一种基于自适应搜索的免疫粒子群算法. 首先,该算法改善了浓度机制;然后由粒子最大浓度值来控制子种群数目 以充分利用粒子种群资源;最后对劣质子种群进行疫苗接种,利用粒子最大浓度值调节接种疫苗的搜索范围,不仅避免了种 群退化现象,而且提高了算法的收敛精度和全局搜索能力. 仿真结果表明该算法求解复杂函数优化问题的有效性和优越性. 关键词 粒子群算法; 人工免疫算法; 自适应搜索; 海明距离 分类号 TP18 Immune particle swarm optimization algorithm based on the adaptive search strategy ZHANG Chao 1) , LI Qing 1) 苣 , WANG Wei鄄qian 2) , CHEN Peng 1) , FENG Yi鄄nan 1) 1) School of Automation and Electrical Engineering, University of Science and Technology Beijing, Beijing 100083, China 2) The Second Research Institute of China Electronics Technology Group Corporation, Taiyuan 030024, China 苣 Corresponding author, E鄄mail: liqing@ ies. ustb. edu. cn ABSTRACT The particle swarm algorithm is often trapped in a local optimum due to poor diversity, resulting in a premature stagna鄄 tion phenomenon. In order to overcome this shortcoming, an immune particle swarm optimization algorithm based on the adaptive search strategy was proposed in this paper. Firstly, the concentration mechanism was improved. Secondly, in order to make full use of the resources of the particle population, the number of particles of sub鄄populations was controlled by the maximum concentration of particles. Finally, the inferior sub鄄populations were vaccinated, and the maximum concentration of particles was used to control the search range of the vaccine, so the population degradation was avoided, and the convergence accuracy and the global search ability of the algorithm were improved. Simulation results show the effectiveness and superiority of the proposed algorithm in solving the complex function optimization problems. KEY WORDS particle swarm optimization; artificial immune algorithm; adaptive search; Hamming distance 收稿日期: 2016鄄鄄01鄄鄄29 基金项目: 国家自然科学基金青年基金资助项目(61603362,61603034) 粒 子 群 优 化 算 法 ( particle swarm optimization, PSO) [1]是模仿鸟类飞行觅食过程的算法,以其速度更 新公式使种群中的粒子迅速向种群历史最优值靠拢, 搜索速度快、效率高且算法简单,适合处理实数编码问 题. 该算法一经提出,便受到众多学者的关注和研究. 目前已被广泛应用于工程技术、科学研究等领域. 但 是粒子群优化算法与其他群智能算法类似,算法后期 多样性差,进化速度大幅降低,容易出现停滞现象,在 应用过程中往往会出现陷入局部最优而导致的早熟停 滞现象,造成算法得不到理想最优解,尤其是在解决复 杂的多峰多谷问题时更为突出[2鄄鄄3] . 因此,研究者开始 尝试将一些其他智能仿生算法与经典粒子群优化算法 相融合,以弥补粒子群优化算法多样性不足的缺点. 如蚁群粒子群算法[4] 、遗传粒子群算法[5] 和免疫粒子 群算法[6] . 人工免疫优化算法 ( artificial immune algorithm

·126· 工程科学学报，第39卷，第1期 AA)]是由人工免疫系统发展而来，以其独特的浓度 (1+1)=ow (1)+cir(pbestix)+car2 (gbestx), 机制，记忆调节机制和疫苗接种机制来控制种群抗体 (1) 的多样性，以确保优秀的抗体始终低浓度存在.人工 x(t+1)=xg(t)+vg(1+1). (2) 免疫优化算法在遗传优化算法(genetic algorithm, 式中，x,和，分别为第i个粒子的位置和速度的第j GA)[劉的基础上发展而来，它很好地克服了遗传优化 维，pbest为第i个粒子的历史最优位置的第j维， 算法易陷入局部最优的缺点，但缺点也十分明显，虽然 gbest,为全局历史最优位置的第j维.另外，w为惯性 种群进化方式与遗传优化算法相同，但收敛速度比大 权重，c和c2分别为调节粒子相自身最优位置和全局 幅落后于遗传优化算法.在融合算法中，人工免疫优 历史最优位置靠近的权重，「，和，为相互独立的随机 化算法常常作为一种辅助算法用来提高种群多 数.随着迭代次数增加，种群粒子不断靠拢和重叠，从 样性 而易造成所有粒子陷入局部最优，因此需要引入人工 免疫粒子群算法(immune particle swarm optimiza- 免疫的浓度机制来增加种群后期的多样性. ion,PS0)[o是将经典粒子群算法和人工免疫算法 1.2人工免疫算法 相结合的融合算法.它将粒子群算法的进化机制与人 人工免疫算法是模拟人体抗体对抗抗原的过程. 工免疫算法的浓度调节机制相结合，使融合后的算法 当外界抗原入侵人体时，免疫系统会调用人体内部的 全局性搜索能力更强.不少学者也将免疫粒子群算法 抗体去抵抗抗原，之后身体会将该抗体信息存人记忆 改进并运用到实际问题当中，例如文献[11]提出一种 细胞，将当下抗体浓度降低，保证体内抗体多样性.当 基于混沌克隆选择的免疫粒子群优化算法(CPS0), 下次对应抗原再次出现时，免疫系统又将记忆细胞的 并将该算法运用到优化BP神经网络权值当中.文献 抗体大量繁殖以对抗抗原，必要时还需从外界注入优 [12]提出一种改进的粒子群免疫优化算法(PS0), 秀的抗体疫苗来对抗抗原 并把这种算法运用到机器人路径规划当中.文献[13] 人工免疫算法的种群进化过程与遗传算法相同， 针对混合车间流水调度问题提出一种带有动态扰动的 由选择、交叉和变异操作来更新种群，区别在于人工免 免疫粒子群算法(PSO-DDT).目前虽然上述改进算 疫算法的评价指标是由亲和力决定，亲和力包括抗体 法从一定程度上改善了经典粒子群算法的多样性，但 与抗原的亲和力（适应度）和抗体之间的亲和力（浓 随机疫苗接种也导致种群退化，造成一部分粒子的资 度).亲和力由以下公式计算. 源浪费. p(x:)=af(x)+(1-a)d(x). (3) 本文提出的自适应免疫粒子群算法(adaptive 式中，P(x)是第i个粒子的亲和力值，f(x)是第i个 search artificial immune algorithms-particle swarm optimi- 粒子的适应度，d(x)是第i个粒子的浓度值，a为权重 cation,ASIPS0)在传统免疫粒子群融合算法基础之 系数 上，动态调整子种群大小，并且根据粒子最大浓度值自 人工免疫算法主要包含三个机制，即记忆存储机 动调整搜索范围.与传统免疫粒子群融合算法相比， 制、浓度调节机制和疫苗接种机制. 自适应免疫粒子群算法避免了种群退化所造成的种群 1.2.1记忆存储机制 资源浪费，而且具有良好的收敛精度和全局搜索性能， 记忆库存储机制用来保留进化中的优秀抗体，防 尤其在处理复杂问题时，由于其可变的搜索范围，增加 止种群退化.记忆库存储少量优秀抗体，保证优秀抗 了整个种群的多样性，提高了算法性能 体一直存在不会丢失.当抗原再次来临时，记忆库中 仿真实验表明，自适应免疫粒子群算法在复杂函 的优秀抗体被直接调取进行复制 数优化、多峰多谷函数全局寻优以及高维度函数优化 疫苗接种主要有两种方式：一种是直接将记忆细 方面取得了较好的效果，与改进的粒子群免疫优化算 胞的优秀粒子繁殖接种，另一种是随机接种，产生随机 法、带有动态扰动的免疫粒子群算法等改进免疫粒子 免疫进行接种.两种方法都有各自优缺点：方式一疫 群算法相比，在求解精度和全局寻优方面有明显的 苗直接继承优秀粒子，有助于提高种群质量，但也易使 优势 整个种群陷入局部最优；方式二疫苗完全随机产生，利 1免疫粒子群算法 于提高种群多样性，但是也可能造成整个种群退化. 1.2.2浓度调节机制 免疫粒子群算法是以粒子群算法的进化模型为核 浓度调节机制是用来调节种群抗体多样性的，保 心，以人工免疫机制为辅助调节的混合算法 证在低浓度高适应度的抗体适量存在的同时，低浓度 1.1粒子群算法进化模型 或者低适应度的个体少量存在.该过程可以提高种群 粒子群算法种群进化是由粒子的速度公式和位置 多样性，防止适应度高的个体大量存在而使种群陷入 公式组成： 局部最优.在实数编码中，计算抗体浓度主要有两种

工程科学学报,第 39 卷,第 1 期 AIA) [7]是由人工免疫系统发展而来,以其独特的浓度 机制,记忆调节机制和疫苗接种机制来控制种群抗体 的多样性,以确保优秀的抗体始终低浓度存在. 人工 免疫 优 化 算 法 在 遗 传 优 化 算 法 ( genetic algorithm, GA) [8]的基础上发展而来,它很好地克服了遗传优化 算法易陷入局部最优的缺点,但缺点也十分明显,虽然 种群进化方式与遗传优化算法相同,但收敛速度比大 幅落后于遗传优化算法. 在融合算法中,人工免疫优 化算 法 常 常 作 为 一 种 辅 助 算 法 用 来 提 高 种 群 多 样性[9] . 免疫粒子群算法( immune particle swarm optimiza鄄 tion, IPSO) [10]是将经典粒子群算法和人工免疫算法 相结合的融合算法. 它将粒子群算法的进化机制与人 工免疫算法的浓度调节机制相结合,使融合后的算法 全局性搜索能力更强. 不少学者也将免疫粒子群算法 改进并运用到实际问题当中,例如文献[11]提出一种 基于混沌克隆选择的免疫粒子群优化算法(CIPSO), 并将该算法运用到优化 BP 神经网络权值当中. 文献 [12]提出一种改进的粒子群免疫优化算法( IIPSO), 并把这种算法运用到机器人路径规划当中. 文献[13] 针对混合车间流水调度问题提出一种带有动态扰动的 免疫粒子群算法( IPSO鄄鄄 DDT). 目前虽然上述改进算 法从一定程度上改善了经典粒子群算法的多样性,但 随机疫苗接种也导致种群退化,造成一部分粒子的资 源浪费. 本文提出的自适应免疫粒子群算法 ( adaptive search artificial immune algorithms鄄particle swarm optimi鄄 zation, ASIPSO) 在传统免疫粒子群融合算法基础之 上,动态调整子种群大小,并且根据粒子最大浓度值自 动调整搜索范围. 与传统免疫粒子群融合算法相比, 自适应免疫粒子群算法避免了种群退化所造成的种群 资源浪费,而且具有良好的收敛精度和全局搜索性能, 尤其在处理复杂问题时,由于其可变的搜索范围,增加 了整个种群的多样性,提高了算法性能. 仿真实验表明,自适应免疫粒子群算法在复杂函 数优化、多峰多谷函数全局寻优以及高维度函数优化 方面取得了较好的效果,与改进的粒子群免疫优化算 法、带有动态扰动的免疫粒子群算法等改进免疫粒子 群算法相比,在求解精度和全局寻优方面有明显的 优势. 1 免疫粒子群算法 免疫粒子群算法是以粒子群算法的进化模型为核 心,以人工免疫机制为辅助调节的混合算法. 1郾 1 粒子群算法进化模型 粒子群算法种群进化是由粒子的速度公式和位置 公式组成: vij(t +1) = 棕vij(t) + c1 r1 (pbest ij - xij) + c21 r2 (gbest j - xij), (1) xij(t + 1) = xij(t) + vij(t + 1). (2) 式中,xij和 vij 分别为第 i 个粒子的位置和速度的第 j 维,pbest ij 为第 i 个粒子的历史最优位置的第 j 维, gbest j 为全局历史最优位置的第 j 维. 另外,棕 为惯性 权重,c1和 c2分别为调节粒子相自身最优位置和全局 历史最优位置靠近的权重,r1和 r2为相互独立的随机 数. 随着迭代次数增加,种群粒子不断靠拢和重叠,从 而易造成所有粒子陷入局部最优,因此需要引入人工 免疫的浓度机制来增加种群后期的多样性. 1郾 2 人工免疫算法 人工免疫算法是模拟人体抗体对抗抗原的过程. 当外界抗原入侵人体时,免疫系统会调用人体内部的 抗体去抵抗抗原,之后身体会将该抗体信息存入记忆 细胞,将当下抗体浓度降低,保证体内抗体多样性. 当 下次对应抗原再次出现时,免疫系统又将记忆细胞的 抗体大量繁殖以对抗抗原,必要时还需从外界注入优 秀的抗体疫苗来对抗抗原. 人工免疫算法的种群进化过程与遗传算法相同, 由选择、交叉和变异操作来更新种群,区别在于人工免 疫算法的评价指标是由亲和力决定,亲和力包括抗体 与抗原的亲和力(适应度) 和抗体之间的亲和力(浓 度). 亲和力由以下公式计算. p(xi) = 琢f(xi) + (1 - 琢)d(xi). (3) 式中,p(xi)是第 i 个粒子的亲和力值,f( xi ) 是第 i 个 粒子的适应度,d(xi)是第 i 个粒子的浓度值,琢 为权重 系数. 人工免疫算法主要包含三个机制,即记忆存储机 制、浓度调节机制和疫苗接种机制. 1郾 2郾 1 记忆存储机制 记忆库存储机制用来保留进化中的优秀抗体,防 止种群退化. 记忆库存储少量优秀抗体,保证优秀抗 体一直存在不会丢失. 当抗原再次来临时,记忆库中 的优秀抗体被直接调取进行复制. 疫苗接种主要有两种方式:一种是直接将记忆细 胞的优秀粒子繁殖接种,另一种是随机接种,产生随机 免疫进行接种. 两种方法都有各自优缺点:方式一疫 苗直接继承优秀粒子,有助于提高种群质量,但也易使 整个种群陷入局部最优;方式二疫苗完全随机产生,利 于提高种群多样性,但是也可能造成整个种群退化. 1郾 2郾 2 浓度调节机制 浓度调节机制是用来调节种群抗体多样性的,保 证在低浓度高适应度的抗体适量存在的同时,低浓度 或者低适应度的个体少量存在. 该过程可以提高种群 多样性,防止适应度高的个体大量存在而使种群陷入 局部最优. 在实数编码中,计算抗体浓度主要有两种 ·126·

张超等：基于自适应搜索的免疫粒子群算法 ·127· 方式：一种是基于矢量矩的浓度机制，另一种是基于海 质粒子，对这些劣质粒子进行疫苗接种，将记忆细胞中 明距离的浓度机制 好的粒子进行繁殖代替这些劣质粒子 基于海明距离是以抗体为出发点，比较抗体之间 这里使用粒子最大浓度值来控制子种群数量，子 的相似度从而判断相似抗体浓度，计算方法如式(4) 种群A和B的种群数分别由式(7)和式(8)计算得出. 和式(5)所示 popA =dM. (7) 1,0.95≤≤1.01， popB =M-popA. (8) p(x）= 式中，popA是子种群A的个体数量；popB是子种群B 0,其他. 的个体数量；M是初始种群个体数量，也是子种群A j=1,2,…,M (4) 和B的总和；d是粒子最大浓度值 d(x)=P() 当粒子分散时，整个粒子群多样性好，不容易陷入 ,i=1,2,…,M (5) 局部最优，这个时候子种群A数量大些，子种群B数 式中，P(x,)是代表种群中有多少粒子与第i个粒子相 量少些，使整个粒子群朝着最优解进化.当粒子群过 似的相似度值.当粒子与某个粒子各个维度都相近 于集中时，整个粒子群多样性差，容易陷入局部最优， 时，判定二者相近，取值为1，否则为0.d(x)是第i个 这个时候则子种群B数量大些，子种群A少些，确保 粒子的浓度 一部分优秀粒子进化的同时，另一部分劣质粒子去周 基于矢量矩是从抗体对抗原的抵抗力为出发点， 围搜寻，增大整个种群的多样性 比较各个抗体对抗体的抗原反应，从而判断相似抗体 动态改变子种群数目相当于控制两种算法的作用 浓度，计算方法如下式所示： 大小.这样可以使种群过于拥挤时改善其多样性，使 三)-1 种群始终朝着更好的方向进化 2.2自适应搜索的实现 d(x:）= i=1,2,…,M 传统免疫粒子群算法的接种方式都有所欠缺，如 If(x;)-f(x)I 果能将两种方式结合，在保证优秀粒子的情况下增加 (6) 随机性，这样能够在提高种群质量的同时，改善其多 两种浓度机制都可以提高种群多样性，基于海明 样性. 距离的浓度机制比基于矢量矩的浓度机制更准确，但 自适应免疫粒子群算法采用两种接种方式相结合 也会消耗更多的时间. 的方式，在继承优秀粒子的基础上，添加一些随机范围 1.2.3浓度调节机制 搜索.结合方式是以记忆库中存入的gbest为中心，在 当需要大量优秀抗体来代替劣质抗体时，疫苗接 其周围随机范围搜索 种机制会将记忆库中的优秀抗体取出进行繁殖进化来 Vaccine(x)gbest range(t),i=1,2,...,popB. 代替种群中的劣质抗体，提高种群质量. (9) 2自适应搜索免疫粒子群算法 range(t)rand x R(t). (10) 式中，Vaccine是接种疫苗，range(t)是第t代搜索范 2.1算法基本思想 围，R()是第t代搜索半径.可见每一个接种疫苗都 传统免疫粒子群算法通常采用串联方式，即在种 是落在群体极值周围的一个随机值. 群更新时，先通过人工免疫算法对种群进行优劣选择， 这样在优秀粒子周围可变范围内产生一些随机粒 再通过标准粒子算法进行种群更新.虽然在种群多样 子，保证继承优秀的基础上又不缺乏多样性.这里可 性方面提高了很多，但是在进化初期粒子群种群多样 变范围也需要粒子最大浓度控制，当粒子最大浓度比 性充足时引入浓度机制和疫苗接种反而会降低种群的 较高时，需要增加搜索范围，使疫苗接种的粒子分散在 多样性.因此，需要在种群进化初期即多样性充足时 群体极值周围大范围内，增加种群多样性.当粒子最 减少人工免疫算法的作用，提高算法效率：在进化后期 大浓度比较低时，说明粒子群不缺乏多样性，需要减少 加大人工免疫算法作用，防止早熟停滞 搜索范围，使疫苗粒子在群体极值周围小范围寻找最 本文提出的自适应免疫粒子群算法采用并联方 优解 式，即在种群更新时，经典粒子群算法和人工免疫算法 具体实现方法是以群体极值为圆心，初始搜索范 是同时进行的.它将种群分为两个数目可变的子种群 围是以粒子群速度极V为半径的圆，之后在上一代 A和B.子种群A是保留那些适应度高浓度低的优秀 搜索范围的基础上改变，根据当前粒子最大浓度来控 粒子的种群，进行速度和位置更新，使整个种群朝着最 制搜索半径范围.搜索规则采用先验经验知识设置. 优解进化：子种群B是含有一些适应度差浓度高的劣 R(1)=Vs, (11)

张 超等: 基于自适应搜索的免疫粒子群算法 方式:一种是基于矢量矩的浓度机制,另一种是基于海 明距离的浓度机制. 基于海明距离是以抗体为出发点,比较抗体之间 的相似度从而判断相似抗体浓度,计算方法如式(4) 和式(5)所示. 籽(xi) = 移 M j = 1 1, 0郾 95臆 xi xj 臆1郾 01, 0, 其他 { . j = 1,2,…,M. (4) d(xi) = 籽(xi) M , i = 1,2,…,M. (5) 式中,籽(xi)是代表种群中有多少粒子与第 i 个粒子相 似的相似度值. 当粒子与某个粒子各个维度都相近 时,判定二者相近,取值为 1,否则为 0. d(xi)是第 i 个 粒子的浓度. 基于矢量矩是从抗体对抗原的抵抗力为出发点, 比较各个抗体对抗体的抗原反应,从而判断相似抗体 浓度,计算方法如下式所示: d(xi) = 移 M j = 1 | f(xi) - f(xj) | 移 M i = 1 移 M j = 1 | f(xi) - f(xj) | , i = 1,2,…,M. (6) 两种浓度机制都可以提高种群多样性,基于海明 距离的浓度机制比基于矢量矩的浓度机制更准确,但 也会消耗更多的时间. 1郾 2郾 3 浓度调节机制 当需要大量优秀抗体来代替劣质抗体时,疫苗接 种机制会将记忆库中的优秀抗体取出进行繁殖进化来 代替种群中的劣质抗体,提高种群质量. 2 自适应搜索免疫粒子群算法 2郾 1 算法基本思想 传统免疫粒子群算法通常采用串联方式,即在种 群更新时,先通过人工免疫算法对种群进行优劣选择, 再通过标准粒子算法进行种群更新. 虽然在种群多样 性方面提高了很多,但是在进化初期粒子群种群多样 性充足时引入浓度机制和疫苗接种反而会降低种群的 多样性. 因此,需要在种群进化初期即多样性充足时 减少人工免疫算法的作用,提高算法效率;在进化后期 加大人工免疫算法作用,防止早熟停滞. 本文提出的自适应免疫粒子群算法采用并联方 式,即在种群更新时,经典粒子群算法和人工免疫算法 是同时进行的. 它将种群分为两个数目可变的子种群 A 和 B. 子种群 A 是保留那些适应度高浓度低的优秀 粒子的种群,进行速度和位置更新,使整个种群朝着最 优解进化;子种群 B 是含有一些适应度差浓度高的劣 质粒子,对这些劣质粒子进行疫苗接种,将记忆细胞中 好的粒子进行繁殖代替这些劣质粒子. 这里使用粒子最大浓度值来控制子种群数量,子 种群 A 和 B 的种群数分别由式(7)和式(8)计算得出. popA = dmaxM. (7) popB = M - popA. (8) 式中,popA 是子种群 A 的个体数量;popB 是子种群 B 的个体数量;M 是初始种群个体数量,也是子种群 A 和 B 的总和;dmax是粒子最大浓度值. 当粒子分散时,整个粒子群多样性好,不容易陷入 局部最优,这个时候子种群 A 数量大些,子种群 B 数 量少些,使整个粒子群朝着最优解进化. 当粒子群过 于集中时,整个粒子群多样性差,容易陷入局部最优, 这个时候则子种群 B 数量大些,子种群 A 少些,确保 一部分优秀粒子进化的同时,另一部分劣质粒子去周 围搜寻,增大整个种群的多样性. 动态改变子种群数目相当于控制两种算法的作用 大小. 这样可以使种群过于拥挤时改善其多样性,使 种群始终朝着更好的方向进化. 2郾 2 自适应搜索的实现 传统免疫粒子群算法的接种方式都有所欠缺,如 果能将两种方式结合,在保证优秀粒子的情况下增加 随机性,这样能够在提高种群质量的同时,改善其多 样性. 自适应免疫粒子群算法采用两种接种方式相结合 的方式,在继承优秀粒子的基础上,添加一些随机范围 搜索. 结合方式是以记忆库中存入的 gbest 为中心,在 其周围随机范围搜索. Vaccine(xi) = gbest + range(t), i = 1,2,…,popB. (9) range(t) = rand 伊 R(t). (10) 式中,Vaccine 是接种疫苗,range( t) 是第 t 代搜索范 围,R(t)是第 t 代搜索半径. 可见每一个接种疫苗都 是落在群体极值周围的一个随机值. 这样在优秀粒子周围可变范围内产生一些随机粒 子,保证继承优秀的基础上又不缺乏多样性. 这里可 变范围也需要粒子最大浓度控制,当粒子最大浓度比 较高时,需要增加搜索范围,使疫苗接种的粒子分散在 群体极值周围大范围内,增加种群多样性. 当粒子最 大浓度比较低时,说明粒子群不缺乏多样性,需要减少 搜索范围,使疫苗粒子在群体极值周围小范围寻找最 优解. 具体实现方法是以群体极值为圆心,初始搜索范 围是以粒子群速度极 Vmax为半径的圆,之后在上一代 搜索范围的基础上改变,根据当前粒子最大浓度来控 制搜索半径范围. 搜索规则采用先验经验知识设置. R(1) = Vmax, (11) ·127·

·128· 工程科学学报，第39卷，第1期 1+n() 初始化粒子群所有M个个体 R(t)=R(t-1) (12) 1+m() 计算粒子群中各粒子亲和力 这里的m和n分别是搜索半径扩大数和缩小数， 他们共同决定着搜索半径的大小.t是最大迭代代 由亲和力计算出各粒子的 优秀粒子ghest 数.而控制m和n的是由一系列规则决定的，m和n 察殖率，并根据繁殖率排序 存入记忆库 的初始值为0 n(t-1)+2,ds>0.8; 察殖率高的部分N个 紧殖率低的部分(M-N)个 个体组成子种群A 个体被随机产生的个体 n(t)={n(t-1)+1,0.8≥ds>0.6;(13) 替代组成子种群B n(t-1), dn≤0.6. 子种群A更新位置和速度 对子种群B中的所有 m(t-1)+2,dm≤0.8； 粒子进行疫苗接种 m(t)={m(t-1)+1,0.2<dnm≤0.4；(14) 子种群A和子种群B组成 m(t-1),dn>0.4. 子种群C 当最大粒子浓度变大到一定程度时，说明整个种 群位置过于密集，多样性差.通过上面的规则，n增 种群C更新位置和 加，m不变，整个搜索半径增加：当最大粒子浓度适中 速度，计算适应度 时，说明种群位置适中，多样性好.保证n和m都不 文 否 变，搜索半径也基本不变；当最大粒子浓度偏低时，说 是否满足条件？> 明整个种群太过分散.通过以上规则，m不变，n增加， 是 整个搜索半径缩小.根据最大粒子浓度不断改变搜索 输出最优解，程序终止 半径，即增加了种群的多样性，同时也把粒子浓度维持 在一个合适的值. 图1自适应免疫粒子群算法流程 2.3算法流程 Fig.1 Flowchart of ASIPSO 该算法具体步骤如下，算法流程图如图1所示. Stepl建立一个种群数量为M的粒子群，并对粒 WIN7平台下的Intel(R)Core(TM)i3-330M处理器，3 子群的速度和位置进行初始化. GB内存.根据实验选择了粒子群算法最优参数，其中 Step2根据式(4)和式(5)计算初始种群各个粒 c1=c2=1.45,0从0.9到0.5梯度下降，种群规模和 子浓度，从而根据式(3)得到各粒子的亲和力.将群体 最大迭代代数分别为40和200.在相同条件下对以下 极值位置gbest赋值存入记忆库作为疫苗. 测试函数进行30次优化，评价指标分别是30次优化 Step3根据粒子的亲和力从高到低排序. 结果里的最优值、30次优化结果的平均值，30次优化 Step4根据粒子群的最大浓度值的大小，由式 结果里的最差值和30次优化结果的标准差.同时记 (7)和式(8)将父代种群分成两个子种群A和B.子 录算法运行时间. 种群A继承了父代亲和力高的粒子，子种群B由剩余 3.2仿真实验一 粒子组成 作为自适应免疫粒子群算法(ASPS0)的对比算 Step5子种群A通过式(1)和式(2)粒子群算法 法有经典粒子群算法和两个改进的免疫粒子群算法 的速度和位置更新公式进化，子种群B通过式(9)进 (IPS0和IPSO-DDT).实验结果如表1所示. 行疫苗接种 图2~图4是四种算法在Rastrigin函数2、5和10 Step6子种群A和子种群B合并形成新种群C. 维情况下的进化比较图.为了更方便显示算法的优化 Step7新种群C根据粒子群算法的速度和位置 精度，将y轴设为对数坐标 公式进化，形成新父代，更新个体极值和群体极值. 从2维、5维和10维的Rastrigin函数的优化结果 Step8群体极值是否满足循环退出条件，若满足 可以看出，四种算法中，自适应免疫粒子群算法无论从 算法停止运行并输出结果，否则跳转Step2. 最优解的平均值，还是最好解都要好于其他算法.粒 子群优化算法偶尔会陷入局部，优化结果次之.而改 3仿真实验 进的粒子群免疫优化算法和带有动态扰动的免疫粒子 3.1实验参数及环境 群算法从标准差可以看出它们的优化结果十分不稳 本文采用MATLAB2014进行仿真，运行环境为 定，易陷入局部最优，优化结果最差

工程科学学报,第 39 卷,第 1 期 R(t) = R(t - 1) 1 + n(t) tmax 1 + m(t) tmax . (12) 这里的 m 和 n 分别是搜索半径扩大数和缩小数, 他们共同决定着搜索半径的大小. tmax是最大迭代代 数. 而控制 m 和 n 的是由一系列规则决定的,m 和 n 的初始值为 0. n(t) = n(t - 1) + 2, dmax > 0郾 8; n(t - 1) + 1, 0郾 8逸dmax > 0郾 6; n(t - 1), dmax臆0郾 6 ì î í ïï ïï . (13) m(t) = m(t - 1) + 2, dmax臆0郾 8; m(t - 1) + 1, 0郾 2 < dmax臆0郾 4; m(t - 1), dmax > 0郾 4 ì î í ïï ïï . (14) 当最大粒子浓度变大到一定程度时,说明整个种 群位置过于密集,多样性差. 通过上面的规则,n 增 加,m 不变,整个搜索半径增加;当最大粒子浓度适中 时,说明种群位置适中,多样性好. 保证 n 和 m 都不 变,搜索半径也基本不变;当最大粒子浓度偏低时,说 明整个种群太过分散. 通过以上规则,m 不变,n 增加, 整个搜索半径缩小. 根据最大粒子浓度不断改变搜索 半径,即增加了种群的多样性,同时也把粒子浓度维持 在一个合适的值. 2郾 3 算法流程 该算法具体步骤如下,算法流程图如图 1 所示. Step1 建立一个种群数量为 M 的粒子群,并对粒 子群的速度和位置进行初始化. Step2 根据式(4)和式(5)计算初始种群各个粒 子浓度,从而根据式(3)得到各粒子的亲和力. 将群体 极值位置 gbest 赋值存入记忆库作为疫苗. Step3 根据粒子的亲和力从高到低排序. Step4 根据粒子群的最大浓度值的大小,由式 (7)和式(8)将父代种群分成两个子种群 A 和 B. 子 种群 A 继承了父代亲和力高的粒子,子种群 B 由剩余 粒子组成. Step5 子种群 A 通过式(1)和式(2)粒子群算法 的速度和位置更新公式进化,子种群 B 通过式(9) 进 行疫苗接种. Step6 子种群 A 和子种群 B 合并形成新种群 C. Step7 新种群 C 根据粒子群算法的速度和位置 公式进化,形成新父代,更新个体极值和群体极值. Step8 群体极值是否满足循环退出条件,若满足 算法停止运行并输出结果,否则跳转 Step2. 3 仿真实验 3郾 1 实验参数及环境 本文采用 MATLAB2014 进行仿真,运行环境为 图 1 自适应免疫粒子群算法流程 Fig. 1 Flowchart of ASIPSO WIN7 平台下的 Intel(R)Core( TM) i3鄄鄄330M 处理器,3 GB 内存. 根据实验选择了粒子群算法最优参数,其中 c1 = c2 = 1郾 45,棕 从 0郾 9 到 0郾 5 梯度下降,种群规模和 最大迭代代数分别为 40 和 200. 在相同条件下对以下 测试函数进行 30 次优化,评价指标分别是 30 次优化 结果里的最优值、30 次优化结果的平均值、30 次优化 结果里的最差值和 30 次优化结果的标准差. 同时记 录算法运行时间. 3郾 2 仿真实验一 作为自适应免疫粒子群算法(ASIPSO) 的对比算 法有经典粒子群算法和两个改进的免疫粒子群算法 (IIPSO 和 IPSO鄄鄄DDT). 实验结果如表 1 所示. 图 2 ~ 图 4 是四种算法在 Rastrigin 函数 2、5 和 10 维情况下的进化比较图. 为了更方便显示算法的优化 精度,将 y 轴设为对数坐标. 从 2 维、5 维和 10 维的 Rastrigin 函数的优化结果 可以看出,四种算法中,自适应免疫粒子群算法无论从 最优解的平均值,还是最好解都要好于其他算法. 粒 子群优化算法偶尔会陷入局部,优化结果次之. 而改 进的粒子群免疫优化算法和带有动态扰动的免疫粒子 群算法从标准差可以看出它们的优化结果十分不稳 定,易陷入局部最优,优化结果最差. ·128·

张超等：基于自适应搜索的免疫粒子群算法 ·129· 表1各个算法对于25和10维Rastrigin函数测试结果 Table 1 Results of each algorithm for Rastrigin(2,5 and 10 dimensions) 维度 优化算法 平均值 最优解 最差解 标准差 时间/s PSO 0.1244 0 0.9950 0.3518 0.316 IIPSO 0.2317 0 0.9950 0.4138 1.153 IPSO-DDT 3.1047 1.1653 4.9925 1.3091 0.950 ASIPSO 0 0 0 0 0.562 PSO 2.8191 0.9950 5.9697 1.6881 0.482 IIPSO 22.8191 8.9386 28.7093 5.3412 0.940 IPSO-DDT 20.9710 8.9143 28.7419 7.1436 1.047 ASIPSO 0.1811 0 1.1379 0.4155 1.154 PSO 12.2803 4.9748 16.6831 3.5379 0.499 IPSO 82.3933 77.3699 87.8156 3.6598 1.013 IPSO-DDT 27.0019 27.0665 27.3421 30.9854 1.214 ASIPSO 4.7684 3.0311 7.3549 1.3352 1.680 10 ---pS0 120 ---PS0 --IIPSO ----IIPSO IPSO-DDT 100 …IPS0-DDT 10 ASIPSO ASIPSO 10- 60t 40 10-0 20 10- 20406080100120140160180200 20406080100120140160180200 进化代数 进化代数 图2四种算法2维进化比较 图4四种算法10维进化比较图 Fig.2 Comparison of four algorithms (2D) Fig.4 Comparison of four algorithms (10D) 10 变不同类型的测试函数，不同的测试维度，多方面进行 测试，测试函数由单峰单谷到多峰多谷 表2给出了七个测试函数的名称、表达式、取值范 10 围和最优解，测试函数是由单峰连续函数和多峰多谷 复杂函数组成.其中，∫~是常用的单峰测试函数； 10- ∫。~，都是多峰多谷的复杂函数，容易造成算法陷入局 ---PS0 部最优导致停滞，均是难度较大的测试函数，能够有效 10 ---IIPSO -IPSO-DDT 测试自适应免疫粒子群算法的性能 ASIPSO 从整体优化结果（表3和图5~图11）来看，自适 10 0204060 80100120140160180200 应免疫粒子群算法的平均优化结果都普遍好于其他三 进化代数 种算法，粒子群优化算法次之，改进的粒子群免疫优化 图3四种算法5维进化比较 算法和带有动态扰动的免疫粒子群算法优化结果最 Fig.3 Comparison of four algorithms (5D) 差.其中，在单峰测试函数∫~中，粒子群优化算法 从时间开销方面来看，粒子群优化算法运算时间 有较高的优化精度，自适应免疫粒子群算法优化精度 最短，三种融合算法运算时间都有所增加，其中自适应 与之接近，部分函数好于粒子群优化算法，改进的粒子 免疫粒子群算法在高维度下运行时间最长 群免疫优化算法和带有动态扰动的免疫粒子群算法优 3.3仿真实验二 化精度略低.在多峰测试函数~，中，粒子群优化算 仿真实验一通过一个多峰多谷的测试函数的实 法优化结果精度降低，改进的粒子群免疫优化算法和 验，证明自适应免疫粒子群算法的有效性.接下来，改 带有动态扰动的免疫粒子群算法在某些函数好于粒子

张 超等: 基于自适应搜索的免疫粒子群算法 表 1 各个算法对于 2、5 和 10 维 Rastrigin 函数测试结果 Table 1 Results of each algorithm for Rastrigin (2, 5 and 10 dimensions) 维度 优化算法 平均值 最优解 最差解 标准差 时间/ s 2 PSO 0郾 1244 0 0郾 9950 0郾 3518 0郾 316 IIPSO 0郾 2317 0 0郾 9950 0郾 4138 1郾 153 IPSO鄄鄄DDT 3郾 1047 1郾 1653 4郾 9925 1郾 3091 0郾 950 ASIPSO 0 0 0 0 0郾 562 5 PSO 2郾 8191 0郾 9950 5郾 9697 1郾 6881 0郾 482 IIPSO 22郾 8191 8郾 9386 28郾 7093 5郾 3412 0郾 940 IPSO鄄鄄DDT 20郾 9710 8郾 9143 28郾 7419 7郾 1436 1郾 047 ASIPSO 0郾 1811 0 1郾 1379 0郾 4155 1郾 154 10 PSO 12郾 2803 4郾 9748 16郾 6831 3郾 5379 0郾 499 IIPSO 82郾 3933 77郾 3699 87郾 8156 3郾 6598 1郾 013 IPSO鄄鄄DDT 27郾 0019 27郾 0665 27郾 3421 30郾 9854 1郾 214 ASIPSO 4郾 7684 3郾 0311 7郾 3549 1郾 3352 1郾 680 图 2 四种算法 2 维进化比较 Fig. 2 Comparison of four algorithms (2D) 图 3 四种算法 5 维进化比较 Fig. 3 Comparison of four algorithms (5D) 从时间开销方面来看,粒子群优化算法运算时间 最短,三种融合算法运算时间都有所增加,其中自适应 免疫粒子群算法在高维度下运行时间最长. 3郾 3 仿真实验二 仿真实验一通过一个多峰多谷的测试函数的实 验,证明自适应免疫粒子群算法的有效性. 接下来,改 图 4 四种算法 10 维进化比较图 Fig. 4 Comparison of four algorithms (10D) 变不同类型的测试函数,不同的测试维度,多方面进行 测试,测试函数由单峰单谷到多峰多谷. 表 2 给出了七个测试函数的名称、表达式、取值范 围和最优解,测试函数是由单峰连续函数和多峰多谷 复杂函数组成. 其中,f 1 ~ f 3是常用的单峰测试函数; f 4 ~ f 7都是多峰多谷的复杂函数,容易造成算法陷入局 部最优导致停滞,均是难度较大的测试函数,能够有效 测试自适应免疫粒子群算法的性能. 从整体优化结果(表 3 和图 5 ~ 图 11)来看,自适 应免疫粒子群算法的平均优化结果都普遍好于其他三 种算法,粒子群优化算法次之,改进的粒子群免疫优化 算法和带有动态扰动的免疫粒子群算法优化结果最 差. 其中,在单峰测试函数 f 1 ~ f 3中,粒子群优化算法 有较高的优化精度,自适应免疫粒子群算法优化精度 与之接近,部分函数好于粒子群优化算法,改进的粒子 群免疫优化算法和带有动态扰动的免疫粒子群算法优 化精度略低. 在多峰测试函数 f 4 ~ f 7中,粒子群优化算 法优化结果精度降低,改进的粒子群免疫优化算法和 带有动态扰动的免疫粒子群算法在某些函数好于粒子 ·129·