算法介绍

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

应用场景

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

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

3.车辆路径规划问题

同类算法

在邻域搜索算法中，有的算法可以只使用一种邻域，如模拟退火算法，因此它仅仅搜索了解空间的一小部分，找到全局最优的概率较小，它的优势之一是可以避免陷入局部最优；

而有的算法可以使用多种算子，如变邻域搜索算法（VNS），它通过在当前解的多个邻域中寻找更满意的解，能够大大提高算法在解空间的搜索范围，但是它在使用算子时盲目地将每种算子形成的邻域结构都搜索一遍，缺少了一些启发式信息的指导；

而自适应大邻域搜索算法就弥补了这种不足，这种算法根据算子的历史表现与使用次数选择下一次迭代使用的算子，通过算子间的相互竞争来生成当前解的邻域结构，而在这种结构中有很大概率能够找到更好的解；

算法流程

 

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
}