|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
旅行商问题，常被称为旅行推销员问题，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单，但在地点数目增多后求解却极为复杂。 - 例:
- 1 2 3 4
- 1 0 6 7 9
- 2 8 0 9 7
- 3 5 8 0 8
- 4 6 5 5 0
- 从各个点出发的距离。
- 从1出发，再回到1的距离。
- 1-2-3-4-1
- 6 9 8 6
- 6+9+8+6 = 29
- 1-3-2-4-1
- 7 8 7 6
- 7+8+7+6 = 28
- 这样求最短路径。
解决这个问题快递小哥就能在最短的路程中送快递了~。
思路0:
1.0版本。
运用递归。(递归在解这种问题时总是那么容易想到~。)
穷举出每条路径，然后比较路程长短来确认最短路径。
下面是代码
- def find_path(map_list):
- # 寻找路径。
- path_result = []
- current_path_result_value = []
- map_len = len(map_list)
- list_map_len = map_len+1
- # 尝试列表的值。
- test_list = list(range(2, list_map_len))
- def test_path(map_list, x, y, path='', path_sum=0):
- if len(path.split('-')) == map_len:
- # 该返回了。
- path_sum += map_list[y-1][0]
- path += '-1'
- if not current_path_result_value:
- # 若当前没有存储值。
- current_path_result_value.append(path_sum)
- path_result.append(path)
- if current_path_result_value:
- # 当前有存储的值，比较大小。
- if current_path_result_value[0] > path_sum:
- current_path_result_value[0] = path_sum
- path_result[0] = path
- return 0
- for i in test_list:
- if str(i) in path:
- # 判断当前的值是否已经走过，保证其只走1此。
- continue
- # 记录路径。 计算路径总距离。
- test_path(map_list, x=y, y=i, path=path+'-{0}'.format(i), path_sum=path_sum+map_list[y-1][i-1])
- # 尝试。
- for i in range(2, list_map_len):
- test_path(map_list=map_list, x=1, y=i, path='1-{0}'.format(i), path_sum=map_list[0][i-1])
- return current_path_result_value,path_result
很容易写出来，相应的，效率非常慢。
十几个点的时候跑出结果不等个十几二十分钟那是不行。
2.0 版本。
所以果断抛弃递归，递归为我们打开了思路，下面用迭代改写。
在Python中的迭代器，自然会搬出itertools，生成地图的全排列，然后计算距离比较并输出。
思路依然是穷举。
- import itertools
- def find_path(map_list):
- # 遍历所有结果。
- path_list = itertools.permutations(range(2, len(map_list)+1))
- path_sum = []
- path = 0
- for i in path_list:
- temp_value = 0
- x = 0
- for j in i:
- temp_value += map_list[x][j-1]
- x = j - 1
- else:
- temp_value += map_list[x][0]
- if not path_sum:
- path_sum = temp_value
- path = i
- elif path_sum > temp_value:
- path_sum = temp_value
- path = i
- return path_sum, path
递归与迭代的写法上思路一样，但是运行过程不一样。
递归中，你可以每走一步，都计算每一步的距离，稳扎稳打。
迭代里，你要么先算出全部情况，要么先算出全部距离，
像递归一样的同时计算，用迭代觉得有些绕。
有了itertools的帮助，效率瞬间提高了很多很多，但是依然慢。(从非常慢变成了慢。)
---
那么牛逼的科学家呢发现用遗传算法解决这个问题比较好。
遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
如果你觉得不好理解看下面这个:
来自知乎如何通俗易懂地解释遗传算法？有什么例子？
就是说，选取两个异性！
蓝后XXOO，生后代，
蓝后继续XXOO，生后代，
蓝后后代越来越接近想要的结果。
基于良好的基因，生出更良好的后代。
大自然说: 适者生存。
遗传算法就是根据这个来编写程序的。
---
那么要实现这么一个算法需要哪些呢？
- 0. 种群。(父辈)
- 1. 基因不好的父辈死去。(结果与想要的结果相对不接近)
- 2. XXOO(你懂~)
- 3. 偶尔的变异，偶尔的灾变。
下面是运用的旅行商问题的具体思路。
0. 获取种群。
想要遗传，就要有父辈。
旅行商问题中的父辈是什么，就是那些路径。
我们可以简单的用itertools排序并取出前20个。(20~30个就可以。)
- def create_population(map_len, how_many=20):
- # 生成初始种群。
- result = []
- t = 0
- for i in itertools.permutations(range(2, map_len)):
- result.append(i)
- t += 1
- if t == how_many:
- result = map(list, result)
- return list(result)
- else:
- result = map(list, result)
- return list(result)
这样我们获取了种群。
下一步就是选择那些基因不好的父辈淘汰掉。
哪些是要淘汰的父辈呢?
就是总距离相对较大的。
1. 计算与淘汰。
- def calc_path(map_list, path):
- # 计算出该路径的所走距离。
- temp_value = 0
- x = 0
- for j in path:
- temp_value += map_list[x][j-1]
- x = j - 1
- else:
- temp_value += map_list[x][0]
- return temp_value
- def selection(all_path, lucky=[]):
- # 进行选择。
- # 每个个体的形式为[path, sum_path]
- # 根据距离长短进行排序。
- raw_result = [x for x in sorted(all_path, key=lambda t: t[1])]
- # 留下一半。
- result = raw_result[:int(len(raw_result)/2 + 1)]
- # 那些可能基因总体不良，但存活下来的个体。
- for i in lucky:
- if all_path[i] not in result:
- result.append(raw_result[i])
- return result
只提供一个思路，并不一定要这样写。
我们计算出偏大的距离，然后留下一半(并不一定要一半。)
适当的让一些基因总体不良，但是某个可能优异的个体有机会留下。(天生我材必有用嘛。)
留下了相对优异与幸运的个体就开始让他们XXOO了。
2. XXOO。
有点小长，为了不影响阅读先隐藏了~。
好吧，这个地方写的时候是难到我了。
简单说一下。
我们获取出来的种群的程序存储是这样的。
1346251
1245631
，然后呢我们随机选取一个位子。
比如说是位子3.
下标: 0 1 2 3 4 5 6
1 3 4 6 2 5 1
1 2 4 5 6 3 1
然后选取一个作为基础。
我就选第一个作为基础了。
1346
然后迭代第二个。
第二个中的第一个数 1存在 1346中，
第二个中的第二个数 2不存在，那么变成13462
第二个中的第三个数 4存在于13462中，
...
以此类推，直到迭代完或者总数够了。
那么这样就会生成一个新的后代。
就有了一个新的基础。
下面是详细的文章。
 介绍了很多种姿势。
