模拟退火算法的旅行商问题的实现

1、基于模拟退火算法的旅行商问题的实现摘 要：主耍介绍了模拟退火算法的原理以及应用，并月将遗传算法应用于解决旅行商问题。关键词:模拟退火算法 旅行商问题中图分类号：文献标识码：a文章编号：1006-7043 (2004) xx-xxxx-xthe application of simulated annealing in the tsptan jian (s311080153)(harbin engineering university information and communication system,harbin 150001)abstract： in this paper,the si

2、mulated annealing algorithm is introduced ,and applaied in sovling tha traveling saleman prombles.key words: simulated annealing , traveling saleman prombles 火算法(sa)与其它搜索方法相比，具有如下 引言的特点：模拟退火算法(simulated annealing, sa) 最早由kirkptitrick等应用于组合优化领域， 它是基于m ente-carlo迭代求解策略的一种 随机寻优算法山。模拟退火算法是一种通用 的优化算法，理论上

3、算法具有概率的全局优 化性能,0前已在工程中得到了广泛应用，诸 如vlsi、生产调度、控制工程、机器学习、 神经网络、信号处理等领域 1模拟退火算法概述模拟退火又称montecarlo退火,是一 种常用的全局优化方法，它来源于固体退火 原理:将固体加温至充分高，再让其徐徐冷 却，加温时，固体内部粒子随温升变为无序 状态，内能增大，而徐徐冷却时粒子渐趋有 序，在每个温度都达到平衡态，最后在常温 时达到基态，内能减为最小；然而要是迅速 冷却或被“碎熄”，那么仅仅能达到其局部 能量极小点，该材料处于易碎状态。这就 是所谓退火在技术上的定义，同时也表明了 确保达到低能量状态所必需的条件。模拟退以一定的

4、概率接受恶化解模拟退火算法(sa)在搜索策略上与传 统的随机搜索方法不同，它不仅引入了适当 的随机因素，而且还引入了物理系统退火过 程的自然机理l4 o这种自然机理的引入使模 拟退火算法在迭代过程中不仅接受使目标 函数变“好”的试探点，而且还能以一定的 概率接受使冃标函数值变“差”的试探点， 迭代屮出现的状态是随机产生的，并不强求 后一状态一定优于前一状态，接受概率随看 温度的下降而逐渐增大。传统的方法往往是 从解空间的一个初始点开始最优解的迭代 搜索过程。如登山法，若一个细微变动能改 善质暈，则沿该方向前进，否则取相反方向。 然而复杂问题会使解空间中出现若干局部 最优解，传统的方法很容易限于

5、局部最优解 而停滞不前，很多传统的优化算法往往是确 定性的，从一个搜索点到另一个搜索点的转 移有确定的转移方法和转移关系，这种确定 性往往可能使得搜索永远达不到最优点，因 而限制了算法的应用范围。模拟退火算法 (sa)以一种概率的方式來进行搜索，增加了 搜索过程的灵活性。(2) 引进算法控制参数引进类似于退火温度的算法控制参数， 它将优化过程分成各个阶段，并决定各个阶 段下随机状态的取舍标准，接受函数由mert 叩。模拟退火算法的两个重要步骤是:一是 在每个控制参数下，由前迭代点出发，产生 邻近的随机状态，市控制参数确定的接受准 则决定此新状态的取舍，并由此形成一定长 度的随机markov链:

6、二是缓慢降低控制参 数，提高接收准则，直至控制参数趋于零， 状态链稳定于优化问题的最优状态，提高模 拟退火算法全局最优解的可靠性。(3) 使用对象函数值进行搜索传统搜索算法不仅盂要利用目标函数 值，而且往往需耍目标函数的导数值等其它 一些辅助信息刁能确定搜索方向，当这些 信息不存在时，算法就失效了。而模拟退火 算法仅使用由目标函数变换来的适应度函 数值，就可确定进一步的搜索方向和搜索范 围，无需其它的辅助信息。需要着重指出的 是:模拟退火算法的适应度函数不仅不受连 续可微的约束，而且其定义域可以任意设 定，对适应度函数唯一-的要求是对于输入可 计算出加以比较的正的输出。这个特性对很 多无法或很

7、难求导数的两数，或导数不存在 的函数的优化问题，以及组合优化问题等， 应用模拟退火算法就比较方便。另外，直 接利用目标函数值或个体适应度，也可以把 搜索范围集中到适应度较高的部分搜索空 间，从而提高搜索效率。(4) 隐含并行性并行算法是60年代发展起来的，其发 展速度相当快。有些专家甚至认为目前提高 计算机系统性能的唯一方法是“选择大量的 并行”。从目前情况看，并行算法的设计主 要采用两种方法:一是对现有的串行算法加 工改造，使之成为好的并行算法;二是结合 所用并行计算机的结构特点，直接设计新的 并行算法。将模拟退火算法改造为并行算法 还是比较容易的。目前常见的有以下儿种并 行策略:操作并行策

8、略，试演并行策略，区 域分裂策略和混乱松弛策略等。这儿种并行 算法在不同程度上対解的质量，收敛速度上 较模拟退火算法优，由此可预见，大规模的 并行计算模式将成为研究全局优化问题的 主流，即模拟退火算法隐含并行性，它是优 于其它求解过程的关键所在。另外模拟退火 算法的隐含并行性还有助于处理非线性问 题。(5) 搜索复杂区域模拟退火算法最善于搜索复杂地区，从 中找出期望值高的区域，在求解简单问题上 效率并不高。2算法原理2. 1旅行商问题屮的相关定义(1) 问题定义：dij代表从城市i到城市j的距离 (i, j=l,2,3,20),问题是要找出遍 访每个城市恰好一次的一条回路，且其 路径长度r为最

