基于大规模邻域搜索的模拟退火算法求解TSP

孙 鉴,刘凇佐,武晓晓

(北方民族大学计算机科学与工程学院,宁夏 银川 750021)

1 引言

旅行商问题[1](Traveling Salesman Problem,TSP)是较早提出的组合优化问题,其目标是求得在给定城市坐标集合,每个城市遍历且仅遍历一遍构成的城市序列,该城市序列代表旅行商将随机选择一个城市作为起点,每个城市遍历一次,回到出发城市。旅行商问题的最优解是总路程最短的城市序列。在车辆路径规划[2]、物流配送问题[3]等领域有重要的现实意义。考虑到该问题在各个领域的应用价值,研究人员从计算机、数学、运筹学等多个学科交叉入手,集中研究解决旅行商问题。该问题的解决方法大致划分为精确算法和近似算法两大类。

常用的精确算法主要有枚举法、动态规划法以及分支限界法。但是大量的实验证明,精确算法只适用于求解城市规模较小的旅行商问题,随着城市规模的增大,精确算法求解开销较大,短时间内难以求得可行解,在实际生活中应用价值不高[4]。

近似算法是在近乎合理的时间内找到问题的近似解,近似算法可以分为常规的启发式算法和元启发式算法两类。常规的启发式算法根据问题的特点,按照规则经验、规则和知识设计而成,虽然算法设计简单,但是不具有迁移性[5]。当问题结构发生变化,就需要设计新的模型求解。元启发式算法更具有通用性,也因其特点成为求解TSP问题的主要方法,包括人工蜂群算法[6](ABC)、粒子群算法[7](PSO)、模拟退火算法[8,9](SA)。朱继生[10]提出一种人工蜜蜂融合量子编码的方法,在算法运行过程中量子位代表城市的访问序列,同时利用量子影响最佳蜜蜂的方向移动,影响整个蜜蜂种群找到最优解。李文、伍铁斌等人[11]分析了基本粒子群算法的优点和缺点,利用混沌运动的随机性,自适应调整惯性权重,平衡了粒子群算法的局部搜索能力和全局搜索能力。本文利用模拟退火算法,修改降温函数结合大邻域搜索和2-opt算子,求解旅行商问题收敛速度快,寻优能力强。

2 基本知识

2.1 基本的模拟退火算法

模拟退火算法受固体退火原理的启发,金属固体退温为加温、等温、冷却三个过程。在退火最初,固体的温度较高,内部分子没有稳定顺序,分子之间热运动较为剧烈,温度缓慢降低,分子逐渐有序稳定,这一过程称为退火;温度快速下降,能量无法降到最低,这一过程称为淬火。如图1是固体退火和淬火的过程示意图。

图1 物理退火和淬火过程图示

退火的过程与组合优化的问题具有一定的相似性,故而将模拟退火算法应用到一系列组合优化问题中,如表1是组合优化问题和模拟退火算法的对应关系。

表1 降温函数初始化参数

表1 过程对应关系表

模拟退火算法首先设定当前解为初始值,通过降温产生新解,通过比较新解和初始解的适应度函数,按照Metropolis准则[12]对新解进行一定概率的接受,达到终止温度则停止迭代。

3 解决旅行商问题的模拟退火算法

3.1 改进的模拟退火算法

模拟退火算法的主要组成要素分别是状态产生函数、状态接受函数、降温函数、热平衡稳定准则、退火结束准则、初始温度的选取。本文针对旅行商问题的特性,对算法的降温函数进行改进,降温函数是控制温度下降的方式,温度的大小是算法的搜索能力的体现,当温度较高时,算法进行广域搜索;当温度较低时,算法进行局域搜索。温度下降较快导致算法从广域搜索直接进入局域搜索,这将使得当前状态的解无法得到验证,进而无法找到全局最优解。当温度下降过慢时,算法局域搜索能力较弱,将会漏掉很多可行解。常用的降温方式有以下两种:

第一种:T=T*a,其中a是退火率,a的大小决定温度下降的速度,在算法迭代的过程中,都是按照线性递减的规律进行变化的。

第二种:T=T-ΔT,ΔT是每次温度下降的幅度,可以事先控制温度下降的总次数,之后依次递减。

基于第一种温度的下降方式修改温度下降函数为如下形式

T0=T0*α

(1)

