第 33卷 第 1期 控 制 与 决 策 Vol.33 No.1
2018年 1月 Control and Decision Jan. 2018
文章编号: 1001-0920(2018)01-0060-07 DOI: 10.13195/j.kzyjc.2016.1303
一种基于密度的局部搜索NSGA2算法
栗三一
†
, 李文静, 乔俊飞
(1. 北京工业大学 自动化学院，北京 100124；2.计算智能与智能系统北京市重点实验室，北京 100124)
摘 要: 针对局部搜索类 NSGA2 算法计算量大的问题, 提出一种基于密度的局部搜索 NSGA2 算法 (NSGA2-
DLS). 使用解的密度衡量解的稀疏度, 并将当前非支配解中稀疏度最小的解定义为稀疏解, 每次遗传过程在稀疏
解周围进行局部搜索. 在局部搜索过程中, 同时采用极限优化策略和随机搜索策略以提高解的质量和收敛速
度. 对 ZDT 系列函数和 DTLZ 系列函数进行仿真实验并与标准 NSGA2 算法、一种局部随机搜索算法和一种定向
搜索算法进行比较,结果表明, NSGA2-DLS在消耗计算量和优化效果方面均优于对比方法.
关键词: NSGA2；密度；局部搜索；多目标优化
中图分类号: TP301 文献标志码: A
A local search strategy based on density for NSGA2 algorithm
LI San-yi
†
, LI Wen-jing, QIAO Jun-fei
(1. College of Automation，Beijing University of Technology，Beijing 100124，China；2. Beijing Key Laboratory of
Computational Intelligence and Intelligent System，Beijing 100124，China)
Abstract: In order to reduce the amount of calculation and keep the advantage of local search strategy simultaneously,
this paper proposes a kind of local search method based on density for the NSGA2(NSGA2-DLS) algorithm. Firstly, the
sparse degree of each solution is evaluated with the density of each solution in the solution space. Then the non-dominated
solution with the smallest sparse deg ree is defined as the sparse solution, and the sparse solutionig is searched around
locally during every genetic process. The NSGA2-DLS algorithm adopts extreme optimization strategy and random
search strategy simultaneously to improve the quality of solutions and convergence rate. The performance of the NSGA2-
DLS algorithm is compared with the performance of the baseline NSGA2 algorithm and two other reported local search
NSGA2 algorithms for multi-objective test problems, including ZDT and DTLZ functions. The simulation results show
that the solution quality and the calculation amount of the NSGA2-DLS algorithm are much better than that of other
methods.
Keywords: NSGA2；density；local search；multi-objective optimization
0 引 言
实际工程中通常存在一些相互冲突的工程目
标, 这类工程问题可以被视为一个多目标优化问题
(MOP). 由于很多实际多目标优化问题的理想最优解
集(帕累托解集) 是凹的或非连续的, 传统的数学规划
方法无法解
[1]
,在一次学习中可以得到一组解的多目
标进化算法受到广泛关注.
在解决 MOP 问题的过程中, 人们提出很多经典
进化算法, 其中 Deb 等
[2]
提出了 NSGA2 算法是目前
最优秀的多目标进化算法之一. NSGA2 算法引入精
英策略, 采用快速非支配排序方法, 并结合拥挤度比
较算子选择胜出解. 但 NSGA2算法作为一种类随机
搜索算法,存在收敛速度慢(遗传操作次数多)和解分
布特性(广泛性和均匀性)较差的问题
[3]
.
局部搜索策略可以有效提高 NSGA2 算法的收
敛速度和分布特性, 研究者已提出多种基于局部搜
索策略的改进型 NSGA2 算法. Deb 等
[4]
首次针对多
目标进化算法提出爬山局部搜索方法, 使用加权求
和的方式形成复合目标函数, 使解向帕累托前沿快
速靠近, 并且有更好的分布性. Lara 等
[5]
提出一种混
收稿日期: 2016-10-16；修回日期: 2016-12-19.
基金项目: 国家自然科学基金重点项目 (61533002)；国家杰出青年科学基金项目 (61225016)；国家自然科学基金
青年基金项目(61603009)；中国博士后科学基金项目(2015M570910)；北京工业大学基础研究基金项目
(002000514315501)；朝阳区博士后工作经费项目(2015ZZ-6).
作者简介: 栗三一 (1988−), 男, 博士生, 从事优化控制的研究；乔俊飞 (1968−), 男, 教授, 博士生导师, 从事智能优
化控制等研究.
†
通讯作者. E-mail: wslisanyi@126.com
剩余6页未读，继续阅读
资源评论
