《1　前言》

1　前言

模拟退火算法[1]（simulated an nealing , SA）原理就是模拟在某个温度下，金属分子停留在能量小的状态时刻的概率要比停留在能量大的状态的概率要大。

模拟退火算法与爬山算法对比，爬山算法是一种简单的贪婪搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

爬山算法的主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图 1 所示：假设 C 点为当前解，爬山算法搜索到 A 点这个局部最优解就会停止搜索，因为在 A 点无论向哪个方向小幅度移动都不能得到更优的解。

《图1》

图1　最优解搜索最优示意图

Fig.1　Schematic diagram of search for the optimal solution

爬山算法是完完全全的贪心算法，每次都以较小的步长选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火算法其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图 1 为例，模拟退火算法在搜索到局部最优解 A 后，会以一定的概率接受到 D 的移动。也许经过几次这样的不是局部最优的移动后会到达 E 点，于是就跳出了局部最大值 A 的范围。

在物流的配送网络中[2]，存在寻优的网络方案，如果采用这种优选方案，对物流配送企业来说会节省资金，增加配送速度；对货物接收方来说能够在较为合理的时间内接收物品，从而节省生产成本或消费成本。

《2　模拟退火算法数学描述》

2　模拟退火算法数学描述

若

即移动后得到更优解，则总是接受该移动；若

即移动后的解比当前解要差，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）。这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。根据热力学的原理，在温度为 T 时，出现能量差为ｄE 的降温的概率为 P（ｄE），可表示为

其中， k 是一个常数，ｅ 表示自然指数，且ｄE ＜０。

公式是指：温度越高，出现一次能量差为ｄE 的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于ｄE 总是小于０（这是模拟退火的本质决定的），因此ｄE／kT ＜０，所以 P（ｄE）的函数取值范围是（0,1），随着温度 T 的降低， P（ｄE）会逐渐降低。

将一次向较差解的移动看做一次温度跳变过程，以概率 P（ｄE）来接受这样的移动。

终止条件：设置一个接近于０ 的较小的值，例如 0.3。

《3　模拟退火算法的程序语言描述》

3　模拟退火算法的程序语言描述

《3.1　模拟退火算法流程》

3.1　模拟退火算法流程

模拟退火算法流程如图 2 所示。

《图2》

图2　模拟退火算法流程

Fig.2　Process of simulated annealing

《3.2　参数与函数定义》

3.2　参数与函数定义

在计算程序中的各个参数与函数的定义说明如下：

：在状态 y 时的评价函数值；：表示当前状态；：表示新的状态；r：用于控制降温的快慢；T：系统的温度，系统初始应该要处于一个高温的状态； T＿min：温度的下限，若温度 T 达到 T＿min，则停止搜索。

《3.3　模拟退火算法伪代码》

3.3　模拟退火算法伪代码

;

／／表达移动后得到更优解，则总是接受移动

 ；／／接受从Ｙ（i）到Ｙ（i ＋1）的移动

Else

{

    ／／函数 exp( dE/T )的取值范围是（0 , 1），dE/T 越大，则 exp( dE/T )也变大。

if （ exp( dE/T ) ＞random（0 , 1））

;   ／／接受从Ｙ（i）到Ｙ（i ＋1）的移动

}

 ；／／降温退火，０＜ｒ＜１。 ｒ越大，降温越慢；ｒ越小，降温越快

若ｒ过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若ｒ过小，则搜索的过程会很快，但最终可能会达到一个局部最优值

《4　模拟退火算法在区域交通流预测示例》

4　模拟退火算法在区域交通流预测示例

《4.1　区域物流配送示例》

4.1　区域物流配送示例

图 3 为一简单配送网络图，该网络表示在一个区域中进行配送分配问题，等同于最优化问题，表述模型表达式见式（4）。

《图3》

图3　配送网络图

Fig.3　Network diagram of distribution and delivery

式（4）中， q 为 OD（origin-destination）量； 为路线上的流量； 为路线 的路阻函数。

用退火算法解决此类问题，假设道路损耗的时间和经济价值如（2，3，5，1，4）和（2，5，8，3，6）。

可行解采用 0 和 1 的序列表示，如  ＝（10101）表示选择 1，3，5 线路，不选择 2 和 4 。

《4.2　计算进行步骤》

4.2　计算进行步骤

第一步，初始化，假设初始解 ＝（11001），初始温度为 10 ℃，计算开始。

第二步，在温度 T 下局部搜索，直到“平衡”；降温时机用在同一温度下反复进行 Metropolis[3]演算，假设次数为 3，搜寻法则，随机改变某一位的 0，1 或交换某两位 0，1 的值。假设产生新解 j ＝（11100），＝2 ＋5 ＋8 ＝15 ＞13，所以接受新解。假设产生的新解 j ＝（11010），＝2 ＋5 ＋3 ＝10 ＜13，计算接受概率 =exp （（10 –13） /10） ≈0.741，在（0，1）范围内产生一个随机数，如果随机数小于接受概率，则接受 j 为新解，否则不接受。

第三步，降温，假设温度降为 T ＝T – 1，如果没有达到结束标准，则返回第二步继续执行。

《4.3　计算结果》

4.3　计算结果

通过以上步骤的计算， ＝（10010），即选择线路1 和 4 作为最优解。存在２ 个最优的原因是结束过早，如果把成本计算进行的终止条件设置为 0.03，则结果将是＝（00010），即结果 4 为最优解。

《5　结语》

5　结语

模拟退火算法同其他各类人工智能算法相似，是一种随机算法，该算法并不一定能找到全局的最优精确解，但是可以比较快地找到问题的近似最优解，这是由算法本身决定的。但是作为一种在物流配送路径中的最优预测模型，可以认为是比较好的工具。模拟退火算法缺点在于如果参数设置不当，很容易造成得到结果耗费大量的时间，这无疑近似于穷举算法，这是科研工作者不希望看到的，故此参数设置将是模拟退火算法需要注重的一步。