阅读本文大概需要 10 分钟。

算法介绍

自适应大邻域搜索算法（Adaptive Large Neighborhood Search），简称（ALNS），是由Ropke与Pisinger在2006年提出的一种启发式方法，其在邻域搜索的基础上增加了对算子的作用效果的衡量，使算法能够自动选择好的算子对解进行破坏与修复，从而有一定几率得到更好的解。

应用场景

1.外卖场景：搜索订单分配骑手的最优方案

2.派单场景：搜索订单分配司机的最优方案

3.车辆路径规划问题

算法流程

邻域自适应算法,变邻域搜索算法


1.生成初始解，当前解X0=初始解，最优解X1=X0
2.重复以下步骤进行迭代直到停止准则
2.1根据算子权重选择破坏与修复算子，并更新算子使用次数
2.2破坏算子和修复算子依次对当前解操作得到新解X2
2.3更新当前解
-如f(X2)<f(X0)，则X0=X2
-如f(X2)>f(X0)，则以一定的概率接受该解作为当前解
2.4更新最优解
-如f(X2)<f(X1)，则X1=X2
2.5更新算子的分数
2.6更新算子的权重
2.7重置当前解
3.返回最优解X1

每次迭代就是从初始解中删除N个点，然后依次将删除的点重新插入，得到一个新的解，即当前解的邻域解；重复上述迭代过程，得到一个成本（cost）最低的一个解，即最优解。

「ALNS会为每个destroy和repair算子分配一个权重，通过该权重从而控制每个destroy和repair算子在搜索期间使用的频率。」 在搜索的过程中， 「ALNS」 会对各个destroy和repair方法的权重进行 「动态调整」 ，以便获得更好的邻域和解。

「ALNS通过使用多种destroy和repair算子，然后再根据这些destroy和repair算子生成的解的质量，选择那些表现好的destroy和repair算子，再次生成邻域进行搜索」

算法实现

算法本身由算法参数、当前解、状态管理器、算子管理器、最优解管理器组成

邻域自适应算法,变邻域搜索算法

算法参数

算法执行过程中一些初始化参数

typeParametersstruct{
MaxExecTimeint`json:"max_exec_time"`//最长执行时间（单位s）
TimeSegmentsItint`json:"time_segments_iteration"`//重新计算权重迭代次数
ReloadFrequencyint`json:"reload_frequency"`//重置当前解的迭代次数
Sigma1int`json:"sigma1"`//算子提升最优解增加分数
Sigma2int`json:"sigma2"`//算子提升当前解增加分数
Sigma3int`json:"sigma3"`//算子更新当前解增加分数
Rhofloat64`json:"rho"`//重新计算算子权重的系数
MinimumWeightfloat64`json:"min_weight"`//最小权重值
MaximumWeightfloat64`json:"max_weight"`//最大权重值
MaxTemperaturefloat64`json:"max_temperature"`//最大温度
MinTemperaturefloat64`json:"min_temperature"`//最小温度
TemperatureAlphafloat64`json:"temperature_alpha"`//降温系数
MaxNoImproveRatiofloat64`json:"max_no_improve_ratio"`//最大没有提升解的迭代次数占比（超过停止）
}

最大温度 * math.pow(降温系数, n) < 最小温度，max(n)即为 「最大迭代次数」 ，超过最大迭代次数停止

最大迭代次数 * MaxNoImproveRatio = 最大无改善最优解的迭代次数，超过最大无改善最优解的迭代次数停止

超过最长执行时间停止

状态管理器

管理计数的状态变量

