A Regional Local Search Strategy for NSGA II Algorithm
-
摘要: 针对局部搜索类非支配排序遗传算法 (Nondominated sorting genetic algorithms, NSGA II)计算量大的问题, 提出一种基于区域局部搜索的NSGA II算法(NSGA II based on regional local search, NSGA II-RLS). 首先对当前所有种群进行非支配排序, 根据排序结果获得交界点和稀疏点, 将其定义为交界区域和稀疏区域中心; 其次, 围绕交界点和稀疏点进行局部搜索. 在局部搜索过程中, 同时采用极限优化策略和随机搜索策略以提高解的质量和收敛速度, 并设计自适应参数动态调节局部搜索范围. 通过ZDT和DTLZ系列基准函数对NSGA II-RLS算法进行验证, 并将结果与其他局部搜索类算法进行对比, 实验结果表明NSGA II-RLS算法在较短时间内收敛速度和解的质量方面均优于所对比算法.Abstract: In order to reduce the amount of calculation and keep the advantage of local search strategy simultaneously, this paper proposed a kind of nondominated sorting genetic algorithms (NSGA II) algorithm based on regional local search (NSGA II-RLS). Firstly, get corner points and sparse point according to the results of non-dominated sorting of current populations, define those points as the centers of border areas and sparse area respectively; secondly, search around the corner points and sparse point locally during every genetic process; NSGA II-RLS adopts extreme optimization strategy and random search strategy simultaneously to improve the quality of solutions and convergence rate; adaptive parameter is designed to adjust local search scope dynamically. ZDT and DTLZ functions are used to test the effectiveness of NSGA II-RLS, the performance is compared with four other reported local search algorithms. Results show that: the solution quality of NSGA II-RLS is better than the other methods within limited time; the time complexity of NSGA II-RLS needed to achieve the set IGD value is less than the other methods.
-
带精英策略的非支配排序遗传算法(Nondominated sorting genetic algorithms, NSGA II)作为一种启发式算法, 通过模拟进化论的自然选择和遗传学机理, 可以在不考虑实际工程内部工作方式的情况下求解高度复杂的非线性最优值问题, 被广泛应用于经济结构优化[1]、路径规划[2]、生产调度[3]等实际工程中. 然而作为一种类随机搜索算法, NSGA II存在收敛速度慢的问题[4].
针对NSGA II收敛速度慢的问题, 已有的研究表明局部搜索策略可以有效提高种群收敛速度, 并且在靠近Pareto前沿时避免陷入局部极优[5]. 目前已经提出的局部搜索算法可以分为两类: 随机搜索算法和定向搜索算法.
随机搜索算法将指定解(设为
$X)$ 周围区域作为搜索区间, 对该解增加一较小的随机值形成新的解(设为$Y )$ , 若$ Y $ 支配$ X $ 则$ Y $ 取代$X,$ 之后以$ Y $ 为中心继续进行搜索. 一些研究者认为初始种群对局部搜索算法的效果有重要影响[6-7], 初始种群分布范围越大、分布越均匀, 随机搜索的效果越好, 从这一方面出发设计了基于任务分解的种群初始化方法, 产生初始解之后使用随机搜索尝试从不同的初始解逼近Pareto前沿. 部分研究者尝试将单目标局部搜索算法扩展应用于解决多目标优化问题[8]. 还有一些专家尝试调整搜索区域和搜索范围以提高局部搜索的效率[9-10]. 在专家学者的努力下, 已有的随机搜索类算法可以有效提高种群的收敛速度, 避免种群陷入局部极优, 然而在每一次迭代过程中都需要对每个解进行局部搜索, 普遍存在计算复杂度高的问题.定向搜索算法通过梯度或任务分解等方法指定搜索方向, 使初始种群朝着指定方向收敛. 一些专家使用梯度求导等方法获得搜索方向[11-12], 可以有效指导种群向Pareto前沿逼近, 但是求导计算量太大. 为了避免求导, 研究者利用目标空间几何信息[13]、解的邻域信息[14]和父代与子代之间差别信息[15]等获得搜索方向. 定向搜索算法通过指定搜索方向, 搜索效率高, 但由于搜索方向固定, 对初始种群的分布特性要求很高, 且方向函数的计算也增加了计算复杂度, 与随机算法相同的是随机算法在每一次迭代过程中对每个解进行局部搜索, 计算成本高.
随机搜索算法和定向搜索算法在搜索过程中对每个解均进行局部搜索, 计算复杂度很高[9, 16], 限制了局部搜索算法在对优化速度要求较高场合的应用. 针对这一问题本文提出基于区域局部搜索的NSGA II算法(NSGA II based on regional local search,NSGA II-RLS). NSGA II-RLS以NSGA II为框架, 在交叉变异操作过程后进行局部搜索, 首先根据非支配排序结果获得交界点(目标空间中单个目标向量方向上值最大的解)和稀疏点(除了交界点以外拥挤距离最大的点), 将其定义为交界区域和稀疏区域中心, 然后围绕交界点和稀疏点进行局部搜索. 局部解由极限优化变异策略[17]和随机搜索策略产生, 在局部搜索过程中设计自适应参数动态调整局部搜索范围, 提高了局部搜索的效率. NSGA II-RLS主要有以下优势:
1)交界点和稀疏点可以直接根据非支配排序结果获得, 不需要计算密度和梯度, 计算量小.
2)在交界区域和稀疏区域进行局部搜索可以同时提高收敛速度和增加种群分布的均匀性.
3)只在交界区域和稀疏区域进行局部搜索可以避免计算资源浪费, 有效降低计算复杂度.
4)自适应参数的设定可以使算法在初期具有较大的搜索范围, 靠近Pareto前沿时具有较小的搜索范围, 提高了局部搜索的搜索效率.
通过基准多目标优化实验验证算法的有效性. 实验结果证明NSGA II-RLS可以有效提高NSGA II算法的收敛速度. NSGA II-RLS在有限时间内得到的解的质量明显优于其他算法; 评价指标达到设定值所消耗的计算量明显少于其他算法; 优化效果优于固定搜索范围的局部搜索方法.
1. 非支配、拥挤距离排序
NSGA II算法结合非支配关系与拥挤距离对非支配解进行排序. 假设当前种群为
$ P, $ 种群规模为$N ,$ 对每个个体$ X^i $ (第个$ i $ 个个体), 设两个参数$ S_i $ 和$C_i ,$ $ S_i $ 为被$ X^i $ 支配的个体的集合,$ C_i $ 为支配$ X^i $ 的个体的数量. 将所有$ C_i = 0 $ 的个体组成集合$P_1,$ 其为第1级非支配解, 也是当前的非支配解集. 然后将剩下的所有个体的$ C_i $ 减1, 此时$ C_i = 0 $ 的个体组成集合$P_2 ,$ 其为第2级非支配解, 重复上述过程直到所有解完成分级.然后对每一级的解进行拥挤距离排序, 设第
$ i $ 个解的拥挤距离为$D_i,$ 定义为在个体$ i $ 周围包含个体本身但不包含其他个体的最小的长方形(周长最小的长方形), 如图1所示. 将同一级别的解按照拥挤距离从大到小排列, 最边界的解的拥挤度为无穷大, 同一级别的解拥挤距离越大越好.2. NSGA II-RLS算法
为了解决目前局部搜索多目标优化算法计算复杂度高的问题, 本文提出基于一种基于分区局部搜索的多目标优化算法NSGA II-RLS. NSGA II-RLS根据NSGA II算法的非支配排序结果直接获得交界点和稀疏点, 将其设为交界区域和稀疏区域中心, 不需要额外的计算量; 在交界点和稀疏点周围进行局部搜索, 在提高种群收敛速度的同时保证了进化过程中种群的多样性和均匀性; 分区搜索较以往的局部搜索算法计算复杂度明显降低; 为了提高局部搜索的效率, 对局部搜索范围进行自适应动态调整.
2.1 获取区域中心
局部搜索可以有效提高收敛速度[8-12], 然而对每一个解都进行局部搜索计算量很大, 而且对远离Pareto前沿的被支配解进行局部搜索对种群逼近Pareto前沿贡献不大. 因此人们尝试分区域进行搜索, 区域搜索的中心思想是在重点区域进行局部搜索, 有侧重点的搜索以增加搜索效率, 如在目标空间进行聚类得到聚类中心、通过拐点确定中心等, 然后围绕中心点进行局部搜索.
然而通过聚类、密度计算等确定中心, 任意两个解之间的欧氏距离都需要计算, 增加了算法的计算量. 因此本文直接利用非支配排序和拥挤距离排序获得搜索区域中心, 非支配排序和拥挤距离排序是NSGA II算法的固有步骤, 因此利用其获得搜索区域中心不会增加计算复杂度.
获取区域中心具体方法如下: 设第
$ t $ 代种群为$P,$ 目标函数个数为$ m, $ 根据第1节对种群$ P $ 进行非支配排序和拥挤距离排序, 则第1级非支配解$ P_1 $ 为当前种群的非支配解. 由拥挤距离排序机理可知, 交界点的个数等于目标函数个数, 在种群$ P_1 $ 中前$ m $ 个个体的拥挤距离为无穷大, 第$ m+1 $ 个个体的拥挤距离为除了边界点之外最大的点, 意味着第$ m+1 $ 个个体周围解的密度最低. 由此可知非支配解集$ P_1 $ 中前$ m $ 个个体为交界点, 第$ m+1 $ 个个体为稀疏点, 对应着$ m $ 个交界区域的中心和稀疏区域的中心.本文以交界点和稀疏点为中心进行局部搜索, 交界点是至少在一个目标向量方向上的极大值或极小值, 以交界点为中心进行搜索是确保种群分布范围的一个措施. 拥挤距离最低的点周围是解最稀疏的区域, 围绕稀疏点进行局部搜索可以增加种群分布的均匀性. 因此本文以交界点和拥挤距离最小的点为中心进行局部搜索是有意义的.
以两目标优化问题为例, 图2显示了NSGA II-RLS算法的种群进化过程. 从图中可以看到以下三点: 局部搜索可以提高种群收敛速度; 围绕稀疏点进行局部搜索可以增加种群的分布均匀性; 围绕交界点进行局部搜索可以保持种群的分布范围.
2.2 局部搜索
搜索区域中心确定之后需要围绕区域中心进行局部搜索, 局部搜索的方法对局部搜索效果有重要影响. 本文采用文献[18]提出的局部搜索方法, 同时采用极限优化策略和随机优化策略产生局部解, 可以平衡局部搜索算法的全局搜索能力和局部搜索能力.
极限优化的具体方法如下[17]: 设被搜索区域的中心解为
$X = (x_1,x_2,\cdots,x_n),$ $ n $ 为决策变量个数, 种群规模为N, 则产生局部解个数为$\;n,$ 变异公式为$$ X_i = (x_1,\cdots,x'_i,\cdots,x_n),\; \; \; \; 0<i\leq n $$ (1) $$ x'_i = x_i+\alpha\times\beta_{\max}(x_i),\; \; \; \; 0<i\leq n $$ (2) $$ \alpha = \left\{ {\begin{aligned} &{(2h)^{\textstyle\frac{1}{q+1}}-1},&{0<h<0.5}\\ &{1-[2(1-h)]^{\textstyle\frac{1}{q+1}}},&{0.5\leq h<1} \end{aligned}} \right. $$ (3) $$ \beta_{\max}(x_i) = \max[x_i\!-\!l_i,u_i\!-\!x_i], \; \; \; 0<i\leq n $$ (4) 其中,
$\;x_i$ 为决策变量;$ h $ 为0到1之间的随机数;$ q $ 为正实数, 称为形状参数, 根据文献[17]将$ q $ 设为11;$ l_i $ 和$ u_i $ 分别为第$ i $ 个决策变量的下界和上界;$ \beta_{\rm{max}}(x_i) $ 为当前决策变量$ x_i $ 可变动的最大值.随机局部搜索策略为: 设当前搜索中心解为
$X = (x_1,x_2,\cdots,x_n),$ $ n, $ $ n $ 为决策变量个数, 种群总数为$ N, $ 随机搜索产生局部解个数为种群总数的20%[19] (如不能整除则取整), 随机搜索变异公式为$$\begin{split} &X_k^j = x_1,\cdots,x'_i,\cdots,x_n,\; \; \; \; k = 1,2,\cdots,n\\ &\quad\quad\quad\quad\quad\qquad\qquad\;\; j = 1,2,\cdots,\lceil \frac{0.2N}{n}\rceil \end{split}$$ (5) $$ x'_k = x_k+{\rm{rand}}(\gamma){(u_k-l_k)}\!\quad\qquad\qquad\qquad $$ (6) 其中,
$\;\gamma$ 为搜索范围参数, 用于确定搜索范围的大小;$\rm{rand}(\gamma)$ 表示取值在$ (-\gamma,\gamma) $ 之间的随机数. 同时还产生$ 0.1N $ 个随机解以保证种群的多样性[17]. 以上变异策略共产生$ (m+1)(n+\lceil0.3N\rceil) $ 个局部解,$ m $ 为目标函数个数.2.3 自适应参数设定
对于随机局部搜索策略, 在算法运行初期较大的搜索范围可以提高全局搜索能力, 使种群快速靠近Pareto前沿. 在靠近Pareto前沿后, 较小的搜索范围可以提高种群逼近Pareto前沿的能力. 本文根据最大优化时间(
$ T_{\rm{max}} $ )设计参数动态调整方法.根据经验与已有的研究成果[9-10, 19]设定的取值范围为(0.05,0.2), 设最大优化时间为
$ T_{\rm{max}}, $ 搜索范围调整公式为$$ \gamma_t = 0.05+0.15{\rm{e}}^{\textstyle-\frac{5t}{T_{\rm{max}}}} $$ (7) 其中,
$ t $ 为从优化开始到当前时刻的时间, 使用式(9)时需$ T_{\rm{max}} $ 的值大于5, 若小于5则单位量级可以降低一个等级, 如当$ T_{\rm{max}} $ 为3 s, 则可设其为3 000 ms,$ t $ 与$ T_{\rm{max}} $ 统一单位. 图2和图3分别显示了$ T_{\rm{max}} $ 为5 s和1 000 s时$ \gamma $ 的变化曲线, 从图中可以看出, 其变化轨迹完全相同, 且其变化规律符合预期的搜索范围变化规律, 因此本文提出的自适应公式针对不同的$ T_{\rm{max}} $ 设定值具有很好的自适应性.
图 3$ T_{\rm{max}} $ 为5 s时$ \gamma $ 的变化曲线Fig. 3 the change curve of$ \gamma $ when$ T_{\rm{max}} $ is set to be 5 s注1.
$ \gamma $ 的取值范围本文根据经验与相关文献[9-10, 19]进行设定, 并没有通过实验验证, 后期研究可以通过实验找到最佳的搜索范围.注2. 多数实际优化问题的Pareto前沿是未知的, 本文提出的搜索范围调整方法并不需要知道Pareto前沿, 而且需要设定的参数很少, 适用于解决实际问题.
图 4$ T_{\rm{max}} $ 为1 000 s时$ \gamma $ 的变化曲线Fig. 4 the change curve of$ \gamma $ when$ T_{\rm{max}} $ is set to be 1 000 s2.4 NSGA II-RLS算法流程
根据实际MOP问题设定算法参数: 初始种群数量为
$ N; $ 最大优化时间$ T_{\rm{max}}; $ 决策向量维数$ n ;$ 决策变量取值上界$u = (u_1,u_2,\cdots,u_n)$ 和下界$ l = (l_1,$ $l_2,\cdots, l_n);$ 目标函数个数$ m; $ 形状参数$ q; $ 交叉概率$ p_c $ 和变异概率$ p_m; $ 交叉参数$ \eta_c $ 和变异参数$ \eta_m .$ NSGA II-RLS的具体算法流程如下:步骤1. 在取值范围内随机初始化种群
$ P_I = $ $\{X^1,X^2,\cdots,X^N\}$ , 其中,$X^i = (x'_1,x'_2,\cdots,x'_n)$ ,$i =$ $1,2,\cdots,n$ .步骤2. 对
$ P_I $ 进行非支配、拥挤距离排序, 当前种群中所有非支配解记为$ P_C ,$ 根据排序结果确定交界区域中心和稀疏区域中心.步骤3. 按照标准NSGA II算法对
$ P_I $ 中的种群进行交叉变异, 形成子代$ P_M. $ 步骤4. 围绕交界中心和稀疏区域中心进行局部搜索, 共产生
$ (m+1)(n+\lceil0.3N\rceil) $ 个局部解, 将其集合设为种群$ P_N. $ 步骤5. 将
$ P_I $ 、$ P_M $ 和$ P_N $ 合并, 并对所有解进行非支配、拥挤距离排序, 从中选取最优的$ N $ 个解形成下一代种群$ P_O ,$ 并设$ P_I = P_O. $ 步骤6. 重复步骤2~5, 当达到最大优化时间
$ T_{\rm{max}} $ 或目标精度时进行步骤7.步骤7. 当前
$ P_I $ 中的非支配解即为得到的最优解.与其他局部搜索NSGA II算法相比, NSGA II-RLS算法只在边界和稀疏区域进行局部搜索, 计算量明显降低, 并且能够保证算法的收敛速度和种群的分布性; 采用两种局部搜索策略, 使算法在搜索前期和后期都有较好的搜索效率; 搜索范围的自适应调整平衡了全局搜索与局部搜索的比重; 本文提出的搜索范围调整方法不需要提前获知Pareto前沿, 需要设定的参数也较少, 符合实际工程应用要求.
下面分析NSGA II-RLS算法运行一代的时间复杂度(函数计算次数, 每一次公式的计算都增加计算复杂度1). NSGA II-RLS的时间开销主要集中在子代目标函数值求解部分.
子代目标函数值求解: 交叉变异和局部搜索共产生
$ 0.5N+(m+1)(n+\lceil0.3N\rceil) $ 个解, 因决策变量个数$ n $ 和目标个数$ m $ 一般远小于$ N ,$ 因此该步骤计算复杂度为${\rm{O}}(mN)$ , 一代函数计算次数为${\rm{O}} (0.8N+$ $0.3mN) $ .综合以上分析, NSGA II-RLS的计算复杂度为
${\rm{O}}(mN)$ . 当单个解的局部搜索解数量与本文相同时, 全部解都进行局部搜索的随机搜索算法的计算复杂度为${\rm{O}}(N^2)$ . 对于定向搜索算法, 由于需要通过梯度等方法计算方向, 计算复杂度一般高于随机搜索算法. 标准NSGA II的一代计算复杂度为${\rm{O}}(N)$ ,由此可以看出, 本文提出算法的计算复杂度与标准NSGA II都为$ N $ 的一次方级别, 且其系数也不大, 因此NSGA II-RLS的计算复杂度远远低于其他局部搜索算法, 而且其搜索范围也可以自适应调整.注3. NSGA II-RLS算法采用分区搜索机制, 重点在交界区和解稀疏区域局部搜索, 因此, 对于Pareto非连续的问题, 在优化过程中可能出现某些片段无解的情况, 所以NSGA II-RLS适用于解决Pareto前沿连续的问题.
3. 仿真实验
本文通过双目标ZDT系列函数和三目标DTLZ系列函数对算法NSGA II-RLS进行验证, 测试函数的特征及参数如表1所示. 实验结果与基于密度的局部搜索算法NSGA II-DLS[18]、随机局部搜索算法ED-LS[9]、变深度随机局部搜索算法MOILS[10]和定向搜索算法DirLS[15]进行对比, 一代函数计算次数分别为
${\rm{O}}(0.8N+0.1N^2)$ 、${\rm{O}}(0.5N+C_n^2N)$ 、${\rm{O}}(0.5N+ 15 (n-3)N)$ 和${\rm{O}}(2.5N+C_n^2N)$ , 计算复杂度分别为${\rm{O}}(N^2)$ 、${\rm{O}}(n^2N)$ 、${\rm{O}}(nN)$ 和${\rm{O}}(n^2N)$ . 本文提出的NSGA II-RLS的一代函数计算次数为${\rm{O}}(0.8N+0.3mN)$ , 计算复杂度为${\rm{O}}(mN)$ . 采用MATLAB10.0b软件进行仿真实验, 处理器为3.60 GHz, 8.00 GB内存, Microsoft实验环境.表 1 测试函数参数Table 1 Paramter setting of the test functions函数 Pareto前沿特征 决策变量维度 目标维度 种群规模 ZDT1 凸 30 2 1 000 ZDT2 凹 30 2 1 000 ZDT4 凸 10 2 1 000 ZDT6 凹 10 2 1 000 DTLZ1 非凸非凹 7 3 2 500 DTLZ2 凹 7 3 4 096 DTLZ3 凹 7 3 4 096 DTLZ4 凹 12 3 4 096 双目标实验初始种群规模
$ N $ 为100, 三目标实验初始种群规模为200; 决策变量个数$ n $ 如表1所示; 所有实验均采用模拟二进制交叉变异方法, 交叉参数$ \eta_c $ 和变异参数$ \eta_m $ 均设为20, 交叉和变异概率分别为0.9和$ 1/n ;$ 形状参数$ q $ 设为11.采用综合评价指标 IGD (Inverted generational distance) 和种群多样性指标
$ I $ 进行评价. IGD的计算公式为$$ IGD(P^*,P) = {{\sum\limits_{v\in P^*}d(v,P)}\over {\mid P^*\mid}} $$ (8) 其中,
$ P^* $ 为帕累托解集;$ P $ 为近似解;$ d(v,P) $ 为向量$ v $ 与解集$ P $ 中的向量的欧氏距离最小值;$ \mid P^*\mid $ 为帕累托解集中解的个数.指标
$ I $ 的计算公式为$$ I = {{d_f+d_l+\sum\limits_{i = 1}^{N-1}\mid d_i-d_m\mid}\over {d_f+d_l+(N-1)d_m}} $$ (9) 其中,
$ d_f $ 和$ d_l $ 为帕累托末端解和所得解集边界解之间的欧氏距离,$d_i, \; i = 1,2,\cdot\cdot\cdot,N-1$ 为所获得的连续非支配解之间的欧氏距离,$ d_m $ 为所有$ d_i $ 的平均值.实验结果使用秩和检验(Wilcoxon ranksum test), 在0.05显著性水平上说明不同结果之间的差异显著性.
注4. 在使用优化算法做基准实验时, 大部分文章将种群规模设定为100或200[3-7], ZDT系列问题是双目标问题, 相对比较简单, 因此我们对ZDT实验设定种群规模为100, DTLZ系列为三目标问题, 比较复杂, 我们设定种群规模为200. Deb等[20]在提出NSGA II算法时设定交叉变异参数为20, 交叉概率为0.9, 变异概率为1/n, 之后人们在使用和改进NSGA II算法时, 有一些保持了该参数设定[21-23], 而这一部分不是本文研究的重点, 因此本文也按照文献[20]对交叉变异参数进行设定. 文献[17]提出了极限优化算法, 本文根据文献[17]将形状参数q设为11.
3.1 实验1
本实验设定当ZDT系列函数IGD值达到0.01、三目标函数IGD值达到0.1 (所对比算法双目标函数IGD最优值在0.01以下但接近0.01, 三目标函数IGD最优值在0.1以下并接近0.1)时停止优化, 对双目标和三目标函数最大优化时间
$T_{\rm{max}}$ 分别设为50 s和200 s (各对比算法达到目标精度的时间多数情况下小于此设定值, 为了防止未达到目标精度而因达到最大优化时间停止优化, 将最大优化时间设定为较大的值比较合理), 计算停止时的总函数计算次数. 本实验用于验证算法在达到目标精度时函数计算总次数, 可以反映算法的收敛速度, 实验结果如表2和表3所示.表 2 ZDT系列函数IGD值达到0.01时对比算法的总时间复杂度与进化代数 (连续10次实验求平均)Table 2 For ZDT series function the comparison of total time complexity and the evolution algebra of different algorithms when IGD value reaches 0.01 (mean value of ten consecutive experimental results)算法 ZDT1 ZDT2 ZDT3 ZDT4 复杂度 代数 复杂度 代数 复杂度 代数 复杂度 代数 NSGA II-RLS 2 100 15 2 380 17 1 960 14 1 400 10 NSGA II-DLS[17] 46 440 (+) 43 34 560 (+) 32 31 320 (+) 29 32 400 (+) 30 ED-LS[9] 2 569 450 (+) 59 1 698 450 (+) 39 168 350 (+) 37 163 800 (+) 36 MOILS[10] 1 419 250 (+) 35 1 135 400 (+) 28 327 050 (+) 31 232 100 (+) 22 DirLS[15] 1 312 500 (+) 30 1 137 500 (+) 26 156 750 (+) 33 114 000 (+) 24 注: (+) 表示NSGA II-RLS的结果明显优于相应的算法 表 3 DTLZ系列函数IGD值达到0.1时对比算法的总时间复杂度与进化代数 (连续10次实验求平均)Table 3 For DTLZ series function the comparison of total time complexity and the evolution algebra of different algorithms when IGD value reaches 0.1 (mean value of ten consecutive experimental results)算法 DTLZ1 DTLZ2 DTLZ3 DTLZ4 复杂度 代数 复杂度 代数 复杂度 代数 复杂度 代数 NSGA II-RLS 29 920 88 17 340 19 33 660 99 27 540 41 NSGA II-DLS[17] 378 000 (+) 175 99 360 (+) 46 416 880 (+) 193 192 240 (+) 89 ED-LS[9] 369 800 (+) 86 116 100 (+) 27 460 100(+) 107 545 300 (+) 41 MOILS[10] 883 300 (+) 73 254 100 (+) 21 1 028 500 (+) 85 1 084 000 (+) 40 DirLS [15] 385 400 (+) 82 159 800 (+) 34 451 200 (+) 96 671 300 (+) 49 注: (+) 表示NSGA II-RLS的结果明显优于相应的算法 从表2和表3可以看出, 本文提出的NSGA II-RLS在所有实验中达到目标精度时总函数计算次数远远低于其他对比算法. 在双目标ZDT系列实验中, NSGA II-RLS的总进化代数是最低的. 对于ZDT1和ZDT2, MOILS的函数计算次数均低于ED-LS, 说明当n较大时对搜索范围的调整可以有效提高搜索效率. NSGA II-RLS的实验结果优于ED-LS, 说明极限优化策略的引入可以有效提高种群的收敛效果. DirLS的函数计算次数低于ED-LS, 且该两种算法的局部解生成机制同为2-opt (2-optimization)方法, 说明在双目标实验中指向性参数的加入对收敛性有较大提升. 同时从表2中可以看到, NSGA II-RLS结果的波动范围最小, 说明NSGA II-RLS有较好的稳定性.
在三目标DTLZ系列实验中, MOILS在DTLZ1、DTLZ3和DTLZ4中的进化代数最低, 除NSGA II-DLS之外的算法总进化代数差异不超过30%, 因此总函数计算次数的差异主要由单步函数计算次数产生. 从总函数计算次数可以反映出NSGA II-RLS单步计算复杂度低的优势. MOILS在三目标实验中总函数计算次数是最高的, 结合双目标实验结果可知, 当决策变量维数较高时, 变深度局部搜索的总函数计算次数优于2-opt方法, 当决策变量维数低时2-opt方法的总函数计算次数优于变深度搜索. NSGA II-DLS在所有实验中消耗的进化代数最大, 原因是其只在稀疏解周围进行局部搜索, 导致算法先收敛到前沿附近的某一区域, 之后还需要继续对周边区域进行探索. 由以上分析可知, NSGA II-RLS产生局部解时使用极限优化策略和随机搜索策略可以有效提高种群收敛速度, 其单步函数计算次数远远低于所对比算法. 从局部解生成公式(1)~(6)可知, 其生成解数量仅与种群规模N相关, 而目前大部分局部搜索方法产生局部解时采用2-opt及其衍生方法, 产生局部解的个数不仅与N相关, 而且与决策变量维数
$ n $ 成正相关, 实际问题中,$ n $ 的维数一般较高, 这也是导致一般局部搜索计算复杂度高的原因之一.从以上实验结果分析可知, 达到目标精度时NSGA II-RLS的总函数计算次数最低, 说明NSGA II-RLS具有快速收敛的优点, 并且优化效果比较稳定.
注5. 文献[14, 18, 24]以优化函数计算次数作为评价标准, 但对于局部搜索类算法而言, 遗传过程中梯度计算、密度计算等消耗的计算资源也不容忽视. 为了更公平地比较算法效果, 本文以总时间复杂度为评价标准.
3.2 实验2
实际工程中经常以时间作为停止标准, 本实验设定当达到最大优化时间
$ T_{\rm{max}} $ 时停止实验. 本文提出的NSGA II-RLS优势在于计算复杂度低、收敛速度快, 因此为了体现算法的优势, 本实验对ZDT系列实验设$ T_{\rm{max}} $ 为20 s, DTLZ1和DTLZ3实验设$ T_{\rm{max}} $ 为200 s, DTLZ2实验设$\; T_{\rm{max}}$ 为40 s, DTLZ4实验设$ T_{\rm{max}} $ 为80 s, 比较实验停止时的IGD值、GD值和I值. 所有实验除局部搜索步骤不同, 其他部分完全相同, 以保证实验对比的公平性. 本实验的目的是检验在有限的时间内各算法的优化效果. 实验结果如表4和表5所示.表 4 设定时间内NSGA2-RLS与其他局部搜索算法的ZDT和DTLZ系列实验IGD结果(连续10次实验)Table 4 The IGD results of NSGA2-RLS and other local search algorithms in the ZDT and DTLZ series experiments within the set time (ten consecutive experimental results)算法 NSGA II-RLS NSGA II-DLS[17] ED-LS[9] MOILS[10] DirLS[15] ZDT1 最大值 0.0048 0.0144 0.5686 0.2267 0.6891 最小值 0.0042 0.0047 0.3710 0.1549 0.0060 平均值 0.0045 0.0069 (+) 0.4934 (+) 0.1917 (+) 0.3517 (+) 标准差 1.8129 × 10−4 0.0033 0.0734 0.0214 0.2209 ZDT2 最大值 0.0050 0.1047 1.1891 0.8932 1.0808 最小值 0.0045 0.0045 0.5394 0.2294 0.0812 平均值 0.0048 0.0161 (+) 0.8197 (+) 0.5875 (+) 0.4839 (+) 标准差 1.6269 × 10−4 0.0332 0.2337 0.2122 0.3171 ZDT4 最大值 0.0046 0.3231 0.5547 0.8858 1.2584 最小值 0.0042 0.0044 0.1976 0.2982 0.0052 平均值 0.0043 0.0482 (+) 0.3296 (+) 0.5206 (+) 0.3552 (+) 标准差 1.2738 × 10−4 0.1059 0.0967 0.1738 0.4822 ZDT6 最大值 0.0050 0.0638 0.0161 0.0370 0.0617 最小值 0.0029 0.0029 0.0067 0.0081 0.0028 平均值 0.0038 0.0160 (+) 0.0106 (+) 0.0193 (+) 0.0096 (+) 标准差 7.2131 × 10−4 0.0212 0.0028 0.0101 0.0183 DTLZ1 最大值 0.0268 0.5428 0.4200 0.6859 0.4782 最小值 0.0199 0.0203 0.0258 0.0379 0.0278 平均值 0.0218 0.1128 (+) 0.1434 (+) 0.2823 (+) 0.1411 (+) 标准差 0.0025 0.1296 0.1136 0.1865 0.1724 DTLZ2 最大值 0.0648 0.0984 0.0638 0.0789 0.1212 最小值 0.0549 0.0695 0.0477 0.0583 0.0515 平均值 0.0611 0.0833 (+) 0.0597 0.0669 (=) 0.0751 (+) 标准差 0.0040 0.0120 0.0021 0.0075 0.0089 DTLZ3 最大值 0.0628 0.1690 0.2869 0.9678 0.3185 最小值 0.0536 0.0574 0.0682 0.1036 0.0819 平均值 0.0562 0.0778 (+) 0.0813 (+) 0.5109 (+) 0.1345 (+) 标准差 0.0033 0.0335 0.0679 0.3234 0.0850 DTLZ3 最大值 0.0830 0.3515 0.1735 0.2695 0.2701 最小值 0.0715 0.0897 0.1079 0.1616 0.0706 平均值 0.0755 0.1223 (+) 0.1335 (+) 0.2085 (+) 0.1659 (+) 标准差 0.0047 0.0973 0.0179 0.0393 0.0293 注: (+) 表示NSGA II-RLS的结果明显优于相应的算法,
(=) 表示NSGA II-RLS的结果与相应的算法没有显著差异性表 5 设定时间内NSGA2-RLS与其他局部搜索算法的DTLZ系列实验I结果(连续10次实验)Table 5 The I results of NSGA2-RLS and other local search algorithms in the DTLZ series experiments within the set time (ten consecutive experimental results)算法 NSGA II-RLS NSGA II-DLS[17] ED-LS[9] MOILS[10] DirLS[15] DTLZ1 最大值 0.8066 0.9644 0.8068 1.1246 1.4509 最小值 0.7221 0.7270 0.7484 0.7027 0.9524 平均值 0.7847 0.8217 (+) 0.7879 (=) 0.8269 (+) 1.2380 (+) 标准差 0.0201 0.1267 0.0337 0.2303 0.2571 DTLZ2 最大值 0.7905 1.0426 0.7718 0.8194 1.0250 最小值 0.7008 0.7422 0.7187 0.7243 0.8206 平均值 0.7279 0.8345 (+) 0.7108 0.7443 (+) 0.9314 (+) 标准差 0.0319 0.1247 0.0371 0.0578 0.0786 DTLZ3 最大值 0.7486 0.9972 0.7478 0.8824 0.8185 最小值 0.6793 0.6912 0.7057 0.6866 0.6984 平均值 0.7090 0.8685 (+) 0.7205 (+) 0.7298 (+) 0.7529 (+) 标准差 0.0261 0.1163 0.0294 0.0876 0.0542 DTLZ3 最大值 0.8283 0.8599 1.1197 1.2498 1.3799 最小值 0.7377 0.7965 0.8392 1.0581 0.7823 平均值 0.7907 0.8036 (+) 0.8575 (+) 1.1614 (+) 1.0613 (+) 标准差 0.0449 0.0497 0.0684 0.0856 0.1516 注: (+) 表示NSGA II-RLS的结果明显优于相应的算法,
(=) 表示NSGA II-RLS的结果与相应的算法没有显著差异性从表4可以看出, 除DTLZ2实验外NSGA II-RLS的IGD均值与标准差均为最小. DTLZ2实验各算法实验结果相差不超过30%, 说明对于DTLZ2函数将
$ T_{\rm{max}} $ 设为40 s各算法有相对充足时间收敛到Pareto前沿, 也说明当时间足够长时NSGA II-RLS的效果反而不如已有的局部搜索算法, 但其优化效果与对比算法中最优的结果差距在5% 以内, 从实验1的结果可以看出, 在达到目标精度时NSGA II-RLS的总计算量不超过对比算法总计算量的10%, 也就是说用10%的计算资源达到了95%的优化效果. 在其他实验中NSGA II-RLS的IGD均值与方差均最小, 对应实验1的结果可知, 在优化时间有限且较短时, 计算复杂度低、收敛速度快的NSGA II-RLS算法具有明显优势.ED-LS与DirLS算法类似, DirLS比ED-LS多加了方向性指标指导种群进化, 在ZDT函数实验中DirLS的结果优于ED-LS, 而在三目标实验中ED-LS的结果反而优于DirLS, 这是由于DirLS随着种群进化, 根据进化前后两代种群更新方向指标, 在目标个数较少时方向指标可以加快收敛到Pareto前沿的速度, 但当目标空间维数较高时, 虽然其也能加快收敛速度, 但解的分布性反而不如ED-LS, 从而导致其综合评价指标IGD值不理想. NSGA II-RLS的实验结果均优于NSGA II-DLS, 说明本文提出的分区域搜索比只在稀疏区域搜索有更好的效果, 计算复杂度更低.
从表5可以看出, 对于DTLZ1、DTLZ3和DTLZ4, NSGA II-RLS的I值均值与标准差最低, 说明在较短时间内NSGA II-RLS获得的种群有较好的分布特性. 对于优化时间充足的DTLZ2, NSGA II-RLS的I值较最优的ED-LS的I值降低了2.4%, 说明当优化时间充足时NSGA II-RLS的解的分布特性虽不如最优的算法, 但差距不大. 这与从表4得到的结论相一致.
从表4和表5的实验结果可以看出, 对于ZDT系列实验、DTLZ1、DTLZ3和DTLZ4, NSGA II-RLS的实验结果优于对比算法且具有显著差异性, 说明其结果具有统计学意义.
由以上分析可知, 对于多目标优化问题, 在有限的较短时间内NSGA II-RLS获得种群的IGD值与I值优于所对比算法, 说明在较短时间内NSGA II-RLS具有较好的逼近性和分布特性. 从DTLZ2的实验结果可知, 当优化时间充足时NSGA II-RLS算法效果与最优算法相比虽有所降低, 但差距在5%以内.
注6. NSGA II-RLS的提出主要为了解决局部搜索算法计算量大的问题, 因此将停止时间设定较低可以反映算法的优势. 当算法运行时间足够长时NSGA II-RLS失去其优势, 但从DTLZ2的实验结果可以看出, 优化时间充足时NSGA II-RLS的优化效果与其他优秀算法的优化结果差距在5%以内, 效果相差不大. 本文提出的算法更适用于对优化快速性要求较高的场合, 时间充足的场合也可以应用.
注7. 在实验2中, 优化时间是根据实验的目的设定的, 实验2的目的是验证在相同的时间内算法的优化效果, 为了体现本文算法的优势(计算量小、收敛速度快), 因此设定的DTLZ1、DTLZ3和DTLZ4的优化时间是本文提出算法达到较优效果的时间, 以此突出本文提出算法的优势. DTLZ2的优化时间设定为40 s, 在该时间内各算法均能达到稳定的收敛状态, 我们想通过该实验的结果说明: 在相对充足的优化时间下, 本文提出的算法优化效果与其他算法的效果相差不是很大.
3.3 实验3
本实验以DTLZ系列函数验证提出的自适应搜索范围调整公式的效果. 与实验2相同, DTLZ1和DTLZ3实验设
$ T_{\rm{max}} $ 为200 s, DTLZ2实验设$ T_{\rm{max}} $ 为40 s, DTLZ4实验设$ T_{\rm{max}} $ 为80 s, 比较在0.25$ T_{\rm{max}} $ 、0.5$ T_{\rm{max}} $ 、0.75$ T_{\rm{max}} $ 和$ T_{\rm{max}} $ 时的IGD值. 记搜索范围参数固定为0.2时算法为NSGA II-RLS1, 固定为0.05时算法为NSGA II-RLS2, 实验结果如表6所示.表 6 设定时间内不同搜索范围的局部搜索算法的DTLZ系列实验IGD结果(连续10次实验求均值)Table 6 DTLZ series experiments IGD comparison of local search algorithms with different search ranges within the set time (mean value of ten consecutive experimental results)时刻 NSGA II-RLS NSGA II-RLS1 NSGA II-RLS2 DTLZ1 0.25$T_{\rm{max}}$ 0.4491 0.4787 (=) 2.1773 (+) 0.5$T_{\rm{max}}$ 0.0413 0.0782 (+) 0.5583 (+) 0.75$T_{\rm{max}}$ 0.0265 0.0387 (+) 0.2104 (+) $T_{\rm{max}}$ 0.0218 0.0298 (+) 0.0234 (+) DTLZ2 0.25$T_{\rm{max}}$ 0.1299 0.1278 0.1678 (+) 0.5$T_{\rm{max}}$ 0.0891 0.0986 (+) 0.1288 (+) 0.75$T_{\rm{max}}$ 0.0710 0.0804 (+) 0.1113 (+) $T_{\rm{max}}$ 0.0611 0.0719 (+) 0 0970 (+) DTLZ3 0.25$T_{\rm{max}}$ 0.8229 0.5186 2.0068 (+) 0.5$T_{\rm{max}}$ 0.0902 0.1762 (+) 0.5997 (+) 0.75$T_{\rm{max}}$ 0.0589 0.1090 (+) 0.1820 (+) $T_{\rm{max}}$ 0.0562 0.0811 (+) 0.0952 (+) DTLZ4 0.25$T_{\rm{max}}$ 0.1418 0.1733 (=) 0.1804 (+) 0.5$T_{\rm{max}}$ 0.0967 0.1070 (+) 0.1158 (+) 0.75$T_{\rm{max}}$ 0.0799 0.0880 (+) 0.0829 (=) $T_{\rm{max}}$ 0.0755 0.0819 (+) 0.0717 注: (+) 表示NSGA II-RLS的结果明显优于相应的算法,
(=) 表示NSGA II-RLS的结果与相应的算法没有显著差异性从表6可知, 在各实验初期NSGA II-RLS1的收敛速度占优, 在0.25Tmax时刻的DTLZ2和DTLZ3中, NSGA II-RLS1的IGD值均优于NSGA II-RLS2, 从统计分析结果可知, 对于DTLZ1和DTLZ4, NSGA II-RLS1的结果和NSGA II-RLS的结果没有显著差异性, 说明在初期较大的搜索范围可以增加收敛速度, 初期NSGA II-RLS1的收敛速度优于或相近于NSGA II-RLS. 在中后期, NSGA II-RLS的IGD值均优于NSGA II-RLS1, 且有显著差异性, 说明本文提出的自适应搜索范围调整公式可以有效提高算法整体收敛能力. 在DTLZ1、DTLZ2和DTLZ3实验中NSGA II-RLS2收敛速度明显弱于NSGA II-RLS, 而在相对简单的DTLZ4实验中其最终IGD值又是最好的, 说明较小的搜索范围会拖累算法整体收敛速度, 但当种群收敛到Pareto前沿附近后反而可以增加种群的性能.
由以上分析可知, 本文提出的搜索范围自适应调整方法可以有效平衡算法的全局搜索和局部搜索能力, 使算法在初期有较大的搜索范围, 在中后期搜索范围逐渐减小. 从实验结果可以看出, 该自适应调整方法可以有效提高算法的收敛能力.
4. 总结与展望
针对局部搜索NSGA II算法计算量大的问题, 本文提出一种基于区域局部搜索的NSGA II算法NSGA II-RLS. NSGA II-RLS根据当前解非支配排序结果直接获取交界点和稀疏点, 设其为交界区域和稀疏区域中心, 在局部搜索过程中仅对各区域中心进行局部搜索, 有效降低单词遗传操作的计算复杂度, 且在NSGA II框架下中心的获取基本不消耗计算量. 局部搜索采用极限优化策略和随机搜索策略, 并设计了搜索范围自适应调整公式, 使算法在初期有较大搜索范围, 在后期有较小搜索范围, 有效提高了算法整体的收敛速度. 通过与其他局部搜索算法对比可以看出, NSGA II-RLS的收敛速度具有明显优势. 当优化时间充足时, NSGA II-RLS的效果与较好的局部搜索算法相比效果有所降低, 因此NSGA II-RLS更适用于解决对优化速度要求较高的问题.
-
图 3
$ T_{\rm{max}} $ 为5 s时$ \gamma $ 的变化曲线Fig. 3 the change curve of
$ \gamma $ when$ T_{\rm{max}} $ is set to be 5 s
图 4
$ T_{\rm{max}} $ 为1 000 s时$ \gamma $ 的变化曲线Fig. 4 the change curve of
$ \gamma $ when$ T_{\rm{max}} $ is set to be 1 000 s表 1 测试函数参数
Table 1 Paramter setting of the test functions
函数 Pareto前沿特征 决策变量维度 目标维度 种群规模 ZDT1 凸 30 2 1 000 ZDT2 凹 30 2 1 000 ZDT4 凸 10 2 1 000 ZDT6 凹 10 2 1 000 DTLZ1 非凸非凹 7 3 2 500 DTLZ2 凹 7 3 4 096 DTLZ3 凹 7 3 4 096 DTLZ4 凹 12 3 4 096 
下载: 导出CSV
表 2 ZDT系列函数IGD值达到0.01时对比算法的总时间复杂度与进化代数 (连续10次实验求平均)
Table 2 For ZDT series function the comparison of total time complexity and the evolution algebra of different algorithms when IGD value reaches 0.01 (mean value of ten consecutive experimental results)
算法 ZDT1 ZDT2 ZDT3 ZDT4 复杂度 代数 复杂度 代数 复杂度 代数 复杂度 代数 NSGA II-RLS 2 100 15 2 380 17 1 960 14 1 400 10 NSGA II-DLS[17] 46 440 (+) 43 34 560 (+) 32 31 320 (+) 29 32 400 (+) 30 ED-LS[9] 2 569 450 (+) 59 1 698 450 (+) 39 168 350 (+) 37 163 800 (+) 36 MOILS[10] 1 419 250 (+) 35 1 135 400 (+) 28 327 050 (+) 31 232 100 (+) 22 DirLS[15] 1 312 500 (+) 30 1 137 500 (+) 26 156 750 (+) 33 114 000 (+) 24 注: (+) 表示NSGA II-RLS的结果明显优于相应的算法
下载: 导出CSV
表 3 DTLZ系列函数IGD值达到0.1时对比算法的总时间复杂度与进化代数 (连续10次实验求平均)
Table 3 For DTLZ series function the comparison of total time complexity and the evolution algebra of different algorithms when IGD value reaches 0.1 (mean value of ten consecutive experimental results)
算法 DTLZ1 DTLZ2 DTLZ3 DTLZ4 复杂度 代数 复杂度 代数 复杂度 代数 复杂度 代数 NSGA II-RLS 29 920 88 17 340 19 33 660 99 27 540 41 NSGA II-DLS[17] 378 000 (+) 175 99 360 (+) 46 416 880 (+) 193 192 240 (+) 89 ED-LS[9] 369 800 (+) 86 116 100 (+) 27 460 100(+) 107 545 300 (+) 41 MOILS[10] 883 300 (+) 73 254 100 (+) 21 1 028 500 (+) 85 1 084 000 (+) 40 DirLS [15] 385 400 (+) 82 159 800 (+) 34 451 200 (+) 96 671 300 (+) 49 注: (+) 表示NSGA II-RLS的结果明显优于相应的算法
下载: 导出CSV
表 4 设定时间内NSGA2-RLS与其他局部搜索算法的ZDT和DTLZ系列实验IGD结果(连续10次实验)
Table 4 The IGD results of NSGA2-RLS and other local search algorithms in the ZDT and DTLZ series experiments within the set time (ten consecutive experimental results)
算法 NSGA II-RLS NSGA II-DLS[17] ED-LS[9] MOILS[10] DirLS[15] ZDT1 最大值 0.0048 0.0144 0.5686 0.2267 0.6891 最小值 0.0042 0.0047 0.3710 0.1549 0.0060 平均值 0.0045 0.0069 (+) 0.4934 (+) 0.1917 (+) 0.3517 (+) 标准差 1.8129 × 10−4 0.0033 0.0734 0.0214 0.2209 ZDT2 最大值 0.0050 0.1047 1.1891 0.8932 1.0808 最小值 0.0045 0.0045 0.5394 0.2294 0.0812 平均值 0.0048 0.0161 (+) 0.8197 (+) 0.5875 (+) 0.4839 (+) 标准差 1.6269 × 10−4 0.0332 0.2337 0.2122 0.3171 ZDT4 最大值 0.0046 0.3231 0.5547 0.8858 1.2584 最小值 0.0042 0.0044 0.1976 0.2982 0.0052 平均值 0.0043 0.0482 (+) 0.3296 (+) 0.5206 (+) 0.3552 (+) 标准差 1.2738 × 10−4 0.1059 0.0967 0.1738 0.4822 ZDT6 最大值 0.0050 0.0638 0.0161 0.0370 0.0617 最小值 0.0029 0.0029 0.0067 0.0081 0.0028 平均值 0.0038 0.0160 (+) 0.0106 (+) 0.0193 (+) 0.0096 (+) 标准差 7.2131 × 10−4 0.0212 0.0028 0.0101 0.0183 DTLZ1 最大值 0.0268 0.5428 0.4200 0.6859 0.4782 最小值 0.0199 0.0203 0.0258 0.0379 0.0278 平均值 0.0218 0.1128 (+) 0.1434 (+) 0.2823 (+) 0.1411 (+) 标准差 0.0025 0.1296 0.1136 0.1865 0.1724 DTLZ2 最大值 0.0648 0.0984 0.0638 0.0789 0.1212 最小值 0.0549 0.0695 0.0477 0.0583 0.0515 平均值 0.0611 0.0833 (+) 0.0597 0.0669 (=) 0.0751 (+) 标准差 0.0040 0.0120 0.0021 0.0075 0.0089 DTLZ3 最大值 0.0628 0.1690 0.2869 0.9678 0.3185 最小值 0.0536 0.0574 0.0682 0.1036 0.0819 平均值 0.0562 0.0778 (+) 0.0813 (+) 0.5109 (+) 0.1345 (+) 标准差 0.0033 0.0335 0.0679 0.3234 0.0850 DTLZ3 最大值 0.0830 0.3515 0.1735 0.2695 0.2701 最小值 0.0715 0.0897 0.1079 0.1616 0.0706 平均值 0.0755 0.1223 (+) 0.1335 (+) 0.2085 (+) 0.1659 (+) 标准差 0.0047 0.0973 0.0179 0.0393 0.0293 注: (+) 表示NSGA II-RLS的结果明显优于相应的算法,
(=) 表示NSGA II-RLS的结果与相应的算法没有显著差异性
下载: 导出CSV
表 5 设定时间内NSGA2-RLS与其他局部搜索算法的DTLZ系列实验I结果(连续10次实验)
Table 5 The I results of NSGA2-RLS and other local search algorithms in the DTLZ series experiments within the set time (ten consecutive experimental results)
算法 NSGA II-RLS NSGA II-DLS[17] ED-LS[9] MOILS[10] DirLS[15] DTLZ1 最大值 0.8066 0.9644 0.8068 1.1246 1.4509 最小值 0.7221 0.7270 0.7484 0.7027 0.9524 平均值 0.7847 0.8217 (+) 0.7879 (=) 0.8269 (+) 1.2380 (+) 标准差 0.0201 0.1267 0.0337 0.2303 0.2571 DTLZ2 最大值 0.7905 1.0426 0.7718 0.8194 1.0250 最小值 0.7008 0.7422 0.7187 0.7243 0.8206 平均值 0.7279 0.8345 (+) 0.7108 0.7443 (+) 0.9314 (+) 标准差 0.0319 0.1247 0.0371 0.0578 0.0786 DTLZ3 最大值 0.7486 0.9972 0.7478 0.8824 0.8185 最小值 0.6793 0.6912 0.7057 0.6866 0.6984 平均值 0.7090 0.8685 (+) 0.7205 (+) 0.7298 (+) 0.7529 (+) 标准差 0.0261 0.1163 0.0294 0.0876 0.0542 DTLZ3 最大值 0.8283 0.8599 1.1197 1.2498 1.3799 最小值 0.7377 0.7965 0.8392 1.0581 0.7823 平均值 0.7907 0.8036 (+) 0.8575 (+) 1.1614 (+) 1.0613 (+) 标准差 0.0449 0.0497 0.0684 0.0856 0.1516 注: (+) 表示NSGA II-RLS的结果明显优于相应的算法,
(=) 表示NSGA II-RLS的结果与相应的算法没有显著差异性
下载: 导出CSV
表 6 设定时间内不同搜索范围的局部搜索算法的DTLZ系列实验IGD结果(连续10次实验求均值)
Table 6 DTLZ series experiments IGD comparison of local search algorithms with different search ranges within the set time (mean value of ten consecutive experimental results)
时刻 NSGA II-RLS NSGA II-RLS1 NSGA II-RLS2 DTLZ1 0.25$T_{\rm{max}}$ 0.4491 0.4787 (=) 2.1773 (+) 0.5$T_{\rm{max}}$ 0.0413 0.0782 (+) 0.5583 (+) 0.75$T_{\rm{max}}$ 0.0265 0.0387 (+) 0.2104 (+) $T_{\rm{max}}$ 0.0218 0.0298 (+) 0.0234 (+) DTLZ2 0.25$T_{\rm{max}}$ 0.1299 0.1278 0.1678 (+) 0.5$T_{\rm{max}}$ 0.0891 0.0986 (+) 0.1288 (+) 0.75$T_{\rm{max}}$ 0.0710 0.0804 (+) 0.1113 (+) $T_{\rm{max}}$ 0.0611 0.0719 (+) 0 0970 (+) DTLZ3 0.25$T_{\rm{max}}$ 0.8229 0.5186 2.0068 (+) 0.5$T_{\rm{max}}$ 0.0902 0.1762 (+) 0.5997 (+) 0.75$T_{\rm{max}}$ 0.0589 0.1090 (+) 0.1820 (+) $T_{\rm{max}}$ 0.0562 0.0811 (+) 0.0952 (+) DTLZ4 0.25$T_{\rm{max}}$ 0.1418 0.1733 (=) 0.1804 (+) 0.5$T_{\rm{max}}$ 0.0967 0.1070 (+) 0.1158 (+) 0.75$T_{\rm{max}}$ 0.0799 0.0880 (+) 0.0829 (=) $T_{\rm{max}}$ 0.0755 0.0819 (+) 0.0717 注: (+) 表示NSGA II-RLS的结果明显优于相应的算法,
(=) 表示NSGA II-RLS的结果与相应的算法没有显著差异性
下载: 导出CSV
-
[1] Yang S, Cao D, Lo K. Analyzing and optimizing the impact of economic restructuring on Shanghai's carbon emissions using STIRPAT and NSGA-II. Sustainable Cities and Society, 2018, 40: 44−53 [2] Maity S, Roy A, Maiti M. A rough multi-objective genetic algorithm for uncertain constrained multi-objective solid travelling salesman problem. Granular Computing, 2018, 46: 1−18 [3] Wang H F, Fu Y P, Huang M, George Q, Wang J W. A NSGA-II based memetic algorithm for multiobjective parallel flowshop scheduling problem. Computers and Industrial Engineering, 2017, 113: 185−194 [4] Ahmadi A. Memory-based adaptive partitioning (MAP) of search space for the enhancement of convergence in pareto-based multi-objective evolutionary algorithms. Applied Soft Computing, 2016, 41: 400−417 doi: 10.1016/j.asoc.2016.01.029 [5] Palar P S, Tsuchiya T, Parks G. Comparison of scalarization functions within a local surrogate assisted multi-objective memetic algorithm framework for expensive problems. IEEE Transactions on Evolutionary Computation, 2015: 862−869 [6] Lust T, Teghem J. Two-phase pareto local search for the biobjective traveling salesman problem. Journal of Heuristics, 2010, 16(3): 475−510 doi: 10.1007/s10732-009-9103-9 [7] Alsheddy A, Tsang E E P K. Guided Pareto local search based frameworks for biobjective optimization, In: Proceedings of 2010 IEEE Congress on Evolutionary Computation. Barcelona, Spain: IEEE, 2010. 1−8. [8] Ozkis A, Babalik A. A novel metaheuristic for multi-objective optimization problems: The multi-objective vortex search algorithm. Information Sciences, 2017, 402: 124−148 doi: 10.1016/j.ins.2017.03.026 [9] Michalak K. ED-LS — A heuristic local search for the multiobjective firefighter problem. Applied Soft Computing, 2017, 59: 389−404 doi: 10.1016/j.asoc.2017.05.049 [10] Xu J Y, Wu C C, Yin Y Q, Lin W C. An iterated local search for the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times. Applied Soft Computing, 2017, 52: 39−47 doi: 10.1016/j.asoc.2016.11.031 [11] Lin Q Z, Hu B S, Tang Y, Zhang L Y, Chen J Y, Wang X M, Ming Z. A local search enhanced differential evolutionary algorithm for sparse recovery. Applied Soft Computing, 2017, 57: 144−163 doi: 10.1016/j.asoc.2017.03.034 [12] Capitanescu F, Marvuglia A, Benetto E, Ahmadi A, Tiruta-Barna L. Linear programming-based directed local search for expensive multi-objective optimization problems: application to drinking water production plants. European Journal of Operational Research, 2017, 262(1): 322−334 doi: 10.1016/j.ejor.2017.03.057 [13] Lara A, Sanchez G, Coello C A C, Schutze O. HCS: A new local search strategy for memetic multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 2010, 14(1): 112−132 doi: 10.1109/TEVC.2009.2024143 [14] Kim H, Liou M S. Adaptive directional local search strategy for hybrid evolutionary multiobjective optimization. Applied Soft Computing Journal, 2014, 19(6): 290−311 [15] Michalak K. Evolutionary algorithm with a directional local search for multiobjective optimization in combinatorial problems. Optimization Methods and Software, 2016, 31(2): 392−404 [16] Palar P S, Tsuchiya T, Parks G T. A comparative study of local search within a surrogate-assisted multi-objective memetic algorithm framework for expensive problems. Applied Soft Computing, 2016, 43: 1−19 doi: 10.1016/j.asoc.2015.12.039 [17] Zeng G Q, Chen J, Li L M, Chen M R, Wu L, Dai Y X, Zheng C W. An improved multi-objective population-based extremal optimization algorithm with polynomial mutation. Information Sciences, 2016, 330: 49−73 doi: 10.1016/j.ins.2015.10.010 [18] 栗三一, 李文静, 乔俊飞. 一种基于密度的局部搜索NSGA2算法. 控制与决策, 2018, (1): 60−66Li San-Yi, Li Wen-Jing, Qiao Jun-Fei. A local search strategy based on density for NSGA2 algorithm. Control and Decision, 2018, (1): 60−66 [19] Yang S X. Genetic algorithms with memory- and elitism-based immigrants in dynamic environments. Evolutionary Computation, 2014, 16(3): 385−416 [20] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182−197 doi: 10.1109/4235.996017 [21] Kumar M, Guria C. The elitist non-dominated sorting genetic algorithm with inheritance (i-NSGA-II) and its jumping gene adaptations for multi-objective optimization. Information Sciences, 2017, 382−383: 15−37 doi: 10.1016/j.ins.2016.12.003 [22] Brownlee A E I, Wright J A. Constrained, mixed-integer and multi-objective optimisation of building designs by NSGA-II with fitness approximation. Applied Soft Computing, 2015, 33: 114−126 doi: 10.1016/j.asoc.2015.04.010 [23] Chan F T S, Jha A, Tiwari M K. Bi-objective optimization of three echelon supply chain involving truck selection and loading using NSGA-II with heuristics algorithm. Applied Soft Computing Journal, 2016, 38: 978−987 doi: 10.1016/j.asoc.2015.10.067 [24] Sindhya K, Miettinen K, Deb K. A hybrid framework for evolutionary multi-objective optimization. IEEE Transactions on Evolutionary Computation, 2013, 17(4): 495−511 doi: 10.1109/TEVC.2012.2204403 期刊类型引用(15)
1. 陈翔，缪希仁，庄胜斌，谢海鑫. 涡流斥力快速操动机构改进型NSGA-Ⅱ多目标优化设计. 电器与能效管理技术. 2024(01): 24-30 . 
百度学术2. 张昀普，付强，单甘霖，黄燕. 多传感器协同区域搜索与目标跟踪的调度方法. 北京航空航天大学学报. 2024(03): 850-860 . 百度学术3. 宋存利，竺啸天. 求解复杂混合流水车间调度的改进NSGAII算法. 计算机仿真. 2024(03): 379-387 . 百度学术4. 张国晨，樊凯翔，王浩，秦淑芬，孙超利. 自适应建模策略辅助的昂贵多目标进化算法. 太原科技大学学报. 2024(02): 113-118 . 百度学术5. 常大亮，史海波，刘昶. 具有紧时、高能耗特征的混合流水车间多目标调度优化问题. 中国机械工程. 2024(07): 1269-1278 . 百度学术6. 肖世隆，邹国平，安斯光. 基于改进MOEA/D分解算法的天线阵优化设计. 现代电子技术. 2023(01): 12-16 . 百度学术7. 摆世彬，田志浩，刘刚，张文朝. 考虑功角稳定与暂态过电压的新能源送端电网储能系统优化配置模型. 可再生能源. 2023(07): 971-977 . 百度学术8. 关钦月，郑旭，徐敬友，熊炜，郭婷，林洁瑜，张文朝，刘祖耀. 规模新能源接入下考虑安稳风险评估的受端电网运行优化模型. 可再生能源. 2023(07): 957-963 . 百度学术9. 孙超利，李贞，金耀初. 模型辅助的计算费时进化高维多目标优化. 自动化学报. 2022(04): 1119-1128 . 本站查看10. 李鑫，林延平，刘长玺，何义琼，顾大可. 考虑广泛负荷聚合商无功调节优先权的调度决策模型. 太阳能学报. 2022(05): 67-73 . 百度学术11. 黄朝志，耿永民，原红卫. 基于NSGA-Ⅱ的局部范围搜索算法的电机参数优化. 电机与控制应用. 2022(06): 9-18 . 百度学术12. 赵克刚，何坤阳，黎杰，梁志豪，贝泾浩，王玉龙. 基于改进动态规划法的HEV多目标能量管理策略. 华南理工大学学报(自然科学版). 2022(09): 138-148 . 百度学术13. 滕云，弓玮，冷欧阳，王泽镝，周达，陈哲. 用于提升电–气两网调节能力的微网集群协调运行模型. 中国电机工程学报. 2021(02): 642-655 . 百度学术14. 范衠，朱贵杰，李文姬，游煜根，李晓明，林培涵，辛斌. 进化计算在复杂机电系统设计自动化中的应用综述. 自动化学报. 2021(07): 1495-1515 . 本站查看15. 李彦吉，王鑫陶，康赫然，张秀路，张伟，韩永强，闫佳佳. 考虑效率、效益与碳减排提升的含可再生能源配电网投资优选模型. 可再生能源. 2021(12): 1662-1668 . 百度学术其他类型引用(11)
-
下载:
计量
- 文章访问数: 1259
- HTML全文浏览量: 546
- PDF下载量: 263
- 被引次数: 26
