一种基于密度的局部搜索NSGA2算法_局部搜索与局部密度的关系资源-CSDN文库

192 浏览量 2021-01-12 23:21:07 上传评论收藏 238KB PDF 举报

资源推荐

资源详情

资源评论

第 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 deﬁned 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

第1期栗三一等: 一种基于密度的局部搜索NSGA2 算法 61

合局部搜索算法,该方法使用爬山法进行局部搜索以

提高收敛速度和精度, 使用偏移法进行横向搜索, 从

而增加种群分布的广泛性. Ishibuchi等

[6]

针对组合优

化问题提出多目标遗传局部搜索算法 (MOGLS), 该

方法对每一次遗传操作的每一个子代都使用复合目

标函数进行评价, 复合函数的权值随机选取, 但每一

次遗传操作复合函数的权值是固定的. Jaszkiewicz

[7]

改进了 MOGLS 方法, 在原方法的基础上加入父代

选择约束, 提高了子代质量. 与此类似, Sindhya 等

[8]

提出了一种标量函数法, 该方法首先定义一个参考

点, 然后建立一个复合函数, 在优化过程中使得该

函数值最小, 其目的是使当前种群尽量远离参考点,

向 Pareto 前沿靠近, 提高了算法的收敛精度和收敛

速度. 在此基础上, Palar 等

[9]

将标准化的上界作为

参考点, 从而扩大了搜索空间, 提高了解分布的广泛

性. Harada等

[10]

首次将梯度信息用于局部搜索, 提出

一种基于梯度信息的局部搜索算法, 根据梯度信息

找到向Pareto前沿收敛的方向, 从而提高收敛速度和

精度. 但是,梯度的计算耗费大量计算资源, 因此 Kim

等

[11]

从邻近解获得的信息推导出局部搜索的方向,

避免了梯度计算,且设定自适应参数来平衡局部搜索

与全局搜索之间的关系,是目前最好的定向搜索算法

之一. 以上这些局部搜索算法在提高 NSGA2 算法的

收敛速度和种群分布特性方面取得了一定成果. 然

而, 目前所有局部搜索算法存在着共同的缺点

[9]

, 在

局部搜索过程中产生大量局部解,使得遗传过程的计

算量成倍增加.

为解决当前基于局部搜索的 NSGA2 算法计算

量大的问题, 本文受文献 [12] 的启发, 提出一种基

于密度的局部搜索NSGA2算法 (NSGA2-DLS). 文献

[12] 针对单目标动态优化问题提出基于记忆的精英

移民策略,每次学习过程中在当前精英解 (最优解)周

围形成精英移民, 参与到下代竞争中, 该机制有效提

高了单目标优化算法的收敛速度和种群多样性. 将

精英移民思想应用于多目标优化算法, 每次遗传操作

只在一个解周围进行局部搜索,可以大量减少局部解

的数量, 从而减少计算量. 然而, 对多目标优化问题而

言,最优解不只一个,而且需要确保解的分布特性, 因

此本文提出的方法使用目标空间中解的密度衡量一

个解的稀疏度, 将当前非支配解中密度最小的解作

为稀疏解,使用两种变异策略在稀疏解周围进行局部

搜索: 1) 使用文献 [1] 中的极限优化变异策略产生新

种群, 从而增加解的精度; 2) 使用局部随机搜索策略

产生新种群从而加快算法的收敛速度. 实验结果表

明, 该方法有效提高了 NSGA2 算法的收敛速度和解

的分布特性, 并且 NSGA2-DLS 在有限函数调用次数

(计算量评价指标) 内得到的解的质量明显优于其他

算法,评价指标达到设定值所消耗的函数调用次数明

显少于其他算法.

1 基本概󰗆

1.1 MOP及相关定义

定义 1 (MOP 问题) 不受约束的多目标极小化

问题可表示为

min F (X) = (f

(X), f

(X), · · · , f

(X)),

X = (x

, x

, · · · , x

⩽ x

⩽ u

, i = 1, 2, · · · , n. (1)

其中: X = (x

, x

, · · · , x

∈ Ω) 为 n维决策向量, Ω

为决策空间; l

和 u

分别为第 i个决策变量的下界和

上界; F (X) ∈ R

为m 维目标向量; f

(X)(j = 1, 2,

· · · , m)为第j 个目标函数; R

为目标函数空间.

定义 2 (Pareto 支配或 Pareto 占优) 对于任意决

策向量u, v ∈ Ω, 若满足以下条件:







(u) ⩽ f

(v), ∀i ∈ 1, 2, · · · , m;

(u) < f

(v), ∃j ∈ 1, 2, · · · , m.

(2)

则称u支配v,或称u较v 占优,记为u ≺ v.

定义 3 (Pareto 最优解) 在决策空间 Ω 中, 若对

于任意解 x, 不存在 x

′

∈ Ω 使得 F (x

′

) = (f

′

), · · · , f

′

))占优于F (x) = (f

(x), f

(x), · · · ,

(x)),则称x为Pareto最优解或非劣解.

定义 4 (Pareto 最优解集) 对于给定的 MOP, 所

有Pareto最优解的集合称为 Pareto最优解集.

定义 5 (Pareto 最优前沿) 对于给定的 MOP, 所

有 Pareto 最优解在目标空间中对应的目标向量的集

合称为Pareto最优前沿.

1.2 局部搜索NSGA2算法

NSGA2算法与局部搜索 NSGA2算法的种群操

作流程如图 1 所示. NSGA2算法的主要框架为, 父代

进行交叉、变异操作形成子代, 然后通过非支配排序

和拥挤距离排序从父代和子代中挑选优秀个体保

留. 局部搜索NSGA2算法在挑选优秀个体之前对每

个父代都进行局部搜索操作, 产生局部解集, 然后在

父代、子代和局部解集中挑选优秀个体保留. 不同的

局部搜索 NSGA2 算法仅在具体局部搜索操作上有

所不同,因为每次局部搜索操作都在每个父代个体周

围产生局部解, 局部解个数数倍于父代个体数, 所有

局部解都要调用目标函数进行计算, 所以局部搜索类

NSGA2算法存在计算量大的问题.

剩余6页未读，继续阅读

评论收藏

内容反馈

weixin_38603924

粉丝: 9
资源: 892

一种基于密度的局部搜索NSGA2算法

NSGA2算法,nsga2算法全称,matlab

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

NSGA2算法介绍

MTALAB NSGA2算法

NSGAⅡ算法.m

一种基于局部密度的k-means算法 (2014年)

基于密度的局部离群数据挖掘算法研究.pdf

论文研究-一种基于局部密度的核K-means算法.pdf

基于相对局部密度的三维节点调度算法

基于改进NSGA-Ⅱ算法的多无人机编队控制路径规划_牛源.zip

一种多目标非线性优化的NSGA-II改进算法.docx

NSGA3算法.zip

02-NSGA-2算法matlab实现-120-nsga-ii.rar

NSGA2算法源程序

NSGA2算法MATLAB程序

NLOF_一种新的基于密度的局部离群点检测算法_王敬华1

一种基于密度的局部离群点检测算法DLOF_胡彩平1

一种改进的基于密度的聚类算法

Matlab实现NSGA-II算法的多目标优化算法实例教程0基础！！易懂！！

多目标遗传算法NSGA

NSGA-II Matlab代码

基于平均距离聚类的NSGA-Ⅱ.docx

基于matlab实现非主导排序遗传算法2.rar

一种新的基于k-NN中心密度启发式密度的聚类算法

最新资源