T=T0*(1+cos(t*pi/gapIter)

(2)

其中T0表示初始温度,T表示变化后的温度,α为降温系数,t迭代次数,gapIter表示浮动的间隔数。

3.2 大规模邻域搜索

模拟退火算法产生新解的步骤中引入大规模邻域搜索算法[13](Large Neighborhood Search,LNS)。如图2所示,初始解空间为3-5-1-8-7-2-6-4,首先对初始解空间进行破坏移除城市,移除的城市数是随机的,本文设置为1～N/3(N为城市总数)。在图2中破坏选择移除的是城市1和城市6,把选中的城市从初始解空间中拿掉,剩下的按照初始解依次排序为破坏解空间:3-5-8-7-2-4。最后进行修复,对破坏解空间进行处理,例如图2选择城市1重新插入破坏解空间中,第一次插入后的结果为Sr,插入后的路径为1-3-5-8-7-2-4,计算Sr的适度值f(Sr)并且记录,因插入首尾效果相同,可以插入的位置为破坏解空间中的城市数量,分别计算插入不同位置的适度值,选择适度值效果最好的进行输出,之后把城市6插入新的破坏解空间中,直到所有移除的城市修复完成得到最终解空间,算法伪代码如算法1所示。

图2 大规模邻域搜索算法的流程图

Algorithm1:Large Neighborhood Search

Input:Original route Snow,destroy＿num

Output:New optimal path sequence＿repair

sequence＿random=random.permutation(Snow)

Sequence＿destroy ← sequence＿random[0: destroy＿num]

sequence＿remain← remove the Sequence＿destroy in Snow

remain＿num ← len(Sd)

for j in range(0,destroy＿num):

for i in range(0,remain＿num+1):

if i==1:

sequence＿remain＿temp ← [Sequence＿destroy[j]+sequence＿remain]

else:

sequence＿remain＿one ←sequence＿remain [0:i-1]

sequence＿remain＿two ←sequence＿remain [i-1:]

sequence＿remain＿temp ← sequence＿remain＿one+[ sequence＿destroy[j]]+sequence＿remain＿two

len＿remain=fitness(sequence＿remain＿temp)

if i==1:

len＿remain＿best ←len＿remain

Sbest ←sequence＿remain＿temp

else:

if len＿remain

len＿remain＿best ←len＿remain

Sbest ←sequence＿remain＿temp

sequence＿remain ← sequence＿remain＿temp

3.3 局部搜索算子2-opt

2-opt是一种随机性算法,基本思想就是随机选择两个元素进行优化,在求解TSP问题中得到了广泛的应用。如图3所示,路径为C1,C2,…,Cn,其中d(Ci,Cj)表示城市Ci和城市Cj之间的距离,图3为2-opt思想实例。如果条件d(Ci,Cj)+d(Ci+1,Cj+1)

图3 2-opt过程图

Algorithm2:2opt algorithm

Input:Original route R=(c1,…,ci,ci+1,…,cj,cj+1,…,cn)

Output:new shorter route R′=(c1,…,ci,cj,…,ci+1,cj+1,…,cn)

Best＿distance ← fitness(R)

for i in range(1,n-1):

for j in range(1,n-1):

if |j-(i+1)| >2:

速冻。保证冷冻食品食物感觉处于良好状态极为重要，为实现该目标，在冷冻食品时主要可以应用两种方法：一种为快速冻结，另一种为深度冻结。同时严格控制冻结温度，使其位于-35℃-45℃。设定一定时间限制，通常为30秒，使中心温度上升到-18℃。

New＿route ← 2opt(Current＿route,i,j)

New＿distance ←fitness(New＿route)

if New＿distance

Current＿route ← New＿route

Best＿distance ← New＿distance

Return Current＿route

3.4 交换和插入

本文使用交换和插入两种操作来增加邻域结构,作用是防止进入局部最优,并且轮盘赌算法的方式来选择使用交换,插入和LNS。交换和插入概率设置高可以减少时间复杂度和提高局部搜索能力,交换和插入两种操作介绍如下:

例如当前城市路径为:

1→3→4→6→2→7→8→5

1)交换操作

随机选择两个城市进行交换修改路径,如果选择的城市是3和7,那么变换后的城市序列为:1→7→4→6→2→3→8→5

2)插入操作

随机选取两个城市,选中进行插入操作的为i=3和j=7,进行判断如果i

1→4→6→2→7→3→8→5

3.5 算法流程

综上所述,本文算法步骤如下:

1)初始化迭代次数,交换概率P,初始化温度等参数;

2)贪婪策略初始化;

3)计算适应度值,记录最优路径Pbest和最优距离Lbest;

4)对当前路径根据轮盘赌策略以一定的概率选择执行交换,插入和LNS操作产生新的路径Pnew;