typeStatusstruct{
//迭代次数：Id of the iteration corresponding to this status.
IterationIdint
//迭代次数中解可行的迭代次数：Number of iteration solution avaliable
NIterationAvaliableint
//距离上一次改善最优解的迭代次数：Number of iteration since the last improvement of the BKS
NIterationWithoutImprovementint
//距离上一次重置当前解后改善最优解的迭代次数：Number of iteration since the last improvement of the BKS
//orthelastreloadofthebestknownsolution.
NIterationWithoutImprovementSinceLastReloadint
//没有改善当前解的迭代次数：Number of iterations since the last improvement of the current
//solution.
NIterationWithoutImprovementCurrentint
//没有更新当前解的迭代次数：Number of iterations without transition.
NIterationWithoutTransitionint
//重置当前解的迭代次数：Number of iterations with reload current solution
NIterationReloadCurrentint
//更新最优解的迭代次数：Number of iterations with update best solution
NIterationUpdateBestint
//更新算子权重的迭代次数：Number of iterations with recopute weights
NIterationRecomputeWeightsint
//当前解是否是最优解：Indicate ifanewbestsolutionhasbeenobtained.
NewBestSolutionint
//是否更新了当前解：Indicate ifthenewsolutionhasbeenacceptedasthe
//currentsolution.
AcceptedAsCurrentSolutionint
//是否提升了当前解：Indicate ifthenewsolutionimprovethecurrentsolution.
ImproveCurrentSolutionint
}

最优解管理器

管理最优解

更新最优解

获取最优解

算子管理器

算子管理类，提供如下接口

添加摧毁算子

添加修复算子

选择摧毁算子

选择修复算子

更新算子分数

更新算子权重

更新算子调用次数

选择算子

算子管理器根据算子权重选择破坏算子与修复算子

func(m*OperatorManager)selectOperator(vecOp[]IOperator,sumWfloat64)IOperator{
randomVal:=rand.Float64()
randomWeightPos:=randomVal*sumW
cumulSum:=0.0
fori:=0;i<len(vecOp);i++{
cumulSum+=vecOp[i].GetWeight()
ifcumulSum>=randomWeightPos{
ifm.noise{
vecOp[i].SetNoise()
}else{
vecOp[i].UnsetNoise()
}
vecOp[i].IncreaseNumberOfCalls()//更新算子使用次数
returnvecOp[i]
}
}
returnvecOp[len(vecOp)-1]
}

获取邻域解

先使用破坏算子进行删除，然后使用修复算子将删除的进行添加

func(s*AlnsProcess)generateNeighborSolution(repairIRepairOperator,destroyIDestroyOperator)*alg.Solution{
//从局部最优中生成新解
neighbor:=s.currentSolution.CopySolution()
//destroysolution
removeJobs:=destroy.DestroySolution(neighbor)
//repairsolution
repair.RepairSolution(neighbor,removeJobs)
returnneighbor
}

更新当前解

新解 < 当前解，一定接受

新解 > 当前解，根据温度与成本变化值随机接受

func(a*Acceptance)TransitionAccepted(currentSolution,newSolution*alg.Solution)bool{
//降温
a.temperature*=a.parameters.TemperatureAlpha
ifnewSolution.SolutionCost<currentSolution.SolutionCost{
returntrue
}else{
difference:=newSolution.SolutionCost-currentSolution.SolutionCost
random:=rand.Float64()
returnmath.Exp(-1.0*difference/a.temperature)>=random
}
}

更新最优解

新解 < 最优解，一定接受

func(s*AlnsProcess)updateBestSoution(newSol*alg.Solution)bool{
bestSolution:=s.bestSolManager.GetBestSolution()
accept:=false
ifnewSol.SolutionCost<bestSolution.SolutionCost{
accept=true
}
ifaccept{
s.bestSolManager.AddNewBestSolution(newSol)
s.status.NewBestSolution=TRUE
s.status.NIterationWithoutImprovement=s.nIterationsWithoutImprovement
s.status.NIterationWithoutImprovementSinceLastReload=0
s.status.NIterationUpdateBest+=1
returntrue
}else{
s.status.NewBestSolution=FALSE
s.status.NIterationWithoutImprovement=s.nIterationsWithoutImprovement
s.status.NIterationWithoutImprovementSinceLastReload++
returnfalse
}
}

