欧洲旅行优化:遗传算法和Google Maps API解决旅行商问题

Optimizing European travel Genetic algorithms and Google Maps API solve the Traveling Salesman Problem.

来源:unsplash.com

还记得看完《欧洲任我行》等电影后的感觉吗?角色们在风景如画的欧洲城市中展开了一生中的冒险之旅,令人着迷。然而,现实很快提醒我们:策划一次跨越多个目的地的旅程并不是一件简单的任务。但是,有了编程技术和对遗传算法的理解,我着手开发了一个解决方案。想象一下能够精确优化跨越数十个地点的复杂路线。这就是数据科学与冒险规划艺术相交的地方。在本文中,我揭示了一种优雅解决复杂旅行推销员问题(TSP)的算法脚本,承诺帮助旅行规划并提高我们对数据科学优化的理解。

阅读本文将使您清楚地了解Python、Google地图API和遗传算法之间的协同作用,为非平凡任务提供基于数据驱动的解决方案。

了解旅行推销员问题

踏上旅程往往会引发冒险的感觉,但是当我们考虑旅行的复杂性时,兴奋感可能会伴随着物流挑战。数十年来,旅行推销员问题(TSP)一直引起数学家、计算机科学家和物流专家的关注。TSP的核心是一个看似简单的问题:给定一个城市列表和它们之间的距离,有哪条最短的路径可以让销售员每个城市只访问一次并返回起点?虽然问题的陈述很简洁,但其影响远远超出了表面的简单。

在优化和物流领域,TSP不仅仅是一个理论上的好奇心;它具有巨大的实际意义。考虑到减少行驶距离直接转化为降低燃料成本和更快的服务的快递服务。

在这个看似简单的问题陈述下隐藏着深层次的复杂性。TSP的组合性质源于城市数量的指数级增长,随着城市数量的增加,可能的解决方案的数量迅速超过了任何计算可行性,使得对于更大的实例来说传统的暴力方法变得不可行。可能的路径数量等于

其中n表示城市数量,这是一个阶乘爆炸,很快变得不可承受。仅仅有50个城市,可能的路径数量就等于3*10⁶²,这大约是银河系中的原子数量。

TSP是数学、计算机科学和现实世界物流挑战之间有趣交叉的典型例子。随着城市数量的增加,揭示最短路径要求创新策略,超越传统的计算方法。

对TSP的高效解决方案的追求推动研究人员探索各种方法。其中之一是遗传算法,一类受自然选择过程启发的优化技术。遗传算法擅长在复杂解空间中导航,使其非常适合解决TSP等问题,其中随着城市数量的增加,暴力方法很快变得不可行。

本文的目的是探索这两个领域的结合——旅行推销员问题和遗传算法。具体而言,我们深入探讨一个实际应用:一个旨在利用遗传算法解决TSP的Python脚本。我们的探索将突出显示这种算法融合在旅行规划、物流和各行各业的优化挑战中的潜力。当我们理解基于遗传算法的解决方案的内部工作原理时,数据科学和算法创新的世界将相交,为我们提供新的见解和通过最复杂的路线的高效路径。

遗传算法简介

在其核心,遗传算法(GA)是一种受自然选择和进化过程启发的启发式搜索技术。

遗传算法的灵感可以追溯到查尔斯·达尔文的进化理论。遗传算法通过迭代演化潜在解的种群来模拟自然选择的过程。在这个数字熔炉中,展现有利特征的解将存活并繁殖,将它们的“基因”传递给下一代。这种世代演化将继续,直到达到最优或接近最优的解。

遗传算法具有四个基本组成部分:

  1. 选择:与自然界类似,选择机制识别和支持适应度更高的解决方案,反映了“适者生存”的概念。
  2. 交叉:解决方案或“染色体”通过交换遗传材料创建具有父母特征混合的后代。
  3. 突变:为了引入多样性并防止过早收敛到次优解,遗传算法引入突变操作。该操作随机改变解决方案的某些元素,类似于自然界中的基因突变。
  4. 适应度评估:确定每个解决方案的适应度,量化其在手头任务中的表现。适应度函数通过为优秀的解决方案分配更高的繁殖概率来指导选择过程。

遗传算法在解决优化问题方面表现出了非凡的多功能性。它们以非线性、多维的方式探索解决方案空间的能力使其非常适合处理复杂的现实世界挑战。无论是优化复杂的工程设计、微调神经网络参数,还是像我们将要看到的那样解决TSP问题,遗传算法在传统算法失败的场景中表现出色。

