2009年7月第16卷增刊控制工程
ControlEngineeringofChina
Jul.2009Vol.16,S1
文章编号:1671-7848(2009)S1-0001-05
变邻域搜索算法综述
董红宇,黄 敏,王兴伟,郑秉霖
1,2
1,2
1
2
(1.东北大学信息科学与工程学院,辽宁沈阳 110004;
2.教育部流程工业综合自动化重点实验室(东北大学),辽宁沈阳 110004)
摘 要:变邻域搜索算法(VariableNeighborhoodSearch,VNS)作为一种新的元启发式算法,
已初步成功地用于解决优化问题,尤其是对于大规模组合优化问题效果良好。对VNS的扩展研究层出不穷,并将其成功地应用到旅行商问题、车辆路径问题、调度、图着色等问题中。简述了经典的元启发式算法,并依次论述了优化问题,VNS算法起源,VNS算法原理,VNS算法分析,扩展的VNS分析,VNS在初始解构造、邻域结构构造、局部搜索和停止准则几个方面的改进方法,针对不同版本的VNS归纳了其在各种优化问题应用情况。基于对改进的VNS的分类,从算法自身研究角度和实际应用角度提出了未来研究方向。
关 键 词:变邻域搜索算法;精确启发式算法;元启发式算法;精确算法;组合优化;连续优化
中图分类号:TP301 文献标识码:A
ReviewofVariableNeighborhoodSearchAlgorithm
DONGHong-yu,HUANGMin,WANGXing-wei,ZHENGBing-lin
2.KeyLaboratoryofIntegratedAutomationofProcessIndustry(NortheasternUniversity),MinistryofEducation,
1,2
1,2
1
2
(1.FacultyofInformationScienceandEngineering,NortheasternUniversity,Shenyang 110004,China;
Shenyang 110004,China)
Abstract:Anewmetaheuristicalgorithm,thevariableneighborhoodsearch(VNS),hasbeensuccessfullyusedtosolveoptimizaiton
problem,especiallyforthelarge-scalecombinationaloptimizationproblem.ManyversionsofVNShavebeenproposedandadoptedtosolvetheTSP,VRP,scheduling,graphcoloringandsoon.Thebriefdescriptionofoptimizaitonproblemandmetaheuristicsarefirstlyintroduced,then,theoriginofVNS,thepricipleofVNS,theananysisofVNS,extensionsofofVNSarepropovedrespectively,andmanycommonmethodstoimprovetheVNSareproposedfromfouraspects,theinitialsolutiondesign,neighborhooddesign,localsearchandstoppingconditions.TheapplicationsofimprovedVNSarealsointroduced.BasedontheclassificationofVNS,researchaboutVNSisproposed,includingapplicationsandimprovements.Keywords:variableneighborhoodsearch;mathheuristics;metaheuristics;optimization
exactmethods;
combinationnaloptimization;
thefuturecontinuous
1 引 言
NP-hard问题一般都需要启发式算法来求解,至少启发式算法可以用于处理大规模实例或者用来获得精确算法的初始解。
启发式算法不具有通用性,故研究者构造通用的启发式算法构架-元启发式算法(亦称亚启发式算法,Metaheuristic)。经典的元启发式算法包括模拟退火算法(SimulatedAnnealing,SA),遗传算法(Ge-neticAlgorithms,GA),禁忌搜索算法(TabuSearch,TS),蚁群优化算法(AntColonyOptimization,
ACO),粒子群优化算法(ParticleSwarmOptimiza-[1]
tion,PSO)等。
1997年Hansen和Mladenovic'首次提出的变邻
[2]
域搜索算法,已成为国外研究热点,近5年来,大量关于VNS的论文涌现在欧洲运筹学等国际杂志上。
VNS的基本思想是在搜索过程中系统地改变邻域结构集来拓展搜索范围,获得局部最优解,再基于此局部最优解重新系统地改变邻域结构集拓展搜索范围找到另一个局部最优解的过程。
收稿日期:2009-04-20; 收修定稿日期:2009-06-29
基金项目:国家自然科学基金资助项目(70671020,70431003,70721001,60673159);新世纪优秀人才支持计划基金资助项目(NCET-05-0295,NCET-05-0289);高等学校博士学科点专项科研基金资助项目([1**********],[1**********]);国家高技术研究发展计划
基金资助项目(2006AA01Z214)
作者简介:董红宇(1982-),男,吉林长春人,博士,主要研究方向为Metaheuristics,流程工业生产计划与调度等;黄敏(1968-),女,
教授,博士生导师。
#2#控 制 工 程 第16卷
xdIN(x),满足min{fi(xl)}[min{fi(xd)},xl称为局部最优解,记为xl。
推论1 若OP存在局部最优解xl,则在F
*
内,给定一个解x(xXxg),则至少存在一个邻域结构N,满足N=|xyxl|。
推论2 若OP存在最优解xg和局部最优解,则对于给定局部最优解xl(xlXxg),至少存在邻域结构N,满足N=|xlyxg|。
一般地,对于一个OP,可能存在p个局部最*(l,g)
优解xl,这样至少存在p个邻域结构N,满足N
=|xlyxg|。
推论3 若OP存在多个局部最优解,则对于
***
任意给定2个局部最优解x(l,1)和x(l,2)(x(l,1)Xx(l,
**
2)(l,g)
*
*
(l,g)
(l,g)
*
*
*
*
**
l
l
*
*
*
2 VNS算法
2001年Hansen和Mladenovic'系统而全面地在
欧洲运筹学杂志(EuropeanJournalofOperationalRe-search,EJOR)上发表了特邀综述,分析了VNS的改进版,针对具体问题与经典算法对比分析。由于VNS在易实性、时效性、人性化和创新性等方面表现突出,若干改进算法已应用于NP-hard问题[3]中。
1)VNS算法起源 Hansen和Mladenovic'归纳了Metaheuristics的基本属性,基于这些属性提出了VNS算法。
[4]
Metaheuristics的基本属性包括:
¹易实性 原理简单,实用性广泛。º通用性 需按照原算法基本步骤。»有效性 对特殊问题应该有效,如可以对大部分实例求得最优解或近优解。最好能很好地解决大部分benchmark问题。¼时效性 求解时间要适当。½鲁棒性 求解不同问题需具有良好的有效性和时效性,较好地解决问题中的不同实例。¾人性化 易于定义、理解和应用,即参数要少,便于操控。¿创新性 将策略机制引入到元启发式算法中可以有更好的有效性或者时效性。
Metaheuristics的优劣可基于上述属性评价。引入VNS算法前,首先给出相关定义和定理,一般地,优化问题OP可以定义如下:
min{fi(x)}(1)
s..t
hj(x)[bj(2)
式中,xIF,FAS;i=1,2,,,n;j=1,2,,,m;S,F,x,fi和hj分别为解空间、可行解集、可行解、目标函数和约束条件函数。
若S是有限的则OP为组合优化问题,若S=n
R则OP为连续优化问题。
定义1 若OP存在最优解,在F内,任意解x与任意解xc之间的广义距离(xXxc),定义为邻域结构,记为N=|xyxc|。称解xc在解x的邻域结构N内。N(x)表示解x的邻域结构,这里的广义距离可以为欧式距离,或者汉明距离,又或是k-OPT算子等。
*
定理1 若OP存在最优解xg,则在F内,给定一个解x(xXxg),则至少存在一个邻域结构gg*
N,满足N=|xyxg|。
证明 对于任意给定可行解xc(xcIF),则存
*
在N=|xyxc|。显然若定理不成立,则xg|F,与已知矛盾,证毕。
定义2 任意给定一个解x,与解x广义距离为解l有
*
),至少存在一个邻域结构N
*
(l,l)
,满足N
(l,l)
=
|x(l,1)yx(l,2)|。
特殊地,对于任意相等的2个解x其邻域结构定义为o邻域结构,记为o=|xyx|,这里的o邻域结构的物理意义为2个解相同,表现在编码上则为编码保持不变。
定理2 若OP为组合优化问题且存在最优解,任意给定一个解x,则在N(x)内可以找到所有局部最优解。
证明 因为OP为组合优化问题,则N(x)内解空间有限,这样可以通过枚举算法获得所有局部最优解,证毕。
[1]
2)VNS原理 VNS源于如下3个性质:¹差异性 基于推论1和定理2,若OP存在
**
局部最优解x(l,k),则在F内,给定解x(xXx(l,k)),对于不同的邻域结构Nk,局部最优解可能不同,即若Nk1=|xyx(l,k1)|,Nk2=|xyx(l,k2)|且k1Xk2,则x(l,k1)与x(l,k2)不一定相同。
º全局性 基于推论1,2和定理2,全局最优**
解xg可以通过局部最优解xl考虑所有可能的邻域结构来获得。
»可达性 基于推论3和定理2,任意一个局
***
部最优解x(l,1)和任意一个局部最优解x(l,2)(x(l,1)Xx(l,|x
*
2)*
*
l
*
l
*
l
)间至少存在一个邻域结构N,满足Nyx
*(l,2)
,ll(l,l)
=
*
(l,1)
|,这样基于局部最优解x
*
(l,2)
*(l,1)
和邻域结
构N
是可以找到局部最优解x的。
基于上述3点性质,对于OP,对所有或部分邻域结构进行系统组合排序(如按照汉明距离由小到大排序),构成邻域结构集Nk(k=1,,,kmax),VNS在搜索过程中系统地不断改变(扩大)邻域结构集Nk来拓展搜索范围,获得局部最优解,再基于获得的局部最优解重新系统地不断改变(扩大)邻域结构集Nk来拓展搜索范围,获得另一个局部,,(l,l)
增刊 董红宇等:变邻域搜索算法综述VNS算法的基本步骤如下:
Step1 初始化 选择邻域结构集Nk(k=1,,,kmax)和停止准则,并给出初始解x。
Step2 重复如下步骤直到满足停止准则:Step211 设置k=1;
Step212 直到k=kmax,重复如下步骤:
Step21211 随机搜索 在x的第k个邻域结构中随机产生xc(xcINk(x));
Step21212 局部搜索 以xc为初始解,应用一些局部搜索方法获得的局部最优解,对应局部最优解为xl。
Step21213 更新 如果局部最优解优于当前最优解,设置x=x,继续在邻域结构N1内搜索;否则设置k=k+1。
与TS对比,VNS是基于邻域结构集的,而TS则是基于单个邻域的,根据上述推论和定理,显然,基于邻域结构集的VNS更加合理有效。
3)VNS算法分析 VNS涉及邻域结构集构造,随机搜索,局部搜索和停止准则等几个关键环节,参数少。Metaheuristics可以分为两类,一类是单点元启发式算法,即若求解过程中始终基于单个解向量进行寻优,称将这种算法为单点元启发式算法(S-Metaheuristics);另一类为多点元启发式算法,即若求解过程中基于多个解向量进行寻优,将这类算法叫做单点元启发式算法(M-Metaheuris-tics)。
S-Metaheuristics与M-Metaheuristcs相比,前者为单点出发,显然在时效性方面比较突出,解决大规模多约束问题尤为有效。但是,前者在解的质量上往往不如后者,因为前者难以保证解的多样性。
VNS算法属于S-Metaheuristics,继承了时效性,突出的是人性化和易适性,故操控参数少,原理简单。通用性方面则是一个Metaheuristics的基本特性,创新性和鲁棒性已经在本文中大量研究中得到验证。另外,邻域结构集和随机搜索过程保证了解具有良好的多样性,而局部搜索过程,则保证了局部搜索能力。因此,有效性方面也较为突出。
良好的VNS主要取决于邻域结构集、邻域结构之间的搜索顺序、同一邻域结构内的搜索机制、局部搜索及停止准则等方面。VNS在求解复杂的大规模组合优化问题有着突出的表现,并且求解时间并不随着问题规模的增大呈指数增长。如KytÊjoki[5]
等针对32个大规模VRP问题设计了VNS,与TS等算法作了对比分析,在求解时效性方面明显优于TS算法。同时设计和测试了20个新的超大规模VRP问题,达到20000个城市数。在港口泊位分配等问题中已经验证算法要优于GA,MA等算[6]法*l
*
#3#
VNS算法的全局收敛性体现在邻域结构集的构造、局部搜索设计和停止准则几处,分析如下:
停止准则只选择k=kmax时,算法全局收敛性仅与邻域结构集Nk有关,根据算法的全局性可知,ky+]且局部搜索部分可以保证在邻域结构集Nk内获得局部最优时,则可以找到全局最优解。实际
g
上,当Nk=N时,已找到全局最优解,但是实际
g
问题中N的选择和确认是难以证明的。因此,算法设计中邻域结构集的设计需要考虑全局性。
停止准则不局限于选择k=kmax时,算法的全局收敛性视具体的局部搜索和停止准则而定。
3 扩展的VNS
扩展的VNS主要包括变邻域深度搜索算法(VariableNeighborhoodDescen,tVND),简化变邻域搜索算法(ReducedVNS,RVNS),偏态变邻域搜索算法(SkewedVNS,SVNS)和变邻域分解搜索算法(VNDecompositionSearch,VNDS)等。
1)VND 解决实际问题时往往通过引入启发式策略到Metaheuristics中,这种方法的时效性要比随机的搜索过程强,有效性有时也比较突出。VND正是省略了标准的VNS算法中的随机搜索,通过探测邻域部分来取代VNS中的随机搜索和局部搜索两个部分,这样以求解质量来换取求解时间。通常情况下,VND在求解质量上难以保证优于VNS,但是求解时间上要优于VNS,因此,对于时效性要求高的大规模问题算法较为有效。当停止准则选择k=kmax时,算法的全局收敛性依赖于探测邻域部分,若探测邻域部分满足定理2,则ky+]时,可以找到最优解。
2)RVNS RVNS是对VNS的简化,目的是节省耗时的局部搜索部分,以解的质量来换取时间。
[7]
省略了VNS算法Step212中Step21212,适用于局域搜索耗时的大规模计算问题。实验结果表明
[3]
RVNS平均耗时比FI方法平均耗时快18倍,而
[2,7]
求解效果上与FI算法相当。RVNS的全局收敛性很难保证。
综上,各版本的VNS有各自的特点,但每个版本都要解决如下几个问题:
初始解的构造问题;邻域结构集Nk和数目kmax的构造问题;邻域结构之间搜索顺序构造问题;同一邻域结构搜索机制构造问题;局域搜索的设计问题;停止准则设计问题。
一般来说,局域搜索可能采用不同算法或策略,而这些算法或策略也涉及到邻域设计问题,这里的邻域设计与邻域结构集Nk一般是不同的。
4 VNS的改进
#4#控 制 工 程 第16卷
1)组合优化问题 组合优化问题中众多问题属于NP-hard,因此,VNS算法在组合优化问题中应用前景广阔。
[3]
¹旅行商问题(TSP) Hansen和Mladenovic'用VNS与2-opt算法求解n从100到1000的TSP问题,结果表明VNS在解的质量上平均有2173%的改进,求解时间上平均节省22109s,并将2-opt算法嵌入到VNS的局部搜索步骤中,仿真结果显
[13]
示算法要优于VNS。Hansen等采用VNS,FI,
[14]
RVNS和VNDS解决TSP问题。Polacek等基于CROSS-exchange和iCROSS-exchange两种操作,设计了8个邻域的VNS算法,用于周期性TSP问题。
[5]
º车辆路径问题(VRP) KytÊjoki等设计了引导式VNS算法处理了32个现有的大规模VRP问题,与TS等算法对比表明,在求解时效性方面明显优于TS算法。解决了达到20000个城市数的
[15]
VRP问题。Hemmelmayr等针对周期性VRP问题设计了VNS,初始解的构造采用节约算法,并构造了移动和十字交叉邻域,采用3-opt算子作为局部搜索策略,改进部分采用SA方法,与以往研究
[16]
成果进行了对比,显示了算法的有效性。Br¾ysy详细地给出了VND和RVNS算法内部设计,对VRPTW问题进行细致的仿真分析,指出VND算法是解决VRPTW问题的最有效的方法之一。
[17]
»调度问题 Blazewicz等将SA,TS算法分别嵌入VNS算法中,解决了F2|dj=d|Yw问题。Zobolas等设计了高效省时的混合Metaheuristics,采用贪婪算法构造初始解,解的进化改进阶段采用GA算法,VNS算法则用于改进个体,并用bench-mark问题验证算法。
[19]
¼能力p-中位问题 Mladenovic'和Hansen设计了VNS算法,基于ORLIB和TSPLIB与TS算
[20]
法对比,效果良好。Crainic等提出了协同邻域VNS算法,并在TSPLIB实例中测试,求解规模达到11948顾客1000中位。
[21]
½图论 Avanthay等首次引入VNS算法解
[22]
决图着色问题。Ribeiro和Souza则采用VND算法求解该问题,其邻域设计采用k-edge交换方法,k=1,2,3,实验表明VND在求解时效性方面要优于GA等算法。
[23]
¾其他领域 Hansen等将色彩量化(压缩)问题看作p-中位问题进行建模,并采用VNS算法求解,与GA,PSO算法作了对比分析。另外,
[7][24]
VNS算法在港口泊位分配、电缆布线等问题中都取得了较好效果。
2)连续优化问题 对于连续优化问题,尤其是非线性非凸的复杂的连续优化问题,VNS算法是[18]
域结构集的构造,邻域结构之间的搜索顺序,同一邻域结构内的搜索机制,局部搜索的设计及停止准则设计几个方面,下文将做详细论述。
1)初始解构造问题 初始解构造的优劣直接影响算法的性能,良好的初始解可以保证算法在较短的时间内获得全局最优解或近优解。通常,初始解的构造有随机策略和启发式策略两种。
2)邻域结构集构造问题 它是算法设计的核心部分之一,原则是尽量保证算法的全局性。通常,全局性好则找到最优解的可能性高,但同时求解时间长。邻域结构构造包括如下问题:
邻域结构集的形式及邻域结构集的个数;邻域结构之间的顺序;邻域结构间移动的策略。
组合优化问题的邻域结构集的设计如下:
[8]
¹汉明距离 汉明距离Q(x,xc)=|x\xc|,表示2个解向量间不同元素的个数,邻域结构集Nk(x)可以表达为Nk(x)={xc|Q(x,xc)=k}或者Nk(x)={xc|Q(x,xc)[Qk}等。
º算子组合 常用算子有包括or-op,tswap,
[10]
2-opt等,Prandtstetter和Raidl设计了10个算子组合。
连续优化问题在邻域结构内解是无限的,
[8]
DraÑic'等将距离定义为
Q(x,y)=(E|xi-yi|),1[p[]
p
1/p
i=1n
其邻域结构定义同上述邻域结构集Nk(x)。对于OP,邻域结构间的顺序可以通过改变邻域结构间次序实现,通常将邻域结构按照由小到大排序,即|Nc|Nc|Nc,1(x)|[2(x)|[,[kmax(x)|邻域结构间移动策略通常采用前向/后向(forward/backward)策略,所谓forward策略就是邻域结构次序始于k=1,然后k自增,而backward策略则是
[11]
邻域结构次序始于k=kmax,然后k自减。
3)局部搜索设计 它是VNS算法的另一个核心部分。局部搜索算法以引入Metaheuristics和策略
[12]
居多,比如first/best改进策略,VND,TS,SA,PSO等等,算法选择视具体问题而定。
4)停止准则 停止准则的选择对算法全局收敛性和时效性有直接影响。VNS算法常见的停止准则有3种:
¹遍历所有邻域结构k=kmax的次数。º设置邻域结构内最大叠迭代次数t,以及最优解最大重复次数r。»最大允许CPU时间。
通常选取上述几种方法的某种组合。
5 VNS在优化问题中应用
VNS算法已经在诸多优化问题中崭露锋芒,下
增刊 董红宇等:变邻域搜索算法综述Mladenovic'首次全面地将VNS用于连续优化问题,其针对无约束连续优化问题和有约束连续优化问题(外点罚函数法处理约束)设计了VNS,与
[8]
GA等算法进行实验对比,效果良好。DraÑic'等提出影响算法性能的参数包括邻域大小和结构,随机过程的分布函数的选择,局部搜索算法设计,通过对测试函数测试,与GA等算法作了对比,效果
[26]
良好。Toksar¥和G
2009年7月第16卷增刊控制工程
ControlEngineeringofChina
Jul.2009Vol.16,S1
文章编号:1671-7848(2009)S1-0001-05
变邻域搜索算法综述
董红宇,黄 敏,王兴伟,郑秉霖
1,2
1,2
1
2
(1.东北大学信息科学与工程学院,辽宁沈阳 110004;
2.教育部流程工业综合自动化重点实验室(东北大学),辽宁沈阳 110004)
摘 要:变邻域搜索算法(VariableNeighborhoodSearch,VNS)作为一种新的元启发式算法,
已初步成功地用于解决优化问题,尤其是对于大规模组合优化问题效果良好。对VNS的扩展研究层出不穷,并将其成功地应用到旅行商问题、车辆路径问题、调度、图着色等问题中。简述了经典的元启发式算法,并依次论述了优化问题,VNS算法起源,VNS算法原理,VNS算法分析,扩展的VNS分析,VNS在初始解构造、邻域结构构造、局部搜索和停止准则几个方面的改进方法,针对不同版本的VNS归纳了其在各种优化问题应用情况。基于对改进的VNS的分类,从算法自身研究角度和实际应用角度提出了未来研究方向。
关 键 词:变邻域搜索算法;精确启发式算法;元启发式算法;精确算法;组合优化;连续优化
中图分类号:TP301 文献标识码:A
ReviewofVariableNeighborhoodSearchAlgorithm
DONGHong-yu,HUANGMin,WANGXing-wei,ZHENGBing-lin
2.KeyLaboratoryofIntegratedAutomationofProcessIndustry(NortheasternUniversity),MinistryofEducation,
1,2
1,2
1
2
(1.FacultyofInformationScienceandEngineering,NortheasternUniversity,Shenyang 110004,China;
Shenyang 110004,China)
Abstract:Anewmetaheuristicalgorithm,thevariableneighborhoodsearch(VNS),hasbeensuccessfullyusedtosolveoptimizaiton
problem,especiallyforthelarge-scalecombinationaloptimizationproblem.ManyversionsofVNShavebeenproposedandadoptedtosolvetheTSP,VRP,scheduling,graphcoloringandsoon.Thebriefdescriptionofoptimizaitonproblemandmetaheuristicsarefirstlyintroduced,then,theoriginofVNS,thepricipleofVNS,theananysisofVNS,extensionsofofVNSarepropovedrespectively,andmanycommonmethodstoimprovetheVNSareproposedfromfouraspects,theinitialsolutiondesign,neighborhooddesign,localsearchandstoppingconditions.TheapplicationsofimprovedVNSarealsointroduced.BasedontheclassificationofVNS,researchaboutVNSisproposed,includingapplicationsandimprovements.Keywords:variableneighborhoodsearch;mathheuristics;metaheuristics;optimization
exactmethods;
combinationnaloptimization;
thefuturecontinuous
1 引 言
NP-hard问题一般都需要启发式算法来求解,至少启发式算法可以用于处理大规模实例或者用来获得精确算法的初始解。
启发式算法不具有通用性,故研究者构造通用的启发式算法构架-元启发式算法(亦称亚启发式算法,Metaheuristic)。经典的元启发式算法包括模拟退火算法(SimulatedAnnealing,SA),遗传算法(Ge-neticAlgorithms,GA),禁忌搜索算法(TabuSearch,TS),蚁群优化算法(AntColonyOptimization,
ACO),粒子群优化算法(ParticleSwarmOptimiza-[1]
tion,PSO)等。
1997年Hansen和Mladenovic'首次提出的变邻
[2]
域搜索算法,已成为国外研究热点,近5年来,大量关于VNS的论文涌现在欧洲运筹学等国际杂志上。
VNS的基本思想是在搜索过程中系统地改变邻域结构集来拓展搜索范围,获得局部最优解,再基于此局部最优解重新系统地改变邻域结构集拓展搜索范围找到另一个局部最优解的过程。
收稿日期:2009-04-20; 收修定稿日期:2009-06-29
基金项目:国家自然科学基金资助项目(70671020,70431003,70721001,60673159);新世纪优秀人才支持计划基金资助项目(NCET-05-0295,NCET-05-0289);高等学校博士学科点专项科研基金资助项目([1**********],[1**********]);国家高技术研究发展计划
基金资助项目(2006AA01Z214)
作者简介:董红宇(1982-),男,吉林长春人,博士,主要研究方向为Metaheuristics,流程工业生产计划与调度等;黄敏(1968-),女,
教授,博士生导师。
#2#控 制 工 程 第16卷
xdIN(x),满足min{fi(xl)}[min{fi(xd)},xl称为局部最优解,记为xl。
推论1 若OP存在局部最优解xl,则在F
*
内,给定一个解x(xXxg),则至少存在一个邻域结构N,满足N=|xyxl|。
推论2 若OP存在最优解xg和局部最优解,则对于给定局部最优解xl(xlXxg),至少存在邻域结构N,满足N=|xlyxg|。
一般地,对于一个OP,可能存在p个局部最*(l,g)
优解xl,这样至少存在p个邻域结构N,满足N
=|xlyxg|。
推论3 若OP存在多个局部最优解,则对于
***
任意给定2个局部最优解x(l,1)和x(l,2)(x(l,1)Xx(l,
**
2)(l,g)
*
*
(l,g)
(l,g)
*
*
*
*
**
l
l
*
*
*
2 VNS算法
2001年Hansen和Mladenovic'系统而全面地在
欧洲运筹学杂志(EuropeanJournalofOperationalRe-search,EJOR)上发表了特邀综述,分析了VNS的改进版,针对具体问题与经典算法对比分析。由于VNS在易实性、时效性、人性化和创新性等方面表现突出,若干改进算法已应用于NP-hard问题[3]中。
1)VNS算法起源 Hansen和Mladenovic'归纳了Metaheuristics的基本属性,基于这些属性提出了VNS算法。
[4]
Metaheuristics的基本属性包括:
¹易实性 原理简单,实用性广泛。º通用性 需按照原算法基本步骤。»有效性 对特殊问题应该有效,如可以对大部分实例求得最优解或近优解。最好能很好地解决大部分benchmark问题。¼时效性 求解时间要适当。½鲁棒性 求解不同问题需具有良好的有效性和时效性,较好地解决问题中的不同实例。¾人性化 易于定义、理解和应用,即参数要少,便于操控。¿创新性 将策略机制引入到元启发式算法中可以有更好的有效性或者时效性。
Metaheuristics的优劣可基于上述属性评价。引入VNS算法前,首先给出相关定义和定理,一般地,优化问题OP可以定义如下:
min{fi(x)}(1)
s..t
hj(x)[bj(2)
式中,xIF,FAS;i=1,2,,,n;j=1,2,,,m;S,F,x,fi和hj分别为解空间、可行解集、可行解、目标函数和约束条件函数。
若S是有限的则OP为组合优化问题,若S=n
R则OP为连续优化问题。
定义1 若OP存在最优解,在F内,任意解x与任意解xc之间的广义距离(xXxc),定义为邻域结构,记为N=|xyxc|。称解xc在解x的邻域结构N内。N(x)表示解x的邻域结构,这里的广义距离可以为欧式距离,或者汉明距离,又或是k-OPT算子等。
*
定理1 若OP存在最优解xg,则在F内,给定一个解x(xXxg),则至少存在一个邻域结构gg*
N,满足N=|xyxg|。
证明 对于任意给定可行解xc(xcIF),则存
*
在N=|xyxc|。显然若定理不成立,则xg|F,与已知矛盾,证毕。
定义2 任意给定一个解x,与解x广义距离为解l有
*
),至少存在一个邻域结构N
*
(l,l)
,满足N
(l,l)
=
|x(l,1)yx(l,2)|。
特殊地,对于任意相等的2个解x其邻域结构定义为o邻域结构,记为o=|xyx|,这里的o邻域结构的物理意义为2个解相同,表现在编码上则为编码保持不变。
定理2 若OP为组合优化问题且存在最优解,任意给定一个解x,则在N(x)内可以找到所有局部最优解。
证明 因为OP为组合优化问题,则N(x)内解空间有限,这样可以通过枚举算法获得所有局部最优解,证毕。
[1]
2)VNS原理 VNS源于如下3个性质:¹差异性 基于推论1和定理2,若OP存在
**
局部最优解x(l,k),则在F内,给定解x(xXx(l,k)),对于不同的邻域结构Nk,局部最优解可能不同,即若Nk1=|xyx(l,k1)|,Nk2=|xyx(l,k2)|且k1Xk2,则x(l,k1)与x(l,k2)不一定相同。
º全局性 基于推论1,2和定理2,全局最优**
解xg可以通过局部最优解xl考虑所有可能的邻域结构来获得。
»可达性 基于推论3和定理2,任意一个局
***
部最优解x(l,1)和任意一个局部最优解x(l,2)(x(l,1)Xx(l,|x
*
2)*
*
l
*
l
*
l
)间至少存在一个邻域结构N,满足Nyx
*(l,2)
,ll(l,l)
=
*
(l,1)
|,这样基于局部最优解x
*
(l,2)
*(l,1)
和邻域结
构N
是可以找到局部最优解x的。
基于上述3点性质,对于OP,对所有或部分邻域结构进行系统组合排序(如按照汉明距离由小到大排序),构成邻域结构集Nk(k=1,,,kmax),VNS在搜索过程中系统地不断改变(扩大)邻域结构集Nk来拓展搜索范围,获得局部最优解,再基于获得的局部最优解重新系统地不断改变(扩大)邻域结构集Nk来拓展搜索范围,获得另一个局部,,(l,l)
增刊 董红宇等:变邻域搜索算法综述VNS算法的基本步骤如下:
Step1 初始化 选择邻域结构集Nk(k=1,,,kmax)和停止准则,并给出初始解x。
Step2 重复如下步骤直到满足停止准则:Step211 设置k=1;
Step212 直到k=kmax,重复如下步骤:
Step21211 随机搜索 在x的第k个邻域结构中随机产生xc(xcINk(x));
Step21212 局部搜索 以xc为初始解,应用一些局部搜索方法获得的局部最优解,对应局部最优解为xl。
Step21213 更新 如果局部最优解优于当前最优解,设置x=x,继续在邻域结构N1内搜索;否则设置k=k+1。
与TS对比,VNS是基于邻域结构集的,而TS则是基于单个邻域的,根据上述推论和定理,显然,基于邻域结构集的VNS更加合理有效。
3)VNS算法分析 VNS涉及邻域结构集构造,随机搜索,局部搜索和停止准则等几个关键环节,参数少。Metaheuristics可以分为两类,一类是单点元启发式算法,即若求解过程中始终基于单个解向量进行寻优,称将这种算法为单点元启发式算法(S-Metaheuristics);另一类为多点元启发式算法,即若求解过程中基于多个解向量进行寻优,将这类算法叫做单点元启发式算法(M-Metaheuris-tics)。
S-Metaheuristics与M-Metaheuristcs相比,前者为单点出发,显然在时效性方面比较突出,解决大规模多约束问题尤为有效。但是,前者在解的质量上往往不如后者,因为前者难以保证解的多样性。
VNS算法属于S-Metaheuristics,继承了时效性,突出的是人性化和易适性,故操控参数少,原理简单。通用性方面则是一个Metaheuristics的基本特性,创新性和鲁棒性已经在本文中大量研究中得到验证。另外,邻域结构集和随机搜索过程保证了解具有良好的多样性,而局部搜索过程,则保证了局部搜索能力。因此,有效性方面也较为突出。
良好的VNS主要取决于邻域结构集、邻域结构之间的搜索顺序、同一邻域结构内的搜索机制、局部搜索及停止准则等方面。VNS在求解复杂的大规模组合优化问题有着突出的表现,并且求解时间并不随着问题规模的增大呈指数增长。如KytÊjoki[5]
等针对32个大规模VRP问题设计了VNS,与TS等算法作了对比分析,在求解时效性方面明显优于TS算法。同时设计和测试了20个新的超大规模VRP问题,达到20000个城市数。在港口泊位分配等问题中已经验证算法要优于GA,MA等算[6]法*l
*
#3#
VNS算法的全局收敛性体现在邻域结构集的构造、局部搜索设计和停止准则几处,分析如下:
停止准则只选择k=kmax时,算法全局收敛性仅与邻域结构集Nk有关,根据算法的全局性可知,ky+]且局部搜索部分可以保证在邻域结构集Nk内获得局部最优时,则可以找到全局最优解。实际
g
上,当Nk=N时,已找到全局最优解,但是实际
g
问题中N的选择和确认是难以证明的。因此,算法设计中邻域结构集的设计需要考虑全局性。
停止准则不局限于选择k=kmax时,算法的全局收敛性视具体的局部搜索和停止准则而定。
3 扩展的VNS
扩展的VNS主要包括变邻域深度搜索算法(VariableNeighborhoodDescen,tVND),简化变邻域搜索算法(ReducedVNS,RVNS),偏态变邻域搜索算法(SkewedVNS,SVNS)和变邻域分解搜索算法(VNDecompositionSearch,VNDS)等。
1)VND 解决实际问题时往往通过引入启发式策略到Metaheuristics中,这种方法的时效性要比随机的搜索过程强,有效性有时也比较突出。VND正是省略了标准的VNS算法中的随机搜索,通过探测邻域部分来取代VNS中的随机搜索和局部搜索两个部分,这样以求解质量来换取求解时间。通常情况下,VND在求解质量上难以保证优于VNS,但是求解时间上要优于VNS,因此,对于时效性要求高的大规模问题算法较为有效。当停止准则选择k=kmax时,算法的全局收敛性依赖于探测邻域部分,若探测邻域部分满足定理2,则ky+]时,可以找到最优解。
2)RVNS RVNS是对VNS的简化,目的是节省耗时的局部搜索部分,以解的质量来换取时间。
[7]
省略了VNS算法Step212中Step21212,适用于局域搜索耗时的大规模计算问题。实验结果表明
[3]
RVNS平均耗时比FI方法平均耗时快18倍,而
[2,7]
求解效果上与FI算法相当。RVNS的全局收敛性很难保证。
综上,各版本的VNS有各自的特点,但每个版本都要解决如下几个问题:
初始解的构造问题;邻域结构集Nk和数目kmax的构造问题;邻域结构之间搜索顺序构造问题;同一邻域结构搜索机制构造问题;局域搜索的设计问题;停止准则设计问题。
一般来说,局域搜索可能采用不同算法或策略,而这些算法或策略也涉及到邻域设计问题,这里的邻域设计与邻域结构集Nk一般是不同的。
4 VNS的改进
#4#控 制 工 程 第16卷
1)组合优化问题 组合优化问题中众多问题属于NP-hard,因此,VNS算法在组合优化问题中应用前景广阔。
[3]
¹旅行商问题(TSP) Hansen和Mladenovic'用VNS与2-opt算法求解n从100到1000的TSP问题,结果表明VNS在解的质量上平均有2173%的改进,求解时间上平均节省22109s,并将2-opt算法嵌入到VNS的局部搜索步骤中,仿真结果显
[13]
示算法要优于VNS。Hansen等采用VNS,FI,
[14]
RVNS和VNDS解决TSP问题。Polacek等基于CROSS-exchange和iCROSS-exchange两种操作,设计了8个邻域的VNS算法,用于周期性TSP问题。
[5]
º车辆路径问题(VRP) KytÊjoki等设计了引导式VNS算法处理了32个现有的大规模VRP问题,与TS等算法对比表明,在求解时效性方面明显优于TS算法。解决了达到20000个城市数的
[15]
VRP问题。Hemmelmayr等针对周期性VRP问题设计了VNS,初始解的构造采用节约算法,并构造了移动和十字交叉邻域,采用3-opt算子作为局部搜索策略,改进部分采用SA方法,与以往研究
[16]
成果进行了对比,显示了算法的有效性。Br¾ysy详细地给出了VND和RVNS算法内部设计,对VRPTW问题进行细致的仿真分析,指出VND算法是解决VRPTW问题的最有效的方法之一。
[17]
»调度问题 Blazewicz等将SA,TS算法分别嵌入VNS算法中,解决了F2|dj=d|Yw问题。Zobolas等设计了高效省时的混合Metaheuristics,采用贪婪算法构造初始解,解的进化改进阶段采用GA算法,VNS算法则用于改进个体,并用bench-mark问题验证算法。
[19]
¼能力p-中位问题 Mladenovic'和Hansen设计了VNS算法,基于ORLIB和TSPLIB与TS算
[20]
法对比,效果良好。Crainic等提出了协同邻域VNS算法,并在TSPLIB实例中测试,求解规模达到11948顾客1000中位。
[21]
½图论 Avanthay等首次引入VNS算法解
[22]
决图着色问题。Ribeiro和Souza则采用VND算法求解该问题,其邻域设计采用k-edge交换方法,k=1,2,3,实验表明VND在求解时效性方面要优于GA等算法。
[23]
¾其他领域 Hansen等将色彩量化(压缩)问题看作p-中位问题进行建模,并采用VNS算法求解,与GA,PSO算法作了对比分析。另外,
[7][24]
VNS算法在港口泊位分配、电缆布线等问题中都取得了较好效果。
2)连续优化问题 对于连续优化问题,尤其是非线性非凸的复杂的连续优化问题,VNS算法是[18]
域结构集的构造,邻域结构之间的搜索顺序,同一邻域结构内的搜索机制,局部搜索的设计及停止准则设计几个方面,下文将做详细论述。
1)初始解构造问题 初始解构造的优劣直接影响算法的性能,良好的初始解可以保证算法在较短的时间内获得全局最优解或近优解。通常,初始解的构造有随机策略和启发式策略两种。
2)邻域结构集构造问题 它是算法设计的核心部分之一,原则是尽量保证算法的全局性。通常,全局性好则找到最优解的可能性高,但同时求解时间长。邻域结构构造包括如下问题:
邻域结构集的形式及邻域结构集的个数;邻域结构之间的顺序;邻域结构间移动的策略。
组合优化问题的邻域结构集的设计如下:
[8]
¹汉明距离 汉明距离Q(x,xc)=|x\xc|,表示2个解向量间不同元素的个数,邻域结构集Nk(x)可以表达为Nk(x)={xc|Q(x,xc)=k}或者Nk(x)={xc|Q(x,xc)[Qk}等。
º算子组合 常用算子有包括or-op,tswap,
[10]
2-opt等,Prandtstetter和Raidl设计了10个算子组合。
连续优化问题在邻域结构内解是无限的,
[8]
DraÑic'等将距离定义为
Q(x,y)=(E|xi-yi|),1[p[]
p
1/p
i=1n
其邻域结构定义同上述邻域结构集Nk(x)。对于OP,邻域结构间的顺序可以通过改变邻域结构间次序实现,通常将邻域结构按照由小到大排序,即|Nc|Nc|Nc,1(x)|[2(x)|[,[kmax(x)|邻域结构间移动策略通常采用前向/后向(forward/backward)策略,所谓forward策略就是邻域结构次序始于k=1,然后k自增,而backward策略则是
[11]
邻域结构次序始于k=kmax,然后k自减。
3)局部搜索设计 它是VNS算法的另一个核心部分。局部搜索算法以引入Metaheuristics和策略
[12]
居多,比如first/best改进策略,VND,TS,SA,PSO等等,算法选择视具体问题而定。
4)停止准则 停止准则的选择对算法全局收敛性和时效性有直接影响。VNS算法常见的停止准则有3种:
¹遍历所有邻域结构k=kmax的次数。º设置邻域结构内最大叠迭代次数t,以及最优解最大重复次数r。»最大允许CPU时间。
通常选取上述几种方法的某种组合。
5 VNS在优化问题中应用
VNS算法已经在诸多优化问题中崭露锋芒,下
增刊 董红宇等:变邻域搜索算法综述Mladenovic'首次全面地将VNS用于连续优化问题,其针对无约束连续优化问题和有约束连续优化问题(外点罚函数法处理约束)设计了VNS,与
[8]
GA等算法进行实验对比,效果良好。DraÑic'等提出影响算法性能的参数包括邻域大小和结构,随机过程的分布函数的选择,局部搜索算法设计,通过对测试函数测试,与GA等算法作了对比,效果
[26]
良好。Toksar¥和G