算法介紹
自適應(yīng)大鄰域搜索算法（Adaptive Large Neighborhood Search），簡稱（ALNS），是由Ropke與Pisinger在2006年提出的一種啟發(fā)式方法，其在鄰域搜索的基礎(chǔ)上增加了對(duì)算子的作用效果的衡量茵典，使算法能夠自動(dòng)選擇好的算子對(duì)解進(jìn)行破壞與修復(fù)蔬蕊，從而有一定幾率得到更好的解。
應(yīng)用場景
1.外賣場景：搜索訂單分配騎手的最優(yōu)方案
2.派單場景：搜索訂單分配司機(jī)的最優(yōu)方案
3.車輛路徑規(guī)劃問題
同類算法
在鄰域搜索算法中煮盼，有的算法可以只使用一種鄰域理卑，如模擬退火算法，因此它僅僅搜索了解空間的一小部分自赔，找到全局最優(yōu)的概率較小绍妨，它的優(yōu)勢之一是可以避免陷入局部最優(yōu)爆价；
而有的算法可以使用多種算子憔披，如變鄰域搜索算法（VNS）爬立，它通過在當(dāng)前解的多個(gè)鄰域中尋找更滿意的解侠驯，能夠大大提高算法在解空間的搜索范圍，但是它在使用算子時(shí)盲目地將每種算子形成的鄰域結(jié)構(gòu)都搜索一遍奕巍，缺少了一些啟發(fā)式信息的指導(dǎo)吟策；
而自適應(yīng)大鄰域搜索算法就彌補(bǔ)了這種不足，這種算法根據(jù)算子的歷史表現(xiàn)與使用次數(shù)選擇下一次迭代使用的算子的止，通過算子間的相互競爭來生成當(dāng)前解的鄰域結(jié)構(gòu)檩坚，而在這種結(jié)構(gòu)中有很大概率能夠找到更好的解；
算法流程
1. 生成初始解，當(dāng)前解X0 = 初始解匾委，最優(yōu)解X1 = X0
2. 重復(fù)以下步驟進(jìn)行迭代直到停止準(zhǔn)則
2.1 根據(jù)算子權(quán)重選擇破壞與修復(fù)算子拖叙，并更新算子使用次數(shù)
2.2 破壞算子和修復(fù)算子依次對(duì)當(dāng)前解操作得到新解X2
2.3 更新當(dāng)前解
- 如f(X2) < f(X0)，則X0 = X2
- 如f(X2) > f(X0)剩檀，則以一定的概率接受該解作為當(dāng)前解
2.4 更新最優(yōu)解
- 如f(X2) < f(X1)憋沿，則X1 = X2
2.5 更新算子的分?jǐn)?shù)
2.6 更新算子的權(quán)重
2.7 重置當(dāng)前解
3. 返回最優(yōu)解X1
每次迭代就是從初始解中刪除N個(gè)點(diǎn)，然后依次將刪除的點(diǎn)重新插入沪猴，得到一個(gè)新的解，即當(dāng)前解的鄰域解采章；重復(fù)上述迭代過程运嗜，得到一個(gè)成本（cost）最低的一個(gè)解，即最優(yōu)解悯舟。
ALNS會(huì)為每個(gè)destroy和repair算子分配一個(gè)權(quán)重担租，通過該權(quán)重從而控制每個(gè)destroy和repair算子在搜索期間使用的頻率。 在搜索的過程中抵怎，ALNS會(huì)對(duì)各個(gè)destroy和repair方法的權(quán)重進(jìn)行動(dòng)態(tài)調(diào)整奋救，以便獲得更好的鄰域和解。
ALNS通過使用多種destroy和repair算子反惕，然后再根據(jù)這些destroy和repair算子生成的解的質(zhì)量尝艘，選擇那些表現(xiàn)好的destroy和repair算子，再次生成鄰域進(jìn)行搜索
算法實(shí)現(xiàn)
算法本身由算法參數(shù)姿染、當(dāng)前解背亥、狀態(tài)管理器、算子管理器悬赏、最優(yōu)解管理器組成
算法參數(shù)
算法執(zhí)行過程中一些初始化參數(shù)
type Parameters struct {
MaxExecTime int `json:"max_exec_time"` // 最長執(zhí)行時(shí)間（單位s）
TimeSegmentsIt int `json:"time_segments_iteration"` // 重新計(jì)算權(quán)重迭代次數(shù)
ReloadFrequency int `json:"reload_frequency"` // 重置當(dāng)前解的迭代次數(shù)
Sigma1 int `json:"sigma1"` // 算子提升最優(yōu)解 增加分?jǐn)?shù)
Sigma2 int `json:"sigma2"` // 算子提升當(dāng)前解 增加分?jǐn)?shù)
Sigma3 int `json:"sigma3"` // 算子更新當(dāng)前解 增加分?jǐn)?shù)
Rho float64 `json:"rho"` // 重新計(jì)算算子權(quán)重的系數(shù)
MinimumWeight float64 `json:"min_weight"` // 最小權(quán)重值
MaximumWeight float64 `json:"max_weight"` // 最大權(quán)重值
MaxTemperature float64 `json:"max_temperature"` // 最大溫度
MinTemperature float64 `json:"min_temperature"` // 最小溫度
TemperatureAlpha float64 `json:"temperature_alpha"` // 降溫系數(shù)
MaxNoImproveRatio float64 `json:"max_no_improve_ratio"` // 最大沒有提升解的迭代次數(shù)占比（超過停止）
}
最大溫度 * math.pow(降溫系數(shù), n) < 最小溫度狡汉，max(n)即為最大迭代次數(shù)，超過最大迭代次數(shù)停止
最大迭代次數(shù) * MaxNoImproveRatio = 最大無改善最優(yōu)解的迭代次數(shù)闽颇，超過最大無改善最優(yōu)解的迭代次數(shù)停止
超過最長執(zhí)行時(shí)間停止
狀態(tài)管理器
管理計(jì)數(shù)的狀態(tài)變量
type Status struct {
// 迭代次數(shù)：Id of the iteration corresponding to this status.
IterationId int
// 迭代次數(shù)中得到可行解的迭代次數(shù)：Number of iteration solution avaliable
NIterationAvaliable int
// 距離上一次改善最優(yōu)解的迭代次數(shù)：Number of iteration since the last improvement of the BKS
NIterationWithoutImprovement int
// 距離上一次重置當(dāng)前解后改善最優(yōu)解的迭代次數(shù)：Number of iteration since the last improvement of the BKS
// or the last reload of the best known solution.
NIterationWithoutImprovementSinceLastReload int
// 沒有改善當(dāng)前解的迭代次數(shù)： Number of iterations since the last improvement of the current
// solution.
NIterationWithoutImprovementCurrent int
// 沒有更新當(dāng)前解的迭代次數(shù)：Number of iterations without transition.
NIterationWithoutTransition int
// 重置當(dāng)前解的迭代次數(shù)：Number of iterations with reload current solution
NIterationReloadCurrent int
// 更新最優(yōu)解的迭代次數(shù)：Number of iterations with update best solution
NIterationUpdateBest int
// 更新算子權(quán)重的迭代次數(shù)：Number of iterations with recopute weights
NIterationRecomputeWeights int
// 當(dāng)前解是否是最優(yōu)解： Indicate if a new best solution has been obtained.
NewBestSolution int
// 是否更新了當(dāng)前解：Indicate if the new solution has been accepted as the
// current solution.
AcceptedAsCurrentSolution int
// 是否提升了當(dāng)前解：Indicate if the new solution improve the current solution.
ImproveCurrentSolution int
}
最優(yōu)解管理器
管理最優(yōu)解
更新最優(yōu)解
獲取最優(yōu)解
算子管理器
算子管理類盾戴，提供如下接口
添加摧毀算子
添加修復(fù)算子
選擇摧毀算子
選擇修復(fù)算子
更新算子分?jǐn)?shù)
更新算子權(quán)重
更新算子調(diào)用次數(shù)
選擇算子
算子管理器根據(jù)算子權(quán)重選擇破壞算子與修復(fù)算子
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() // 更新算子使用次數(shù)
return vecOp[i]
}
}
return vecOp[len(vecOp)-1]
}
獲取鄰域解
先使用破壞算子進(jìn)行刪除，然后使用修復(fù)算子將刪除的進(jìn)行添加
func (s *AlnsProcess) generateNeighborSolution(repair IRepairOperator, destroy IDestroyOperator) *alg.Solution {
// 從局部最優(yōu)中生成新解
neighbor := s.currentSolution.CopySolution()
// destroy solution
removeJobs := destroy.DestroySolution(neighbor)
// repair solution
repair.RepairSolution(neighbor, removeJobs)
return neighbor
}
更新當(dāng)前解
新解 < 當(dāng)前解兵多，一定接受
新解 > 當(dāng)前解尖啡，根據(jù)溫度與成本變化值隨機(jī)接受
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
}
}
更新最優(yōu)解
新解 < 最優(yōu)解，一定接受
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
}
}
更新算子的分?jǐn)?shù)
根據(jù)新解的質(zhì)量中鼠，給當(dāng)前使用算子加上不同的分?jǐn)?shù)
func (m *OperatorManager) UpdateScores(des IDestroyOperator, rep IRepairOperator, status *Status) {
// 新解是最優(yōu)解
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
}
// 新解改善了當(dāng)前解
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
}
// 新解更新了當(dāng)前解
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)
}
}
更新算子的權(quán)重
每迭代TimeSegmentsIt次可婶，更新所有算子的權(quán)重，新的權(quán)重和算子分?jǐn)?shù)援雇、算子調(diào)用次數(shù)等有關(guān)
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()
}
重置當(dāng)前解
每迭代 ReloadFrequency 次矛渴，重置當(dāng)前解
// 重置當(dāng)前解（防止陷入局部最優(yōu)解）
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
}