将遗传算法应用于旅行商问题

现在,让我们深入探讨将遗传算法(GAs)应用于解决旅行商问题(TSP)。

从本质上讲,GAs通过将每个潜在路线视为种群中的一个个体来处理TSP。这个路线种群在不同的世代中逐渐演化,每条路线代表了旅行商的独特行程。

为了促进这种遗传演化,我们将每条路线表示为一个染色体,即定义访问顺序的城市序列。例如:

Image by author.

基本任务是发现最优染色体,即最小化总旅行距离的序列。每个染色体的适应度通过计算其按指定顺序访问城市时所覆盖的总距离来量化。较短的距离对应较高的适应度,反映了寻找最短路径的目标。

Python实现

现在,让我们按照高级步骤逐步实现用于解决TSP的Python脚本。完整的代码可以在我的GitHub存储库中找到。

获取数据

第一步是选择目的地。对于本例,我选择了欧洲最受欢迎的50个城市。一旦确定了目的地,我需要获取每对城市之间的旅行距离和时间。对于这种查询,Google Maps API是当今最先进的解决方案。在此处设置一个帐户后,您可以请求您的个人API密钥,用于身份验证。

向Google Maps API发送请求的方式如下:

初始化

该过程开始时,会生成一组初始路线。这些路线通常是随机生成的,或通过启发式方法生成的。

适应度评估和选择

在每个步骤中,在生成后代并对某些路线进行突变之后,计算每条路线的总距离以评估其适应度。这一步确保算法专注于选择最短路径。

按照自然选择的原则,根据适应度选择路线进行繁殖。总距离较短的路线(更接近最优解)更有可能被选中,允许具有有利特征的个体更有可能繁殖。

交叉和突变

对于这个特定问题的特殊特征,不执行经典的交叉操作。我选择了两种突变:

  1. 单点突变:为了保持多样性并引入新的解决方案,算法对选定的路线进行小的随机变化。这模拟了基因突变,引入了轻微的变化。
  2. “交叉突变”:通过将其基因组的随机子集切片并附加到另一个位置来突变一个解决方案。回想一下生物学术语,这是一种无性繁殖。

迭代

上述步骤会重复执行一定数量的代数,使得种群随着时间的推移逐渐进化。每次迭代都会使算法更接近最优或接近最优解。

算法会一直迭代,直到达到终止条件。在这种情况下,终止条件是达到预定的代数数量。

结果和结论

在这次探索中,我使用了一个包含200个个体的遗传算法,并运行了1000代,以解决包含50个城市的TSP问题。从初始代到最终结果的过程展示了遗传算法的显著效率。

首先,在第0代中,第一个解决方案出现,其适应度为70,755公里:

('保加利亚索非亚', '法国尼斯', ..., '意大利那不勒斯', '卢森堡城, 卢森堡')

正如预期的那样,这个初始解决方案代表了城市的随机排列,标志着算法的起点。然而,随着遗传算法穿越连续的代数,我们观察到解决方案质量的显著改善。

经过1000代,遗传算法找到了其路径。终点是一个适应度为21,345公里的解决方案,与初始的随机解决方案相比,旅行距离显著减少。这近49,410公里的显著改进突显了遗传算法在优化类似TSP这样复杂路线中的效果。

我进行了4次试验,改变了种群大小。总体而言,较大的种群获得了更好的结果,但计算时间显然更长。我们可以看到,在每次试验中,适应度值在前几次迭代中迅速下降,然后稳定在一个平稳值上。这是收敛算法的典型行为。

作者提供的图片。

虽然TSP问题仍然是一个NP难题,也就是说,对于较大的实例来说,找到绝对最优解可能在计算上具有挑战性,但遗传算法接近最优解的能力在实际应用中证明是非常宝贵的。这一成就为更高效的旅行规划、精简的物流和不同行业的优化提供了更多可能性。这个实验突出了数据科学和创新算法之间的共生关系。它强调了受自然选择机制启发的进化计算如何优雅地解决现实世界中复杂的问题。

参考文献

[1]: Tri-Objective Optimal PMU Placement Including Accurate State Estimation: The Case of Distribution Systems[2]: Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem[3]: Probabilistic model with evolutionary optimization for cognitive diagnosis[4]: Simulated Binary Crossover for Continuous Search Space[5]: A new mutation operator for real coded genetic algorithms[6]: Computing the optimal road trip across the U.S.