第5期 钱淑渠，等：动态多目标免疫优化算法及性能测试研究 ·71· aff (x.raw(x.+f(x ①算法最终获得的记忆集及记忆细胞的平均 (1) 浓度 式中：raw(x,)=1+ls(x,t 1 一为抗体x在其S ②算法执行中，相邻两代的抗体群间相互的 覆盖率 (邻域内的浓度：S(x,)为该环境下，抗体群A中 6)环境判别规则 抗体x的5()邻域内，所有抗体y(y≠x)构成的集 首先随机生成m个候选解构成集合M={x' 合，即 1函≤w},然后依据下列式子确定环境t是否有 S(x,=y:f(x,)-f(y,‖≤s(), 相似环境： y∈A∧y≠xy, 0 ，1≤n()≤m, n(t) 时fx,-fx,Ⅱ ()= e(t.k) 点，n(0>m mm阳f(x,功·fX,亚刊 x'EM 式中：、为可调参数，m为大于1的正整数， 式中：k为1与1-1之间的正整数：若￡(t,< n()为1环境的当前代数，此设计的目的在于使算 1025则确定满足此条件的第1个k值，并认为环 法在最终所获的非控面有较好的分布：式(1)中右 境t和环境k是相似环境，否则为非相似环境 边的第1项说明若某抗体的邻域内的抗体数较少， 4 性能测试准则 则其亲和力偏高，反之则偏低，此有助于被选中个 体分布均匀；第2项有助于提高算法的搜索性能. 给定算法A与算法B在环境t分别执行G次： 3)亲和突变 S、S分别是此两算法在该环境中第m次执行所 设x为参与突变的抗体，则其突变概率设计为 获非控解集. 1)平均覆盖率.定义映射S,S)一0,1]， 即 R(x)1-ks exp af f (x)-af fma 3 af f max af f min S,S)=∈↓3∈<4 1S1 式中：0<台<I,affmax、affmin分别为抗体群中最 (5 大、最小亲和力.突变方式为多项式突变4 则在环境1下，算法A对算法B的平均覆盖率为 4)更新记忆池 G 由于随环境的变化，各环境所获的最好解之间 C(A,B=人∑p(Sd,s9 G 6 不能比较优劣：相应地，相同、相似或不同抗原所 对应的记忆细胞之间不能比较各自的优劣，这导致 若C(A,B)=1,则在环境1，算法B所获非控解集 记忆池的容量将逐渐增大：为了克服此问题，降低 完全被算法A的覆盖 算法的计算复杂度，记忆池由若干类记忆集构成， 2)平均浓度、平均覆盖.平均浓度D()和平均 具体设计如下： 覆盖H()可分别用于度量算法A所获非控解集的 将环境划分成若干类，每一类由相同或相似环 整体分布状况及覆盖的范围，基于文献[9]的设计， 境构成.？由第1类环境中各环境下算法所获记忆 它们被设计为 细胞构成，特别地，若仅由一种环境下的记忆细 1 胞构成，则表示该环境属于新环境：反之，若？由 D(=1 S (dm-dum)2 GG S-1-1c 多种环境的记忆细胞构成，则这些记忆细胞的各分 量被等价转化为0,11区间上的值，进一步，中 7) 仅保存m2个记忆细胞，若超出此数，则计算各记 H(0=士∑max{I(x.: 忆细胞的浓度)，保存浓度大的m个记忆细胞 G1G1945 x',X∈Sm} (8) 5)统计特征存储 式中： 该模块用于保存算法在每一环境中获得的统计 dam min{llxx ll:xx ES, 特征，存储： 1为，1写司S1 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.netaf f ( x , t) = raw ( x , t) + k1 ‖f ( x , t) ‖ . (1) 式中 : raw ( x , t) = 1 1 +| S ( x , t) | 为抗体 x 在其ζ ( t) 邻域内的浓度; S ( x , t) 为该环境下 , 抗体群 A 中 抗体 x 的ζ( t) 邻域内 ,所有抗体 y( y ≠x) 构成的集 合 , 即 S ( x , t) = { y : ‖f ( x , t) - f ( y , t) ‖ ≤ζ( t) , y ∈A ∧y ≠x} , ζ( t) = k1 n( t) ,1 ≤n( t) ≤m1 , k2 m1 , n( t) > m1 . (2) 式中 : k1 、k2 为可调参数 , m1 为大于 1 的正整数 , n( t) 为 t 环境的当前代数 , 此设计的目的在于使算 法在最终所获的非控面有较好的分布; 式 (1) 中右 边的第 1 项说明若某抗体的邻域内的抗体数较少 , 则其亲和力偏高 , 反之则偏低 ,此有助于被选中个 体分布均匀; 第 2 项有助于提高算法的搜索性能. 3) 亲和突变 设 x 为参与突变的抗体 , 则其突变概率设计为 R ( x) = 1 - k3 ·exp af f ( x) - af f max af f max - af f min . (3) 式中 :0 < k3 < 1 , af f max 、af f min 分别为抗体群中最 大、最小亲和力. 突变方式为多项式突变[14 ] . 4) 更新记忆池 由于随环境的变化 , 各环境所获的最好解之间 不能比较优劣; 相应地 , 相同、相似或不同抗原所 对应的记忆细胞之间不能比较各自的优劣 , 这导致 记忆池的容量将逐渐增大; 为了克服此问题 , 降低 算法的计算复杂度 , 记忆池由若干类记忆集构成 , 具体设计如下 : 将环境划分成若干类 ,每一类由相同或相似环 境构成. τi 由第 i 类环境中各环境下算法所获记忆 细胞构成 , 特别地 , 若τi 仅由一种环境下的记忆细 胞构成 , 则表示该环境属于新环境; 反之 , 若τi 由 多种环境的记忆细胞构成 , 则这些记忆细胞的各分 量被等价转化为[0 , 1 ]区间上的值 , 进一步 , τi 中 仅保存 m2 个记忆细胞 , 若超出此数 , 则计算各记 忆细胞的浓度[13 ] , 保存浓度大的 m2 个记忆细胞. 5) 统计特征存储 该模块用于保存算法在每一环境中获得的统计 特征 , 存储 : ①算法最终获得的记忆集及记忆细胞的平均 浓度. ②算法执行中 , 相邻两代的抗体群间相互的 覆盖率. 6) 环境判别规则 首先随机生成 m0 个候选解构成集合 M = { x i , 1 ≤i ≤m0 } , 然后依据下列式子确定环境 t 是否有 相似环境 : ε( t , k) = ∑ m0 i =1 ‖f ( x i , t) - f ( x i , k) ‖ m0 max x i ∈M { ‖f ( x i , t) - f ( x i , k) ‖} . (4) 式中 : k 为 1 与 t - 1 之间的正整数; 若ε( t , k) < 10 - 215则确定满足此条件的第 1 个 k 值 , 并认为环 境 t 和环境 k 是相似环境 ,否则为非相似环境. 4 性能测试准则 给定算法 A 与算法 B 在环境 t 分别执行 G 次; S A tm 、S B tm分别是此两算法在该环境中第 m 次执行所 获非控解集. [3 ] 1) 平均覆盖率. 定义映射Φ( S A tm , S B tm ) →[0 ,1 ] , 即 Φ( S A tm , S B tm ) = | { x B ∈S B tm | ϖ x A ∈S A tm :x A < x B } | | S B tm | . (5) 则在环境 t 下 , 算法 A 对算法 B 的平均覆盖率为 C( A , B) = 1 G ∑ G k =1 Φ( S A tk , S B tk ) . (6) 若 C( A , B) = 1 , 则在环境 t , 算法 B 所获非控解集 完全被算法 A 的覆盖. 2) 平均浓度、平均覆盖. 平均浓度 D ( t) 和平均 覆盖 H ( t) 可分别用于度量算法 A 所获非控解集的 整体分布状况及覆盖的范围 ,基于文献[9 ]的设计 , 它们被设计为 D ( t) = 1 G1 ≤∑m ≤G 1 | S A tm | - 1 1 ≤i∑ ≤| S A tm | ( dtm - dtim ) 2 , (7) H ( t) = 1 G 1 ≤∑m ≤G max 1 ≤j , j ≤| S A tm | { ‖( x i - x j ) ‖: x i , x j ∈S A tm } . (8) 式中 : dtim = min i ≠j ,1 ≤j ≤| S A tm | { ‖x i - x j ‖: x i , x j ∈S A tm } , 第 5 期 钱淑渠 ,等 :动态多目标免疫优化算法及性能测试研究 · 17 ·