第3期 钱小宇，等：基于目标空间分解和连续变异的多目标粒子群算法 ·465· 广泛认可。后来更多学者对多目标粒子群算法 PS={x∈2-3ze2:z>x刘 (3) (MOPSO)进行了更深入的研究：Raquel等使用 定义4 Pareto前沿(PF): 了拥挤距离作为适应值对粒子进行排序：Lⅰ等 PF={F(x)x∈PSI (4) 通过整合粒子的GMR(global margin ranking)和粒 1.2粒子群优化 子密度信息的方法来对粒子进行排序，能高效快 粒子群算法中的粒子由速度信息和位置信息 速地选择出Pest和gbet粒子；除了对排序选择的 组成，更新公式为 方法进行优化外，有的利用聚合函数来对多个目 Vi=WKi+CiR(P-X)+C2R2(G-X) (5) 标函数进行处理：有的使用了目标空间分解的方 X=V+X (6) 法来保障粒子最优解的多样性m:以及将MOPSO 式中：k指粒子群中第k个粒子；1为当前迭代次 和其他优化算法进行交叉使用，如教与学方法圆、 数；W为权衡局部搜索和全局搜索的参数， 差分方法等，通过一定的比例调用MOPSO。 W∈0.1,0.9：C,和C2为学习因子，其大小都为2； 上述的这些方法不断地对MOPSO的多样性 R和R都是[O,1]之间的随机数；P指当前粒子最 和全局收敛进行改进和优化，虽然取得了较好的 好位置Ppesti;G指引导粒子Sbest的位置；V?指在 研究成果，但是这些方法的改进策略只对MOPSO 第1次迭代中第k个粒子的速度；X指在第1次迭 某一性能效果进行改进，其他的性能指标并没有 代中第k个粒子的位置。 同时得到很好的改进。例如：文献[]中，多样性 2 MOPSO/DC算法 方面得到很大的提升，但是其收敛性方面仍有很 大不足。所以，本文借鉴Pareto支配强度uo和连 2.1目标空间分解 续变异的方法对基于目标空间分解方法的多目 把目标空间Y分成M个子区域Y,Y2,…, 标粒子群算法进行优化，在给每个子区域分配 YM。令je{1,2,…,M,对任一给定的第j个子区 粒子时，删除没有归属的粒子，给没分到粒子的 域，每个目标函数在所有目标函数中所占有的权 区域初始化新的粒子，增加获得较优粒子的可能 重a,(=1,2.…,m,且4=1)所组成的向量 性。这样既从整体和局部两方面提升了粒子的收 敛性，同时多样性也得到了一定的优化提升，这 (a1,a2,…,am)定义为该子区域的中心向量A。当 种新的算法被称为基于目标空间分解和连续变异 目标函数个数m=2时，则第j子区域的中心向 的多目标粒子群优化算法(multi-.objective particle 量A,表示 [品1-当m=3时，进行 swarm optimization based on decomposition and con- 两层循环，令k为第1层（外层）循环变量，2为 tinuous mutation,MOPSO/DC). 第2层（内层）循环变量，k1从0取到h,从0取 1多目标优化问题 到h-,每次循环令u=+1+乃+2-，其 k,=1 1.1基本概念 中h和M满足：当C2≥M时h取最小值，则第 miny F(x)=(fi(x),f(x),...fin(x)) stg(x)≤0，i=01,2,…,q (1) “个子区镜的中心向量为伤会1-会-当 Γh-h h,(x)=0,j=1,2,…,p m>3时，进行m-1层循环，k1为第一层循环变量 式中：x=(,x2,…,x)为n维决策变量；m为目标 (最外层)，依次由外向内，令k为第层循环变量， 函数的个数；g(:)函数为目标函数的q个不等式 km1为第m-1层（最内层）循环变量，k1从0取到 约束；h()为目标函数的p个等式约束。所有这 h,k2从0取到h-k,k从0取到(h-k1-k2-…k), 些满足条件的决策变量用集合2表示，Y={F(x)x∈2 最里层循环变量km1从0取到(h-k1-k2-…km-2), 为目标空间。接下来介绍4个关于多目标问题的 每次循环令 重要定义。 u=的 定义1 Pareto支配。解d,ee2,d支配e,记 4=02=0 为d>e,满足下面的两个关系式： ∫i∈(,2,…,ml,fd≤f(e) 3ie{1,2,…,m以，f(d<f(e) (2) 其中参数h、m和子区数M满足关系：h取满 定义2 Pareto最优。如果x是Pareto最优 足C1≥M时的最小值，则第u个子区域的中心 解，则在2中，∈2使z>x成立。 定义3 Pareto最优解集(PS): 向量为 …1-小 当m≥3时，一共产 hh h台广泛认可。后来更多学者对多目标粒子群算法 (MOPSO) 进行了更深入的研究：Raquel 等 [4]使用 了拥挤距离作为适应值对粒子进行排序；Li 等 [5] 通过整合粒子的 GMR(global margin ranking) 和粒 子密度信息的方法来对粒子进行排序，能高效快 速地选择出 pbest 和 gbest 粒子；除了对排序选择的 方法进行优化外，有的利用聚合函数来对多个目 标函数进行处理[6] ；有的使用了目标空间分解的方 法来保障粒子最优解的多样性[7] ；以及将 MOPSO 和其他优化算法进行交叉使用，如教与学方法[8] 、 差分方法[9]等, 通过一定的比例调用 MOPSO。 上述的这些方法不断地对 MOPSO 的多样性 和全局收敛进行改进和优化，虽然取得了较好的 研究成果，但是这些方法的改进策略只对 MOPSO 某一性能效果进行改进，其他的性能指标并没有 同时得到很好的改进。例如：文献[7]中，多样性 方面得到很大的提升，但是其收敛性方面仍有很 大不足。所以，本文借鉴 Pareto 支配强度[10]和连 续变异的方法[11]对基于目标空间分解方法的多目 标粒子群算法[7]进行优化，在给每个子区域分配 粒子时，删除没有归属的粒子，给没分到粒子的 区域初始化新的粒子，增加获得较优粒子的可能 性。这样既从整体和局部两方面提升了粒子的收 敛性，同时多样性也得到了一定的优化提升，这 种新的算法被称为基于目标空间分解和连续变异 的多目标粒子群优化算法 (multi-objective particle swarm optimization based on decomposition and con￾tinuous mutation ，MOPSO/DC)。 1 多目标优化问题 1.1 基本概念    miny = F(x) = (f1(x), f2(x),··· , fm(x)) s.t.gi(x) ⩽ 0, i = 0,1,2,··· ,q hj(x) = 0, j = 1,2,··· , p (1) x = (x1, x2,··· , xn) n m g(x) q h(x) p Ω Y = {F(x)|x ∈ Ω} 式中： 为 维决策变量； 为目标 函数的个数； 函数为目标函数的 个不等式 约束； 为目标函数的 个等式约束。所有这 些满足条件的决策变量用集合 表示， 为目标空间。接下来介绍 4 个关于多目标问题的 重要定义。 d, e ∈ Ω d e d ≻ e 定义 1 Pareto 支配。解 ， 支配 ，记 为 ，满足下面的两个关系式： { ∀i ∈ {1,2,··· ,m}, fi(d) ⩽ fi(e) ∃i ∈ {1,2,··· ,m}, fi(d) < fi(e) (2) x Ω ¬∃z ∈ Ω z ≻ x 定义 2 Pareto 最优。如果 是 Pareto 最优 解，则在 中， 使 成立。 定义 3 Pareto 最优解集 ( PS )： PS = {x ∈ Ω|¬∃z ∈ Ω;z ≻ x} (3) 定义 4 Pareto 前沿 ( PF )： PF = {F(x)|x ∈ PS} (4) 1.2 粒子群优化 粒子群算法中的粒子由速度信息和位置信息 组成，更新公式为 V t+1 k = WKt k +C1R1(P− X t k )+C2R2(G − X t k ) (5) X t+1 k = V t+1 k + X t k (6) W ∈ [0.1,0.9] C1 C2 R1 R2 V t k X t k 式中：k 指粒子群中第 k 个粒子；t 为当前迭代次 数 ； W 为权衡局部搜索和全局搜索的参数， ； 和 为学习因子，其大小都为 2； 和 都是[0，1]之间的随机数；P 指当前粒子最 好位置 pbest；G 指引导粒子 gbest 的位置； 指在 第 t 次迭代中第 k 个粒子的速度； 指在第 t 次迭 代中第 k 个粒子的位置。 2 MOPSO/DC 算法 2.1 目标空间分解 j ∈ {1,2,··· , M} ai(i = 1,2,··· ,m, ∑m i=1 ai = 1) (a1,a2,··· ,am) Aj m = 2 j Aj [ j−1 M −1 1− j−1 M −1 ] m = 3 k1 k2 k1 k2 h−k1 u = k2 +1+ ∑h k1=1 (h+2−k1) C 2 h+2 ⩾ M [ k1 h k2 h 1− k1 h − k2 h ] m > 3 m−1 k1 ki m−1 k1 h−k1 ki (h−k1 −k2 − ··· ki) (h−k1 −k2 − ··· km−2) 把目标空间 Y 分成 M 个子区域 Y1，Y2，···， YM。令 ，对任一给定的第 j 个子区 域，每个目标函数在所有目标函数中所占有的权 重 且 所组成的向量 定义为该子区域的中心向量 。当 目标函数个数 时，则第 子区域的中心向 量 表示为 ；当 时，进行 两层循环，令 为第 1 层 (外层) 循环变量， 为 第 2 层 (内层) 循环变量， 从 0 取到 h， 从 0 取 到 ，每次循环令 ，其 中 h 和 M 满足：当 时 h 取最小值，则第 u 个子区域的中心向量为 ；当 时，进行 层循环， 为第一层循环变量 (最外层)，依次由外向内，令 为第 i 层循环变量， km-1 为第 层 (最内层) 循环变量， 从 0 取到 h，k2 从 0 取到 ， 从 0 取到 ， 最里层循环变量 km-1 从 0 取到 ， 每次循环令 u = ∑h k1=0 ∑h−k1 k2=0 ··· h−k1∑−···−ki−1 ki=0 ··· h−k1∑−···−km−4 km−3=0   h−k1∑−···−km−3 km−2=1 (h+2− ∑m−2 l=1 kl)+km−1 +1   C m−1 h+m−1 ⩾ M   k1 h k2 h ··· 1− 1 h ∑m−1 l=1 kl   m ⩾ 3 其中参数 h、m 和子区数 M 满足关系：h 取满 足 时的最小值，则第 u 个子区域的中心 向量为 。当 时，一共产 第 3 期 钱小宇，等：基于目标空间分解和连续变异的多目标粒子群算法 ·465·