閱讀本文大概需要 10 分鐘。
演算法介紹
自適應大鄰域搜尋
演算法（Adaptive Large Neighborhood Search），簡稱（ALNS），是由Ropke與Pisinger在2006年提出的一種啟發式方法，其在鄰域搜尋的基礎上增加了對運算元的作用效果的衡量，使演算法能夠自動選擇好的運算元對解進行破壞與修復，從而有一定機率得到更好的解。
應用場景
1。外賣場景：搜尋訂單分配騎手的最優方案
2。派單場景：搜尋訂單分配司機的最優方案
3。車輛路徑規劃問題
同類演算法
在鄰域搜尋演算法中，有的演算法可以只使用一種鄰域，如
「模擬退火演算法」
，因此它僅僅搜尋瞭解空間的一小部分，找到全域性最優的機率較小，它的優勢之一是可以避免陷入區域性最優；
而有的演算法可以使用多種運算元，如
「變鄰域搜尋演算法」
（VNS），它透過在當前解的多個鄰域中尋找更滿意的解，能夠大大提高演算法在解空間的搜尋範圍，但是它在使用運算元時盲目地將每種運算元形成的鄰域結構都搜尋一遍，缺少了一些啟發式資訊的指導；
而
「自適應大鄰域搜尋演算法」
就彌補了這種不足，這種演算法根據運算元的歷史表現與使用次數選擇下一次迭代使用的運算元，透過運算元間的相互競爭來生成當前解的鄰域結構，而在這種結構中有很大機率能夠找到更好的解；
演算法流程
1。 生成初始解，當前解X0 = 初始解，最優解X1 = X02。 重複以下步驟進行迭代直到停止準則 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運算元，再次生成鄰域進行搜尋」
演算法實現
演算法本身由演算法引數、當前解、狀態管理器、運算元管理器、最優解管理器組成
演算法引數
演算法執行過程中一些初始化引數
type Parameters struct { MaxExecTime int `json：“max_exec_time”` // 最長執行時間（單位s） TimeSegmentsIt int `json：“time_segments_iteration”` // 重新計算權重迭代次數 ReloadFrequency int `json：“reload_frequency”` // 重置當前解的迭代次數 Sigma1 int `json：“sigma1”` // 運算元提升最優解 增加分數 Sigma2 int `json：“sigma2”` // 運算元提升當前解 增加分數 Sigma3 int `json：“sigma3”` // 運算元更新當前解 增加分數 Rho float64 `json：“rho”` // 重新計算運算元權重的係數 MinimumWeight float64 `json：“min_weight”` // 最小權重值 MaximumWeight float64 `json：“max_weight”` // 最大權重值 MaxTemperature float64 `json：“max_temperature”` // 最大溫度 MinTemperature float64 `json：“min_temperature”` // 最小溫度 TemperatureAlpha float64 `json：“temperature_alpha”` // 降溫係數 MaxNoImproveRatio float64 `json：“max_no_improve_ratio”` // 最大沒有提升解的迭代次數佔比（超過停止）}
最大溫度 * math。pow（降溫係數， n） < 最小溫度，max（n）即為
「最大迭代次數」
，超過最大迭代次數停止
最大迭代次數 * MaxNoImproveRatio = 最大無改善最優解的迭代次數，超過最大無改善最優解的迭代次數停止
超過最長執行時間停止
狀態管理器
管理計數的狀態變數
type Status struct { // 迭代次數：Id of the iteration corresponding to this status。 IterationId int // 迭代次數中解可行的迭代次數：Number of iteration solution avaliable NIterationAvaliable int // 距離上一次改善最優解的迭代次數：Number of iteration since the last improvement of the BKS NIterationWithoutImprovement int // 距離上一次重置當前解後改善最優解的迭代次數：Number of iteration since the last improvement of the BKS // or the last reload of the best known solution。 NIterationWithoutImprovementSinceLastReload int // 沒有改善當前解的迭代次數：Number of iterations since the last improvement of the current // solution。 NIterationWithoutImprovementCurrent int // 沒有更新當前解的迭代次數：Number of iterations without transition。 NIterationWithoutTransition int // 重置當前解的迭代次數：Number of iterations with reload current solution NIterationReloadCurrent int // 更新最優解的迭代次數：Number of iterations with update best solution NIterationUpdateBest int // 更新運算元權重的迭代次數：Number of iterations with recopute weights NIterationRecomputeWeights int // 當前解是否是最優解：Indicate if a new best solution has been obtained。 NewBestSolution int // 是否更新了當前解：Indicate if the new solution has been accepted as the // current solution。 AcceptedAsCurrentSolution int // 是否提升了當前解：Indicate if the new solution improve the current solution。 ImproveCurrentSolution int}
最優解管理器
管理最優解
更新最優解
獲取最優解
運算元管理器
運算元管理類，提供如下介面
新增摧毀運算元
新增修復運算元
選擇摧毀運算元
選擇修復運算元
更新運算元分數
更新運算元權重
更新運算元呼叫次數
選擇運算元
運算元管理器根據運算元權重選擇破壞運算元與修復運算元
func （m *OperatorManager） selectOperator（vecOp ［］IOperator， sumW float64） IOperator { randomVal ：= rand。Float64（） randomWeightPos ：= randomVal * sumW cumulSum ：= 0。0 for i ：= 0； i < len（vecOp）； i++ { cumulSum += vecOp［i］。GetWeight（） if cumulSum >= randomWeightPos { if m。noise { vecOp［i］。SetNoise（） } else { vecOp［i］。UnsetNoise（） } vecOp［i］。IncreaseNumberOfCalls（） // 更新運算元使用次數 return vecOp［i］ } } return vecOp［len（vecOp）-1］}
獲取鄰域解
先使用破壞運算元進行刪除，然後使用修復運算元將刪除的進行新增
func （s *AlnsProcess） generateNeighborSolution（repair IRepairOperator， destroy IDestroyOperator） *alg。Solution { // 從區域性最優中生成新解 neighbor ：= s。currentSolution。CopySolution（） // destroy solution removeJobs ：= destroy。DestroySolution（neighbor） // repair solution repair。RepairSolution（neighbor， removeJobs） return neighbor}
更新當前解
新解 < 當前解，一定接受
新解 > 當前解，根據溫度與成本變化值隨機接受
func （a *Acceptance） TransitionAccepted（currentSolution， newSolution *alg。Solution） bool { // 降溫 a。temperature *= a。parameters。TemperatureAlpha if newSolution。SolutionCost < currentSolution。SolutionCost { return true } else { difference ：= newSolution。SolutionCost - currentSolution。SolutionCost random ：= rand。Float64（） return math。Exp（-1。0*difference/a。temperature） >= random }}
更新最優解
新解 < 最優解，一定接受
func （s *AlnsProcess） updateBestSoution（newSol *alg。Solution） bool { bestSolution ：= s。bestSolManager。GetBestSolution（） accept ：= false if newSol。SolutionCost < bestSolution。SolutionCost { accept = true } if accept { s。bestSolManager。AddNewBestSolution（newSol） s。status。NewBestSolution = TRUE s。status。NIterationWithoutImprovement = s。nIterationsWithoutImprovement s。status。NIterationWithoutImprovementSinceLastReload = 0 s。status。NIterationUpdateBest += 1 return true } else { s。status。NewBestSolution = FALSE s。status。NIterationWithoutImprovement = s。nIterationsWithoutImprovement s。status。NIterationWithoutImprovementSinceLastReload++ return false }}
更新運算元的分數
根據新解的質量，給當前使用運算元加上不同的分數
func （m *OperatorManager） UpdateScores（des IDestroyOperator， rep IRepairOperator， status *Status） { // 新解是最優解 if status。NewBestSolution == TRUE { rep。SetScore（rep。GetScore（） + float64（m。parameters。Sigma1）） des。SetScore（des。GetScore（） + float64（m。parameters。Sigma1）） m。perfRepairOperatorsWithNoise += 1 m。perfRepairOperatorsWithoutNoise += 1 } // 新解改善了當前解 if status。ImproveCurrentSolution == TRUE { rep。SetScore（rep。GetScore（） + float64（m。parameters。Sigma2）） des。SetScore（des。GetScore（） + float64（m。parameters。Sigma2）） m。perfRepairOperatorsWithNoise += 1 m。perfRepairOperatorsWithoutNoise += 1 } // 新解更新了當前解 if status。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 } if m。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（op IOperator， 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 // We ensure that the weight is within the bounds。 if newWeight > m。parameters。MaximumWeight { newWeight = m。parameters。MaximumWeight } if newWeight < m。parameters。MinimumWeight { newWeight = m。parameters。MinimumWeight } *sumW += newWeight op。SetWeight（newWeight） op。ResetScore（） op。ResetNumberOfCalls（）}
重置當前解
每迭代 ReloadFrequency 次並且沒有改善最優解，就重置當前解
// 重置當前解（防止陷入區域性最優解）func （s *AlnsProcess） reloadCurrentSolution（） *alg。Solution { if s。status。NIterationWithoutImprovementSinceLastReload > 0 && s。status。NIterationWithoutImprovementSinceLastReload%s。params。ReloadFrequency == 0 { s。status。NIterationWithoutImprovementSinceLastReload = 0 s。status。NIterationReloadCurrent += 1 return s。bestSolManager。GetBestSolution（）。CopySolution（） } return s。currentSolution}
