模拟退火算法在TSP求解中的应用Word格式文档下载.docx
《模拟退火算法在TSP求解中的应用Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《模拟退火算法在TSP求解中的应用Word格式文档下载.docx（11页珍藏版）》请在冰点文库上搜索。
虽然该方法在理论上是可行的，但路径的个数与城市的个数成指数增长，当城市个数较大时，该方法的求解时间是难以忍受的，甚至是不可能完成的。
以每秒1亿次的计算速度来估算，如果TSP问题包含20个城市时，求解时间长达350年；
如果要处理30个城市，则求解时间更长达1+10e16年。
如此长的时间，在实际中完成是不现实的。
基于模拟退火算法在处理全局优化、离散变量优化等困难问题中，具有传统优化算法无可比拟的优势。
本文介绍了模拟退火算法的基本原理，并利用SA算法实验求解TSP问题，借此显现了SA算法比传统算法的优势。
2算法理论分析
2.1模拟退火算法简介
模拟退火算法的思想最早由Metropolis等提出的。
其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。
模拟退火法是一种通用的优化算法，其物理退火过程由以下三部分组成：
（1）加温过程。
其目的是增强粒子的热运动，使其偏离平衡位置。
当温度足够高时，固体将熔为液体，从而消除系统原先存在的非均匀状态。
（2）等温过程。
对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡状态。
（3）冷却过程。
使粒子热运动减弱，系统能量下降，得到晶体结构。
其中，加温过程对应算法的设定初温，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降。
这里能量的变化就是目标函数，我们要得到的最优解就是能量最低态。
其中Metro-polis准则是SA算法收敛于全局最优解的关键所在，Metropolis准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱。
2.2模拟退火算法的模型
模拟退火算法可以分解为解空间、目标函数和初始解三部分。
模拟退火的基本思想：
1．初始化：
初始温度T（充分大），初始解状态S（是算法迭代的起点），每个T值的迭代次数L；
2．对k=1，…，L做第（3）至第6步；
3．产生新解S′；
4．计算增量Δt′=C（S′）-C（S），其中C（S）为评价函数；
5．若Δt′<
0则接受S′作为新的当前解，否则以概率exp（-Δt′/T）接受S′作为新的当前解；
6．如果满足终止条件则输出当前解作为最优解，结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法；
7．T逐渐减少，且T->
0，然后转第2步。
2.3TSP模型
（1）问题定义：
设n为城市数目，D=[dij]为n×
n阶距离矩阵，dij代表从城市i到城市j的距离（i，j=1，2，3…n），则问题是要找出遍访每个城市恰好一次的一条回路，且其路径长度为最短。
（2）解空间：
解空间S是遍访每个城市恰好一次的所有回路，可表示为（1…n）的所有循环排列的集合，即S=[Sij]为（1…n）的排列，Si表示第i个城市第Si个被访问。
（3）目标函数：
目标函数为访问所有城市的回路长度或称为代价函数，需求其最小值，选d=
为最小。
3模拟退火算法求解TSP
求解TSP的模拟退火算法模型可描述如下：
图1模拟退火算法的流程图
我们要求的最优路径为目标函数为最小值时对应的路径。
新路径的产生：
随机产生1和n之间的两相异数k和m，不妨假设k<
m，则将原路径（w1，w2，…，wk，wk+1，…，wm，wm+1，…，wn）变为新路径：
（w1，w2，…，wm，wk+1，…，wk，wm+1，…，wn）上述变换方法就是将k和m对应的两个城市在路径序列中交换位置，称为2-opt映射。
根据上述描述，模拟退火算法求解TSP问题的流程框图如图1所示。
图1展示了模拟退火算法的大体流程图。
选定初始状态X0，作为当前解：
并且确定初始温度T0，令当前的Xi=X0和Ti=T0。
然后从Xi的邻域中随即选择Xj，计算Xi与Xi的路径差，比较差值。
按一定方式将T降温，即令T（t+1）＝k×
T（t），i=i+1，然后检查退火过程是否结束，如果不是继续交换，如果是的话输出Si作为最优输出。
4仿真实验
实验环境：
MATLAB7.1.0
实验算例：
20个城市TSP（自定义），相对坐标如图2所示。
参数设定：
初始温度：
4000，冷却速率：
0.95，阈值：
3500
算法终止条件为控制参数t的值小于某个充分小的正数D。
求解得到的最优路径图如图3所示。
图220座城市相对坐标
图3模拟退火算法得到的最优路径图
从实验结果看，利用模拟退火算法求解TSP问题是可行有效的，但当TSP求解的城市规模增大时，找到最优解的次数也在降低。
5结论
模拟退火算法是一种可行、有效的全局优化的数值计算方法，它在解决高维空间、高复杂度及非线性问题的优化中具有全局最优、效率高及易于并行计算等优点，有很强的解决实际问题的能力。
近年来在模式识别、自动控制、机器学习、人工神经网络结构参数优化等许多领域受到重视，应用范围不断扩大。
本文给出了用SA算法求解TSP问题的流程，并详述了各参数的取值，程序是在MATLAB环境中编写的，该程序基本实现了该课题的任务目标，研究SA算法的基本原理以及TSP组合优化问题，用一种程序语言实现基于SA算法的TSP问题求解方法。
并且本文说明了用SA算法能够较好地求解旅行商问题。
因而理论上能够找到最优解，但所得结论与实际应用还有一定距离，特别是对连续变量函数的优化问题。
目前，SA算法参数的选择仍然依赖于一些启发式准则和待求问题的性质。
SA算法的通用性很强，算法易于实现，但要真正取得质量和可靠性高、初值鲁棒性好的效果，客服计算时间较长、效率较低的缺点，并适用于规模较大的问题，尚需进行大量的研究工作。
参考文献：
[1]王大志，汪定伟，闫杨.一类多旅行商问题的计算及仿真分析[J].系统仿真学报，2009（20）：
6378-6381.
[2]汪定伟等编著.智能优化方法[M]，北京：
高等教育出版社，2007
[3]冯剑，岳琪.模拟退火算法求解TSP问题[J].森林工程，2008，24
（1）：
94-96.
[4]朱静丽.用模拟退火算法求解TSP[J].湖北广播电视大学学报，2011，31（9）：
159-160.
[5]庞峰.模拟退火算法的原理及算法在优化问题上的应用[D].吉林大学，2006.
[6]马良.旅行推销员问题的算法综述[J].数学的实践与认识，2000，30
（2）：
156-165.
附录：
程序代码
代码使用了模拟退火的思想解决TSP问题。
在仿真实验中解决了自定义的20个城市的TSP问题，在设定合适参数后每次的运行中都能得到一个比较理想的结果。
主要的程序代码如下：
functionf=plotcities（inputcities）
%将输入的城市在二维平面上表示出来,每个星号代表一个城市。
shg
temp_1=plot（inputcities（1,:
）,inputcities（2,:
）,'
b*'
）;
set（temp_1,'
erasemode'
'
none'
temp_2=line（inputcities（1,:
Marker'
*'
set（temp_2,'
color'
b'
x=[inputcities（1,1）inputcities（1,length（inputcities））];
y=[inputcities（2,1）inputcities（2,length（inputcities））];
xl=10*round（min（inputcities（1,:
））/10）;
yl=10*round（min（inputcities（2,:
ifxl>
0
xl=0;
end
ifyl>
yl=0;
xu=10*round（max（inputcities（1,:
yu=10*round（max（inputcities（2,:
ifxu==0
xu=1;
ifyu==0
yu=1;
axis（[xlxuylyu]）;
temp_3=line（x,y）;
set（temp_3,'
dist=distance（inputcities）;
distance_print=sprintf（...
'
Theroundtriplengthfor%dcitiesis%4.6funits'
...
length（inputcities）,dist）;
text（xl/1.05,1.05*yu,distance_print,'
fontweight'
bold'
drawnow;
functions=simulatedannealing（inputcities,initial_temperature,cooling_rate,threshold,numberofcitiestoswap）
%模拟退火算法。
参数有输入城市数据，初始温度，冷却速率，阈值和交换城市数量。
globaliterations;
temperature=initial_temperature;
initial_cities_to_swap=numberofcitiestoswap;
iterations=1;
complete_temperature_iterations=0;
previous_distance=distance（inputcities）;
whileiterations<
threshold
temp_cities=swapcities（inputcities,numberofcitiestoswap）;
current_distance=distance（temp_cities）;
diff=abs（current_distance-previous_distance）;
ifcurrent_distance<
previous_distance
inputcities=temp_cities;
ifrem（iterations,100）==0
plotcities（inputcities）;
end
ifcomplete_temperature_iterations>
=10
temperature=cooling_rate*temperature;
complete_temperature_iterations=0;
numberofcitiestoswap=round（numberofcitiestoswap*exp（-diff/（iterations*temperature）））;
ifnumberofcitiestoswap==0
numberofcitiestoswap=1;
previous_distance=current_distance;
iterations=iterations+1;
complete_temperature_iterations=complete_temperature_iterations+1;
else
ifrand
（1）<
exp（-diff/（temperature））
functions=swapcities（inputcities,n）
%随机交换两个城市。
s=inputcities;
fori=1:
n
city_1=round（length（inputcities）*rand
（1））;
ifcity_1<
1
city_1=1;
city_2=round（length（inputcities）*rand
（1））;
ifcity_2<
1
city_2=1;
temp=s（:
city_1）;
s（:
city_1）=s（:
city_2）;
city_2）=temp;
functiond=distance（inputcities）
%计算输入城市的距离解决旅行商问题。
d=0;
forn=1:
length（inputcities）
ifn==length（inputcities）
d=d+norm（inputcities（:
n）-inputcities（:
1））;
else
n+1））;
升级会员 