怎么用Python遗传算法处理TSP问题

本文小编为大家详细介绍“怎么用Python遗传算法处理TSP问题”，内容详细，步骤清晰，细节处理妥当，希望这篇“怎么用Python遗传算法处理TSP问题”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。那么在开始之前的话，咱们来仔细描述一下这个TSP问题。这个打过数模，或者接触过智能优化或者机器学习方面的朋友应该都知道，当然为了本文的受众普适性，咱们在这里尽可能去完善一点，说清楚，这样便于咱们去实际解决问题。那么这个问题的其实简单，是这样子的：在我们的N维平面是，咱们今天的话是拿这个二维平面来的，在这个平面上有很多个城市，城市之间是彼此联通的，我们现在要找出一条最短的路径可以将全部城市都走完。例如我们有城市A，B，C，D，E。现在知道了城市间的坐标，也就是相当于知道了城市之间的距离，那么现在找到一个顺序，能够使得走完A，B，C，D，E所有城市的路径和最短。比如计算完之后可能是B－－＞Ａ－－＞Ｃ－－＞Ｅ－－＞Ｄ。换一句话说找到这个顺序。首先要解决这个问题的话，其实方案有很多，说变白了，咱们就是要找到一个顺序，能够让路径之和最小，那么最容易想到的自然就是枚举，例如让Ａ先走然后看距离Ａ最近的假设是Ｂ，那么就走Ｂ，然后从Ｂ走。当然这个是局部贪心策略，很容易走到局部最优，那么这个时候我们可以考虑ＤＰ，也就是说依然假设从Ａ开始，然后确保2个城市最短，3个城市最短，4个5个。最后在假设从B开始同理。或者直接 枚举全部情况，计算距离。但是无论如何，随着城市数量的上升，他们的复杂度都会增加，所以这个时候我们就要想办法让计算能不能发挥一下咱们人类的专长了。我称之为“瞎蒙”。现在我们来聊聊这个智能算法，以及为什么要用着玩意，刚刚咱们说了前面的方案对于大量的数据计算量会很大，也不见得编写简单。那么这个时候，首先单单对于TSP问题来说，我们要的就是一个序列，一个不会重复的序列。那么这个时候，有什么一个更加简便的方案，而且在数据足够大的情况下，我们也不见得需要一个完全精准，完全最小的解，只要接近就好。那么这个时候，采用传统的那些算法的话，一就是一，他只会按照我们的规则去计算，而且我们也确实不知道标准答案是什么，对传统算法也比较难去设定一个阈值去停止运算。但是对我们人来说，有一种东西叫做“运气”，有的人运气贼好，可能一发入魂，一下子就懵出了答案。那么我们的智能算法其实就是有点类似于“蒙”。但是人家蒙是讲究技巧的，例如经验告诉我们，三长一短选最短，通过这个技巧可以去蒙一下答案，或者找男盆友的时候像博主一样帅气的男孩纸，只要一张40系（30也可以）显卡就可以轻松带走一样。蒙是要技巧的，我们管这个叫做策略。那么我们刚刚说的这个技巧，这个蒙的技巧。在智能算法里面，这个蒙，就是我们的一种策略。我们要怎么去蒙才能够让我们的解更加合理。那么这个时候，就开始百花齐放了，这里我就免费云主机域名不念经了，我们拿最金典的两个算法为例子，一个是遗传算法，一个是粒子群算法（PSO）。为例子，他们就是采用了一种策略去蒙，例如遗传算法，通过模拟物竞天择，一开始先随机蒙出一堆解，一堆序列，然后按照咱们的这个物竞天择的策略出筛选这些解，然后通过这些解再去蒙出新的更好的解。如此往复，之后蒙出不错的解。粒子群也是类似的，这些部分咱们用的时候再详细说明。现在咱们已经知道了这个策略，那么算法是啥，其实就是实现这些策略的步骤啊，就是咱们的代码，咱们的循环，数据结构。我们要去实现刚刚说的例如物竞天择，例如咱们TSP，如何随机生成一堆解。ok,到这里咱们已经说完了，基本的一些概念，那么这个时候的话，咱们来看看咱们如何表示这个TSP的问题，这个其实很简单，咱们这边的话就简单的准备一个测试数据，我们这里假设有14个城市，那么我们的这些城市的数据如下：我们后面都用这组数据进行测试，现在在上面已经有了14个城市。那么接下来我们开始我们的解决方案ok,那么我们来说一说咱们的这个遗传算法是怎么一回事，之后的话，咱们用这个来解决这个TSP问题。那么现在的话，我们来看看我们的遗传算法是怎么蒙的。遗传算法其实是在用计算机模拟我们的物种进化。其实更加通俗的说法是筛选，这个就和我们袁老爷爷种植水稻一样。有些个体发育良好，有些个体发育不好，那么我就先筛选出发育好的，然后让他们去繁衍后代，然后再筛选，最后得到高产水稻。其实也和我们社会一样，不努力就木有女朋友就不能保留自己的基因，然后剩下的人就是那些优秀的人和富二代的基因，这就是现实呀。所以得好好学习，天天向上！那么回到主题，我们的遗传算法就是在模拟这一个过程，模拟一个物竞天择的过程。所以在我们的算法里面也是分为几大块首先我们的种群需要先繁殖。这样才能不断产生优良基于，那么对应我们的算法，假设我们需要求取Y = np.sin(10 * x) * x + np.cos(2 * x) * x的最大值（在一个范围内）那么我们的个体就是一组（X1）的解。好的个体就会被保留，不好的就会被pass，选择标准就是我们的函数 Y 。那么问题来了如何模拟这个过程？我们都知道在繁殖后代的时候我们是通过DNA来保留我们的基因信息，在这个过程当中，父母的DNA交互，并且在这个过程当中会产生变异，这样一来，父母双方的优秀基于会被保存，并且产生的变异有可能诞生更加优秀的后代。所以接下来我们需要模拟我们的ＤＮＡ，进行交叉和变异。这个交叉过程和我们的生物其实很像，当然我们在我们的计算机里面对于数字我们可以将其转化为二进制，当做我们的DNA交叉的方式有很多，我们这边选择这一个，进行交叉。那这个在我们这里就更加简单了我们只需要在交叉之后，再随机选择几个位置进行改变值就可以了。当然变异的概率是很小的，并且是随机的，这一点要注意。并且由于变异是随机的，所以不排除生成比原来还更加糟糕的个体。最后我们按照一定的规则去筛选这个些个体就可以了，然后淘汰原来的个体。那么在我们的计算机里面是使用了两个东西，首先我们要把原来二进制的玩意，给转化为我们原来的十进制然后带入我们的函数运算，然后保存起来，之后再每一轮统一筛选一下就好了。这个咋说呢，说好听点叫逆转，难听点就算，对于一些新的生成的不好的解，我们是要舍弃的。那么这部分用代码描述的话就是这样的：这个代码是以前写的，逆转没有写上（下面的有）ok,刚刚的例子是拿的解方程，也就是说是一个连续问题吧，当然那个连续处理的话并不是很好，只是一个演示。那么我们这个的话其实类似的。首先我们的ＤＮＡ，是城市的路径，也就是A-B-C-D等等，当然我们用下标表示城市。首先我们确定了使用城市的序号作为我们的个体DNA，例如咱们种群大小为100，有ＡＢＣＤ四个城市，那么他就是这样的，我们先随机生成种群，长这个样：1 2 3 4
2 3 4 5
3 2 1 4
…那个1,2,3,4是ABCD的序号。这里面的话，值得一提的就是，由于暂定城市需要是不能重复的，且必须是完整的，所以如果像刚刚那样进行交叉或者变异的话，那么实际上会出点问题，我们不允许出现重复，且必须完整，对于我们的DNA，也就是咱们瞎蒙的个体。由于咱们每一步在代码里面都有注释，所以的话咱们在这里就不再进行复述了。ok,我们来看看运行的结果：读到这里，这篇“怎么用Python遗传算法处理TSP问题”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注百云主机行业资讯频道。

相关推荐: javascript是不是基于java的

本文小编为大家详细介绍“javascript是不是基于java的”，内容详细，步骤清晰，细节处理妥当，希望这篇“javascript是不是基于java的”文章能帮助大家解决疑惑，免费云主机域名下面跟着小编的思路慢慢深入，一起来学习新知识吧。 javascrip…