5)比较两次路径的适应度值之差,f(Pnew) <=f(Pbest),则Pbest=Pnew;否则,按照Metropolis准则进行更新;

6)根据式(1)和(2)更新温度,执行2-opt优化;

7)判断是否达到结束条件,如果没有达到执行4)～6),达到结束条件输出结果。

4 数值实验

为了检测大规模邻域搜索的模拟退火算法(simulated annealing algorithm with large neighborhood search,SALNS)的性能,使用TSPLIB中标准数据集作为实验数据进行测试。实验环境为:Python3.8,Inter(R)i7-9750H 2.60GHz,内存为16GB的PC进行实验分析。过程中交换概率设为0.4,插入概率设为0.5,LNS概率设为0.1。表中已知最优解,最优解和平均解分别用Hbest,Best和Avg表示。

4.1 改进的模拟退火算法降温曲线模拟

首先针对改进的降温函数进行测试,在本文函数的测试中选择标准降温、快速降温[14]和本文降温函数进行效果对比,初始条件和降温函数如表1,降温曲线如图4下所示。

图4 降温曲线对比图

由图4中可知,快速降温可以在较少的迭代次数达到低温状态,过早的达到了低温状态使得后续多次迭代做无效功。标准降温在多次迭代依旧无法达到低温状态,达到低温状态需要的迭代次数过多。然而本文降温曲线图很好的结合二者的优点,同时规避了缺点,降温的速度刚好,在整个退火过程中出现回火升温的过程,算法就可以在该点跳出局部最优,从而更有机会找到全局最优解。多次降温增加算法的记忆功能,能够保持最优解。

4.2 改进的模拟退火算法性能测试

在本节选取经典的粒子群算法(PSO)、遗传算法(GA) 、模拟退火算法(SA)和SALNS在数据集Att48和KroA100运行相同时间做了一个对比,对比时间和最终解如表2所示。四种算法使用贪婪策略初始解提高算法的效率,四种算法对比图如图5和图6。

表2 对比时间和最终解

图5 att48时间对比图

图6 kroA100时间对比图

图5,6中,横坐标为时间,纵坐标为距离的总和,由图5可知,在Att48数据集中,SALNS在第7s找到已知最优解,遗传算法早早的收敛陷入局部最优,而粒子群算法和模拟退火算法和已知最优解相差过大。由图6可知,在KroA100数据集中,SALNS在第23s找到已知最优解,遗传算法在11s陷入了局部最优,粒子群算法和模拟退火算法迭代时间过长结果较差。结果可知,SALNS在收敛速度和寻优能力方面均优于所对比的三种经典启发式算法。

4.3 SALNS与IACOPSO对比

将SALNS独立运行10次与IACOPSO[15]求解质量对比如表3所示。

表3 SALNS与IACOPSO对比结果

从表3可知共测试5个数据集,IACOPSO算法只获取了Burma14和Oliver30这两个数据集最优解,而SALNS获取了全部数据集的已知最优解;从均值来看IACOPSO算法只在Burma14数据集中达到已知最优解,而SALNS除Ch130数据集外均值都达到已知最优解,Ch130数据集的均值比IACOPSO算法最优解效果好。

4.4 大规模数据实验

将SALNS独立运行10次与文献一[16]求解大规模数据集质量对比如表4所示。

表4 SALNS在大规模数据集对比结果

从表4可知共测试8个大规模数据集进行实验,文献一最优解都接近已知最优解,而且Tsp225数据集优于已知最优解,而SALNS得到了6个实验数据的已知最优解,在数据集Tsp225中最优解优于文献一和已知最优解,并且Tsp225的均值优于已知最优解。

选取Eil51、Ch130、KroA200和Tsp225数据集最优解路径如图7～图10所示。

图7 Eil51最优路径图

图8 Ch130最优路径图

图9 KroA200最优路径图

图10 Tsp225最优路径图

5 总结

本文针对旅行商问题的特性,在模拟退火算法的基础上,修改降温函数,降温函数是控制温度下降的方式,温度的大小关乎算法的搜索能力,改进后的降温函数可以很好的跳出局部最优解。同时采用在产生新解的过程中采用随机选择产生方式,使用交换和插入来增加邻域结构,作用是防止进入局部最优,并且轮盘赌算法的方式来选择使用交换,插入和LNS,之后通过2-opt优化解空间。通过实验仿真证明,SALNS修改的降温函数效果得到了很大的提高,求解质量相较于三种经典的启发式算法较好,同时和当前较新改进的算法比较,收敛速度快,求解质量高。