基于全局粒子群的协作型人工免疫网络优化算法

基于全局粒子群的协作型人工免疫网络优化算法

1协作型人工免疫网络模型ais是一种软计算方法，用于模拟生物网络系统以抵制病源生物的强大信息能力，并在故障诊断和参数优化等研究领域报告良好的性能。人工防疫网络（ain）是一种基于独立免疫网络理论的人工防疫系统模型。模拟免疫储存通过b细胞之间的相互作用进行。细胞间的抑制作用产生了网络适应机制，网络存储结构的稳定。现在，ain技术主要用于多个领域，尤其是在各种模型函数优化、动态优化和方案优化方面，并表现出全球优秀的整体评估能力。然而，ain算法的快速收敛主要表现为：基于多模优化、动态优化和方案优化，这需要网络抑制。为了避免算法的早期收敛，传统的方法增加了克隆选择过程的变异率，降低了网络抑制的阈值，并保持了免疫网络中存储细胞的多样性。然而，我们面临的风险是，算法的收敛速度缓慢，搜索精度低。本文提出协作型人工免疫网络模型(CooperativeArtificialImmuneNetworkModel,CoAIN),通过增加免疫记忆细胞间的协作,相互借鉴寻优的历史经验,加快算法的搜索速度,提高记忆细胞的多样性.这种免疫网络细胞间既相互竞争又相互协作的机制符合自然界免疫系统的运行模式.例如,在机体免疫系统中,B淋巴细胞和T淋巴细胞协同起来识别抗原;生物免疫领域的研究发现TLRs、NLRs和RLRs受体传感器之间协作完成天然免疫功能.此外,提出可变步长的克隆选择过程以提高算法的搜索精度.在协作算子的设计中,模拟群体智能算法的个体协作机制,即单个不具备智能的自然生物通过群体行为表现出整个生物群体的智能性,能够处理复杂问题.其中,粒子群优化(PSO)算法简单且容易实现,收敛速度快,与AIS具有良好的互补性.目前,PSO与AIS算法的结合可以分为两大方向:1)将AIS中的某些特性加入PSO算法中,以改进PSO算法容易陷入局部极值点的缺陷,这种算法被称为免疫粒子群算法,如高鹰等人将免疫记忆、免疫接种分别应用于粒子群优化算法中,以加快粒子群算法的进化速度;孙逊等人将基于浓度的抗体繁殖策略用于粒子群优化算法中.2)用PSO改进免疫算法的克隆选择过程,如Fu等人用PSO改造免疫细胞的变异操作,提出HaiNet人工免疫网络;Lin用混沌PSO改进免疫算法的变异机制.我们认为,充分发挥人工免疫网络的特性能够提高算法处理复杂优化问题的能力.粒子群算法相比更简单、参数少、收敛速度快,因此更适宜作为算子引入AIN中,以提高算法的寻优能力.本文实现基于全局粒子群的协作型人工免疫网络(GlobalPSOBasedCooperativeArtificialImmuneNetwork,gpso-CoAIN),提出记忆细胞的可变步长的克隆选择过程,以提高算法的搜索精度.保留人工免疫网络的网络抑制过程,移除高浓度的免疫记忆细胞,控制网络规模.这样保持下来的记忆细胞记录了局部搜索的最优信息.随后,实现全局粒子群协作算子,免疫记忆细胞根据同伴的寻优结果结合自身寻优经历,生成新的记忆细胞.与现有的PSO混合AIS的算法不同,协作算子只对经过网络抑制后的记忆细胞执行粒子群操作,因此降低算法的时间开销.实验中,gpso-CoAIN算法用于多模函数优化,与opt-aiNet人工免疫网络,B细胞免疫算法(B-CellImmuneAlgorithm,BCA),混合遗传算法(HybridGeneticAlgorithm,HGA)和粒子群优化算法(PSO)相比,在寻优能力以及执行速度方面都表现良好.2协作型人工免疫网络模型协同进化论认为某些生物种属的进化与另一些生物种属的进化相互关联、相互受益,既表现为不同物种、不同个体之间的相互受益,也表现为不同物种、不同个体之间的相互制约.下面给出两个定义.定义1(共生)指两个个体(A,B)间的一种关系,其中的一个个体A的适应度直接受到另一个个体B的影响.这里提到的适应度是一个个体广义的、全局的适应度.定义2(协同进化)种群内部的协同进化是指个体与同种群内的其他个体属于共生关系的状态;种群之间的协同进化是指某一种群内的个体与其它种群内的个体属于共生关系.本文的协作是指种群内部个体之间的协同进化,意与种群间的协同进化加以区别.基于这一假设和免疫网络理论,建立了协作型人工免疫网络模型(CooperativeArtificialImmuneNetwork,CoAIN).CoAIN中的记忆细胞代表函数优化问题的一个可行解.以求函数最大值的优化问题为例,记忆细胞的适应度对应于可行解的函数值,值越高代表它所编码的函数解越接近优化目标.克隆、变异、精英选择这3个步骤组成的可变步长的克隆选择过程,完成记忆细胞的局部寻优,这是人工免疫系统种群进化的主要方式.新一代的网络细胞竞争生存权,通过网络抑制过程控制网络的规模.保持下来的记忆细胞执行协作操作,交流历史寻优经验,提高自身的适应度.最后,网络中随机产生新的记忆细胞并更新部分低适应度的记忆细胞.CoAIN模型的执行过程如下所示.step1初始化.随机生成记忆细胞M(0).step2克隆扩增.对第n代记忆细胞M(n)中的每个记忆细胞m根据适应度值进行克隆,产生克隆细胞种群C.step3变异.计算变异步长,对克隆细胞种群C执行变异产生成熟细胞种群C′.step4精英选择.对成熟抗体C′计算适应度,适应度最高的个体替换记忆细胞m,对每个记忆细胞循环执行step2～step4.step5网络抑制.评价更新后的记忆细胞之间的相似度,将与适应度高的记忆细胞相似的低适应度记忆细胞清除,余下的记忆细胞记作S(n+1).step6网络协作.在S(n+1)上执行协作算子,生成高适应度的记忆细胞加入S(n+1),形成新一代M(n+1).step7动态更新.随机生成M(n+1)new(n+1)new的新记忆细胞,替换M(n+1)中部分适应度低的记忆细胞.如终止条件不满足转至step2执行.本文实现全局粒子群协作算子,基于这一算子的协作型人工免疫网络记为gpso-CoAIN.下面给出可变步长的克隆选择、网络抑制以及全局粒子群协作算子的具体实现.2.1步长参数加标系统在克隆选择过程中,每个记忆细胞都经过克隆扩增、变异和精英选择3个步骤.每个记忆细胞扩增成Nc个克隆细胞c,变异后生成成熟细胞c′,如下所示:c′=c+αΝ(0,1),α=(1β)exp(-f*),c′=c+αN(0,1),α=(1β)exp(−f∗),其中,N(0,1)是均值为0、标准差为1的高斯型随机分布;α是变异步长,它与步长参数β成反比,与细胞适应度的归一化结果f*的负数成指数关系.产生的变异结果是,适应度低的记忆细胞变异程度高,以较高概率发现更好的解;相反,适应度高的优秀个体变异相对较少,以保持其优势.研究中发现,步长参数β控制每代细胞的平均变异范围.如果设置偏大,变异范围缩小,导致算法收敛速度较慢;相反,过小又不适合于高精度搜索.参数β的理想值是,在程序迭代初期,较小的β有利于提高种群多样性以提高搜索速度,而当多次迭代后,增大β将有利于精确搜索.为了同时满足这两种情况,提出可变步长的克隆选择过程,将参数β设置为迭代次数的函数,即β=2a-b+2(b-a)1+exp(-ts),β=2a−b+2(b−a)1+exp(−ts),其中,a、b是变异步长的基本范围,t为当前迭代次数,s控制参数β变化的速率.此外,记忆细胞的克隆数Nc:Νc=round(β⋅Νi).Nc=round(β⋅Ni).其中,克隆个数Nc与变异参数β成正比,N为常数,i为记忆细胞适应度从高到低排序的序号,round(·)是取整操作.因此,适应度最高的记忆细胞克隆β×N个,适应度第二高的抗体克隆(β×N)/2个,依此类推.由于Nc随β的增加而增加,在迭代后期,记忆细胞会产生更多的后代有利于高精度搜索.2.2基于记忆细胞的相似度CoAIN人工免疫网络的运行是在记忆细胞种群上,因此记忆细胞的数量直接影响算法的执行速度.网络抑制过程既是对自然免疫系统优胜劣汰的一种模拟,又是保证执行效率的必然要求.在这个过程中,既要减少网络中存储的记忆细胞的个数,又要保证高适应度的解能够保留下来.首先,计算记忆细胞间的相似度,如果两记忆细胞相似度小于给定的抑制阈值,就将其中适应度低的记忆细胞从网络中移除.在求解实数空间函数优化问题中,对L个参数编码为记忆细胞m∈RL,则两个记忆细胞mi、mj的相似度度量:simility(mi,mj)=√L∑k=1(mik-mjkuboundk-lboundk)2,simility(mi,mj)=∑k=1L(mik−mjkuboundk−lboundk)2−−−−−−−−−−−−−−−−ue001⎷ue000ue000,其中,mik为mi第k维的值;uboundk、lboundk为第k个参数的取值上限和下限,即为两记忆细胞归一化后的解空间距离.抑制阈值的取值在之间,阈值越大,网络中记忆细胞被删除的比例越大.2.3记忆细胞的一种新一种—全局粒子群协作算子Eberhart和Kennedy于1995年提出的粒子群优化算法(PSO)是基于对鸟群、鱼群的模拟.粒子群优化算法通过个体间的协作来寻找最优解,从而使整个粒子群表现出复杂的特性.PSO最初是处理连续优化问题,目前其应用已扩展到组合优化.由于其简单有效的特点,得到广泛应用.在全局粒子群协作算子中,经过网络抑制后的记忆细胞种群m={m1,…,mi,…,mn}作为一群粒子P={p1,…,pi,…,pn}.每个记忆细胞mi拥有粒子的特性,能够通过跟踪两个“极值”来更新自己:1)个体极值点,记录自己的最佳位置,记作pi·pb属性;2)全局极值点,记录记忆细胞种群目前找到的最好解,记作Pgb.每个记忆细胞根据自己的历史搜索经历以及整个网络中记忆细胞的历史搜索经历计算新的更新速度vi,这种位置的改变是记忆细胞的一种新的变异形式,体现记忆细胞之间的协作关系.如果更新后记忆细胞的适应度提高,则更新pi·pb属性;如果适应度的提高好于原全局极值点,则更新Pgb.经过Its次迭代,得到高适应度的一群粒子,对应于一组新的记忆细胞.全局粒子群协作算子的执行过程伪码如下所示.FUNCTIONP=gpso(m)FOReachmemorycellmipi·pb=miEND-FORPgb=mf//mf为适应度最高的记忆细胞FORt=1ToItsFOReachparticlepi,w=0.5(Its-t)/Its+0.4;vi=w×vi+c1×rand()×(pi·pb-pi)+c2×rand()×(p·pgb-pi);pi=pi+vi;IFfitness(pi)>fitness(pi·pb),THENpi·pb=pi;END-IF//fitness(·)为适应度函数IFfitness(pi)>fitness(pgb),THENpgb=pi;END-IFENDEND合适的c1、c2参数可加快算子收敛且不易陷入局部最优,通常令c1=c2=2,rand()函数产生之间的随机数.3fpso算法测试条件本文用gpso-CoAIN算法对如下10个函数进行测试.1)F1.2(x-0.75)2+sin(5πx-0.4π)-0.125‚x∈.2)F2.-10∑j=1jsin((j+1)x+j)‚x∈[-10,10].3)F3.(x2-5.14π2x21+5πx1-6)2+10(1-18π)cos(x1)+10‚x1∈[-5,10],x2∈[-10,10].4)F4.5∑j=1jsin((j+1)x1+j)⋅5∑j=1jsin((j+1)x2+j)+0.5[(x1+1.4513)2+(x2+0.80032)2]‚x1∈[-10,10],x2∈[-10,10].5)F5.5∑j=1jsin((j+1)x1+j)⋅5∑j=1jsin((j+1)x2+j)+(x1+1.4513)2+(x2+0.80032)2‚x1∈[-10,10],x2∈[-10,10].6)F6.x414-x212+x110+x222‚x1∈[-10,10],x2∈[-10,10].7)F7.5∑j=1jsin((j+1)x1+j)⋅5∑j=1jsin((j+1)x2+j)‚x1∈[-10,10],x2∈[-10,10].2(x−0.75)2+sin(5πx−0.4π)−0.125‚x∈.2)F2.−∑j=110jsin((j+1)x+j)‚x∈[−10,10].3)F3.(x2−5.14π2x21+5πx1−6)2+10(1−18π)cos(x1)+10‚x1∈[−5,10],x2∈[−10,10].4)F4.∑j=15jsin((j+1)x1+j)⋅∑j=15jsin((j+1)x2+j)+0.5[(x1+1.4513)2+(x2+0.80032)2]‚x1∈[−10,10],x2∈[−10,10].5)F5.∑j=15jsin((j+1)x1+j)⋅∑j=15jsin((j+1)x2+j)+(x1+1.4513)2+(x2+0.80032)2‚x1∈[−10,10],x2∈[−10,10].6)F6.x414−x212+x110+x222‚x1∈[−10,10],x2∈[−10,10].7)F7.∑j=15jsin((j+1)x1+j)⋅∑j=15jsin((j+1)x2+j)‚x1∈[−10,10],x2∈[−10,10].8)Multi.xsin(4πx1)-x2sin(4πx2+π)+1,x1∈[-2,2],x2∈[-2,2].9)Schaffer.0.5-sin2(√x21+x22)-0.5(1+0.001(x21+x22))2‚x1∈[-10,10],x2∈[-10,10].9)Schaffer.0.5−sin2(x21+x22√)−0.5(1+0.001(x21+x22))2‚x1∈[−10,10],x2∈[−10,10].10)Roots.11+|z6-1|,z=x1+ix2,x1∈[-2,2],x2∈[-2,2].11+|z6−1|,z=x1+ix2,x1∈[−2,2],x2∈[−2,2].F1～F7函数来自文献,Multi、Schaffer、Roots函数来自文献和.上述10个函数用于测试算法的性能,并且和文献中的方法进行比较.每项测试都经过50次独立运行,最大运行代数为500代.以下分别从寻优能力、执行效率以及人工免疫网络的动态特征这3方面对gpso-CoAIN算法进行测试,并与opt-aiNet、BCA、HGA以及PSO算法进行比较.3.1配方的寻优能力算法的寻优能力以50次独立运行的平均最优值及其标准差表示.表1是gpso-CoAIN算法在F1～F7函数上的运行结果以及与文献中的实验结果的比较.在500代内,gpso-CoAIN算法都可以找7个函数的最优解,而opt-aiNet对F3、F4、F5、F6函数没有达到已知最优解,BCA对F1、F6函数没有到达最优解,HGA对F6没有达到最优解.表2是gpso-CoAIN、opt-aiNet、PSO算法对Multi、Schaffer、Roots函数执行500代得到的平均最优值以及标准差.可以清楚地看到,3个算法中只有CoAIN算法在500代内找到最优值.这两个实验表明gpso-CoAIN算法的寻优能力优于opt-aiNet、BCA、HGA和PSO算法.3.2gpso-coan算法在全局运行中的最优运行次数算法的执行效率通过执行时间和执行函数计算的次数这2个指标评价.在文献中,算法执行函数计算的总次数被用来评价不同类型算法的寻优效率.gpso-CoAIN算法执行函数计算就是适应度计算.由算法的执行过程可知,算法需要对每次迭代克隆变异产生的成熟细胞、全局粒子群协作算子中的粒子以及随机生成的新记忆细胞执行此项计算.则算法执行第(n+1)次迭代时所需的函数计算次数如下:E(n+1)f=Ν(n)m∑i=1round(β⋅Νi)+Ν(n+1)s⋅Ιts+Ν(n+1)new,E(n+1)f=∑i=1N(n)mround(β⋅Ni)+N(n+1)s⋅Its+N(n+1)new,其中,N(n)m(n)m为第n代记忆细胞M(n)的个数,N(n+1)s为经过压缩后的记忆细胞S(n+1)的个数,Its为全局粒子群协作算子中的迭代次数参数,N(n+1)new为随机新增的记忆细胞M(n+1)new的个数.可见gpso-CoAIN算法执行协作算子增加每代的函数计算次数.gpso-CoAIN、opt-aiNet、BCA和HGA算法在F1～F7函数上求解全局最优解所需的函数计算次数的平均值以及标准差如表3所示.可见4个算法寻优所需的函数计算次数差异较大.与opt-aiNet算法相比,gpso-CoAIN只需经过少量函数值计算就可达到函数最优值.与BCA和HGA算法相比,对F1、F2、F3、F6这4个函数寻优中,gpso-CoAIN的函数计算次数最少.这说明,虽然gpso-CoAIN算法每代的函数计算次数比opt-aiNet多,但它只需少量的迭代次数就可找到最优值.表4显示gpso-CoAIN、opt-aiNet、PSO算法在Multi、Schaffer、Roots函数上寻优所需的函数计算次数以及平均运行时间.平均运行时间更直接反映算法的运行效率.对于Multi和Schaffer函数,gpso-CoAIN算法的函数计算次数最少,平均运行时间也最低.由于Roots函数的最大值位于陡峭峰值,增加了寻优精确度要求.gpso-CoAIN算法对Roots函数寻优所需的函数计算次数最大.这表明高精度寻优是以更大的计算量为代价的.然而,gpso-CoAIN算法的平均运行速度却是最短的.由此可知,虽然gpso-CoAIN算法每