遗传算法与深度学习实战（8）——使用遗传算法解决旅行商问题

0. 前言

旅行商问题 (Traveling Salesman Problem, TSP) 是一个经典的优化问题，其目标是找到一条最短的路径，使得旅行商可以访问一系列给定的城市并且每个城市只访问一次，最终回到出发地点。在本节中，我们将学习如何使用遗传算法解决 TSP 问题。

1. 旅行商问题

旅行商问题 (Traveling Salesman Problem, TSP)，又称旅行推销员问题、货郎担问题，是一个经典的数学优化问题。指一个旅行商从一个出发点出发，必须恰好访问一次每个给定的城市，然后回到出发点，使得总的旅行距离最短。这是一个经典的组合优化问题，属于 NP-hard 问题，意味着随着城市数量的增加，寻找最优解的时间复杂度呈指数级增长。
TSP 可以形式化地描述为：给定一个带权完全图 $G=(V,E)$，其中 $V$ 是城市的集合，$E$ 是连接这些城市的边集合，每条边 $e\in E$ 有一个正的权重或距离 $d(e)$，目标是找到一个访问城市序列 $(v_1,v_2,\dots ,v_n)$，其中 $v_1$ 是出发城市，$v_n=v_1$ 是回到出发城市的城市序列，使得总的旅行距离最小。
进化算法 (Evolutionary Algorithm, EA) 和遗传算法 (Genetic Algorithms, GA) 在优化难解的数学问题上取得了巨大的成功，包括经典的旅行商问题，推销员需要亲自穿越整个国家销售商品，问题的目标是解决推销员所需采取的路线，以确保他们不会两次访问相同的位置，并优化他们的旅程长度。下图展示了TSP 在一个 100x100 单位的地图网格上的示例，在图中，推销员的路线已经得到优化，以便可以每个城市只访问一次，然后在旅程结束时回到出发点。

TSP 在数学中被认为是 NP-hard 问题，这意味着它在计算上无法在线性时间内解决，解决该问题的算力需求随着位置数量的增加而呈指数级增长。在上图中，推销员需要前往 22 个目的地，包括出发点。
旅行商问题不仅在学术研究中具有重要性，还在实际应用中有许多现实生活中的应用，如交通路径规划、电路板设计、基因组测序等领域。

2. NP 问题

在数学中，可以根据解决问题所需的时间或算力的多少，将算法进行分类。NP 问题中，N 代表解决问题所需的元素数量，P 表示解决问题所需的时间。如果问题可以在线性时间内解决，我们将其归类为 NP 简单 (NP-easy) 问题——即 N×P 以线性速率增加。相反，NP 难 (NP-hard) 问题定义为无法在线性时间内解决的问题，而其需要指数级时间。NP 难问题解决方案的复杂性为 $N^2\times P$ 或更高指数级，随着元素数量的增加，问题的复杂性呈指数级增长。
由于旅行商问题 (Traveling Salesman Problem, TSP) 问题是 NP 难问题，我们尚未找到能够以线性时间解决该问题的数学解。相反，许多用于解决 TSP 的方法都是估计方法，这些经过精心调整的方法已被成功应用于具有成千上万个点的问题上。
使用大 $O$ 符号法，我们可以将 TSP 问题的时间复杂度表示为 $O(n^2{2}^n)$。对于每个新的目标点，我们需要重新计算与之对应的其余各点，计算 22 个目的地最多需要 20 亿次计算，而计算 23 个目的地则需要 45 亿次计算。
以 22 个目的地所需计算量为例，如果每次计算需要 1 毫秒来完成，那么 20 亿次计算需要 23 天才能完成。随着额外目的地数量的增加，这个数字会呈指数级增长，使得常规的编程解决方案不实用。相反，EA/GA 等方法提供了解决这种复杂问题的有效方案。

3. 构建 TSP 求解器

接下来，使用 DEAP 构建遗传算法 (Genetic Algorithms, GA) 解决 TSP 问题的解决方案，在本节中，假设推销员可以走任意距离去到所有的目的地(除此之外，也可以将推销员限制在一定的行驶距离或长度内)。

