Python3 趣味系列题11 ------旅行商问题

2019-04-17 本文已影响27人 AiFany

34.png

一、问题描述
旅行商问题(Traveling Salesman Problem)，即TSP，又称为旅行推销员问题、货郎担问题，是数学领域中著名的问题之一。说的是一个旅行商要去往N个城市，每个城市只能去一次，最后还要回到开始出发的城市。选择的路径的路程必须是所有路径中值最小的。本文以全国34城市为例，利用遗传算法(Genetic Algorithm)获得最终的方案。其中城市之间的距离为城市经纬度之间的地球表面的距离。

image

二、解题思路

TSP，已经被证明为NP完全问题。当N较大时，无法通过枚举的方法来获得最优解。此时就可以通过优化求解的算法来获得最优解。遗传算法就是一种通过模拟自然进化过程来搜索最优解的方法。

通俗来讲，该算法就是首先随机给出一些解的集合(可看作某种生物的初始种群)，在选择比较接近最优解的解(物竞天择，适者生存)，然后集合中解与解之间生成新的解(父辈之间的基因交叉，形成新的个体)，单个解也可以变成新的解(*个体产生了变异)，当集合中的解都很相似时(种群中的生物个体之间差异性不大)，就停止搜索。

遗传算法的步骤(以本题为例)：

编码：对问题的解进行编码，也就是如何表示问题的解，一个生物个体；在本例中问题的解就是路径。首先对城市进行数字编码，例如上海对应0，乌鲁木齐对应1，兰州对应2。因此0120，1021，2102均可是问题的解，种群中的个体。其中0，1，2可看作个体中的基因。不同的问题，可设置不同的编码方式。
初始化种群：种群中的每个个体都是该问题的一个解；【0120，1021，2102】这个种群，就可看作初始的种群。其中种群的个数可以自定义。
适应度：评判解的好坏的函数，也就是评判某个生物个体优劣的函数。适应度函数的设置一定要和最优解的判断是一致的。例如本例中适应度就是路径的长度，适应度小的就是比较好的解，比较优秀的个体。
选择：计算种群中每个个体的适应度，再根据不同的选择策略，形成新的种群；选择可以不是绝对的优胜劣汰，因为这样做可能会丧失种群内个体的多样性。一般可采用轮盘赌的方式选择，正如本例。
交叉：在种群中任意选取2个个体，作为父辈，进行交叉，从而形成新的个体；为了模拟生物进化，是否执行交叉，在什么位置执行交叉需要具有随机性。因此需要自定义交叉系数，如果随机数大于该系数则执行交叉。交叉的策略有很多，可以根据不同的问题自由设置。对于tsp问题，交叉算子是关键，因为既需要保证新生个体的多样性，又不能损坏优秀父辈的基因序列。本文采用了自定义的贪心交叉算子。
变异：个体的基因发生改变。和交叉算子也类似，需要自定义变异系数，来决定是否发生变异，以及变异的位置。变异的策略有很多，可以根据不同的问题自由设置。本例采用自身优化变异算子，也就是保证变异是往好的方向变异。
终止：种群经过选择，交叉，变异，形成新的下一代种群。当种群代数达到结束条件，或者种群中个体的适应度相差不大时，或者与上一代种群差别不大时就终止。