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

2024-08-28 14:52

本文主要是介绍遗传算法与深度学习实战(8)——使用遗传算法解决旅行商问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

    • 0. 前言
    • 1. 旅行商问题
    • 2. NP 问题
    • 3. 构建 TSP 求解器
    • 小结
    • 系列链接

0. 前言

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

1. 旅行商问题

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

TSP 问题

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

2. NP 问题

在数学中,可以根据解决问题所需的时间或算力的多少,将算法进行分类。NP 问题中,N 代表解决问题所需的元素数量,P 表示解决问题所需的时间。如果问题可以在线性时间内解决,我们将其归类为 NP 简单 (NP-easy) 问题——即 N×P 以线性速率增加。相反,NP 难 (NP-hard) 问题定义为无法在线性时间内解决的问题,而其需要指数级时间。NP 难问题解决方案的复杂性为 N 2 × P N^2×P N2×P 或更高指数级,随着元素数量的增加,问题的复杂性呈指数级增长。
由于旅行商问题 (Traveling Salesman Problem, TSP) 问题是 NP 难问题,我们尚未找到能够以线性时间解决该问题的数学解。相反,许多用于解决 TSP 的方法都是估计方法,这些经过精心调整的方法已被成功应用于具有成千上万个点的问题上。
使用大 O O O 符号法,我们可以将 TSP 问题的时间复杂度表示为 O ( n 2 2 n ) O(n^22^n) O(n22n)。对于每个新的目标点,我们需要重新计算与之对应的其余各点,计算 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 中传递 01 的值来绘制目的地点。然后,使用 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() 函数的输出结果如下所示:

TSP 问题

(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 问题的解决方案如下所示。评估解决方案是否正确的一个简单方法是观察所有连接点是否相交,如果并不相交可以说该解决方案正确,基本上形成一个循环的圈。

TSP 解决方案

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

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

小结

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

系列链接

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

这篇关于遗传算法与深度学习实战(8)——使用遗传算法解决旅行商问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1115085

相关文章

vue使用docxtemplater导出word

《vue使用docxtemplater导出word》docxtemplater是一种邮件合并工具,以编程方式使用并处理条件、循环,并且可以扩展以插入任何内容,下面我们来看看如何使用docxtempl... 目录docxtemplatervue使用docxtemplater导出word安装常用语法 封装导出方

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

Android中Dialog的使用详解

《Android中Dialog的使用详解》Dialog(对话框)是Android中常用的UI组件,用于临时显示重要信息或获取用户输入,本文给大家介绍Android中Dialog的使用,感兴趣的朋友一起... 目录android中Dialog的使用详解1. 基本Dialog类型1.1 AlertDialog(