2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于区域局部搜索的NSGA II算法

栗三一 王延峰 乔俊飞 黄金花

栗三一, 王延峰, 乔俊飞, 黄金花. 一种基于区域局部搜索的NSGA II算法. 自动化学报, 2020, 46(12): 2617−2627 doi: 10.16383/j.aas.c180583
引用本文: 栗三一, 王延峰, 乔俊飞, 黄金花. 一种基于区域局部搜索的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
Citation: 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

一种基于区域局部搜索的NSGA II算法

doi: 10.16383/j.aas.c180583
基金项目: 全国教育科学规划一般课题(BJA170096), 湖北省教育科学规划课题 (2018GB148), 教育部新一代信息技术创新项目(2019ITA04002), 河南省科技攻关项目基金 (202102310284)资助
详细信息
    作者简介:

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

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

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

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

A Regional Local Search Strategy for NSGA II Algorithm

Funds: Supported by General Project of National Education Science (BJA170096), Education Science Project of Hubei Province (2018GB148), Innovation Project in Information Technology of Education Ministry (2019ITA04002), and Key Projects of Science and Technology of Henan Province (202102310284)
  • 摘要: 针对局部搜索类非支配排序遗传算法 (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算法在较短时间内收敛速度和解的质量方面均优于所对比算法.
  • 图  1  个体$ i $的拥挤距离

    Fig.  1  Crowded distance of individual $ i $

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

    Fig.  2  The evolution process of NSGA II-RLS algorithm

    图  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前沿特征决策变量维度目标维度种群规模
    ZDT13021 000
    ZDT23021 000
    ZDT41021 000
    ZDT61021 000
    DTLZ1非凸非凹732 500
    DTLZ2734 096
    DTLZ3734 096
    DTLZ41234 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)

    算法ZDT1ZDT2ZDT3ZDT4
    复杂度代数复杂度代数复杂度代数复杂度代数
    NSGA II-RLS2 100152 380171 960141 40010
    NSGA II-DLS[17]46 440 (+)4334 560 (+)3231 320 (+)2932 400 (+)30
    ED-LS[9]2 569 450 (+)591 698 450 (+)39168 350 (+)37163 800 (+)36
    MOILS[10]1 419 250 (+)351 135 400 (+)28327 050 (+)31232 100 (+)22
    DirLS[15]1 312 500 (+)301 137 500 (+)26156 750 (+)33114 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)

    算法DTLZ1DTLZ2DTLZ3DTLZ4
    复杂度代数复杂度代数复杂度代数复杂度代数
    NSGA II-RLS29 9208817 3401933 6609927 54041
    NSGA II-DLS[17]378 000 (+)17599 360 (+)46416 880 (+)193192 240 (+)89
    ED-LS[9]369 800 (+)86116 100 (+)27460 100(+)107545 300 (+)41
    MOILS[10]883 300 (+)73254 100 (+)211 028 500 (+)851 084 000 (+)40
    DirLS [15]385 400 (+)82159 800 (+)34451 200 (+)96671 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-RLSNSGA II-DLS[17]ED-LS[9]MOILS[10]DirLS[15]
    ZDT1最大值0.00480.01440.56860.22670.6891
    最小值0.00420.00470.37100.15490.0060
    平均值0.00450.0069 (+)0.4934 (+)0.1917 (+)0.3517 (+)
    标准差1.8129 × 10−40.00330.07340.02140.2209
    ZDT2最大值0.00500.10471.18910.89321.0808
    最小值0.00450.00450.53940.22940.0812
    平均值0.00480.0161 (+)0.8197 (+)0.5875 (+)0.4839 (+)
    标准差1.6269 × 10−40.03320.23370.21220.3171
    ZDT4最大值0.00460.32310.55470.88581.2584
    最小值0.00420.00440.19760.29820.0052
    平均值0.00430.0482 (+)0.3296 (+)0.5206 (+)0.3552 (+)
    标准差1.2738 × 10−40.10590.09670.17380.4822
    ZDT6最大值0.00500.06380.01610.03700.0617
    最小值0.00290.00290.00670.00810.0028
    平均值0.00380.0160 (+)0.0106 (+)0.0193 (+)0.0096 (+)
    标准差7.2131 × 10−40.02120.00280.01010.0183
    DTLZ1最大值0.02680.54280.42000.68590.4782
    最小值0.01990.02030.02580.03790.0278
    平均值0.02180.1128 (+)0.1434 (+)0.2823 (+)0.1411 (+)
    标准差0.00250.12960.11360.18650.1724
    DTLZ2最大值0.06480.09840.06380.07890.1212
    最小值0.05490.06950.04770.05830.0515
    平均值0.06110.0833 (+)0.05970.0669 (=)0.0751 (+)
    标准差0.00400.01200.00210.00750.0089
    DTLZ3最大值0.06280.16900.28690.96780.3185
    最小值0.05360.05740.06820.10360.0819
    平均值0.05620.0778 (+)0.0813 (+)0.5109 (+)0.1345 (+)
    标准差0.00330.03350.06790.32340.0850
    DTLZ3最大值0.08300.35150.17350.26950.2701
    最小值0.07150.08970.10790.16160.0706
    平均值0.07550.1223 (+)0.1335 (+)0.2085 (+)0.1659 (+)
    标准差0.00470.09730.01790.03930.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-RLSNSGA II-DLS[17]ED-LS[9]MOILS[10]DirLS[15]
    DTLZ1最大值0.80660.96440.80681.12461.4509
    最小值0.72210.72700.74840.70270.9524
    平均值0.78470.8217 (+)0.7879 (=)0.8269 (+)1.2380 (+)
    标准差0.02010.12670.03370.23030.2571
    DTLZ2最大值0.79051.04260.77180.81941.0250
    最小值0.70080.74220.71870.72430.8206
    平均值0.72790.8345 (+)0.71080.7443 (+)0.9314 (+)
    标准差0.03190.12470.03710.05780.0786
    DTLZ3最大值0.74860.99720.74780.88240.8185
    最小值0.67930.69120.70570.68660.6984
    平均值0.70900.8685 (+)0.7205 (+)0.7298 (+)0.7529 (+)
    标准差0.02610.11630.02940.08760.0542
    DTLZ3最大值0.82830.85991.11971.24981.3799
    最小值0.73770.79650.83921.05810.7823
    平均值0.79070.8036 (+)0.8575 (+)1.1614 (+)1.0613 (+)
    标准差0.04490.04970.06840.08560.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-RLSNSGA II-RLS1NSGA II-RLS2
    DTLZ10.25$T_{\rm{max}}$0.44910.4787 (=)2.1773 (+)
    0.5$T_{\rm{max}}$0.04130.0782 (+)0.5583 (+)
    0.75$T_{\rm{max}}$0.02650.0387 (+)0.2104 (+)
    $T_{\rm{max}}$0.02180.0298 (+)0.0234 (+)
    DTLZ20.25$T_{\rm{max}}$0.12990.12780.1678 (+)
    0.5$T_{\rm{max}}$0.08910.0986 (+)0.1288 (+)
    0.75$T_{\rm{max}}$0.07100.0804 (+)0.1113 (+)
    $T_{\rm{max}}$0.06110.0719 (+)0 0970 (+)
    DTLZ30.25$T_{\rm{max}}$0.82290.51862.0068 (+)
    0.5$T_{\rm{max}}$0.09020.1762 (+)0.5997 (+)
    0.75$T_{\rm{max}}$0.05890.1090 (+)0.1820 (+)
    $T_{\rm{max}}$0.05620.0811 (+)0.0952 (+)
    DTLZ40.25$T_{\rm{max}}$0.14180.1733 (=)0.1804 (+)
    0.5$T_{\rm{max}}$0.09670.1070 (+)0.1158 (+)
    0.75$T_{\rm{max}}$0.07990.0880 (+)0.0829 (=)
    $T_{\rm{max}}$0.07550.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−66

    Li 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
  • 加载中
图(4) / 表(6)
计量
  • 文章访问数:  1179
  • HTML全文浏览量:  524
  • PDF下载量:  249
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-09-01
  • 录用日期:  2019-01-18
  • 网络出版日期:  2020-12-29
  • 刊出日期:  2020-12-29

目录

    /

    返回文章
    返回