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

A Regional Local Search Strategy for NSGA Ⅱ Algorithm

针对局部搜索类非支配排序遗传算法(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.