说 TSP 问题代表了一类组合优化问题, 因而探讨 TSP 问题的有效求解方法有着广泛的应用前景,如旅游问题、电子地图、运输线路、电器布线、计算机联网等[3]。 TSP 问题表面看很简单,其实不然。当 TSP 问题的规模为 N 个城市时,可行解集中的路径数为(N-1)!/2, 要从(N-1)!/2 个可行解中找出哪条路径最短, 若以路径间的比较为基本操作, 则需进行的基本操作数是(N-1)!/2-1, 随 N 的不断增长,将出现“指数爆炸”现象。若用每秒运算一亿次的计算机, N=10 时只需 0.0018 秒, N=20 时就需 19年, N=30 时则猛增为 1.4 ×10 ^15 年!显然,这样求 TSP 问题的方法是不可行的。模拟退火算法(Simulated Annealing Algorithm ,简称 SAA) 为求解上述传统方法难处理的问题提供了一个有效的途径和通用框架,并逐渐发展成一种迭代自适应启发式概率性搜索算法。用以求解不同的非线性问题;对不可微甚至不连续的函数优化, SAA 能通过 Metropolis 接受准则概率接受劣化解并以此跳出局部最优, 通过温度更新函数的退温过程进行趋化式搜索并最终进入全局最优解集,从而以较大概率求得全局优化解;具有较强的鲁棒性、全局收敛性、隐含并行性及广泛的适应性; 并且能处理不同类型的优化第一章前言 2 设计变量(离散的、连续的和混合型的);不需要任何的辅助信息,对目标函数和约束函数没有任何要求。利用 Metropolis 算法并适当地控制温度下降过程, 在优化问题中具有很强的竞争力,因此研究 SAA 算法在优化中的应用显得尤为重要[4] 。本文就应用 SAA 解决 TSP 问题,并针对典型的 TSP 问题,应用 MATLAB 语言给出了这一方法的具体实现过程,在此基础上对旅行商问题的仿真运行结果说明了方法和编程的正确性。
全文预览
