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

A Regional Local Search Strategy for NSGA Ⅱ Algorithm

作　　者：栗三一 王延峰[1] 乔俊飞 黄金花[3] LI San-Yi;WANG Yan-Feng;QIAO Jun-Fei;HUANG Jin-Hua(Zhengzhou University of Light Industry,Zhengzhou 450002;Faculty of Information Technology,Beijing University of Technology,Beijing 100124;Wuhan Institute of Shipbuilding Technology,Wuhan 430000)

机构地区：[1]郑州轻工业学院,郑州450002 [2]北京工业大学信息学部,北京100124 [3]武汉船舶职业技术学院,武汉430000

出　　处：《自动化学报》2020年第12期2617-2627,共11页Acta Automatica Sinica

基　　金：全国教育科学规划一般课题(BJA170096);湖北省教育科学规划课题(2018GB148);教育部新一代信息技术创新项目(2019ITA04002);河南省科技攻关项目基金(202102310284)资助。

摘　　要：针对局部搜索类非支配排序遗传算法(Nondominated sorting genetic algorithms, NSGA Ⅱ)计算量大的问题,提出一种基于区域局部搜索的NSGA Ⅱ算法(NSGA Ⅱ based on regional local search, NSGA Ⅱ-RLS).首先对当前所有种群进行非支配排序,根据排序结果获得交界点和稀疏点,将其定义为交界区域和稀疏区域中心;其次,围绕交界点和稀疏点进行局部搜索.在局部搜索过程中,同时采用极限优化策略和随机搜索策略以提高解的质量和收敛速度,并设计自适应参数动态调节局部搜索范围.通过ZDT和DTLZ系列基准函数对NSGA Ⅱ-RLS算法进行验证,并将结果与其他局部搜索类算法进行对比,实验结果表明NSGA Ⅱ-RLS算法在较短时间内收敛速度和解的质量方面均优于所对比算法.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 Ⅱ) algorithm based on regional local search(NSGA Ⅱ-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 Ⅱ-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 Ⅱ-RLS, the performance is compared with four other reported local search algorithms. Results show that: the solution quality of NSGA Ⅱ-RLS is better than the other methods within limited time;the time complexity of NSGA Ⅱ-RLS needed to achieve the set IGD value is less than the other methods.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]