模拟退火算法解决 TSP 问题
一、代码介绍:
这段代码使用了模拟退火的思想解决 问题。在这个仿真实验中解决了自定义的
个城市的 问题,在设定合适参数后每次的运行中都能得到一个比较理想的结果。
文件是程序入口。
文件设置自定义的城市数据。
文件中包含随机交换两个城市的函数。
文件中包含将城市数据在二维平面上表示的函数。
文件中包含计算城市距离的函数,用来解决旅行商问题。
文件中包含模拟退火算法。这部分是程序的主体,我参考了许多讨论
关于模拟退火算法方面的论文。
二、模拟退火算法原理:
模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,
固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都
达到平衡态,最后在常温时达到基态,内能减为最小。根据 准则,粒子在温度
时趋于平衡的概率为 !",其中 为温度 时的内能, 为其改变量,! 为
#$ 常数。用固体退火模拟组合优化问题,将内能 模拟为目标函数值 ,温度 演
化成控制参数 ,即得到解组合优化问题的模拟退火算法:由初始解 和控制参数初值 开
始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减 值,算
法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机
搜索过程。退火过程由冷却进度表 %&"控制,包括控制参数的初值 及其衰减
因子 、每个 值时的迭代次数 ' 和停止条件 。Ñ
三、模拟退火的基本思想:
("初始化:初始温度 充分大",初始解状态 是算法迭代的起点",每个 值的迭代
次数 ')。
"对 !*(,……,' 做第 +"至第 , 步:Ñ
+"产生新解 -)
."计算增量 -*% -"% ",其中 % "为评价函数Ñ
/"若 -0 则接受 -作为新的当前解,否则以概率 1 -"接受 -作为新的当前解)
,"如果满足终止条件则输出当前解作为最优解,结束程序。Ñ
终止条件通常取为连续若干个新解都没有被接受时终止算法。Ñ
2" 逐渐减少,且 3,然后转第 步。Ñ
四、求解 TSP 的模拟退火算法:Ñ
解空间解空间 是遍访每个城市恰好一次的所有回路,是4(,……,5的所有循环排
列的集合, 中的成员记为 (6677,",并记 8(*(。初始解可选为 (,
……,")
目标函数此时的目标函数即为访问所有城市的路径总长度或称为代价函数:Ñ
我们要求此代价函数的最小值。Ñ
新解的产生随机产生 ( 和 之间的两相异数 ! 和 ,若 ! (667,!6!8(6
7,67,")
变为:Ñ
评论0