更新算子的分数

根据新解的质量，给当前使用算子加上不同的分数

func(m*OperatorManager)UpdateScores(desIDestroyOperator,repIRepairOperator,status*Status){
//新解是最优解
ifstatus.NewBestSolution==TRUE{
rep.SetScore(rep.GetScore()+float64(m.parameters.Sigma1))
des.SetScore(des.GetScore()+float64(m.parameters.Sigma1))
m.perfRepairOperatorsWithNoise+=1
m.perfRepairOperatorsWithoutNoise+=1
}
//新解改善了当前解
ifstatus.ImproveCurrentSolution==TRUE{
rep.SetScore(rep.GetScore()+float64(m.parameters.Sigma2))
des.SetScore(des.GetScore()+float64(m.parameters.Sigma2))
m.perfRepairOperatorsWithNoise+=1
m.perfRepairOperatorsWithoutNoise+=1
}
//新解更新了当前解
ifstatus.ImproveCurrentSolution==FALSE&&
status.AcceptedAsCurrentSolution==TRUE&&
status.AlreadyKnownSolution==FALSE{
rep.SetScore(rep.GetScore()+float64(m.parameters.Sigma3))
des.SetScore(des.GetScore()+float64(m.parameters.Sigma3))
m.perfRepairOperatorsWithNoise+=1
m.perfRepairOperatorsWithoutNoise+=1
}
ifm.parameters.Noise{
performanceRepairOperatorsGlobal:=0.0
performanceRepairOperatorsGlobal+=m.perfRepairOperatorsWithNoise
performanceRepairOperatorsGlobal+=m.perfRepairOperatorsWithoutNoise
randomVal:=rand.Float64()
randomWeightPos:=randomVal*performanceRepairOperatorsGlobal
m.noise=(randomWeightPos<performanceRepairOperatorsGlobal)
}
}

更新算子的权重

每迭代TimeSegmentsIt次，更新所有算子的权重，新的权重和算子分数、算子调用次数等有关

func(m*OperatorManager)recomputeWeight(opIOperator,sumW*float64){
prevWeight:=op.GetWeight()
*sumW-=prevWeight
currentScore:=op.GetScore()
nbCalls:=op.GetNumberOfCallsSinceLastEvaluation()
newWeight:=(1-m.parameters.Rho)*prevWeight+m.parameters.Rho*(float64(nbCalls)/float64(m.parameters.TimeSegmentsIt))*currentScore
//Weensurethattheweightiswithinthebounds.
ifnewWeight>m.parameters.MaximumWeight{
newWeight=m.parameters.MaximumWeight
}
ifnewWeight<m.parameters.MinimumWeight{
newWeight=m.parameters.MinimumWeight
}
*sumW+=newWeight
op.SetWeight(newWeight)
op.ResetScore()
op.ResetNumberOfCalls()
}

重置当前解

每迭代 ReloadFrequency 次并且没有改善最优解，就重置当前解

//重置当前解（防止陷入局部最优解）
func(s*AlnsProcess)reloadCurrentSolution()*alg.Solution{
ifs.status.NIterationWithoutImprovementSinceLastReload>0&&
s.status.NIterationWithoutImprovementSinceLastReload%s.params.ReloadFrequency==0{
s.status.NIterationWithoutImprovementSinceLastReload=0
s.status.NIterationReloadCurrent+=1
returns.bestSolManager.GetBestSolution().CopySolution()
}
returns.currentSolution
}

变邻域搜索算法与迭代搜索的区别 (大规模邻域搜索算法)

算法介绍

应用场景

同类算法

算法流程

算法实现

算法参数

状态管理器

最优解管理器

算子管理器

选择算子

获取邻域解

更新当前解

更新最优解

更新算子的分数

更新算子的权重

重置当前解