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

《模拟退火算法的旅行商问题的实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于模拟退火算法的旅行商问题的实现摘要：主耍介绍了模拟退火算法的原理以及应用，并月•将遗传算法应用于解决旅行商问题。关键词:模拟退火算法旅行商问题中图分类号：文献标识码：A文章编号：1006-7043(2004)xx-xxxx-xTheApplicationofSimulatedAnnealingInTheTSPTanJian(S311080153)(HarbinEngineeringUniversityInformationandCommunicationsystem,Harbin150001)Abstract：Inthispaper,theSimulatedAn

2、nealingalgorithmisintroduced,andapplaiedinsovlingthatravelingsalemanprombles.Keywords:SimulatedAnnealing,travelingsalemanprombles火算法(SA)与其它搜索方法相比，具有如下引言的特点：模拟退火算法(SimulatedAnnealing,SA)最早由Kirkptitrick等应用于组合优化领域，它是基于Mente-Carlo迭代求解策略的一种随机寻优算法山。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,0前已在工程中得到

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

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

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

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

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