一种改进启发式算法在解决组合优化问题中的应用

秦媛媛

（江苏财经职业技术学院，江苏 淮安 223003）

一、引言

人们在日常生活当中经常会遇到关于组合优化方面的问题，该类问题主要任务是要在组合问题所有的可行解集合里面找到最优的解，一般可以表示成：令集合Ω={s1，s2，…，sn}，该集合Ω是为一切状态组合而成的问题解的集合，C(si)是状态si是所照应的目标函数的解，要求寻找最优解s，使得对于所有的si∈Ω，有C(s)=minC(si)。常见的组合优化问题包括：旅行商问题（TravelingSalesman Problem-TSP）、生产调度问题（Production Scheduling Problem，如Flow-Shop，Job-Shop）、0-1 背包问题（KnapsackProblem）、装箱问题（Bin Packing Problem）、图着色问题（Graph ColoringProblem）、聚类问题（ClusteringProblem）和最大团问题等。该类问题的表达很简单，同时表现出鲜明的工程行业相关特性，然而想获得最优解相对较难，根本的原因在于使用传统的解决这类问题的算法需要很长的运算时间和很大的存储容量，对计算机性能的要求很高，这就是常见的一个词“组合爆炸”的由来。组合优化问题的复杂性和应用广泛引起研究人员的对其理论和算法的研究热情，各种启发式算法纷纷展现。本文从应用十分广泛的旅行商问题出发，研究应用一种启发式算法来解决此类问题。

二、研究现状

旅行商问题为比较典型的组合优化的应用案例，它通常被这样描述为：旅行推销员经常会面临这样一种问题，就是在给出既定的许多城市（坐标点已定）和这些城市之间的相对距离条件后，从中求解出推销员走过每个城市一次然后还能回到起点城市的最短的回路，还可以找到推销员行走过路程的最短路径。旅行商问题还能衍生用至像车辆调度优化问题、运输路线规划、物流和计算机应用网络等领域里，应用方向相当广泛。

追根溯源，18世纪中叶欧拉提出的骑士环游问题，被认为是最早开始发现的旅行商问题。当时研究的对象是国际象棋，众所周知，国际象棋是64个方格，欧拉研究的是棋子走完这64个格子，每个格子仅仅走一次，然后还能回到起点。1954年Danzig等人创造性地解决了美利坚合众国49城市之间的巡回路线规划难题，用的是线性规划算法。它还有着很多变种形式，比如欧几里得旅行商（ETSP）、对称旅行商（STSP）和非对称旅行商（ATSP）等。详细地说明，欧几里得旅行商问题说明是所有城市间相对距离都是欧氏距离，在现实的二、三维物理空间里，欧氏距离为两个端点间的实际间距。对称问题意思为从城市A到城市B之间的距离等于从城市B到城市A的距离。非对称问题则说明从城市A到城市B的距离不一定等于从城市B到城市A的距离，通常情况下都为不等于。此外，据实而言，某些旅行商问题还可能会增加一些约束性条件，像附有时间窗的旅行商问题（城市增加了服务时间区间属性，旅行商到达每个城市时刻不能过早或者过晚）、附有瓶颈的旅行商（这个并不要求遍历路线总距离最短,而是要求在遍历路线中每次从一个城市到另一个城市时的单次距离尽可能是最短的）、中国邮递员问题（一个邮递员从邮局出发，走遍负责区域范围里所有街道至少一次，再回到出发点邮局，怎么选出一条最短路径）、以及多旅行商问题（顾名思义，由多个旅行商遍历所有城市的问题）等。

因为条件较少，所以旅行商问题在逻辑上是比较简单的，但其计算复杂度很高，属于非确定性多项式时间可解的判定问题。当城市数量不断增加，旅行商问题的计算难度会发生指数级的变化，需要强大的计算能力的辅助设备，并且计算机时间很长。常规运算方法在解决这一类问题时已经不太现实，因此启发式算法应运而生。启发式算法在数学上是这样定义的：它是一种通过直观认知和现实经验形成的算法，在相对较少的运算时间和空间花费里求得组合优化难题的所有实例的可行的解，但是这些可行解和最优解之间的偏离程度通常情况下无法得到提前获取。启发式算法最初是从仿生学中提出的概念，科学家通过仿生学中的生物行为特征和生物族群运行规律等创新性研究出一些算法来解决较为复杂的组合优化问题。目前，为求解旅行商问题用到的启发算法通常有：模拟退火算法、局部搜索算法、禁忌搜索、遗传算法、蚁群算法、粒子群算法和蜂群算法等，还有对这些算法进行综合研究得到的新型启发式算法。本文研究一种改进型模拟退火法解决旅行商相关问题。

