模拟退火算法

模拟退火算法

模拟退火算法是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是一种通用的优化算法，其物理退火过程由加温过程、等温过程、冷却过程这三部分组成。

原理：模拟退火的原理也和金属退火的原理近似，将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。演算法先以搜寻空间内一

Google OR-Tools(五) 路径问题 Routing

本文参考Google OR-Tools 官网文档 介绍OR-Tools的使用方法。实际生活中有很多组合优化问题，例如最短路径、背包问题、人员排班等，这些组合优化问题一般属于规模较大的整数规划或者约束满足问题，一般没有直接的算法获得绝对最优解，只能通过启发式或元启发式算法获得相对最佳解。OR-Tools针对路径问题、背包问题和流问题提供了专用接口，相对于通用的求解器有更高的计算效率。

路径优化问题的目标都是在一个复杂的网络中找一个效能最高的路径，这个网络可以用下面这个节点图来示意

按照优化的目标是针对节点还是边，路径优化问题可以分成两类：节点路径优化( node-routing)和边路径优化(arc-routing)。节点路径优化的目标是以最短的路径长度访问到每个节点，而边路径优化的目标是以最短的路径长度实现访问图中的每条边。
旅行商(TSP)问题就是一个非常经典的node-routing问题，在这个问题下，图中每个节点代表了一个城市，而节点之间的边表示两座城市间的行程；每条边赋予一个权值，代表了两座城市间的距离；目标就是为旅行商找一条行程最短的路线来访问到每座城市。在这个标准的TSP问题定义上还可以附加各种额外条件来符合现实情况：

下面我们先了解一些解决以TSP为例的路径问题的算法，再使用OR-Tools演示一下。

启发(heuristic)这个词带有联想、经验的意思，这也正是启发式算法的思想，是带有领域知识的非精确算法，启发式算法一般要依赖于问题领域，不同的问题因为环境的不同启发式算法的形式也不同。对于TSP问题，一种最简单和直接的启发式算法是最邻近优先(Nearest Neighbor)法，就是每次都访问离当前位置最近的城市，这种算法的时间复杂度为：

这种算法得到的解通常来说只有最优解的10%到15%。或者可以用一种更好的启发式算法，最短边贪心算法，就是不断选择最短的边来构造路径：

贪心算法的时间复杂度为，解的优良程度大概是最优解的15%到20%。除了这两种典型的启发式算法，还有其他很多种实现，就不列举了。
启发式算法的最大优点就是计算速度非常快，但是缺点也很明显，解的质量不高，因为本质上所有的启发式算法都属于局部最优算法，在随机初始化后只会沿这个方向发展，到达局部最优点后就停止了。

元启发式算法有时也称为智能优化算法，宽泛的来说也属于启发式算法，不过因为相对朴素的启发式算法有很大程度的改进因此一般单独划分出来讨论。元启发式算法的一大特点是面向全局的优化，会利用各种手段跳出局部最优来尝试寻找更好的解；另一个特点是通常会参考现实世界的物理过程来具体实现，从大多数元启发式算法的名字就可以直接体现，例如模拟退火算法、遗传算法、蚁群算法和霍普菲尔德神经网络等等。
在这篇文章里我们介绍一下模拟退火算法。它是受加热金属的退火过程所启发而提出的一种逼近算法，该算法在1983年由Kirkpatrick等人提出，并且最初设计这个算法就是为了解决TSP问题的。
模拟退火参考了一个物理现象：在某个温度下，金属分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。更加具体的物理背景是这样的，在温度下，金属物体的分子可能会处于若干种状态，停留在状态的概率满足Boltzmann分布:

其中表示分子能量的随机变量，表示在状态下的能量，为Boltzmann常量，而为概率分布的标准化因子

其中是状态空间。根据分子能量的Boltzmann分布方程，分子不同状态的能量与温度的关系具有以下的特性：

