引用本文

栗三一, 王延峰, 乔俊飞, 黄金花. 一种基于区域局部搜索的NSGA II算法. 自动化学报, 2020, 46(12): 2617−2627 doi: 10.16383/j.aas.c180583

Li San-Yi, Wang Yan-Feng, Qiao Jun-Fei, Huang Jin-Hua. A regional local search strategy for NSGA II algorithm. Acta Automatica Sinica, 2020, 46(12): 2617−2627 doi: 10.16383/j.aas.c180583

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180583

关键词

非支配排序遗传算法，分区搜索，局部搜索，多目标优化 

摘要

针对局部搜索类非支配排序遗传算法 (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算法在较短时间内收敛速度和解的质量方面均优于所对比算法.

文章导读

带精英策略的非支配排序遗传算法(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  个体i的拥挤距离

图 2  NSGA II-RLS算法的种群进化过程

图 3  Tmax为5 s时γ的变化曲线

针对局部搜索NSGA II算法计算量大的问题, 本文提出一种基于区域局部搜索的NSGA II算法NSGA II-RLS. NSGA II-RLS根据当前解非支配排序结果直接获取交界点和稀疏点, 设其为交界区域和稀疏区域中心, 在局部搜索过程中仅对各区域中心进行局部搜索, 有效降低单词遗传操作的计算复杂度, 且在NSGA II框架下中心的获取基本不消耗计算量. 局部搜索采用极限优化策略和随机搜索策略, 并设计了搜索范围自适应调整公式, 使算法在初期有较大搜索范围, 在后期有较小搜索范围, 有效提高了算法整体的收敛速度. 通过与其他局部搜索算法对比可以看出, NSGA II-RLS的收敛速度具有明显优势. 当优化时间充足时, NSGA II-RLS的效果与较好的局部搜索算法相比效果有所降低, 因此NSGA II-RLS更适用于解决对优化速度要求较高的问题.

作者简介

栗三一

郑州轻工业大学讲师. 主要研究方向为智能优化控制, 神经网络结构设计和优化. E-mail: wslisanyi@163.com

王延峰

郑州轻工业大学教授. 主要研究方向为DNA计算, DNA自组装及其功能化和生化电路系统. E-mail: yanfengwang@yeah.net

乔俊飞

北京工业大学教授. 主要研究方向为智能控制, 神经网络分析与设计. 本文通信作者. E-mail: junfeq@bjut.edu.cn

黄金花

博士, 武汉船舶职业技术学院电气与电子工程学院教授. 主要研究方向为智能控制及故障诊断. E-mail: angela0412@126.com