三、模拟退火算法

模拟退火算法（Simulated AnnealingAlgorithm,简写SA）源自固体退火现象，模仿固体在熔化状态下慢慢降温冷下来，一直持续直到最后稳定状态。模拟退火算法是1953年由Metropolis第一次发现并研究的。它是基于蒙特卡洛方法思想的一种解决优化组合问题算法。物理现象中退火原理是对于一个非晶体形态的物体，首先要对其加热到一定程度，在这个持续加热的过程中，物体内部的粒子的状态将跟着加热温度的变高而成为无序状态，并且离子的内能会变大，在物体到达最高温后，开始降温，缓慢进行，也就是我们提到的退火，这时物体内部粒子会在降温过程中慢慢变得有序，逐渐平衡，在达到最后的特定温度时候，物体变成结晶状态，此时物体内部粒子都排列有序。SA算法中有代表性的是Metropolis规则，这个规则Metropolis等人提出的。通常在SA中的高温度过程中把温度划分为若干温度段，每段的新解选取标准不一样，选用Metropolis规则来比较随机选择组合优化问题的最优解，然后在持续降温中重复选择抽样，一直持续至得到近似的最优解值。

SA算法和一般的随机搜索方法重点区别于搜索方法不同，SA既吸收随机的理念，又借鉴物理现象退火过程规律，既可以在迭代运算时接受更优解，还能在某些时候接受比目前差一些的解，增加了遍历的灵活度。在初始阶段SA算法接收劣解的概率偏低，收敛较快。在温度继续降低过程中接收劣解的概率逐渐变大，可以预防局部最优陷阱。复杂度很高的问题经常有许多局部最优，不能只遵循选取优解的方法，否则将会陷入局部最优的境地，难以求出最优解。

为了描述Metropolis规则采样过程，如图1所示，这里我们假设问题的初始状态为A，状态变化会跟着迭代，当迭代到一定程度后，获得局部最优解B，此时B点对应的能量低于A点，说明问题正在接近最优解。下一步状态跳过B点后，出现系统的能量变化上升，此时需要算法通过一个概率跳出坑，该概率与目前问题的状态和能量值关联较大。从B点跳出到达局部最优C后，还会继续通过概率继续跳坑，直至到达全局最优解D时，才会进入稳定状态。

图1 Metropolis规则采样示意图

SA算法的流程描述为以下步骤：

（1）对各个参数和初始解进行初步设定，确定初温t0和终温tend，并且随机生成一个初始解，用S表示，并以经验设定循环数R；

（2）当温度大于终止温度时

根据Metropolis规则产生新优化解S’，把S’用概率p代替初始解S

（3）执行结束，输出最后结果。

SA算法的流程图如图2所示。

图2 模拟退火算法流程图

通常而言，SA算法需要满足初始温高、降温慢和终温低这三个条件，一般可以得到全局最优解，但是这些条件需要进过反复试验。此外，SA算法的执行效果和初始解S设置没什么相关性。

四、改进的SA算法

改进的SA算法使用随机的选择概率P，用来选择比目前次一点的解，可以以一定的概率走出局部最优解陷阱，实现全局最优解。

设之前某个状态为x(n)，算法通过某个指标（如梯度上升下降的能量），状态变化为x(n+1),相应的，算法的能量由E(n)变为E(n+1)，定义由x(n)变为 x(n+1)的选择概率P为

上述公式说明，当能量变小，能量转移会被接受（此时概率为1），当能量变大时，意味着此时偏离全局最优解，算法在此时不会抛弃该值，而是对其进行概率操作：在取值区间[0,1]中产生一个均匀分布的随机数，当随机数小于P时，说明这种转移是被算法接受，否则拒绝转移，进入下一步循环流程。选择概率P的取值是动态变化的，它是大小是由能量的变化量与温度大小决定的。

改进的SA算法流程：

（1）设定S是初始解，假设S_i=S，并设定初温为T，令 i=0。

（2）设 T=T_i，用参数 T和 S_i引入 Metorpolis抽样算法中计算，返回状态Si作为本算法的当前解，S_i=Si。

（3）降温流程，令 T=T_(i+1)，其中 T_(i+1)＜T_i，i=i+1。

（4）检查是否满足终止条件，当满足时下一步转到步骤(5)，否则下一步转到步骤(2)。

（5）认定当前解S_i为最优解，输出最终结果，算法停止执行。