上面这些特性归结起来就是温度越低，能量越低的状态的概率越高，极限情况下，只有能量最低的状态点概率不为零。举个例子，假设分子的能量概率分布函数如下:

其中能量点为，，则可能的概率变化情况如下表所示

我们了解了金属分子能量的退火过程，会发现在温度降低的过程中，分子能量一直在试图往最低的状态发展，这个过程就类似于我们求解最优问题解的过程。具体来对比的话，可以有以下细节：

因此，模拟退火算法就参照实际的物理过程，并采用实际物理过程的一些术语来实现。基本的算法流程如下：

模拟退火算法的主流程并不复杂，但是具体到每一步还有很多细节需要注意，我们针对主要的几个点进行叙述。

首先是解的定义和形式，不同的问题解的定义也不同，但都要尽量让解的形式简洁并利于操作，邻域中每个邻居解都是可行解，并且解空间中任何两个状态可达。邻域可以理解为当前解附近的解空间。对于TSP问题，一种可行的解定义是：用解表示为访问城市的一个排序，而解的领域可用不同的操作算子来定义，例如最简单的互换操作，下图是采用互换操作从当前解转到下一个解的示意图
优化问题的目标函数就对应于分子退火过程中的状态能量，具体的目标函数表达形式和自身问题相关，在TSP里，目标函数就是当前解下的路径总长度

关于算法第2步的退火操作，就是在当前温度下，由一个状态(解)变到另一个状态(解)，而这个转变的过程服从一个概率分布，通常采用Metropolis接受准则，即：

这里表示如果当前状态是，则下一个状态是的概率；表示当前状态的目标值；。按照这个接受准则，如果下一个状态对应的目标值比当前状态的更小，则一定会跳到这个状态；如果更大，并不是肯定不接受，而是按一定的概率去转换。利用概率特征，算法在陷入局部最优时将有机会跳出。

实际的退火过程中降温是不能太快的，否则容易导致形成不是最稳定的状态；同样在退火算法中，降温过程需要保持合适的速度以保证解的质量。一般有两种降温方式，一种是

这里的一般会取接近1的小数。另一种是

这里的表示设定的降温总次数。

而退火算法的停止准则可以是温度下降到指定值时停止，也可以是总降温次数到达指定的次数时停止，或者是设定一个目标值，当前解接近这个值时停止。

以模拟退火算法为代表的元启发算法看起来有点“玄妙”的感觉，我们其实在用算法在模拟某些物理过程，通常情况下元启发算法的效果相当令人满意，而且相比启发式算法，元启发式算法更加通用，不同的问题只要合理的定义变量都可以用元启发算法来解算。不过元启发算法也有些缺点，比如某些算法参数无法定量，只能靠经验设定，例如在模拟退火算法中，温度的初始值很重要，如果设的太大会导致计算时间过程；如果太小则会影响解的质量。而且元启发算法找寻相对最优解的时间会比启发式算法长，这在某些场景下并不适用。

事实上现在一般的组合优化引擎(包括OR-Tools)会把启发式算法和元启发算法进行结合，例如把初始解的生成过程用启发式算法计算，后续的元启发过程在这个解上进行，因此在OR-Tools工具的参数中会有些启发式参数可配置。

我们新建一个.Net Core控制台应用，利用OR-Tools解决一个标准的TSP问题。首先定义一个简单的数据集

DistanceMatrix存储了城市的距离信息，一维索引 i 代表了城市的编号，共有13个城市，DistanceMatrix[i][j]表示第i个城市和第j个城市的距离，比如DistanceMatrix[0][1]=2451，就表示城市0和城市1的距离是2451.。VehicleNumber表示访问城市的个体数，为1就是标准的TSP问题，大于1则扩展为VRP问题。Depot表示了起始城市索引，这里就从第0号城市开始。
在Routing接口中，OR-Tools除了把模型单独封装为一个类，还多出一个地点索引管理类，由它负责算法内部对城市地点索引的管理和计算。新建一个RoutingIndexManager对象，指定当前TSP问题的基础参数

