·72 智能系统学报 第2卷 G(t)sin(0.5t/10) 3)收敛行为 x1=(x)∈[0,11， 设X(n2)为算法A在第t环境第m次执行 xm=(x2,x3,….x0)∈「-1,11 中，第n代所得的记忆集合，则其收敛性可由下式度 量： 表2DBM对各问题在不同环境独立运行 30次所需平均时间 Pa(t)= 9) Table 2 DBM:Average run time for each environment of the given problem with respectively 30 executions /min 式中：6∈Z 环境t 1 2 34 5 67 P(i.m.0=IC()+c() 问题12.82.82.72.72.72.72.7 问题229 2.82.8 2.8 2.82.82.8 式9)表明，若lim_Pa()=0,则算法A在环境1 问题32.83.02.92.92.92.92.9 有很好的收敛性」 5数值实验 该问题的理论Pareto面满足f2=1-1.各 选取参与比较的算法为DBM,DNSGAII-A 算法在7个环境中分别独立执行30次后所获的统 及CSADMO,各算法的初始群体规模均为N=80. 计值及平均覆盖率如表3、4；此3种算法借助式 在给定环境下，指定保存此3种算法及DMIOA所 9),所获收敛行为曲线如图2，但由于DBM是一种 获非控个体的集合的规模均为80，也假定环境总个 邻域搜索算法，其结构的特殊性使得在此不能描述 数为7，即T=7.由于算法在解决给定环境优化问 出其搜索曲线，各算法在各环境中执行一次所获的 题时，其执行时间是评价动态环境优化算法的性能 非控面比较如图3.表3是各算法对各环境独立运 之一I,为此，对DNSGAII-A、CSADMO及 行30次所获非控解集的平均浓度、平均覆盖比较， DMIOA,规定其在每个环境内的执行时间T,=5s, 由此表获知：参与比较的3种算法所获非控解集的 而对于DBM,由于其结构设计的特殊性，指定每次 平均浓度较差，其中DBM最差，DNSGAⅡ-A、 执行的最大迭代数为20000，这要求DBM对每个 CSADMO稍好，而DMIOA所获效果较好；由各 测试问题在每一次执行中至少需要162s(见表2)， 环境所获非控解集平均覆盖获知：DNS GAⅡ-A、 即T.=162s.各算法对每一测试问题的各环境分 CSADMO稍差，DBM及DMIOA较好.表4是各 别独立执行30次，即G=30,获相应的统计特征值 算法对各环境所获平均覆盖率比较，其中X、 及DBM在每个环境的平均执行时间（表2），DBM XDN、XS、XM分别为算法DBM、DNSGAII·-A、 的进化策略中的突变概率为0.35，梯度搜索法中停 CSADMO DMIOA所获非控解集，由此表获知： 机精度ε=0.01：其他算法参数值的选取可参考文 DMIOA与DNSGAII-A在各环境效果较接近，而 献10-11J:对于DMIOA,除了m=10外，其他 CSADMO及DBM效果较差.图2是DNSGAII- 参数如表1. A、CSADMO DMIOA对各环境独立运行30次所 获平均收敛曲线，n是实际时刻算法所对应的代 表1 DMIOA算法参数设置 Table 1 DMIOA's Parameter settings 数，由图2可知，三算法在给定时间内运行的最大代 参数aB 数均有所不同，DMIOA在较少的代数内收敛行为 k1反m 曲线接近0，而其他两算法收敛较慢.图3是各算法 值0.40.70.210.9520 100 在各环境所获非控面的点分布比较；为便于图形直 问题1FDA1PI 观，将目标函数值f2以G=0.21平移，由图获知： minf(x)=(f1(x)f2(x)) DNSGAII-A收敛较好，但其在f1接近于1的点 较难找到，而CSADMO及DBM分布较好，但收敛 s.t.fi(x x..f2 (x)=g(1- 稍差，而DMIOA所获非控面的点分布较均匀，且 与DNSGAIⅡ-A收敛行为曲线相似，此也可由表4 g(m)=1+∑(x:-G()2 获知 1994-2008 China Academie Journal Electronic Publishing House.All rights reserved.http://www.cnki.netdtm = 1 | S A tm | 1 ≤i∑ ≤| S A tm | dtim . 3) 收敛行为 设 X n tm ( n ≥2) 为算法 A 在第 t 环境第 m 次执行 中,第 n代所得的记忆集合, 则其收敛性可由下式度 量: PGn ( t) = 1 Gl 0 1 ≤∑m ≤G, n+1 -∑l 0 ≤i ≤n P ( i , m , t) . (9) 式中 :l0 ∈Z + , P( i , m , t) = 1 2 [ C( X i tm , X i - 1 tm ) + C( X i - 1 tm , X i tm ) ]. 式(9) 表明 , 若 lim G, n→∞ PGn ( t) = 0 , 则算法 A 在环境 t 有很好的收敛性. 5 数值实验 选取参与比较的算法为 DBM , DNSGA II - A 及 CSADMO , 各算法的初始群体规模均为 N = 80. 在给定环境下 ,指定保存此 3 种算法及 DMIOA 所 获非控个体的集合的规模均为 80 ,也假定环境总个 数为 7 ,即 T = 7. 由于算法在解决给定环境优化问 题时 ,其执行时间是评价动态环境优化算法的性能 之 一[1 ] , 为 此 , 对 DNSGAII - A 、CSADMO 及 DMIOA ,规定其在每个环境内的执行时间 Tt = 5 s, 而对于 DBM , 由于其结构设计的特殊性 ,指定每次 执行的最大迭代数为 20 000 , 这要求 DBM 对每个 测试问题在每一次执行中至少需要 162 s(见表 2) , 即 Tt = 162 s. 各算法对每一测试问题的各环境分 别独立执行 30 次 , 即 G = 30 , 获相应的统计特征值 及 DBM 在每个环境的平均执行时间 (表 2) . DBM 的进化策略中的突变概率为 0135 , 梯度搜索法中停 机精度ε= 0101 ;其他算法参数值的选取可参考文 献[10 - 11 ];对于 DMIOA , 除了 m2 = 10 外 , 其他 参数如表 1. 表 1 DMIOA算法参数设置 Table 1 DMIOA’s Parameter settings 参数 α β k1 k2 k3 m0 m1 值 0. 4 0. 7 0. 2 1 0. 95 20 100 问题 1 FDA1 [2 ] min f ( x) = ( f 1 ( x) , f 2 ( x) ) , s. t. f 1 ( xI) = xi , f 2 ( x) = g (1 - f 1 g ) , g ( xΠ) = 1 + x i∑∈x I ( xi - G( t) ) 2 , G( t) = sin (015πt/ 10) , xI = ( x1 ) ∈[0 ,1 ] , xΠ = ( x2 , x3 , …, x30 ) ∈[ - 1 ,1 ]. 表 2 DBM 对各问题在不同环境独立运行 30 次所需平均时间 Table 2 DBM : Average run time for each environment of the given problem with respectively 30 executions / min 环境 t 1 2 3 4 5 6 7 问题 1 2. 8 2. 8 2. 7 2. 7 2. 7 2. 7 2. 7 问题 2 2. 9 2. 8 2. 8 2. 8 2. 8 2. 8 2. 8 问题 3 2. 8 3. 0 2. 9 2. 9 2. 9 2. 9 2. 9 该问题的理论 Pareto 面满足 f 2 = 1 - f 1 . 各 算法在 7 个环境中分别独立执行 30 次后所获的统 计值及平均覆盖率如表 3、4 ; 此 3 种算法借助式 (9) ,所获收敛行为曲线如图 2 ,但由于 DBM 是一种 邻域搜索算法 ,其结构的特殊性使得在此不能描述 出其搜索曲线 ; 各算法在各环境中执行一次所获的 非控面比较如图 3. 表 3 是各算法对各环境独立运 行 30 次所获非控解集的平均浓度、平均覆盖比较 , 由此表获知 :参与比较的 3 种算法所获非控解集的 平均浓度较差 , 其中 DBM 最差 , DNSGA II - A 、 CSADMO 稍好 , 而 DMIOA 所获效果较好 ; 由各 环境所获非控解集平均覆盖获知 :DNSGA II - A 、 CSADMO 稍差 , DBM 及 DMIOA 较好. 表 4 是各 算法对各环境所获平均覆盖率比较 , 其中 X DB 、 X DN 、X CS 、X DM 分别为算法 DBM、DNSGAII - A 、 CSADMO、DMIOA 所获非控解集 , 由此表获知 : DMIOA 与 DNSGA II - A 在各环境效果较接近 ,而 CSADMO 及 DBM 效果较差. 图 2 是 DNSGAII - A 、CSADMO、DMIOA 对各环境独立运行 30 次所 获平均收敛曲线 , n 是实际时刻算法所对应的代 数 ,由图 2 可知 ,三算法在给定时间内运行的最大代 数均有所不同 ,DMIOA 在较少的代数内收敛行为 曲线接近 0 ,而其他两算法收敛较慢. 图 3 是各算法 在各环境所获非控面的点分布比较 ;为便于图形直 观 , 将目标函数值 f 2 以δt = 0. 2 t 平移 ,由图获知 : DNSGA II - A 收敛较好 ,但其在 f 1 接近于 1 的点 较难找到 ,而 CSADMO 及 DBM 分布较好 ,但收敛 稍差 ,而 DMIOA 所获非控面的点分布较均匀 , 且 与 DNSGA II - A 收敛行为曲线相似 ,此也可由表 4 获知. · 27 · 智 能 系 统 学 报 第 2 卷