当前位置: 代码迷 >> 综合 >> 自适应大邻域搜索(Adaptive Large Neighborhood Search)(二)解决TSP问题
  详细解决方案

自适应大邻域搜索(Adaptive Large Neighborhood Search)(二)解决TSP问题

热度:54   发布时间:2023-10-27 20:39:11.0

https://mp.weixin.qq.com/s/l7fTHRye4pPBtWrlPrZ6mA

1. ALNS介绍

从LNS谈起

LNS,即大规模邻域搜索算法(large neighborhood search)由Shaw在论文A new local search algorithm providing high quality solutions to vehicle routing problems中提出。主要的算法分为两部分:remove and insert,每次从当前的解中移除一定量的顾客(在原论文中,这个值设为25)随后得到一个部分解,对部分解应用insert算子,重新插入的所有可能情况构成了原始解的一个邻域。在原论文中,作者使用了Branch and Bound算法来搜索整个邻域的最优解。假如邻域中的最优解比当前解更优,则当前解进行改进。当然,remove方法很大程度上决定了算法的效率。

LNS正如论文名一样,效果非常好。但同时也存在着它的问题,当邻域逐渐增大的同时,时间复杂度依然是呈指数级上升,以至于当移除的顾客数超过30时,搜索最优解的时间变得无法接受,这时候在探索大邻域的时候就同样需要一种启发式的方法,找到邻域中的满意解。

ALNS其实和VND有很多类似之处,都是通过变换不同的邻域来增大搜索空间,如下图所示:
在这里插入图片描述
ALNS是对LNS的拓展,其设计了一组remove算子和一组insert算子来竞争改进的机会。在每次迭代过程中,从remove算子和insert算子集合中各选择一个来对当前解进行改进。不同算子被选择到的概率由之前的效率决定。获得邻域满意解后,ALNS中可以任意选用接受准则,如SA接受,TS接受等来更新当前解。

其算法主流程如下:
在这里插入图片描述

2. remove算子介绍

remove算子就是通过不同的方法,选择一定数量的顾客,把他从solution中移除即可。

举个例子大概是这样:

原solution:

route 1: [0,1,2,3,4,5,0]

route 2: [0,6,7,8,9,10,0]

假设要remove的顾客数为5个站点:

after remove:

route 1:[0,1,2,0]

route2:[0,8,9,10,0]

下面具体介绍几种remove算子:

1.Random remove

如其名,随机移除。随机选择一定数量的顾客并移除即可,主要作用是增加搜索的多样性。

2.Worst remove

这种remove的思想是在改进解的过程中,那些非常长的,在目标函数中贡献非常大的顾客,往往需要被考虑重新安置。

如图所示:
在这里插入图片描述
可以发现假如去掉红色笔划的边后,目标函数有明显下降,说明这些边对应的点值得考虑被重新安排:

在实现中,我们定义
在这里插入图片描述
就是把点i从解中完全移除后,目标函数值的提高(降低)。把所有点按 f?if_{-i}f?i?值来排序,排在前面的顾客被选择到的概率更大。
在这里插入图片描述

3. insert算子介绍

插入算子将被移除的顾客再重新加回到解中,从而对解进行改进,不同于LNS,这里的insert方法都是启发式的:

1.Basic greedy heuristic

基本的贪心思想。不断的将被移除的顾客加回到cheapest(使目标函数提高最少的位置)上。具体的方法如下:

我们定义fikf_{ik}fik?为把顾客i插入到route k中使目标函数提高最少的位置后,目标函数的改变量。当顾客i无法插入到route k中,我们有。之后计算
在这里插入图片描述
不断把i插入到route中即可。

其实质就是从所有待服务顾客中选择能使目标函数增长最小的顾客。

不断执行以上流程,直到所有的顾客都插回到solution中,或是已经没有可以插入的位置。

这里值得注意的一点是可以将所有的 fikf_{ik}fik? 列成表,来减少时间复杂度,避免每次都要重新计算。

2.Regret heuristics

第一种基于贪心的思想的插入算子有明显的问题:总是将那些困难(能使目标函数值提高很多)的顾客放到后面插入。这使得可插入的点变得很少。

Regret heuristic通过加入look-ahead information来避免这一种情况的发生。具体流程如下:

我们定义 fiqf_{iq}fiq? 为把顾客i插入到第 qqq 个使目标函数提高最少的route的最好位置上后,目标函数的改变量

我们有:
在这里插入图片描述
即要最大化了把顾客 i 插入到最好的 route 中和第 q 好的route中目标函数的差异

4. 接受准则

在算法主框架上,我们使用模拟退火算法的思想:以概率
在这里插入图片描述

接受目标函数值劣于当前解的候选解。

5. 自适应参数调整

我们通过收集在100次迭代中,不同的remove和insert算子的表现来对他们进行打分,分数更高的算子被选择的概率更大:

我们定义三个打分机制:

r1r_1r1?:上一个remove-insert 操作获得了新的全局最优解

r2r_2r2?:上一次remove-insert操作获得了之前没发现过的解,但该解目标函数值劣于当前解

r3r_3r3?:上一次remove-insert操作获得了之前没发现过的解,但该解目标函数值劣于当前解,但该解被接受了

每次迭代过后将分数加到对应的操作中。

我们更喜欢能够改进solution的方法,但我们也希望奖励能够在一定程度上使搜索多样化的方法。我们通过为每个solution分配一个哈希键并将该键存储在一个哈希表中来储存获得过的solution。

在每迭代100次后,我们计算新的分数:
在这里插入图片描述
aia_iai? 是在上个周期中该启发式操作被调用的次数,reaction factor p控制了参数调整算法对分数改变的灵敏度。p=1的话新的分数只和最近一次分数有关,p<1的话就开始考虑历史因素。\

6.remove-insert选择

这里采用轮盘赌选择法:

具体操作如下:

(1)计算出每个算子的分数f(i=1,2,…,M),M为算子总数;

(2)计算出每个算子占总分数和的比例
在这里插入图片描述
(3)计算出每个算子的累积概率 qiq_iqi?

(4)在[0,1]区间内产生一个伪随机数 r

(5)若r<q[1],则选择算子1,否则,选择算子k,使得:q[k-1]<r≤q[k]成立

其实就是遗传算法中选择过程所使用的轮盘赌的方法。

  相关解决方案