10分钟彻底理解自适应大邻域搜索算法

程序员小猿

发布于 2021-03-07 18:01:11

2.6K0

发布于 2021-03-07 18:01:11

文章被收录于专栏：程序IT圈

算法介绍

自适应大邻域搜索算法（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算子，再次生成邻域进行搜索」

算法实现

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

算法参数

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

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
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-03-05，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自程序员小猿微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度