旅行商问题-模拟退火法和爬山法
模拟退火法和爬山法都是启发式算法,也就是说,他们的目的不在于寻找最优解,而是在寻找最优解和成本之间找到平衡。这适用于一些计算机难解问题。比如说旅行商问题。
本文数据下载自: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/a280.tsp.gz
模拟退火的代码: https://gist.coding.net/u/feanor/a8e2351ce0fb44578f7c0181f28bd846
爬山法的代码:https://gist.coding.net/u/feanor/d061dac114fd4b6fb44268bb48da1d0b
读取数据
数据文件前六行为声明、最后一行为EOF字符。中间每行有三个数字:第一个为节点的编号、第二三个为节点的横纵坐标。则读取文件数据的函数可以类似这样:
1 | def read_data(filename='../data/a280.tsp'): |
这样读出了数据的坐标并作为一个列表。
求距离
求距离矩阵以表示节点之间的距离;使用python自带的itertools中的笛卡尔积函数:
1 | def distances(points): |
选取一定数量的点
优化算法都需要说的是,它们并不会比较所有的点,它们只选择其中的一部分进行比较。然后我们就需要构造一个这样的集合:当点的数量多的时候,取得多;点的数量少的时候取得少。这样基本就是正比关系。但是当最后几个数字时候我们则很难取到…:
(说实话,这里的逻辑其实简单粗暴地我不太想写:
1 | def get_next(indexs): |
爬山法
爬山法的主要逻辑就是给一堆点。然后每次都选取离我最近的点,然后这样我每一步都是最短的,最后遍历完的时候至少也是比较短的点。
1 | def next_step(distances, curnode, next_list): |
然后算法的主要逻辑如下:
1 | def hill_climb(distances): |
模拟退火法
模拟退火法主要逻辑就是不是每个都取最近的点,给概率会接受选取其它的点。然后是对这个概率做文章:最开始这个概率很大,到后来这个就干脆不接受了。这就是模拟退火算法:
1 | def next_step(dist, curnode, next_list, temp): |
然后算法的主要逻辑如下:
1 | def simulate_anneal(distances): |
可视化
因为旅行商问题是遍历所有点的最短路径,所以只要直接将选出的最短路画出来,也就确保所有点都在纸上了。
1 | def pic_visualization(path, points): |
效果比较
不画图的效率比较
爬山法:
1 | $ time python tsp.py |
模拟退火法:
1 | $ time python tsp.py |
二者产生的路径
爬山法:
模拟退火法:
贪心法
贪心法其实跟爬山法是一样的:每次选出最好的结果,但是在贪心法里面是对所有数据进行比较的。
因此它花费的时间会比启发式算法慢,但是它的结果肯定会好不少。这里就用它的结果作为好的对比。
$ python tsp.py
最合适的路径为:
[108, 88, 80, 79, 78, 75, 74, 73, 72, 71, 70, 69, 66, 65, 64, 63, 62, 61, 117, 60, 59, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 30, 29, 124, 123, 122, 121, 120, 119, 118, 156, 157, 158, 159, 174, 160, 161, 162, 163, 164, 165, 166, 167, 168, 100, 99, 98, 97, 92, 93, 94, 95, 96, 91, 90, 89, 103, 102, 101, 169, 170, 171, 172, 105, 104, 106, 107, 109, 110, 113, 112, 86, 83, 82, 81, 87, 111, 114, 116, 115, 85, 84, 57, 56, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 58, 67, 68, 76, 77, 173, 181, 180, 175, 176, 150, 151, 155, 152, 154, 153, 128, 127, 20, 19, 18, 17, 16, 132, 131, 130, 129, 126, 125, 28, 27, 26, 25, 21, 24, 22, 23, 13, 12, 11, 10, 9, 7, 6, 8, 274, 273, 272, 271, 270, 15, 14, 269, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 177, 178, 179, 182, 183, 184, 186, 185, 188, 187, 189, 190, 191, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 250, 249, 246, 243, 240, 239, 238, 237, 230, 231, 232, 233, 234, 235, 236, 245, 244, 242, 241, 1, 279, 2, 278, 277, 3, 276, 275, 5, 4, 0, 247, 248, 255, 254, 251, 252, 253, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 31, 192]
最小花费为:3116.016610
路径可视化:
为什么要写这么一个东西
因为我在网上搜到了一篇错误的教程,里面出现的代码不但错误,而且思想也不对。我愿想做一个更深入地了解的,但是期末已经临近了,博客还是暂时少花一点时间为妙。于是想着就算是纯贴代码也好了,于是就有了这篇博客。如果您也吃过错误教程的亏,您应该会明白我感到愤怒的原因。