遗传算法心得
一般来说，到这里就结束了。
XXOO嘛，不断进化进化进化(XXOO)就会得到最优或者近似最优解。
但是我们的区间小，而且并不能保证生成的后代基因比上一代要好。(因为我们是随机搞得。)
我们的结果很有可能在一个小区间里循环，基因全部都是一样的。
当然你可以计算每段的距离来进行精准的XXOO保证后代一定比父辈牛。
大自然呢也是随机的，但是依然进化出了人类，并不断进化着。
这就引入新的机制——变异。
3. 神童or脑残
并没有歧视意味，见谅。
我们可以在进化的途中随机让某个小子变异。
但是不宜过多。
- def mutation(all_population):
- # 某个人基因变异。
- # 使用逆转法进行变异。
- # 单个变异。
- length = len(all_population[0])
- who = random.randint(0, len(all_population)-1)
- while 1:
- where_1 = random.randint(0, length-1)
- where_2 = random.randint(0, length-1)
- if where_1 != where_2:
- break
- a = all_population[who][where_1]
- b = all_population[who][where_2]
- all_population[who][where_1], all_population[who][where_2]= b, a
- return all_population
上面的文章里也有详细介绍。
变异就是让进化多了种可能性。
光变异是不能满足伟大的大自然的。
伟大的大自然不可能只有单体技能，
自然有AOE。
4. 灾变。
呃，这个没有写代码。
有兴趣的同学仔细看看文章吧~。
遗传算法的局部搜索能力较强，但是很容易陷入局部极值。引用网上的一段原话: “那么如何解决遗传算法容易陷入局部极值的问题呢？让我们来看看大自然提供的方案。六千五百万年以前，恐龙和灵长类动物并存，恐龙在地球上占绝对统 治地位，如果恐龙没有灭绝灵长类动物是绝没有可能统治地球的。正是恐龙的灭绝才使灵长类动物有了充分进化的余地，事实上地球至少经历了5次物种大灭绝，每 次物种灭绝都给更加高级的生物提供了充分进化的余地。所以要跳出局部极值就必须杀死当前所有的优秀个体，从而让远离当前极值的点有充分的进化余地。这就是灾变的思想。” 灾变就是杀掉最优秀的个体，这样才可能产生更优秀的物种。那何时进行灾变，灾变次数又如何设定？ 何时进行灾变，可以采用灾变倒计数的方式。如果n代还没有出现比之前更优秀的个体时，可以发生灾变。灾变次数可以这样来确定，如果若干次灾变后产生的个体的适应度与没灾变前的一样，可停止灾变。
5. 全部代码。
方便阅读已隐藏。
下面的一样只是打包了~。不想回复的同学可以直接下载。
 不感兴趣的同学可以和我唠唠嗑呦~。
TspAndGa.zip
(3.48 KB, 下载次数: 136)
|
评分
-
查看全部评分
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2016-9-12 19:55:56
置顶卡
千斤顶
显身卡
发表于 2016-9-12 21:57:50
发表于 2016-9-12 21:58:03