选择合适的初温对本算法影响较大，初温越高，搜索性则越强，得到最优解的概率就越大，而其计算时间会变得很长。本算法选取初始温度经过反复试验获得。

本算法中循环链的链长表示为任何一个温度段，或者为遍历次数，这里我们称循环数。循环数多，意味着遍历时间会增长，计算时间会很长，但算法得到最优解的概率则越大。所以，循环次数的设置我们综合现实情况来进行合理设定。

本算法采用的降温办法为快速退火办法，使用的降温方程式是：T(t)=T0/1+αt，α为常数，取值小于1。快速退火办法可以使得在高温状态时温降变快，低温时温降变缓，这种特性吻合热力学中的粒子运动理论。粒子在处于高温状态时候，内部能量大，内外温度差别大，因此，热传递速很快，温降也快；而粒子处于低温状态时，热量传递速度变缓慢，温降也变慢。该方式可以使算法执行深度搜索。

五、实验

本文的实验环境：硬件环境为CPU：Intel(R)Core(TM)i3-7100@3.90GHz；内存：8GB；操作系统为 Windows10。软件编译环境为Python3.8。TSP问题描述为：给出既定的30座城市的坐标和每座城市之间的距离参数，求出遍历每座城市一次并能回到出发起点城市的最短回路和最短距离。

（一）实验步骤

（1）数据初始化：计算距离矩阵；随机得到初始解（起点为0城市）；编写距离计算函数。

（2）在每个温度下，进行R次迭代。每次迭代时，需要求出新的路径，之后后再计算出该路径的总长度。

（3）当求出新的路径总长小于目前路径总长时，会同时更新目前路径和目前路径总长为新的路径的；当该新路径总长比目前最优路径总长还小时，会更新最优路径和其长度为该新路径。

（4）当求出新的路径总长大于或等于目路径总长时，会通过相应的目标函数计算出接受概率，把算法产生的随机数和计算得到的接受概率进行对比，再决定是否接收新路径（即劣解）。

（5）算法执行检查到当前温度小于终止温度的条件后，算法停止执行，输出最终结果，并回执最终路线图。

（6）调参来优化模型。

（二）实验结果

1.初始温度为150，结束温度为1e-7，循环次数为100，温度衰减系数为0.98的旅行商最佳路线图如图3所示。

图3 循环次数为100的旅行商最佳路线图

最佳路线：[27,25,24,29,22,21,20,19,18,17,16,15,11,10,12,6,5,4,3,1,7,9,8,2,0,14,13,23,28,26]

最佳距离：441.55

运算时间:1.89秒

2.初始温度为150，结束温度为1e-7，循环次数为200，温度衰减系数为0.98的旅行商最佳路线图如图4所示。

图4 循环次数为200的旅行商最佳路线图

最佳路线：[22,29,24,25,27,26,28,23,13,14,0,2,8,9,7,1,3,4,5,6,12,10,11,15,16,17,18,19,20,21]

最佳距离：433.72

运算时间:3.87秒

3.初始温度为150，结束温度为1e-7，循环次数为500，温度衰减系数为0.98的旅行商最佳路线图如图5所示。

图5 循环次数为500的旅行商最佳路线图

最佳路线：[18,17,16,15,11,10,12,6,5,4,3,1,7,9,8,2,0,14,13,23,28,26,27,25,24,29,22,21,20,

最佳距离：426.30

运算时间:10.48秒

（三）实验结果分析

实验结果表明：算法迭代运行次数越多时，算法执行的搜索次数更大，执行程序运行会变慢，但此时得到的最佳距离值最优。本算法在前期增加了新解的接受概率，可以增加算法的搜索区间，避免陷入局部最优解；在算法的后期，减少接受新解的概率，以免丢失目前最优解。当目标函数的差值越大时，新解的接受概率也会变得越大。当迭代次数不断增加，温度下降逐渐减小，系统逐渐趋于稳定状态后，新解的接受概率会越小。

六、结语

组合优化领域目前热点问题之一便是关于旅行商问题，对旅行商问题进行相关研究有着非常重要的理论和实用意义。启发式算法是解决组合优化问题的良策，本文介绍了一种改进的启发式算法及其在解决组合优化问题中的应用，分析该算法的详细流程，并通过仿真实验验证该算法的性能，并对其优势和不足进行了分析。改进的模拟退火算法虽然具有空间开销相对较小、时间消耗不大等优点，但也存在一定的缺陷，比如其初始温度、降温速度等参数难以控制，不能保证一次就收敛到最优值，通常需要多次尝试才可求得最优解。