基于混合策略的快速非支配排序算法Ⅱ  

Fast Non-dominated Sorting Genetic Algorithm Ⅱ Based on Hybrid Strategies

作　　者：张茂清 汪镭[1] 崔志华[2] 郭为安[3] ZHANG Maoqing;WANG Lei;CUI Zhihua;GUO Weian(School of Electronics and Information,Tongji University,Shanghai 201804,China;School of Computer Science and Technology,Taiyuan University of Science and Technology,Shanxi 030024,China;Sino-Germany College of Applied Sciences,Tongji University,Shanghai 201804,China)

机构地区：[1]同济大学电子与信息工程学院,上海201804 [2]太原科技大学计算机科学与技术学院,山西太原030024 [3]同济大学中德工程学院,上海201804

出　　处：《郑州大学学报（工学版）》2020年第4期23-27,共5页Journal of Zhengzhou University（Engineering Science）

基　　金：国家自然科学基金资助项目(71771176,61503287,61703279);科技部科技冬奥项目(2018YFF0300505)。

摘　　要：快速非支配排序算法Ⅱ(fast non-dominated sorting algorithm Ⅱ,NSGA-Ⅱ)是经典多目标优化算法。然而,其采用的锦标赛策略存在重复选择交叉个体的缺陷,导致后代个体多样性降低。为解决此问题,提出两种改进策略:第一,引入Lévy分布。Lévy分布具有同时平衡局部搜索和全局搜索的能力。通过将Lévy分布引入到执行交叉操作的父代个体,可增加发现父代个体周围潜在较优个体的概率。第二,引入三交叉个体策略。一般的两个交叉个体存在来自同一个体的可能性,引入三交叉个体可以明显降低重复选择父代个体的现象。大量实验结果表明,所提策略可有效改进NSGA-Ⅱ的整体性能。Fast Non-dominated Sorting Algorithm Ⅱ( NSGA-Ⅱ) was an classical multi-objective optimization algorithm,However,the tournament selection strategy in NSGA-Ⅱ had the drawback of repeated selection of the same individuals,resulting in the low diversity of offspring population. To tackle this problem,this paper proposed two strategies. The first one was to incorporate Lévy distribution. Lévy distribution had the ability of balancing the local and global search. Incorporating Lévy distribution to parent individuals to do crossover operator could increase the probability of discovering potential better individuals around patent individuals. The second one was to introduce tri-crossing crossover strategy. In general,two parent individuals had the possibility of coming from the same individual. The introduction of tri-crossing individuals could obviously reduce the phenomenon of repeated selection of parent individuals. Extensive experiments demonstrated that the proposed method could efficiently improve the overall performance of NSGA-Ⅱ.

关 键 词：NSGA-Ⅱ 多目标优化 锦标赛策略 混合策略 种群多样性 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]