基于模拟退火算法的旅行商问题的实现
摘 要: 主要介绍了模拟退火算法的原理以及应用，并且将遗传算法应用于解决旅行商问题。
关键词:模拟退火算法 旅行商问题
中图分类号： 文献标识码：A 文章编号：1006-7043 (2004) xx-xxxx-x
The Application of Simulated Annealing In The TSP
Tan Jian（S311080153）
（Harbin Engineering University Information and Communication system,Harbin 150001）
Abstract: In this paper,the Simulated Annealing algorithm is introduced ,and applaied in sovling tha traveling
saleman prombles.
Key words: Simulated Annealing , traveling saleman prombles
火算法(SA)与其它搜索方法相比，具有如下
引言
模拟退火算法(Simulated Annealing，SA)最早由Kirkpatrick等应用于组合优化领域，它是基于Mente-Carlo迭代求解策略的一种随机寻优算法[1]。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域[2]。
的特点:
(l)以一定的概率接受恶化解
模拟退火算法(SA)在搜索策略上与传统的随机搜索方法不同，它不仅引入了适当的随机因素，而且还引入了物理系统退火过程的自然机理[4]。这种自然机理的引入使模拟退火算法在迭代过程中不仅接受使目标函数变“好”的试探点，而且还能以一定的概率接受使目标函数值变“差”的试探点，迭代中出现的状态是随机产生的，并不强求后一状态一定优于前一状态，接受概率随着温度的下降而逐渐增大。传统的方法往往是从解空间的一个初始点开始最优解的迭代搜索过程。如登山法，若一个细微变动能改善质量，则沿该方向前进，否则取相反方向。然而复杂问题会使解空间中出现若干局部最优解，传统的方法很容易限于局部最优解而停滞不前，很多传统的优化算法往往是确定性的，从一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定性往往可能使得搜索永远达不到最优点，因而限制了算法的应用范围
[5]
1模拟退火算法概述
模拟退火又称MonteCarlo退火，是一
种常用的全局优化方法，它来源于固体退火原理:将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状态，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小;然而要是迅速冷却或被“碎熄”，那么仅仅能达到其局部能量极小点，该材料处于易碎状态
[3]
。这就。模拟退火算法
是所谓退火在技术上的定义，同时也表明了确保达到低能量状态所必需的条件。模拟退
(SA)以一种概率的方式来进行搜索，增加了搜索过程的灵活性。
(2)引进算法控制参数
引进类似于退火温度的算法控制参数，它将优化过程分成各个阶段，并决定各个阶段下随机状态的取舍标准，接受函数由Mert叩。模拟退火算法的两个重要步骤是:一是在每个控制参数下，由前迭代点出发，产生邻近的随机状态，由控制参数确定的接受准则决定此新状态的取舍，并由此形成一定长度的随机Markov链:二是缓慢降低控制参数，提高接收准则，直至控制参数趋于零，状态链稳定于优化问题的最优状态，提高模拟退火算法全局最优解的可靠性[6]。 (3)使用对象函数值进行搜索
传统搜索算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其它一些辅助信息刁‘能确定搜索方向，当这些信息不存在时，算法就失效了。而模拟退火算法仅使用由目标函数变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，无需其它的辅助信息。需要着重指出的是:模拟退火算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定，对适应度函数唯一的要求是对于输入可计算出加以比较的正的输出。这个特性对很多无法或很难求导数的函数，或导数不存在的函数的优化问题，以及组合优化问题等，应用模拟退火算法就比较方便
[7]
。另外，直
接利用目标函数值或个体适应度，也可以把
搜索范围集中到适应度较高的部分搜索空间，从而提高搜索效率。 (4)隐含并行性
并行算法是60年代发展起来的，其发展速度相当快。有些专家甚至认为目前提高计算机系统性能的唯一方法是“选择大量的并行”。从目前情况看，并行算法的设计主要采用两种方法:一是对现有的串行算法加工改造，使之成为好的并行算法;二是结合所用并行计算机的结构特点，直接设计新的并行算法。将模拟退火算法改造为并行算法还是比较容易的。目前常见的有以下几种并
行策略:操作并行策略，试演并行策略，区域分裂策略和混乱松弛策略等。这儿种并行算法在不同程度上对解的质量，收敛速度上较模拟退火算法优，由此可预见，大规模的并行计算模式将成为研究全局优化问题的主流，即模拟退火算法隐含并行性，它是优于其它求解过程的关键所在。另外模拟退火算法的隐含并行性还有助于处理非线性问题[8]。
(5)搜索复杂区域
模拟退火算法最善于搜索复杂地区，从中找出期望值高的区域，在求解简单问题上效率并不高。
2算法原理
2.1旅行商问题中的相关定义
(1)问题定义：
Dij代表从城市i到城市j的距离(i,j=1,2,3,„„,20)，问题是要找出遍访每个城市恰好一次的一条回路，且其路径长度R为最小。
(2)解空间：解空间P是遍访每个城市恰好一次的所有回路，可表示为(1,2,3,„„,20)的所有循环排列的集合。
(3)新解的产生：在第1~20个访问的城市中随机选取第i次和第j次访问的城市，在路径P中交换这两个城市的访问顺序其余不变，此时的路径为R1。(新解的产生方法不唯一)
(4)目标函数：目标函数为访问所有城市的回路长度，需求其最小值。 2.2模拟退火算法
模拟退火算法是一种非导数优化方法。模拟退火来源于拉丝玻璃的物理特性，原理类似于以一定的速率冷却金属时所发生的现象。缓慢下降的温度使融化金属中的原子排成有规则的结构，结果将产生具有较高能量的非晶体结构。在该算法中，温度较高时允许对远处的
点求函数值，并且有可能接受一个具有较高能量的新点。而温度低时，模拟退火算法只在局部处求目标函数值，它接受较高能量新点的可能性非常小。
模拟退火算法包含的基本步骤：
(1)选取一个起始点z，并设一个较高的起始温度T令迭代次数N=1； (2)求目标函数E=f(x)的函数值； (3)按照由生成函数g(Δx , T)确定的概率选择Δx，令新点xn等于x+Δx；
(4)计算新的目标函数值En=f(xn)； (5)按照由接受函数h(ΔE，T)确定的概率将x设为xn，E设为En，其中ΔE=En—E；
(6)按照退火时间表降低温度T； (7)增加迭代次数k，如果k达到最大迭代次数，停止迭代，否则返回步骤(3)。
3 模拟退火算法TSP问题的仿真
3.1选取起始点并初始化变量
在利用模拟退火进行优化之前，必须首先选取一个优化的起始点，该优化起始点随机选取。本实验中设城市数目为20，Z=[X,Y]为城市坐标：
X = [17 7 16 9 18 12 1 14 2 15 3 10 11 4 6 5 8 19 13 20]
Y = [1 18 4 7 15 13 11 20 6 19 5 3 8 17 12 9 2 16 14 10]
3.2固定温度的模拟退火子函数
首先，在温度为一个较高值时，利用生成函数确定新的搜索点，常用的生成函数有Boltzman机使用的高斯密度函数，Cauchy机使用的Cauchy分布函数等。为了确定新数据是否能够被接受，必须选择一个适当的接受函数。
3.3降低温度继续优化过程
按照退火时间表降低温度，s=0.98T，重新进行模拟退火推理，直到
满足停止条件。
虽然城市的访问起点不同，但城市的访问次序是一定的，说明程序仿真将结果的稳定性，以及算法的可靠性。流程图以及仿真结果如下图所示：
图一 算法流程图
图二 第一次仿真结果
图三 第二次仿真结果
4 遗传算法的应用领域
遗传算法具有很强的全局搜索能力，通
用性强，鲁棒性高，因而被广泛应用于很多领域，下面简要介绍一些主要的应用领域：（1）函数优化。函数优化不仅是遗传算法的经典应用领域，而且各类复杂的测试函数也是对遗传算法进行性能评价的依据。另外，对于一些使用其他优化方法很难求解的非线性、多目标函数优化问题，应用遗传算法一般可以得到满意的优化结果。 （2）调度问题。遗传算法在生产调度中得到了广泛的应用，不仅避免了只依据靠经验调度的不可靠性，而且避免了在传统求解过程中由于对模型的大幅度简化，而导致求得结果与实际结果之间的巨大差异。
（3）图像处理。遗传算法在模式识别、图像恢复、图像边缘特征提取等方面得到了广泛的应用。
（4）自动控制领域。遗传算法在参数辨识、模糊控制器的优化设计、模糊控制规则的学习中的应用取得了很显著的成果。另外，遗传算法在航空控制系统的优化、空间交会控制器的设计、故障诊断和机器人行走路径规中的应用也取得了成功。
（5）机器学习。基于遗传算法的机器学习，在很多领域中都得到了广泛的应用。其中比较典型的是Holland设计的分类器系统，以及机器人规划、模式识别、概念学习等)。
（6）社会与经济领域。基于遗传算法的思想，软件开发人员设计了很多的软件包，服务于各类社会和经济行业，比如金融系统和股票投资分析行业。
（7）人工智能与科学计算。因为很多求解问题的复杂性，往往得不到问题的解析解，人们尝试运用各种算法求出最优解的近似解来逼近最优解。遗传算法是这类算法中一种典型的方法，被广泛应用在很多问题求解中。例如本文给出了遗传算法在配电网设备检修优化模型中的应用实例，如果将优化
结果应用在配电网设备检修计划中，能从很大程度上降低因检修而带来的损耗，具有很好的经济应用价值。。
7 结束语
本文主要针对模拟退火算法进行了分析，并且将模拟退火算法应用于对旅行商问题的求解，得到了预期效果。
参考文献:
[1] 毕晓君. 信息智能处理技术[M].西安：电子工业出版社.2010,3,93~117
[2] 张晓峰,王茂芝,胥泽银,等.利用模拟退火算法优化计算通讯网络极小生成树[J].成都理工学院学报,2002(1):90-92.
[3].潘昊,曲晓丽.旅行商问题的一种模拟退火算法求解[J].现代电子技,2007(18):5-9
[4] 范千,许承权,陈伟.单纯形———模拟退火混合算法及其在参数估计中的应用[J].地理空间信息,2005(3):57-59.
[5] 杨卫波,赵燕伟.求解TSP问题的改进模拟退火算法[J].计算机工程与应用,2010,46(15):34-36.
[6] 冯剑,岳琪.模拟退火算法求解TSP问题[J].森林工程,2008,24(1):94-96.
[7] 许智宏,宋勃,董建波.用蚂蚁算法和模拟退火算法解大规模TSP问题的研究[J].计算机工程与科学,2008,30(10):43-44,57. [8]陈华根,吴健生,王家林,等.模拟退火算法机理研究[J].同济大学学报:自然科学版,2004,32(6):802-805.
基于模拟退火算法的旅行商问题的实现
摘 要: 主要介绍了模拟退火算法的原理以及应用，并且将遗传算法应用于解决旅行商问题。
关键词:模拟退火算法 旅行商问题
中图分类号： 文献标识码：A 文章编号：1006-7043 (2004) xx-xxxx-x
The Application of Simulated Annealing In The TSP
Tan Jian（S311080153）
（Harbin Engineering University Information and Communication system,Harbin 150001）
Abstract: In this paper,the Simulated Annealing algorithm is introduced ,and applaied in sovling tha traveling
saleman prombles.
Key words: Simulated Annealing , traveling saleman prombles
火算法(SA)与其它搜索方法相比，具有如下
引言
模拟退火算法(Simulated Annealing，SA)最早由Kirkpatrick等应用于组合优化领域，它是基于Mente-Carlo迭代求解策略的一种随机寻优算法[1]。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域[2]。
的特点:
(l)以一定的概率接受恶化解
模拟退火算法(SA)在搜索策略上与传统的随机搜索方法不同，它不仅引入了适当的随机因素，而且还引入了物理系统退火过程的自然机理[4]。这种自然机理的引入使模拟退火算法在迭代过程中不仅接受使目标函数变“好”的试探点，而且还能以一定的概率接受使目标函数值变“差”的试探点，迭代中出现的状态是随机产生的，并不强求后一状态一定优于前一状态，接受概率随着温度的下降而逐渐增大。传统的方法往往是从解空间的一个初始点开始最优解的迭代搜索过程。如登山法，若一个细微变动能改善质量，则沿该方向前进，否则取相反方向。然而复杂问题会使解空间中出现若干局部最优解，传统的方法很容易限于局部最优解而停滞不前，很多传统的优化算法往往是确定性的，从一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定性往往可能使得搜索永远达不到最优点，因而限制了算法的应用范围
[5]
1模拟退火算法概述
模拟退火又称MonteCarlo退火，是一
种常用的全局优化方法，它来源于固体退火原理:将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状态，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小;然而要是迅速冷却或被“碎熄”，那么仅仅能达到其局部能量极小点，该材料处于易碎状态
[3]
。这就。模拟退火算法
是所谓退火在技术上的定义，同时也表明了确保达到低能量状态所必需的条件。模拟退
(SA)以一种概率的方式来进行搜索，增加了搜索过程的灵活性。
(2)引进算法控制参数
引进类似于退火温度的算法控制参数，它将优化过程分成各个阶段，并决定各个阶段下随机状态的取舍标准，接受函数由Mert叩。模拟退火算法的两个重要步骤是:一是在每个控制参数下，由前迭代点出发，产生邻近的随机状态，由控制参数确定的接受准则决定此新状态的取舍，并由此形成一定长度的随机Markov链:二是缓慢降低控制参数，提高接收准则，直至控制参数趋于零，状态链稳定于优化问题的最优状态，提高模拟退火算法全局最优解的可靠性[6]。 (3)使用对象函数值进行搜索
传统搜索算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其它一些辅助信息刁‘能确定搜索方向，当这些信息不存在时，算法就失效了。而模拟退火算法仅使用由目标函数变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，无需其它的辅助信息。需要着重指出的是:模拟退火算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定，对适应度函数唯一的要求是对于输入可计算出加以比较的正的输出。这个特性对很多无法或很难求导数的函数，或导数不存在的函数的优化问题，以及组合优化问题等，应用模拟退火算法就比较方便
[7]
。另外，直
接利用目标函数值或个体适应度，也可以把
搜索范围集中到适应度较高的部分搜索空间，从而提高搜索效率。 (4)隐含并行性
并行算法是60年代发展起来的，其发展速度相当快。有些专家甚至认为目前提高计算机系统性能的唯一方法是“选择大量的并行”。从目前情况看，并行算法的设计主要采用两种方法:一是对现有的串行算法加工改造，使之成为好的并行算法;二是结合所用并行计算机的结构特点，直接设计新的并行算法。将模拟退火算法改造为并行算法还是比较容易的。目前常见的有以下几种并
行策略:操作并行策略，试演并行策略，区域分裂策略和混乱松弛策略等。这儿种并行算法在不同程度上对解的质量，收敛速度上较模拟退火算法优，由此可预见，大规模的并行计算模式将成为研究全局优化问题的主流，即模拟退火算法隐含并行性，它是优于其它求解过程的关键所在。另外模拟退火算法的隐含并行性还有助于处理非线性问题[8]。
(5)搜索复杂区域
模拟退火算法最善于搜索复杂地区，从中找出期望值高的区域，在求解简单问题上效率并不高。
2算法原理
2.1旅行商问题中的相关定义
(1)问题定义：
Dij代表从城市i到城市j的距离(i,j=1,2,3,„„,20)，问题是要找出遍访每个城市恰好一次的一条回路，且其路径长度R为最小。
(2)解空间：解空间P是遍访每个城市恰好一次的所有回路，可表示为(1,2,3,„„,20)的所有循环排列的集合。
(3)新解的产生：在第1~20个访问的城市中随机选取第i次和第j次访问的城市，在路径P中交换这两个城市的访问顺序其余不变，此时的路径为R1。(新解的产生方法不唯一)
(4)目标函数：目标函数为访问所有城市的回路长度，需求其最小值。 2.2模拟退火算法
模拟退火算法是一种非导数优化方法。模拟退火来源于拉丝玻璃的物理特性，原理类似于以一定的速率冷却金属时所发生的现象。缓慢下降的温度使融化金属中的原子排成有规则的结构，结果将产生具有较高能量的非晶体结构。在该算法中，温度较高时允许对远处的
点求函数值，并且有可能接受一个具有较高能量的新点。而温度低时，模拟退火算法只在局部处求目标函数值，它接受较高能量新点的可能性非常小。
模拟退火算法包含的基本步骤：
(1)选取一个起始点z，并设一个较高的起始温度T令迭代次数N=1； (2)求目标函数E=f(x)的函数值； (3)按照由生成函数g(Δx , T)确定的概率选择Δx，令新点xn等于x+Δx；
(4)计算新的目标函数值En=f(xn)； (5)按照由接受函数h(ΔE，T)确定的概率将x设为xn，E设为En，其中ΔE=En—E；
(6)按照退火时间表降低温度T； (7)增加迭代次数k，如果k达到最大迭代次数，停止迭代，否则返回步骤(3)。
3 模拟退火算法TSP问题的仿真
3.1选取起始点并初始化变量
在利用模拟退火进行优化之前，必须首先选取一个优化的起始点，该优化起始点随机选取。本实验中设城市数目为20，Z=[X,Y]为城市坐标：
X = [17 7 16 9 18 12 1 14 2 15 3 10 11 4 6 5 8 19 13 20]
Y = [1 18 4 7 15 13 11 20 6 19 5 3 8 17 12 9 2 16 14 10]
3.2固定温度的模拟退火子函数
首先，在温度为一个较高值时，利用生成函数确定新的搜索点，常用的生成函数有Boltzman机使用的高斯密度函数，Cauchy机使用的Cauchy分布函数等。为了确定新数据是否能够被接受，必须选择一个适当的接受函数。
3.3降低温度继续优化过程
按照退火时间表降低温度，s=0.98T，重新进行模拟退火推理，直到
满足停止条件。
虽然城市的访问起点不同，但城市的访问次序是一定的，说明程序仿真将结果的稳定性，以及算法的可靠性。流程图以及仿真结果如下图所示：
图一 算法流程图
图二 第一次仿真结果
图三 第二次仿真结果
4 遗传算法的应用领域
遗传算法具有很强的全局搜索能力，通
用性强，鲁棒性高，因而被广泛应用于很多领域，下面简要介绍一些主要的应用领域：（1）函数优化。函数优化不仅是遗传算法的经典应用领域，而且各类复杂的测试函数也是对遗传算法进行性能评价的依据。另外，对于一些使用其他优化方法很难求解的非线性、多目标函数优化问题，应用遗传算法一般可以得到满意的优化结果。 （2）调度问题。遗传算法在生产调度中得到了广泛的应用，不仅避免了只依据靠经验调度的不可靠性，而且避免了在传统求解过程中由于对模型的大幅度简化，而导致求得结果与实际结果之间的巨大差异。
（3）图像处理。遗传算法在模式识别、图像恢复、图像边缘特征提取等方面得到了广泛的应用。
（4）自动控制领域。遗传算法在参数辨识、模糊控制器的优化设计、模糊控制规则的学习中的应用取得了很显著的成果。另外，遗传算法在航空控制系统的优化、空间交会控制器的设计、故障诊断和机器人行走路径规中的应用也取得了成功。
（5）机器学习。基于遗传算法的机器学习，在很多领域中都得到了广泛的应用。其中比较典型的是Holland设计的分类器系统，以及机器人规划、模式识别、概念学习等)。
（6）社会与经济领域。基于遗传算法的思想，软件开发人员设计了很多的软件包，服务于各类社会和经济行业，比如金融系统和股票投资分析行业。
（7）人工智能与科学计算。因为很多求解问题的复杂性，往往得不到问题的解析解，人们尝试运用各种算法求出最优解的近似解来逼近最优解。遗传算法是这类算法中一种典型的方法，被广泛应用在很多问题求解中。例如本文给出了遗传算法在配电网设备检修优化模型中的应用实例，如果将优化
结果应用在配电网设备检修计划中，能从很大程度上降低因检修而带来的损耗，具有很好的经济应用价值。。
7 结束语
本文主要针对模拟退火算法进行了分析，并且将模拟退火算法应用于对旅行商问题的求解，得到了预期效果。
参考文献:
[1] 毕晓君. 信息智能处理技术[M].西安：电子工业出版社.2010,3,93~117
[2] 张晓峰,王茂芝,胥泽银,等.利用模拟退火算法优化计算通讯网络极小生成树[J].成都理工学院学报,2002(1):90-92.
[3].潘昊,曲晓丽.旅行商问题的一种模拟退火算法求解[J].现代电子技,2007(18):5-9
[4] 范千,许承权,陈伟.单纯形———模拟退火混合算法及其在参数估计中的应用[J].地理空间信息,2005(3):57-59.
[5] 杨卫波,赵燕伟.求解TSP问题的改进模拟退火算法[J].计算机工程与应用,2010,46(15):34-36.
[6] 冯剑,岳琪.模拟退火算法求解TSP问题[J].森林工程,2008,24(1):94-96.
[7] 许智宏,宋勃,董建波.用蚂蚁算法和模拟退火算法解大规模TSP问题的研究[J].计算机工程与科学,2008,30(10):43-44,57. [8]陈华根,吴健生,王家林,等.模拟退火算法机理研究[J].同济大学学报:自然科学版,2004,32(6):802-805.