第5期 刘柏森，等：一种用于大型舰船总体要素优化设计的约束多目标分解进化算法 ·637. 2.1权重向量的生成 式中：G,和G,分别代表个体X,和X2的约束违反 初始权重向量的设置是MOEA/D算法的一个 度[4，ε随进化迭代次数的变化如式(10)： 重要步骤，通常采用均匀分布的权重向量生成方式。 (s(0)×(1-t/Gmr)2,t≤0.4×G 最常用的是在超平面f+f+…+f+…+f=1(f为第 E(t)= (0,其他 i维上的分量)上生成均匀分布的权重向量]，每个 (10) 权重向量A=(入1，A2,…,入m)满足式(6)的条件，A 式中：t为进化迭代次数，G为最大进化迭代次数， 的每一维分量入，满足式(7)的条件 ε(0)为初始值，其设置方式如式(11)： 入1+入2+…+入：+…+入m=1 (6) ε(0)=0.4×∑G(X)/W,i=1,2,…,N(11) (01H) 入：∈H月…，月i=1,2,…,m (7) 式中：N为种群规模，G(X)为初始种群个体的约束 式中：H是需要定义的正整数，m为优化目标数量生 违反度，i=1,2,…,N。 成权重向量的数量，其值为N=C,N为种群 式(10)和式(11)通过调节e的取值，能够在容 规模。 忍的约束违反度下扩大约束区域，让更多约束违反 2.2分解策略 度较小的不可行解参与进化，从而加强对可行域边 目前MOEA/D算法中应用效果最好的是Tche- 界的探索力度，来提高种群多样性。同时，ε随进化 bycheff分解策略[)]，它利用极大极小策略的思想将 迭代次数的不断增大逐渐减小直至为零，从而不断 多目标优化问题分解成单目标子问题，具体可表示 缩小约束区域，促使进化达到可行域。因此，式 成式(8)的形式： (9)~(11)通过互相配合，在进化前期能够让优秀 min g"(XI A)=max f(X)) 不可行解参与进化来提高多样性：在进化后期约束 (8) 处理技术强调可行解优于不可行解，从而保障算法 收敛到可行Pareto区域。 式中：A≥0且∑入：=1，i=1,2,…,m,2°=(a, 2.4算法流程 2,…,。)为参考点，z是由当前种群中所有个体 综上所述，约束多目标分解进化算法的具体流 在各个目标函数上的最优值构成的理想点。 程如下： 然而，MOEA/D算法需要结合约束技术才能求 1)初始化阶段：生成N个均匀分布的权重向量 解约束多目标优化问题。为此，本文提出一种新的 入'，2，…，入：计算任意两个权重向量之间的欧氏 约束处理技术，并通过结合MOEA/D算法，构成约 距离，求出每一个权重向量的邻域集合B(i)={i, 束多目标分解进化算法。 i2,…,i},{i1,2,…,,}代表距离权重向量入最近 2.3约束处理技术 的T个权重向量的索引：利用随机方式生成初始种 约束处理技术是约束多目标进化算法中最关键 群{X,X2,…,Xx},令FV=F(X):构造参考点z°= 的技术，它对于平衡可行解与不可行解的关系起着 (zz2…z);设置初始进化迭代次数t=1。 十分重要的作用。研究表明，优秀的不可行解在 2)进化阶段：从每一个B(i),i=1,2,…,N中随 进化中扮演着重要角色，让它们参与进化不仅能够 机选取两个个体与X经过差分变异操作[1)和交叉 加大探索范围，而且能够使得进化从不可行域向可 操作)生成试验个体Y·;若Y的某一维分量超出 行域进化，从而提高种群多样性。然而，过多利用不 定义域，则对该分量进行修补操作5]，让其重新在 可行解反而会影响收敛，降低算法效率。通过分析 定义域内：计算新生个体的目标函数值F(Y)= 得知，在进化前期应该更多利用部分优秀不可行解 (fi(Y))f(Y),…f(Y))。 的有效信息，以改善多样性维持能力，而在进化后期 3)更新阶段：若<f(Y),则令=f(Y);利 应该注重收敛性，以保证种群收敛到真实帕累托 用2.3节方法进行个体比较，若Y优于X,令X= (Pareto)前沿。基于上述思想，提出一种新的约束 Y,FV=F(X); 处理技术，如式(9)： 4)判断终止条件。若t=Gx,则算法停止并输 g"(X I Az")g"(X2 I A,z),G2 >s 出种群中的Pareto最优解；否则，t=t+1,返回2)。 X1优于X2台G1,G2≤e 2.5算法的时间复杂度 G1<G2,其他 假设种群规模为N,目标数量为m,则本文算法 (9) 迭代一次的最坏时间复杂度计算为：种群目标函数２．１ 权重向量的生成 初始权重向量的设置是 ＭＯＥＡ／ Ｄ 算法的一个 重要步骤，通常采用均匀分布的权重向量生成方式。 最常用的是在超平面 ｆ １ ＋ｆ ２ ＋…＋ｆ ｉ ＋…＋ｆｍ ＝ １（ｆ ｉ 为第 ｉ 维上的分量）上生成均匀分布的权重向量［１２］ ，每个 权重向量 λ＝ （λ１ ，λ２ ，… ，λｍ ）满足式（６）的条件，λ 的每一维分量 λｉ 满足式（７）的条件 λ１ ＋ λ２ ＋ … ＋ λｉ ＋ … ＋ λｍ ＝ １ （６） λｉ ∈ ０ Ｈ ， １ Ｈ ，…， Ｈ Ｈ { } ，ｉ ＝ １，２，…，ｍ （７） 式中：Ｈ 是需要定义的正整数，ｍ 为优化目标数量生 成权重向量的数量，其值为 Ｎ ＝ Ｃ ｍ－１ Ｈ＋ｍ－１ ，Ｎ 为种群 规模。 ２．２ 分解策略 目前 ＭＯＥＡ／ Ｄ 算法中应用效果最好的是 Ｔｃｈｅ⁃ ｂｙｃｈｅｆｆ 分解策略［１３］ ，它利用极大极小策略的思想将 多目标优化问题分解成单目标子问题，具体可表示 成式（８）的形式： ｍｉｎ ｇ ｔｅ （Ｘ ｜ λ，ｚ ∗ ） ＝ ｍａｘ １≤ｉ≤ｍ ｛｜ λｉ（ｆ ｉ（Ｘ） － ｚ ∗ ｉ ）｝ （８） 式中：λｉ≥０ 且 ∑ ｍ ｉ ＝ １ λｉ ＝ １，ｉ ＝ １，２，…，ｍ，ｚ ∗ ＝ （ｚ ∗ １ ， ｚ ∗ ２ ，…，ｚ ∗ ｍ ） 为参考点，ｚ ∗ 是由当前种群中所有个体 在各个目标函数上的最优值构成的理想点。 然而，ＭＯＥＡ／ Ｄ 算法需要结合约束技术才能求 解约束多目标优化问题。 为此，本文提出一种新的 约束处理技术，并通过结合 ＭＯＥＡ／ Ｄ 算法，构成约 束多目标分解进化算法。 ２．３ 约束处理技术 约束处理技术是约束多目标进化算法中最关键 的技术，它对于平衡可行解与不可行解的关系起着 十分重要的作用。 研究表明［１４］ ，优秀的不可行解在 进化中扮演着重要角色，让它们参与进化不仅能够 加大探索范围，而且能够使得进化从不可行域向可 行域进化，从而提高种群多样性。 然而，过多利用不 可行解反而会影响收敛，降低算法效率。 通过分析 得知，在进化前期应该更多利用部分优秀不可行解 的有效信息，以改善多样性维持能力，而在进化后期 应该注重收敛性，以保证种群收敛到真实帕累托 （Ｐａｒｅｔｏ）前沿。 基于上述思想，提出一种新的约束 处理技术，如式（９）： Ｘ１ 优于 Ｘ２⇔ ｇ ｔｅ （Ｘ１ ｜ λｚ ∗ ） ＜ ｇ ｔｅ （Ｘ２ ｜ λ，ｚ ∗ ）， Ｇ２ ＞ ε Ｇ１ ， Ｇ２ ≤ ε Ｇ１ ＜ Ｇ２ ， 其他 ì î í ï ï ïï （９） 式中：Ｇ１ 和 Ｇ２ 分别代表个体 Ｘ１ 和 Ｘ２ 的约束违反 度［１４］ ，ε 随进化迭代次数的变化如式（１０）： ε（ｔ） ＝ ε（０） × （１ － ｔ ／ Ｇｍａｘ） ２ ， ｔ ≤ ０．４ × Ｇｍａｘ {０， 其他 （１０） 式中：ｔ 为进化迭代次数，Ｇｍａｘ为最大进化迭代次数， ε（０）为初始值，其设置方式如式（１１）： ε（０） ＝ ０．４ × ∑ Ｎ ｉ ＝ １ Ｇ（Ｘｉ） ／ Ｎ，ｉ ＝ １，２，…，Ｎ （１１） 式中：Ｎ 为种群规模，Ｇ（Ｘｉ）为初始种群个体的约束 违反度，ｉ ＝ １，２，…，Ｎ。 式（１０）和式（１１）通过调节 ε 的取值，能够在容 忍的约束违反度下扩大约束区域，让更多约束违反 度较小的不可行解参与进化，从而加强对可行域边 界的探索力度，来提高种群多样性。 同时，ε 随进化 迭代次数的不断增大逐渐减小直至为零，从而不断 缩小约束区域， 促使进化达到可行域。 因此， 式 （９） ～ （１１）通过互相配合，在进化前期能够让优秀 不可行解参与进化来提高多样性；在进化后期约束 处理技术强调可行解优于不可行解，从而保障算法 收敛到可行 Ｐａｒｅｔｏ 区域。 ２．４ 算法流程 综上所述，约束多目标分解进化算法的具体流 程如下： １）初始化阶段：生成 Ｎ 个均匀分布的权重向量 λ １ ，λ ２ ，…，λ Ｎ ；计算任意两个权重向量之间的欧氏 距离，求出每一个权重向量的邻域集合 Ｂ（ ｉ） ＝ ｛ ｉ １ ， ｉ ２ ，…，ｉＴ ｝，｛ｉ １ ，ｉ ２ ，…，ｉＴ ｝代表距离权重向量 λ ｉ 最近 的 Ｔ 个权重向量的索引；利用随机方式生成初始种 群｛Ｘ１ ，Ｘ２ ，…，ＸＮ｝，令 ＦＶ ｉ ＝Ｆ（Ｘ）；构造参考点 ｚ ∗ ＝ （ｚ ∗ １ ｚ ∗ ２ … ｚ ∗ ｍ ）；设置初始进化迭代次数 ｔ ＝ １。 ２）进化阶段：从每一个 Ｂ（ｉ），ｉ ＝ １，２，…，Ｎ 中随 机选取两个个体与 Ｘｉ 经过差分变异操作［１５］ 和交叉 操作［１５］生成试验个体 Ｙ ∗ ；若 Ｙ 的某一维分量超出 定义域，则对该分量进行修补操作［１５］ ，让其重新在 定义域内；计算新生个体的目标函数值 Ｆ （ Ｙ） ＝ （ｆ １（Ｙ）），ｆ ２（Ｙ），…，ｆｍ（Ｙ））。 ３）更新阶段：若 ｚ ∗ ｉ ＜ｆ ｉ（Ｙ），则令 ｚ ∗ ｉ ＝ ｆ ｉ（Ｙ）；利 用 ２．３ 节方法进行个体比较，若 Ｙ 优于 Ｘｉ，令 Ｘｉ ＝ Ｙ，ＦＶ ｉ ＝Ｆ（Ｘ）； ４）判断终止条件。 若 ｔ ＝ Ｇｍａｘ，则算法停止并输 出种群中的 Ｐａｒｅｔｏ 最优解；否则，ｔ ＝ ｔ＋１，返回 ２）。 ２．５ 算法的时间复杂度 假设种群规模为 Ｎ，目标数量为 ｍ，则本文算法 迭代一次的最坏时间复杂度计算为：种群目标函数 第 ５ 期 刘柏森，等：一种用于大型舰船总体要素优化设计的约束多目标分解进化算法 ·６３７·