工程科学学报，第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.20.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 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·
·130· 工程科学学报，第39卷，第1期 表2人~f方测试函数 Table 2 Test functionsf 测试函数 函数公式 取值范围 最优解 Sphere函数 -龙f [-100,100] 0 Stcp函数 )=21 [-10,10] 0 Rosenbrock函数 a=2m(--门 [-2.48,2.48] 0 Ackley函数 -0.4√.-m2+e+20 [-32,32] Schwefe函数 fx)=418.4829D- [-500.500] Alpine函数 )=25,m+0.1l [-10,10] m-5 2 Schaffer函数 f八x)=0.5+ i-1 [-10,10] +0.001 表3斤~方优化结果 Table 3 Optimized results of test functions 参数 Sphere Step Rosenbrock Ackley Schwefel Alpine Schaffer 算法 (2维) (5维) (10维) (2维) (2维) (5维) (10维) 平均值 3.68×10-211.57×10-2 2.79×10-44.63×10-1 3.7435 1.01×10-7 2.30×10-2 PSO 最优值 2.07×10-23 2.40×10-25.6647×10-i5 1.21×10-1 2.54×10-5 1.58×10-8 9.70×10-3 时间/s 0.577 0.530 0.477 0.477 0.582 0.453 0.482 平均值 5.51×105 4.97×10-4 6.38×10-3 1.4297 0.35204 1.4319 6.18×10-2 IIPSO 最优值 5.12×10-8 9.89×10-5 2.28×10-3 0.70138 0.19266 0.92589 1.07×10-2 时间/s 1.025 0.958 0.919 0.937 0.957 0.933 0.907 平均值 3.37×10-3 1.18×10-3 1.66×10-2 1.5969 7.31×10-3 1.0604 3.98×10-2 IPSO-DDT 最优值 1.25×10-5 3.87×10-5 1.43×10-2 0.14529 1.39×10-3 0.92589 3.13×10-2 时间/s 0.807 0.993 0.957 0.988 0.614 0.984 0.991 平均值8.51×10-45 2.13×10-36 4.91×10-3 4.28×10-5 5.43×10-0 3.16×10-2 ASIPSO 最优值 9.09×10-46 3.28×10-39 2.817×10-4 0 2.54×10-5 4.34×10-11 9.70×10-3 时间/s 1.112 1.229 1.649 0.978 1.068 1.237 1.683 群优化算法，自适应免疫粒子群算法始终好于粒子群 并且控制接种疫苗的搜索范围，提高了算法的局部搜 优化算法. 索能力，避免传统免疫粒子群融合算法的种群退化现 从运行时间来看，粒子群优化算法最快，改进的粒 象，保证算法的优化精度，因此优化结果精度较高. 子群免疫优化算法和带有动态扰动的免疫粒子群算法 在优化多峰复杂函数过程中，粒子群优化算法容 次之，自适应免疫粒子群算法最慢 易陷入局部最优，导致算法停滞。因此对于某些复杂 3.4实验结果分析 函数（如f测试函数：Schwefel函数）平均优化结果并 在优化单峰测试函数的过程中，粒子群优化算法 不高.带有动态扰动的免疫粒子群算法和自适应免疫 不会因为局部最优而陷入早熟停滞，因此优化结果精 粒子群算法这两个融合算法由于加入疫苗接种机制， 度较高，而改进的粒子群免疫优化算法和带有动态扰 增加了整个种群的多样性，使种群跳出局部最优，一定 动的免疫粒子群算法都采用完全随机的疫苗接种机 程度避免算法在进化过程中因为陷入局部最优而停 制，从某种程度上降低算法的局部搜索能力，造成种群 止.但盲目的随机接种机制使优化结果也充满随机 退化，所以平均优化结果精度比粒子群优化算法差. 性，可能造成种群初期从一个局部最优跳入另一个局 自适应免疫粒子群算法是由浓度控制种群接种数量， 部最优，因此平均优化结果并不理想，很多时候比粒子
工程科学学报,第 39 卷,第 1 期 表 2 f1 ~ f7测试函数 Table 2 Test functions f1 ~ f7 测试函数 函数公式 取值范围 最优解 Sphere 函数 f(x) = 移 D i = 1 x 2 i [ - 100,100] 0 Step 函数 f(x) = 移 D i = 1 | xi | i + 1 [ - 10,10] 0 Rosenbrock 函数 f(x) = 移 D-1 i = 1 [100 (x 2 i - xi + 1 ) 2 + (xi - 1) 2 ] [ - 2郾 48,2郾 48] 0 Ackley 函数 f(x) = - 20 e -0郾 2 1 D 移 D i = 1 x2 i - e 1 D 移 D i = 1 cos (2仔xi )2 + e + 20 [ - 32,32] 0 Schwefel 函数 f(x) = 418郾 4829D - 移 D i = 1 xi sin | xi | [ - 500,500] 0 Alpine 函数 f(x) = 移 D i = 1 | xi sin xi + 0郾 1xi | [ - 10,10] 0 Schaffer 函数 f(x) ( = 0郾 5 + sin 移 D i = 1 x 2 i ) 2 - [ 0郾 5 1 + 0郾 001 ( 移 D i = 1 x 2 i ) ] 2 [ - 10,10] 0 表 3 f1 ~ f7优化结果 Table 3 Optimized results of test functions f1 ~ f7 算法 参数 Sphere (2 维) Step (5 维) Rosenbrock (10 维) Ackley (2 维) Schwefel (2 维) Alpine (5 维) Schaffer (10 维) 平均值 3郾 68 伊 10 - 21 1郾 57 伊 10 - 22 2郾 79 伊 10 - 14 4郾 63 伊 10 - 11 3郾 7435 1郾 01 伊 10 - 7 2郾 30 伊 10 - 2 PSO 最优值 2郾 07 伊 10 - 23 2郾 40 伊 10 - 23 5郾 6647 伊 10 - 15 1郾 21 伊 10 - 11 2郾 54 伊 10 - 5 1郾 58 伊 10 - 8 9郾 70 伊 10 - 3 时间/ s 0郾 577 0郾 530 0郾 477 0郾 477 0郾 582 0郾 453 0郾 482 平均值 5郾 51 伊 10 - 5 4郾 97 伊 10 - 4 6郾 38 伊 10 - 3 1郾 4297 0郾 35204 1郾 4319 6郾 18 伊 10 - 2 IIPSO 最优值 5郾 12 伊 10 - 8 9郾 89 伊 10 - 5 2郾 28 伊 10 - 3 0郾 70138 0郾 19266 0郾 92589 1郾 07 伊 10 - 2 时间/ s 1郾 025 0郾 958 0郾 919 0郾 937 0郾 957 0郾 933 0郾 907 平均值 3郾 37 伊 10 - 3 1郾 18 伊 10 - 3 1郾 66 伊 10 - 2 1郾 5969 7郾 31 伊 10 - 3 1郾 0604 3郾 98 伊 10 - 2 IPSO鄄鄄DDT 最优值 1郾 25 伊 10 - 5 3郾 87 伊 10 - 5 1郾 43 伊 10 - 2 0郾 14529 1郾 39 伊 10 - 3 0郾 92589 3郾 13 伊 10 - 2 时间/ s 0郾 807 0郾 993 0郾 957 0郾 988 0郾 614 0郾 984 0郾 991 平均值 8郾 51 伊 10 - 45 2郾 13 伊 10 - 36 4郾 91 伊 10 - 13 0 4郾 28 伊 10 - 5 5郾 43 伊 10 - 10 3郾 16 伊 10 - 2 ASIPSO 最优值 9郾 09 伊 10 - 46 3郾 28 伊 10 - 39 2郾 817 伊 10 - 14 0 2郾 54 伊 10 - 5 4郾 34 伊 10 - 11 9郾 70 伊 10 - 3 时间/ s 1郾 112 1郾 229 1郾 649 0郾 978 1郾 068 1郾 237 1郾 683 群优化算法,自适应免疫粒子群算法始终好于粒子群 优化算法. 从运行时间来看,粒子群优化算法最快,改进的粒 子群免疫优化算法和带有动态扰动的免疫粒子群算法 次之,自适应免疫粒子群算法最慢. 3郾 4 实验结果分析 在优化单峰测试函数的过程中,粒子群优化算法 不会因为局部最优而陷入早熟停滞,因此优化结果精 度较高,而改进的粒子群免疫优化算法和带有动态扰 动的免疫粒子群算法都采用完全随机的疫苗接种机 制,从某种程度上降低算法的局部搜索能力,造成种群 退化,所以平均优化结果精度比粒子群优化算法差. 自适应免疫粒子群算法是由浓度控制种群接种数量, 并且控制接种疫苗的搜索范围,提高了算法的局部搜 索能力,避免传统免疫粒子群融合算法的种群退化现 象,保证算法的优化精度,因此优化结果精度较高. 在优化多峰复杂函数过程中,粒子群优化算法容 易陷入局部最优,导致算法停滞. 因此对于某些复杂 函数(如 f 5测试函数:Schwefel 函数)平均优化结果并 不高. 带有动态扰动的免疫粒子群算法和自适应免疫 粒子群算法这两个融合算法由于加入疫苗接种机制, 增加了整个种群的多样性,使种群跳出局部最优,一定 程度避免算法在进化过程中因为陷入局部最优而停 止. 但盲目的随机接种机制使优化结果也充满随机 性,可能造成种群初期从一个局部最优跳入另一个局 部最优,因此平均优化结果并不理想,很多时候比粒子 ·130·
张超等：基于自适应搜索的免疫粒子群算法 ·131· 10 10 10 10-1D 10- 10-s ---1) ---PS0 10-0 -----IIPS0 ---IIPSO -IPSO-DDT 10 IPSO-DDT 100 ASIPSO 10-0 10-is 020406080100120140160180200 020406080100120140160180200 进化代数 进化代数 图5四种算法Sphere(2维)进化比较 图8四种算法Ackley(2维)进化比较 Fig.5 Comparison of 4 algorithms for Sphere (2D) Fig.8 Comparison of 4 algorithms for Ackley (2D) 100 10 10 10 10- 10 ---PS0 ---PS0 型100 2102 …IPSO-DD'T ---PS0 ASIPSO HIPSO …PSO-DDT 100 10 一ASIPS0 10 20406080100120140160180200 10-6 0 020406080100120140160180200 进化代数 进化代数 图6四种算法Stcp(5维)进化比较 图9四种算法Schwefel(2维)进化比较 Fig.6 Comparison of 4 algorithms for Step (2D) Fig.9 Comparison of 4 algorithms for Schwefel (2D) 105 102 10m 10 102 10 10+ ---PS0 ---PS0 ----IIPSO 10 -----IIPSO 10-0 IPSO-DDT -IPSO-DDT -ASIPSO 10-8 -ASIPSO 10-5 020406080100120140160180200 101e 020.406080100120140160180200 进化代数 进化代数 图7四种算法Rosenbrock(10维)进化比较 图10四种算法Alpine(5维)进化比较 Fig.7 Comparison of 4 algorithms for Rosenbrock (10D) Fig.10 Comparison of 4 algorithms for Alpine (5D) 群优化算法优化结果要差.自适应免疫粒子群算法采 在运行时间上，融合算法由于加入浓度调节机制 用由最大粒子浓度控制的并联融合机制和自适应免疫 和疫苗接种机制，导致整个算法复杂性增加，运行时间 搜索的免疫接种机制，动态地平衡算法的全局搜索能 变长.改进的粒子群免疫优化算法和带有动态扰动的 力和局部搜索能力.在处理复杂优化问题时，在保证 免疫粒子群算法的浓度计算机制是基于矢量距的浓度 局部搜索能力的情况下又不失全局搜索能力，有较高 计算方法.它们的运行时间是粒子群优化算法的1~2 优化精度. 倍，不会随着维度增加而大幅增加.而自适应免疫粒
张 超等: 基于自适应搜索的免疫粒子群算法 图 5 四种算法 Sphere (2 维)进化比较 Fig. 5 Comparison of 4 algorithms for Sphere (2D) 图 6 四种算法 Step (5 维)进化比较 Fig. 6 Comparison of 4 algorithms for Step (2D) 图 7 四种算法 Rosenbrock (10 维)进化比较 Fig. 7 Comparison of 4 algorithms for Rosenbrock (10D) 群优化算法优化结果要差. 自适应免疫粒子群算法采 用由最大粒子浓度控制的并联融合机制和自适应免疫 搜索的免疫接种机制,动态地平衡算法的全局搜索能 力和局部搜索能力. 在处理复杂优化问题时,在保证 局部搜索能力的情况下又不失全局搜索能力,有较高 优化精度. 图 8 四种算法 Ackley (2 维)进化比较 Fig. 8 Comparison of 4 algorithms for Ackley (2D) 图 9 四种算法 Schwefel (2 维)进化比较 Fig. 9 Comparison of 4 algorithms for Schwefel (2D) 图 10 四种算法 Alpine (5 维)进化比较 Fig. 10 Comparison of 4 algorithms for Alpine (5D) 在运行时间上,融合算法由于加入浓度调节机制 和疫苗接种机制,导致整个算法复杂性增加,运行时间 变长. 改进的粒子群免疫优化算法和带有动态扰动的 免疫粒子群算法的浓度计算机制是基于矢量距的浓度 计算方法. 它们的运行时间是粒子群优化算法的 1 ~ 2 倍,不会随着维度增加而大幅增加. 而自适应免疫粒 ·131·
·132· 工程科学学报，第39卷，第1期 1 参考文献 ---PS0 ---PS0 [1]Kennedy J,Eberhart R.Particle swarm optimization /Proceed- -IPSO-DDT ing of IEEE International Conference on Neural Neteorks.Nagoya, -ASIPSO 1995:1942 10 [2]Sui C H.The Research of Particle Swarm Optimization Algorithm Improvement Dissertation ]Chengdu:Southwest Jiaotong Univer- sity,2010 10-2 (随聪慧.粒子群算法的改进方法研究[学位论文].成都：西 南交通大学，2010) [3]Khare A,Rangekar S.A review of particle swarm optimization and its applications in Solar Photovoltaic system.Appl Sof Comput, 1002040608010120140160180200 2013,13(5):2997 进化代数 [4]Deng G F,Zhang X P,Liu Y P.Ant colony optimization and par- 图11四种算法Schaffer(10维)进化比较 ticle swarm optimization for robot-path planning in obstacle envi- Fig.11 Comparison of 4 algorithms for Schaffer (10D) ronment.Control Theory Appl,2009.26(8):879 (邓高峰，张雪萍，刘彦葬.一种障碍环境下机器人路径规划 子群算法采用浓度计算机制是基于海明距离的浓度计 的蚊群粒子群算法.控制理论与应用，2009,26(8)：879) 算方法，虽然更加形象准确地计算了粒子的浓度，但算 [5]Zhou X C,Zhao Z X,Zhou K J,et al.Remanufacturing closed- 法的运算量会随着维度的增加而大幅增加.2维运行 loop supply chain network design base on genetic particle swarm 时间是粒子群优化算法的2倍，10维运行时间是粒子 optimization algorithm.Cent South Univ,2012,19(2):482 群优化算法的3倍.因此自适应免疫粒子群算法适用 [6] Gao Y,Xie S L.Particle swarm optimization algorithms with im- 于对时间开销要求不高的复杂优化问题 munity.Comput Eng Appl,2004,40(6):4 (高鹰，谢胜利.免疫粒子群优化算法.计算机工程与应用， 4结论 2004,40(6):4) [7]Woldemariam K M,Yen GG.Vaccine-enhanced artificial im- 本文在对应用广泛的经典粒子群算法和传统免疫 mune system for multimodal function optimization.IEEE Trans 粒子群算法进行深入剖析的基础上，从融合方式和接 Syst Man Cybern Part B,2010,40(1):218 种机制两个方面进行改进.针对经典粒子群算法的早 [8]Giardini G,Kalmar-Nagy T.Genetic algorithm for multi-agent 熟停滞现象和传统免疫粒子群算法的种群退化现象， space exploration//2007 AIAA InfoTech at Aerospace Conference. California,2007 本文提出一种基于自适应搜索的免疫粒子群优化算 [9]Li M J.Luo A,Tong TS.Artificial immune algorithm and its ap- 法.实验结果表明： plications.Control Theory Appl,2004,21(2):153 (1)对于单峰低维测试函数，自适应免疫粒子群 (李茂军，罗安，童调生.人工免疫算法及其应用研究.控制 算法相比于其他算法有很高的优化精度和不错的稳定 理论与应用，2004.21(2)：153) 性，时间开销适中； [10]Liu F,Peng B.Immune particle swarm optimization beats genet- (2)对于单峰高维测试函数，自适应免疫粒子群 ic algorithms //2010 Second WRI Global Congress on Intelligent Systems GCIS).New York,2010:233 算法的优化精度与粒子群优化算法接近，但时间开销 [11]Han L.The Study of Immune Particle Swarm Optimization Algo- 远超传统算法： rithm and Its Application [Dissertation].Xi'an:Xi'an Polytech- (3)对于多峰低维测试函数，自适应免疫粒子群 nic University,2008 算法从一定程度上克服了传统算法陷入局部最优的缺 (韩琳.免疫粒子群算法研究及其应用[学位论文].西安： 陷，有较高的收敛精度和稳定性，运行时间也适中： 西安工程大学，2008) (4)对于多峰高维测试函数，自适应免疫粒子群 [12]Wang H L.Soccer Robot Path Planning Based on Particle Swarm 算法依旧有较高的收敛精度和稳定性，时间开销依然 Optimization Immune Algorithm Dissertation].Chengdu:Xihua University,2013 比较大 (王宏亮.基粒子群免疫算法的足球机器人路径规划[学位 综上所述，自适应免疫粒子群算法无论对于单峰 论文].成都：西华大学，2013) 问题还是多峰问题都有很高的收敛精度，但对于高维 [13]Sun C Y.Research on Hybrid Flowshop Scheduling Problem based 度的优化问题，其精度保证是以牺牲时间开销为代价. on Immune Particle Swarm Optimization Dissertation].Harbin: 因此，自适应免疫粒子群算法适用于多峰低维的复杂 Harbin University of Science and Technology,2012 优化问题和多峰高维的离线优化问题. (孙春宇.基于免疫粒子群算法的混合流水车间调度问题研 究[学位论文].哈尔滨：哈尔滨理工大学，2012)
工程科学学报,第 39 卷,第 1 期 图 11 四种算法 Schaffer (10 维)进化比较 Fig. 11 Comparison of 4 algorithms for Schaffer (10D) 子群算法采用浓度计算机制是基于海明距离的浓度计 算方法,虽然更加形象准确地计算了粒子的浓度,但算 法的运算量会随着维度的增加而大幅增加. 2 维运行 时间是粒子群优化算法的 2 倍,10 维运行时间是粒子 群优化算法的 3 倍. 因此自适应免疫粒子群算法适用 于对时间开销要求不高的复杂优化问题. 4 结论 本文在对应用广泛的经典粒子群算法和传统免疫 粒子群算法进行深入剖析的基础上,从融合方式和接 种机制两个方面进行改进. 针对经典粒子群算法的早 熟停滞现象和传统免疫粒子群算法的种群退化现象, 本文提出一种基于自适应搜索的免疫粒子群优化算 法. 实验结果表明: (1) 对于单峰低维测试函数,自适应免疫粒子群 算法相比于其他算法有很高的优化精度和不错的稳定 性,时间开销适中; (2) 对于单峰高维测试函数,自适应免疫粒子群 算法的优化精度与粒子群优化算法接近,但时间开销 远超传统算法; (3) 对于多峰低维测试函数,自适应免疫粒子群 算法从一定程度上克服了传统算法陷入局部最优的缺 陷,有较高的收敛精度和稳定性,运行时间也适中; (4) 对于多峰高维测试函数,自适应免疫粒子群 算法依旧有较高的收敛精度和稳定性,时间开销依然 比较大. 综上所述,自适应免疫粒子群算法无论对于单峰 问题还是多峰问题都有很高的收敛精度,但对于高维 度的优化问题,其精度保证是以牺牲时间开销为代价. 因此,自适应免疫粒子群算法适用于多峰低维的复杂 优化问题和多峰高维的离线优化问题. 参 考 文 献 [1] Kennedy J, Eberhart R. Particle swarm optimization / / Proceed鄄 ing of IEEE International Conference on Neural Networks. Nagoya, 1995: 1942 [2] Sui C H. The Research of Particle Swarm Optimization Algorithm Improvement [Dissertation]. Chengdu: Southwest Jiaotong Univer鄄 sity, 2010 (随聪慧. 粒子群算法的改进方法研究[学位论文]. 成都: 西 南交通大学, 2010) [3] Khare A, Rangekar S. A review of particle swarm optimization and its applications in Solar Photovoltaic system. Appl Soft Comput, 2013, 13(5): 2997 [4] Deng G F, Zhang X P, Liu Y P. Ant colony optimization and par鄄 ticle swarm optimization for robot鄄path planning in obstacle envi鄄 ronment. Control Theory Appl, 2009, 26(8): 879 (邓高峰, 张雪萍, 刘彦萍. 一种障碍环境下机器人路径规划 的蚁群粒子群算法. 控制理论与应用, 2009, 26(8): 879) [5] Zhou X C, Zhao Z X, Zhou K J, et al. Remanufacturing closed鄄 loop supply chain network design base on genetic particle swarm optimization algorithm. J Cent South Univ, 2012, 19(2): 482 [6] Gao Y, Xie S L. Particle swarm optimization algorithms with im鄄 munity. Comput Eng Appl, 2004, 40(6): 4 (高鹰, 谢胜利. 免疫粒子群优化算法. 计算机工程与应用, 2004, 40(6): 4) [7] Woldemariam K M, Yen G G. Vaccine鄄enhanced artificial im鄄 mune system for multimodal function optimization. IEEE Trans Syst Man Cybern Part B, 2010, 40(1): 218 [8] Giardini G, Kalmar鄄Nagy T. Genetic algorithm for multi鄄agent space exploration / / 2007 AIAA InfoTech at Aerospace Conference. California, 2007 [9] Li M J, Luo A, Tong T S. Artificial immune algorithm and its ap鄄 plications. Control Theory Appl, 2004, 21(2): 153 (李茂军, 罗安, 童调生. 人工免疫算法及其应用研究. 控制 理论与应用, 2004, 21(2): 153) [10] Liu F, Peng B. Immune particle swarm optimization beats genet鄄 ic algorithms / / 2010 Second WRI Global Congress on Intelligent Systems (GCIS). New York, 2010: 233 [11] Han L. The Study of Immune Particle Swarm Optimization Algo鄄 rithm and Its Application [Dissertation]. Xi蒺an: Xi蒺an Polytech鄄 nic University, 2008 (韩琳. 免疫粒子群算法研究及其应用[学位论文]. 西安: 西安工程大学, 2008) [12] Wang H L. Soccer Robot Path Planning Based on Particle Swarm Optimization Immune Algorithm [Dissertation]. Chengdu: Xihua University, 2013 (王宏亮. 基粒子群免疫算法的足球机器人路径规划[学位 论文]. 成都: 西华大学, 2013) [13] Sun C Y. Research on Hybrid Flowshop Scheduling Problem based on Immune Particle Swarm Optimization [Dissertation]. Harbin: Harbin University of Science and Technology, 2012 (孙春宇. 基于免疫粒子群算法的混合流水车间调度问题研 究[学位论文]. 哈尔滨: 哈尔滨理工大学, 2012) ·132·
