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

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

A Regional Local Search Strategy for NSGA II Algorithm

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.