然后用RoutingIndexManager对象初始化一个RoutingModel对象

接着是一个比较繁琐和让人困惑的步骤，我们需要为RoutingModel对象指定获取距离值的回调方法：

当求解器内部计算取两个城市的索引时，会调用我们指定的回调函数获取它们之间的距离。至于为什么要在回调函数内用IndexToNode()方法做一个看似多次一举的操作，是因为算法内部用的索引和原始数据的索引不一样，例如算法内部可能计算到fromIndex为0，toIndex为13的情况(第13个城市其实就是回到起始点)，而在外部原始数据里是没有DistanceMatrix[0][13]这个值的。
然后我们还需要把RegisterTransitCallback返回的回调函数Id值作为SetArcCostEvaluatorOfAllVehicles方法的参数来通知模型，结点间边的权值就用城市距离表示。

我们再写一个打印解的方法

在最终计算之前，我们还可以设定一下算法搜索参数。我们先只指定FirstSolutionStrategy的值，也就是用哪种启发式算法来初始化解，这里指定为PathCheapestArc，即上面提到的最短边算法；此外把LogSearch设为true，从而可以看到算法的过程信息。

最后调用计算方法来得到结果

完整的程序

我们再来试试修改下searchParameters的配置。我们只是指定了FirstSolutionStrategy的值，用哪种元启发算法我们并没有指定，这个值由LocalSearchMetaheuristic指定，其默认值是AUTOMATIC,表示由求解器自己选择。这里例子里求解器应该选择的是Greedy Descent算法，我们手动改成模拟退火：

然后定义好停止时间，否则算法不会停下的

来看看模拟退火算法的结果，最终解和之前一样，不过中间过程就不一样了

模拟退火算法和粒子群算法的优缺点有那些？具体点，谢啦

他们有类似之处，但差别也不小。
蒙特卡洛算法是数值计算方法，原理是利用随机数来解决计算问题。与它对应的是确定性算法。也就是说该种算法属于随机算法，得到的解是近似解。
而遗传算法、粒子群、模拟退火虽然也是随机近似算法，但这三种都是仿生智能算法，且比蒙特卡洛算法要复杂，应用的领域也不太相同。
显然，蒙特卡洛算法很轻巧，求解问题更快速。

遗传算法、数值算法、爬山算法、模拟退火 各自的优缺点

遗传算法：其优点是能很好地处理约束，跳出局部最优，最终得到全局最优解。缺点是收敛速度慢，局部搜索能力弱，运行时间长，容易受到参数的影响。

模拟退火：具有局部搜索能力强、运行时间短的优点。缺点是全局搜索能力差，容易受到参数的影响。

爬山算法：显然爬山算法简单、效率高，但在处理多约束大规模问题时，往往不能得到较好的解决方案。

数值算法：这个数值算法的含义太宽泛了，指的是哪种数值算法，阵列算法与爬山算法一样，各有优缺点。

扩展资料：

注意事项：

遗传算法的机制比较复杂，在Matlab中已经用工具箱中的命令进行了打包，通过调用可以非常方便的使用遗传算法。

函数GA：［x，Fval，reason］＝GA（＠fitnessfun，Nvars，options）x为最优解，Fval为最优值，＠Fitnessness为目标函数，Nvars为自变量个数，options为其他属性设置。系统的默认值是最小值，所以函数文档中应该加上一个减号。

要设置选项，您需要以下函数：options＝GaOptimset（＇PropertyName1＇，＇PropertyValue1＇，＇PropertyName2＇，＇PropertyName3＇，＇PropertyValue3＇…）通过该函数，可以确定一些遗传算法的参数。

声明： 我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理，本站部分文字与图片资源来自于网络，转载是出于传递更多信息之目的,若有来源标注错误或侵犯了您的合法权益，请立即通知我们(管理员邮箱：daokedao3713@qq.com)，情况属实，我们会第一时间予以删除，并同时向您表示歉意,谢谢!