再上一篇: 第 7 章  旅行商问题
上一篇:7.2  应用启发式搜索算法求解 TSP
主页
下一篇:7.4  应用遗传算法求解 TSP
再下一篇:7.5  本征值分析概述
文章列表

7.3  应用模拟退火算法求解 TSP

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

正如4.2.2节中所讨论过的,模拟退火可用于求解TSP。图4.3给出了求解的步骤。

生成一个旅程近邻的是二交换产生机制。它任选两个城市并通过反转在其被访城市中的

次序而得到一个新的旅程。详见(4.25)~(4.26)式和图4.2。

图4.3所示步骤的实现遵守如下规定:

1 + -

(1) 初始温度T 是这样得到的: 从1出发并以T = 1.05 T 增大直至接受概率

大于或等于0.9。

(2) 第k个马尔科夫链的允许长度为Lk= 10 城市个数。

(3) 第k个马尔科夫链的温度为Tk+1= 0.95Tk。

(4) 停止准则为①温度低于0.01,或②没有新旅程生成。

表7.5总结了利用模拟退火求解10城市问题的模拟运行结果。表中,出现次数指每

1000次模拟中出现的次数,平均次数指获得解答所用的平均扫描次数,而旅程自然是指

访问城市的顺序。在从随机初始旅程出发的1000次运行中,模拟退火找到最优旅程的情

况占90%,且每次运行中被接受的转移平均为3952次。

表7.5  利用模拟退火求解10城市问题的统计

90%有效解答 旅程长度 出现次数 平均次数 旅程 `

最优 2.691 906 3952 BCADEFGHIJ

次优 2.752 46 4056 BCADEGFHIJ

第三 2.769 10 4053 DEFGHIJCBA

最差 2.898 5 4497 ABCDEFHIJG

表7.6总结了利用模拟退火求解20城市问题(表7.4)的模拟运行结果。在从随机初

始旅程出发的1000次运行中,模拟退火找到最优旅程的情况占79.2%且每次运行中被

接受的转移平均为8740次。

表7.6  利用模拟退火求解20城市问题的统计

79.2%有效解答 旅程长度 出现次数 平均次数 旅程

最优 24.38 792 8740 ACLBIQFTMEPRGSOJHDKN `

次优 24.62 167 8638 ADCLBIQFTMEPRGSOJHKN `

第三 25.17 39 9902 ANKDHIOJSGRPEMTFQBLC `

最差 25.50 1 5794 AQFTMEPRGSJOIBLCDHKN `

#第69页-