9、小。(2) 解空间：解空间p是遍访每个城 市恰好一次的所有回路，可表示为 (1,2,3,，20)的所有循坏排列的集 合。(3) 新解的产生：在第广20个访问的 城市中随机选取第i次和第j次访问的 城市，在路径p屮交换这两个城市的访 问顺序其余不变，此时的路径为rz (新 解的产生方法不唯一)(4) 目标函数：目标函数为访问所有 城市的回路长度，需求其最小值。2. 2模拟退火算法模拟退火算法是一种非导数优化方 法。模拟退火来源于拉丝玻璃的物理特 性，原理类似于以一定的速率冷却金属 时所发生的现象。缓慢下降的温度使融 化金属中的原子排成有规则的结构，结 果将产生具有较高能量的非晶体结构。 在该算法

10、屮，温度较高时允许对远处的点求函数值，并且有可能接受一个具有 较高能量的新点。而温度低吋，模拟退 火算法只在局部处求目标函数值，它接 受较高能量新点的可能性非常小。模拟退火算法包含的基本步骤：(1) 选取一个起始点并设一个较 高的起始温度t令迭代次数n=l；(2) 求目标函数e=f(x)的函数值；(3) 按照由生成函数g(ax , t)确 定的概率选择ax,令新点xn等于 x+ a x；(4) 计算新的目标函数值e=f (xn)；(5) 按照由接受函数h(ae, t)确定 的概率将x设为xn, e设为e,其 中 e=e»e；(6) 按照退火时间表降低温度t ；(7) 增加迭代次数k,

11、如果k达到最 大迭代次数，停止迭代，否则返回 步骤。3模拟退火算法tsp问题的仿真3. 1选取起始点并初始化变量在利用模拟退火进行优化z前，必 须首先选取一个优化的起始点，该优化 起始点随机选取。本实验中设城市数fi 为20, z=x, y为城市坐标：x = 17 7 16 9 18 12 1 14 2 15 3 10 11 4 6 5 8 19 13 20y = 1 18 4 7 15 13 1 1 20 6 19 5 3 8 17 12 9 2 16 14 103. 2固定温度的模拟退火子函数首先，在温度为一个较高值时，利 用生成函数确定新的搜索点，常用的生 成函数有boltzman机使用

12、的高斯密度函 数,cauchy机使用的cauchy分布函数等。 为了确定新数据是否能够被接受，必须 选择一个适当的接受函数。满足停止条件。3.3降低温度继续优化过程按照退火时间表降低温度，s二0.98t,重新进行模拟退火推理，直到虽然城市的访问起点不同，但城市的访 问次序是一定的，说明程序仿真将结果的稳 定性，以及算法的可靠性。流程图以及仿真 结果如下图所示：图一算法流程图图二第一次仿真结果图三第二次仿真结果4遗传算法的应用领域遗传算法具有很强的全局搜索能力，通 用性强，鲁棒性高，因而被广泛应用于很多 领域，下面简要介绍一些主要的应用领域：(1) 函数优化。函数优化不仅是遗传 算法的经典应用领

13、域，而ii各类复杂的测试 函数也是对遗传算法进行性能评价的依据。 另外，对于一些使用其他优化方法很难求解 的非线性、多冃标函数优化问题，应用遗传 算法一般可以得到满意的优化结果。(2) 调度问题。遗传算法在生产调度 中得到了广泛的应用，不仅避免了只依据靠 经验调度的不可靠性，而r避免了在传统求 解过程中由于对模型的大幅度简化，而导致 求得结果与实际结果z间的巨大差异。(3) 图像处理。遗传算法在模式识别、 图像恢复、图像边缘特征提取等方血得到了 广泛的应用。(4) 自动控制领域。遗传算法在参数 辨识、模糊控制器的优化设计、模糊控制规 则的学习中的应用取得了很显著的成果。另 外，遗传算法在航空控

14、制系统的优化、空间 交会控制器的设计、故障诊断和机器人行走 路径规中的应用也取得了成功。(5) 机器学习。基于遗传算法的机器 学习，在很多领域中都得到了广泛的应用。 其中比较典型的是holland设计的分类器系 统，以及机器人规划、模式识别、概念学习 等)。(6) 社会与经济领域。基于遗传算法 的思想，软件开发人员设计了很多的软件 包，服务于各类社会和经济行业，比如金融 系统和股票投资分析行业。(7) 人工智能与科学计算。因为很多 求解问题的复杂性，往往得不到问题的解析 解，人们尝试运用各种算法求出最优解的近 似解來逼近最优解。遗传算法是这类算法中 一种典型的方法，被广泛应用在很多问题求 解川

15、。例如本文给出了遗传算法在配电网设 备检修优化模型中的应用实例，如杲将优化 结果应用在配电网设备检修计划中，能从很 大程度上降低因检修而带來的损耗，具有很 好的经济应用价值。7结束语本文主要针对模拟退火算法进行了分 析，并且将模拟退火算法应用于対旅行商问 题的求解，得到了预期效果。参考文献：lu毕晓君信息智能处理技术m.西安：电 子工业出版社.2010,3,93117张晓峰，王茂芝,胥泽银，等.利用模拟退火 算法优化计算通讯网络极小生成树j.成都 理工学院学报,2002( 1 ):90-92.3 .潘昊,曲晓丽.旅行商问题的一种模拟 退火算法求解j.现代电子 技,2007(18):5-94 范千,许承权，陈伟.单纯形模拟退火混合算法及其在参数估计中的应用j.地 理空间信息,2005:57