(1) 首先，导入所需库：

import array
import random
import numpy as npfrom deap import algorithms
from deap import base
from deap import creator
from deap import toolsimport matplotlib.pyplot as plt
from matplotlib.pyplot import figure

(2) 可视化初始时推销员的路径。定义保存目的地点的变量 map，用于保存旅行推销员路径的所有位置。接下来，使用 plt.scatter() 函数通过从 map 中传递 0 和 1 的值来绘制目的地点。然后，使用 plt.gca() 获取当前绘图并添加绘图边界限制，以便我们可以清楚地看到所有目的地点：

min_bounds = 0
max_bounds = 100
destinations = 22figure(num=None, figsize=(10, 10), dpi=80, facecolor='w', edgecolor='k')
map = np.random.randint(min_bounds,max_bounds, size=(destinations,2))plt.scatter(map[:,0], map[:,1])
axes = plt.gca()
axes.set_xlim([min_bounds,max_bounds])
axes.set_ylim([min_bounds,max_bounds])
plt.grid()

(3) 当我们应用 GA 时，种群中的每个个体都代表目的地点的索引列表。该列表也表示个体的基因序列，其中每个索引都是一个基因。由于 map 代表了一组随机点，我们可以假设初始个体只是按顺序访问这些点，可以使用以下代码根据个体构建一个简单的路径：

def linear_path(map):path = []for i,pt in enumerate(map):    path.append(i)return pathpath = linear_path(map)

(4) 接下来，可视化上述路径，以便可以观察随着演变的进行，路径的变化情况。draw_path 函数通过传递从 linear_path() 函数构造的路径来实现路径的可视化。在函数内部，代码遍历路径中的索引，并使用 plt.arrow() 函数传递点对。在遍历路径列表中的索引之后，绘制一条连接最终一个点和起点的路径：

def draw_path(path):figure(num=None, figsize=(10, 10), dpi=80, facecolor='w', edgecolor='k')prev_pt = None plt.scatter(map[:,0], map[:,1]) for i in path:    pt = map[i]    if prev_pt is not None:plt.arrow(pt[0],pt[1], prev_pt[0]-pt[0], prev_pt[1]-pt[1])else:start_pt = pt    prev_pt = ptplt.arrow(pt[0],pt[1], start_pt[0]-pt[0], start_pt[1]-pt[1])axes = plt.gca()axes.set_xlim([min_bounds,max_bounds])axes.set_ylim([min_bounds,max_bounds])plt.grid()plt.show()draw_path(path)

在起始路径上调用 draw_path() 函数的输出结果如下所示：

(5) 接下来，实现 evaluate_path() 函数，用于确定每个路径的适应度。函数循环遍历路径中的点索引并计算 L1 或欧几里得距离。然后将所有这些距离加起来得到总路径长度，作为个体的适应度：

import math
def evaluate_path(path):prev_pt = Nonedistance = 0for i in path:    pt = map[i]     if prev_pt is not None:distance += math.sqrt((prev_pt[0]-pt[0]) ** 2 + (prev_pt[1]-pt[1]) ** 2)else:start_pt = ptprev_pt = ptdistance += math.sqrt((start_pt[0]-pt[0]) ** 2 + (start_pt[1]-pt[1]) ** 2)return distance,evaluate_path(path)
# (1162.969879660959,)

(6) 接下来，设置 toolbox 以构建个体。构建基因序列，其长度等于目的地数量，以保存目的地点索引，每个个体都代表了目的地点的不同路径索引：

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", array.array, typecode='i', fitness=creator.FitnessMin)toolbox = base.Toolbox()
# Attribute generator
toolbox.register("indices", random.sample, range(destinations), destinations)
# Structure initializers
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)toolbox.register("mate", tools.cxPartialyMatched)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", evaluate_path)

(7) 执行演化的过程，在本节中，我们不提供提前停止参数。这是因为计算最小路径距离比计算距离的算法更费时，可以使用演化过程的输出来确认演化是否已经得到了合适的解决方案：

