DOC《用模拟退火方法解决TSP问题》

用模拟退火方法解决TSP问题 退火原理 退火是一种物理过程,金属物体在加热到一定温度后,他的分子状态在状态空间D中自由运动.

随着温度的降低,这些分子停留在低能量状态的概率逐渐增大,当温度趋进于0时,分子停留在低能量状态的概率趋向于1. 退火原理运用于组合优化问题 组合优化问题 金属物体 解 状态 最优解 能量最低状态 目标函数 能量 模拟退火算法 步骤1 任选一个初始解,初始温度,给定降温比例系数,以及一个纪录最优解的变量和其函数值best=;

步骤2 若,则停止计算,输出最优解best;

否则执行3;

步骤3 从的邻域中随机选择一个j, ;

若,则令,执行4;

否则若时,,

执行4;

否则执行3;

步骤4 若,则,,

,执行2;

否则,执行2;

实验结果和分析 通过五个城市节点的TSP问题的求解,其城市间的距离矩阵为: 模拟退火找到的最优路径为,总路程为43;

由实验结果我们发现,对于小规模的TSP问题,用模拟退火方法找到的解和用禁忌搜索方法找到的解不谋而合,都能够找到很好的解.