一种多目标优化问题的免疫算法

一种多目标优化问题的免疫算法

1pareto最优解的获得及验证自1985年以来，多目标嵌入式算法已成为解决多目标优化问题的主要工具。许多科学家已经提出了基于权重系数的多目标进化算法。其关键在于确定权重系数。然而，需要大量的初始知识来严格限制初始群体的分布。然而，基于该群体的多目标进化算法（）可以在很大程度上克服基于权重系数的多目标进化算法的许多缺点，如群体多样性差、初始知识不足、最短的pareto解等。该方法具有很高的灵活性，能够有效搜索最合适的pareto解。其重要在于其设计和选择适应方案的适应性。特别是，文献中的speas充分利用了最合适者的概念，并以新的小规模生态方式提高了群体的多样性。同时，在进化的群体中，在它们的基础上生存的最优异体在它们之外进行选择，并通过不断更新获得最合适的pareto最好的个体来获得最合适的pareto最好的解。但是，根据作者的实践，很难在该方法中获得最合适的解。每个子目标同时应尽可能实现最小最合适的解。因此，即使它是用来解决每个子目标为多模态函数的多目标优化问题的，也很难获得预期结果，因此也不适合决策者进行有效选择。可是,免疫系统具有学习、记忆、自适应、自组织、分布性以及群体多样性等特点,模拟其原理开发免疫算法解决工程问题,已成为计算智能中正在兴起的研究领域,并且有些免疫算法在单目标函数优化、模式识别、数据挖掘、组合优化及机器学习等方面得到了有效应用.尤其经仿真获知,构建免疫算法能有效地解决复杂的多目标优化问题,但这方面的结果极为罕见.为此,本文基于免疫应答原理及小生境概念,提出多目标免疫算法(MOIA:MultiobjectiveOptimizationImmuneAlgorithm),并与公认为很好的算法SPEA进行比较,获知MOIA优于SPEA.MOIA的主要思想是:首先复制当前抗体群中最好抗体作为抗原进入抗原群(初始抗原群为空集),并通过一种新的聚类算法不断更新抗原群,其目的是保存较好的Pareto最优个体,接着这抗原群作用于当前抗体群;然后选择当前抗体群中识别能力(亲和力)强的抗体繁殖一定数目的克隆细胞,这些克隆细胞进入亲和突变框架,并选择亲和力高的抗体作为记忆细胞,未被选择繁殖的抗体之间通过相互抑制,消除相同和相似的抗体,未被消除的抗体作为记忆细胞,然后随机产生一定数目的新抗体进入记忆细胞群,此群体作为新抗体群,这构成随机搜索链,即抗体群→选择→克隆→突变→再选择及未被选择繁殖的抗体抑制、吸收新成员→新抗体群,这种链为一进化过程.2群体vppareto设D⊆Rn是有界闭区域,f:D→Rm为取值于Rm中的映射,则多目标极小化模型可描述为:(VΡ)minx∈Df(x)=[f1(x)‚f2(x),⋯,fm(x)]Τ其中D称为可行解域,x∈D称为可行解.不妨设f(x)≥0,x∈D.由于区间[0,1]与区间[a,b]之间存在可逆映射,因此也不妨设D中元素的每一分量皆在区间[0,1]上取值.若xi=[xi1,xi2,…,xin]T,i=1,2,满足x1j≤x2j,1≤j≤n且存在1≤j0≤n使得x1j0<x2j0,则称x1优于x2,记为x1≤x2;若x′∈D,在D中不存在x,使得f(x)≤f(x′),则称x′是(VP)的Pareto最优解;称D的非空子集X为群体;x∈D称为个体;若x′∈X,群体X中不存在优于x′的其它个体,则称x′是(VP)相对于群体X的Pareto最优个体,简称Pareto最优个体.以下简要叙述免疫应答原理.在免疫系统中,免疫应答扮演着重要角色,任何抗原入侵免疫系统时,其皆作免疫应答.当抗原入侵机体时,免疫系统产生的抗体数量较少,机体抵御抗原的能力较弱,抗原清除也比较慢.由于免疫系统具有学习、识别、记忆、自保护、多样性和自适应等特点,其经过一段时间后,抗体数目增加较快,这些抗体被激活、分化和繁殖,经由亲和突变达到亲和成熟,提高识别能力,此时,抗原被清除较快.剩余的抗体中,一部分抗体应答能力弱或产生自反应,被有效地清除,其余的抗体作为记忆细胞存于免疫系统中,防御同一抗原再次入侵,这种应答称为免疫应答.此过程是一种进化过程,模拟其机理并构建免疫算法可解决多目标优化问题.3抗体群x中抗体的激活多目标优化免疫算法的运行机制如图1所示.设抗体Ab(即(VP)的可行解)和抗原Ag(即(VP)的Pareto最优个体)表示为n维向量(分量取值于区间[0,1]上的有理数).由于免疫系统的每个B细胞仅携带一种类型的抗体,因此本文将B细胞与抗体视为同一.用|.|指群体规模,‖.‖表示n维向量的范数.用S表示由所有抗体构成的抗体空间,并设S为有限集,记N=|S|.用S≤N表示由所有规模不超过N的非空群体构成的抗体群空间.对于给定的抗原群Y,抗原刺激免疫系统,使得抗体群X中的部分抗体被激活,抗体Ab的亲和力计算由下确定aff(Ab)=1+1|Y|∑j=1〈f(Ab)f(Agj)〉,Ab∈X,Agj∈Y(1)其中,<.,.>表示n维向量的内积.在此,用内积比用欧氏距离更能确切地刻画抗体识别抗原群的总体能力.亲和力越高的抗体,识别抗原群的能力越强;反之,则越弱.设x,y∈X,若f(x)≤f(y),则置dy(x)=1.于是可引入X中抗体的增强度strength(x)=∑y∈Xdy(x)下面将图1中各操作定义为算子.定义1所谓克隆选择,是指在给定的选择率ζ‰下,在抗体群中选择部分抗体的映射,Ts:S≤N→S.即设X0为抗体群X中Int(ζ‰|X|)个亲和力较高的抗体构成的群体,其中Int(.)表示取整函数.按如下概率规则选择Int(ζ‰|X|)个抗体Ρ(ΤCS(X)i=Xi)={1,Xi∈X00,Xi∉X0定义2设X为给定的抗体群,所谓细胞克隆是指抗体群到S≤N的一个映射,Tc:S→S≤N,它是随机映射,其作用方式是,对于Ab∈X,按其繁殖率λ复制NAb个克隆细胞,即ΝAb=(|Y|-1λaff(Ab))θ其中λ为区间[1/(2(1+aff(Ab))),1/(1+aff(Ab))]上的随机数,1<θ<1.5为参数.此定义表明对于给定的抗体群X,抗体繁殖的克隆细胞个数与其亲和力成正比,且每一抗体所繁殖的克隆细胞个数都大于给定抗原群的规模.亲和突变是提高抗体识别抗原能力的主要途径,识别能力强的抗体遭受突变的可能性小;反之,则突变的可能性大.定义3设Ag为给定的抗原,所谓亲和突变是指抗体空间S到自身的随机映射,Tm:S→S,即(1)超级突变：对于与ab对应的ab，随机生成[0]中的随机数，使ab转化为abAb′←Ab+β(Ag-Ab)其中,α与Ab对Ag的亲和力成正比.此处选定为α=1-exp(-∥Ag-Ab∥)(2)(2)免疫选择算子对抗体Ab,以突变率α作为概率,对其各基因位置上的基因在0到9之间随机突变,其中α由式(2)确定.基因位置指Ab的小数点后的数所对应的位置.高亲和力抗体所繁殖的克隆细胞经突变后,有的细胞的亲和力提高,有的却降低,而亲和力降低的细胞将被随机产生的新抗体或已存在的其它抗体抑制并最终被消除.为此引入免疫选择算子.定义4所谓免疫选择指在抗体群中选择抗体,它是随机映射,Tis:S≤N→S,按如下概率规则Ρ{Τ(X)i=Xi}=exp(aff(Xi)/Τn)∑xj∈Xexp(aff(xj)/Τn)选择抗体群X中的抗体,其中Tn=ln((T0/n)+1)为退温函数,T0为初始温度,n为时间.从免疫机理的角度,其免疫选择反映了随着时间的延长,抗体已达到亲和成熟,几乎不受突变的影响,免疫系统处于相对平衡状态.定义5所谓吸收新成员是指在抗体空间S中随机选择一个抗体的映射.用T(S)表示选择的抗体,Td(S)表示选择的d个抗体.定义6设X是抗体群,所谓小生境抑制是指在小生境中选择一个亲和力最高的抗体的映射,Tch:S≤N→S.即设Xi,i=1,2,…,q,是X的q个子群,X=q∪i=1Xi,xi是Xi中亲和力最高的抗体,按下列概率规则选择q个抗体Ρ(Τch(X)=Xi)={1Xi=xi,i=1,2,⋯,q0否则4使用多目标优化免疫算法为了定量地度量抗原群中抗原之间的关系,引入二元函数d:R×R→R,被给定为d(x,y)={0x＞y1x≤y由于抗原群Y中抗原之间具有相互竞争力,这些抗原对免疫系统的激励具有强弱之分,因此抗原群Y中每一抗原有激活其它抗原的能力,这称为激活力,由下式确定D(Ag)=|Y|∑j=1R(f(Ag),f(Agj))|Y|∑i,j=1R(f(Agi),f(Agj)),Ag,Agi,Agj∈Y其中R(F1,F2)=m∑i=1d(xi,yi),F1=[x1,x2,⋯,xm]Τ,F2=[y1,y2,⋯,ym]Τ于是抗原群聚类算法可描述如下:(1)置初始抗原群为C;(2)将C按∥Agi-Agj∥＜σ(3)划分为子群,选出每个子群中激活力最高的一个抗原构成抗原群C′;(3)若‖C′‖>N0,则C←C′,并调整参数σ及返回步骤(2);否则结束.于是利用定义1至定义6及抗原群聚类算法可描述多目标优化免疫算法如下:(1)随机产生初始抗体群A0,初始抗原群B0为空集.(2)复制An中增强度最高的抗体作为抗原入抗原群Bn,并用抗原聚类算法消去Bn中冗余的抗原;若An∩Bn=φ,则复制An中最高增强度的一个抗体作为抗原于Bn中,此抗原群作用抗体群An.(3)按选择率ξ‰将An作用克隆选择算子,选择Nn=Int(ξ‰|An|)个亲和力较高的抗体构成抗体群An1,其余的抗体构成An2.(4)按类似于式(3)的方式将An2划分为子群,并作用小生境抑制算子,获记忆细胞群An21.(5)将An1作用细胞克隆及亲和突变算子,每抗体Ab所繁殖的NAb个克隆中|Bn|个克隆相应与Bn中抗原作用超突变算子;对其余的每个克隆Ab,随机选择Bn中的一个抗原Ag,并将Ab作用均匀随机突变算子.将此两步所获的克隆组合并消除相同的克隆,获抗体群An11.(6)An11作用免疫选择算子,选择Int(η‰|An11|)个抗体构成抗体群An12.(7)随机产生dn=Int(μ‰|An|)+1个新抗体插入记忆细胞群An21∪An12,获下一抗体群An+1.(8)若满足终止条件,则结束;否则,返回步骤(2).此免疫算法有许多特征,如:群体规模动态调整及群体并行搜索Pareto最优解;合理体现Pareto最优解的概念;利用免疫选择及突变算子增强搜索能力;随机产生新抗体,增强群体多样性及提高搜索速度;Pareto最优个体被保存于抗原群且抗原群不断更新;群体合作进化及引入小生境技术等.5基于an的多目标优化模型为叙述方便,称S≤N中每一元素为状态,表示为i.由该算法可知An→(An1,An2)→(An1,A21)→(An11,An21)→(An12,An21)→(An12,An21,Τdn(S))→An+1构成一随机搜索过程.用Ain表示n时刻抗体群处于状态i,则Ain经一步转移为Ajn+1时,状态j由三部分构成,即j=(j1,j2,j3),其中Aj1n+1=ΤisΤmΤcΤs(Ain)=Aj1n12,Aj1n+1=Τch(Ain\Τs(Ain)),Aj3n+1=Τdn(S)由于An在状态i条件下,Tdn(S)仅与状态i有关,An+1仅与时刻n所处状态及Bn中抗原有关,与n时刻以前的任何状态无关,同时状态空间S为有限维,因此该算法可描述为有限马尔可夫链.但由于突变算子Tm与时间n有关,因而此马氏链是非齐次的.用P(Ain)表示n时刻An处于状态i的概率,P(Ajn+1|Ain)表示Ain经一步转移为Ajn+1的概率.设M*为多目标优化极小化模型(VP)的Pareto最优解构成的集合.于是,可获如下结论,其证明可基于文献及文献的方法获之,限于篇幅,在此省略结论的证明.定理1若0<μ<ξ(1-ηNθ%),则有2≤|An|≤|A1|+1ζ%(1-Νθη%)-μ%此定理表明,在该算法中,抗体群的规模始终是有限数,且由于新抗体产生的随机性,抗体群的规模不恒同.引理1设i,j∈S≤N,i∩M*≠φ,j∩M*=φ,则必有Ρ(Ajn+1|Ain)=0引理2设i,j1∈S≤N,i∩M*≠φ,j1∩M*=φ,则Ρ(Aj1n+1|Ain)≤εn,εn→0,n→∞引理3对任意i∈S≤N,必有Ρ(An+1∩Μ*=φ|Ain)≤(1-|Μ*||S|)1+μ%定理2若0<μ<ξ(1-ηNθ0%),则多目标优化免疫MOIA算法是概率收敛的,即limn→∞Ρ(An∩Μ*≠φ)=1.6spea求解为了验证MOIA解决多优化问题的有效性,将此算法与SPEA进行比较.在比较中,对于SPEA,参数选定为:群体大小80,交叉概率0.6,突变概率0.001,外记忆集的规模为200,迭代次数200;对于MOIA,选择初始抗体群体为80,ζ=