def eaSimple(population, toolbox, cxpb, mutpb, ngen, stats=None, halloffame=None):  logbook = tools.Logbook()logbook.header = ['gen', 'nevals'] + (stats.fields if stats else [])# Evaluate the individuals with an invalid fitnessinvalid_ind = [ind for ind in population if not ind.fitness.valid]fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)for ind, fit in zip(invalid_ind, fitnesses):ind.fitness.values = fitif halloffame is not None:halloffame.update(population)record = stats.compile(population) if stats else {}logbook.record(gen=0, nevals=len(invalid_ind), **record)    print(logbook.stream)done = False# Begin the generational processfor gen in range(1, ngen + 1):if done: return# Select the next generation individualsoffspring = toolbox.select(population, len(population))offspring = [toolbox.clone(ind) for ind in offspring]# Apply crossover and mutation on the offspringfor i in range(1, len(offspring), 2):if random.random() < cxpb:offspring[i - 1], offspring[i] = toolbox.mate(offspring[i - 1],offspring[i])del offspring[i - 1].fitness.values, offspring[i].fitness.valuesfor i in range(len(offspring)):if random.random() < mutpb:offspring[i], = toolbox.mutate(offspring[i])del offspring[i].fitness.values# Evaluate the individuals with an invalid fitnessinvalid_ind = [ind for ind in offspring if not ind.fitness.valid]fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)for ind, fit in zip(invalid_ind, fitnesses):ind.fitness.values = fit  # Update the hall of fame with the generated individualsif halloffame is not None:halloffame.update(offspring)             draw_path(halloffame[0])           # Replace the current population by the offspringpopulation[:] = offspring# Append the current generation statistics to the logbookrecord = stats.compile(population) if stats else {}logbook.record(gen=gen, nevals=len(invalid_ind), **record)print(logbook.stream)pop = toolbox.population(n=300)hof = tools.HallOfFame(1)
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("avg", np.mean)
stats.register("std", np.std)
stats.register("min", np.min)
stats.register("max", np.max)eaSimple(pop, toolbox, 0.7, 0.3, 200, stats=stats, halloffame=hof)

包含 22 个目的地的 TSP 问题的解决方案如下所示。评估解决方案是否正确的一个简单方法是观察所有连接点是否相交，如果并不相交可以说该解决方案正确，基本上形成一个循环的圈。

在大多数情况下，对于包含 22 个目的地的 TSP 问题，可以在 200 代以内得到解决方案。如果无法在 200 代内解决问题，可以尝试减少目的地点数或增加世代数。尝试将目的地数量增加到 23 或 25，然后再次运行代码。需要注意的是，每增加一个目的地点问题的难度都会呈指数级增长，如果没有得到正确的解决方案，可以尝试需要增加代数或种群中的个体数。可以通过完成以下问题进一步理解使用 DEAP 库实现遗传算法的流程：

• 增加或减少推销员需要访问的目的地数量，然后在每次更改后重新运行，观察运行结果
• 调整种群数、交叉和变异率，然后重新运行代码

小结

使用遗传算法 (Genetic Algorithm, GA) 解决旅行商问题 (Traveling Salesman Problem, TSP) 是一种常见且有效的方法。遗传算法模拟了生物进化的过程，通过交叉、变异和选择等操作来逐步优化问题的解。遗传算法作为一种启发式算法，虽然不能保证找到全局最优解，但通常能在合理时间内找到很好的近似解，尤其适合解决大规模的 TSP 问题。

系列链接

遗传算法与深度学习实战（1）——进化深度学习
遗传算法与深度学习实战（2）——生命模拟及其应用
遗传算法与深度学习实战（3）——生命模拟与进化论
遗传算法与深度学习实战（4）——遗传算法详解与实现
遗传算法与深度学习实战（5）——遗传算法框架DEAP
遗传算法与深度学习实战（6）——DEAP框架初体验
遗传算法与深度学习实战（7）——使用遗传算法解决N皇后问题