当前位置：首页 > news >正文

遗传算法求解旅行商问题分析

news 来源：原创 2025/6/27 5:21:32

一、问题分析

二、实现步骤

1）初始化种群

2）计算适应度

3）选择操作

4）交叉操作

5）变异操作

三、求解结果

四、总结

本文通过一个经典的旅行商问题，详细阐述在实际问题中如何运用遗传算法来进行分析求解。

一、问题分析

旅行商问题抽象为数学描述为，在平面内有有限个点，寻找一条路径穿过所有点，使路径长度最短。这个问题描述很简单，其实想要求解也很简单，因为途径所有点的路径数量是有限的，我们可以采用穷举法计算每一条路径的距离值，然后得到最短路径。但是采用穷举法的可行性不高，当我们要途径几十个点时，所有路径的总数是n!，这是一个非常庞大的数字，穷举已经不现实。因此我们选择采用其他智能优化算法来求解该问题。

那么应该如何选择计算方法呢？从上面的分析中我们已经知道，这是一个求解最优解问题，我们还知道这个问题的解是有限范围的，因此我们可以选择遗传算法来求解。下面我们将沿着遗传算法经典步骤，逐步详细说明如何用遗传算法来求解旅行商问题。

二、实现步骤

1）初始化种群

在初始化种群前，我们首先应考虑如何根据实际问题来设计个体和种群。在旅行商问题中，个体也就是解表征的是一组城市的排列结果，这个解不是单个的数值，而是一个组合。如果我们将每个城市依次编号，那么这个解就是一个N维的向量，向量元素为1到N之间的整数，其中N为城市总数。这个向量非常类似于一个群体中的个体，它已经由基因（城市编号）组成。因此我们可以直接使用这个向量作为群体的个体。初始化群体的代码如下。

我们定义种群个体数量为100，最大迭代代数为1000，初始种群的大小就是一个100×31（n_cities）的矩阵，n_cities表示个体的基因数，也是城市数量。第一个for循环完成了初始种群的赋值。

    % 遗传算法参数population_size = 100;    % 种群大小max_generations = 1000;    % 最大迭代次数crossover_rate = 0.8;      % 交叉概率mutation_rate = 0.1;       % 变异概率tournament_size = 5;       % 锦标赛选择大小elite_num = 2;             % 精英保留数目% 初始化种群population = zeros(population_size, n_cities);for i = 1:population_sizepopulation(i,:) = randperm(n_cities);end

2）计算适应度

在旅行商问题中，我们的目标值只有一个，就是路径的距离最短。在得到一个种群之后，我们可以直接计算出种群中每个个体，即每种路径的距离值。显然，距离值越小，适应度越大。因此，可以使用距离的导数来表征个体适应度的大小。具体实现代码如下。distances为已经计算好的两两城市之间的距离，此处直接提出相加即可。

        % 计算适应度fitness = zeros(population_size, 1);for i = 1:population_sizefitness(i) = 1 / calculate_total_distance(population(i,:), distances);end

% 计算路径总长度
function total_dist = calculate_total_distance(path, distances)n = length(path);total_dist = 0;for i = 1:n-1total_dist = total_dist + distances(path(i), path(i+1));endtotal_dist = total_dist + distances(path(end), path(1));
end

3）选择操作

此处采用锦标赛法选择需要继承的父代。该方法的思想是随机从种群中抽取部分个体，然后将这部分个体中适应度最高的个体传递给下一代。此处直接选择两个父代的个体，以便直接进行后续的交叉和变异操作。

% 锦标赛选择父代
parent1 = tournament_selection(population, fitness, tournament_size);
parent2 = tournament_selection(population, fitness, tournament_size);

% 锦标赛选择
function selected = tournament_selection(population, fitness, tournament_size)candidates = randperm(size(population,1), tournament_size);[~, idx] = max(fitness(candidates));selected = population(candidates(idx), :);
end

4）交叉操作

直接对选出的两个父代个体执行交叉操作。此处采用的交叉方法为顺序交叉法，其算法思想如下图所示。首先随机得到一个交叉区域，将个体P1中该区域的元素赋给新个体child1的对应区域位置，然后将P2以交叉区域后边界分为前后两段，并将前后两段互换位置得到一个新的片段，当然这个片段中删除了交叉区域中已经存在的元素，然后再将这个片段分别赋给child1的两端，不要覆盖交叉区域。这样就得到了交叉后的第一个新个体，然后交换P1和P2角色，执行上述操作，得到child2第二个个体，这样交叉操作就完成了。

% 交叉
if rand < crossover_rate[child1, child2] = ox_crossover(parent1, parent2);
elsechild1 = parent1;child2 = parent2;
end

% 顺序交叉 (OX)
function [child1, child2] = ox_crossover(parent1, parent2)n = length(parent1);points = sort(randperm(n, 2));start = points(1);end_ = points(2);% 子代1segment1 = parent1(start:end_);remaining = [];for i = [end_+1:n, 1:end_]city = parent2(i);if ~ismember(city, segment1)remaining = [remaining, city];endendchild1 = zeros(1, n);child1(start:end_) = segment1;child1([1:start-1, end_+1:n]) = remaining(1:n - (end_ - start + 1));  % 子代2segment2 = parent2(start:end_);remaining = [];for i = [end_+1:n, 1:end_]city = parent1(i);if ~ismember(city, segment2)remaining = [remaining, city];endendchild2 = zeros(1, n);child2(start:end_) = segment2;child2([1:start-1, end_+1:n]) = remaining(1:n - (end_ - start + 1));
end

5）变异操作

此处变异使用简单的交换操作，即交换个体中任意两个位置的元素。具体实现代码如下，首先随机产生一个随机数，判断是否满足可变异概率，然后在随机生成两个位置，将这两个位置的元素进行交换即可。

% 变异
child1 = mutate(child1, mutation_rate);
child2 = mutate(child2, mutation_rate);

% 变异（交换）
function mutated = mutate(individual, mutation_rate)mutated = individual;if rand < mutation_raten = length(individual);pos = randperm(n, 2);mutated(pos(1)) = individual(pos(2));mutated(pos(2)) = individual(pos(1));end
end

三、求解结果

程序完整实现代码在这里。最终求解结果如下图所示，得到的最优距离为15598。

四、总结

通过遗传算法求解旅行商问题流程可知，遗传算法的各项具体操作实现方法不是固定不变的，需要根据实际问题分析处理。即使使用本文提供的实际程序计算，每次迭代计算得到的结果也是不一样的。旅行商问题本质上是一个排列问题，且越接近最优解时，解相邻元素的排列顺序越接近。根据这一特性，我们在进行交叉、变异产生新个体时就需要设计合适的算法实现，减小对排列顺序大幅度调整的概率。因此，我们以非常小的概率控制变异发生，在交叉过程中使用分段交叉，尽量保持相邻元素的排列顺序。总之，在遗传算法产生新的子代群体过程中，我们应尽量避免产生大量与上一代差异较大的个体，当然也尽可能保留少量差异大的个体，使种群始终向最优解方向缓慢进化，避免算法不收敛或陷入局部最优解中。

遗传算法求解旅行商问题分析

目录一、问题分析二、实现步骤 1）初始化种群 2）计算适应度 3）选择操作 4）交叉操作 5）变异操作三、求解结果四、总结本文通过一个经典的旅行商问题，详细阐述在实际问题中如何运用遗传算法来进…...

编程日记 2025/6/27 5:21:32

【Hadoop】伪分布式安装

【Hadoop】伪分布式安装什么是 Hadoop 伪分布式安装？ Hadoop 伪分布式安装（Pseudo-Distributed Mode） 是一种在单台机器上模拟分布式集群环境的部署方式。它是介于本地模式（Local Mode） 和完全分布式模式&#xf…...

编程日记 2025/6/27 4:52:34

微服务概述

什么是微服务微服务是一个架构方案，属于分布式架构的一种。微服务提倡将模块以独立服务的方式独立管理，整个项目依靠多个小型的服务（单独进程）同时运作来支撑，单个服务只关注自己的业务实现并且有专业的团队进行开发。服务之间使用轻量的协议进行消息传送，并且对于单个…...

编程日记 2025/6/24 19:28:55

【网工】华为配置基础篇①

目录 ■华为设备登录配置 ■VLAN与VLANIF地址配置 ■DHCP配置命令 ■ACL访问控制列表配置 ■NAT地址转换配置 ■华为设备登录配置 <AR> system-view //进入系统模式 [AR]sysname Huawei //设备命名为Huawei [Huawei] telnet server enable //开启设备telnet功…...

编程日记 2025/6/25 1:22:09

React19源码系列之 Diff算法

在之前文章中root.render执行的过程，beginWork函数是渲染过程的核心，其针对不同类型的fiber进行不同的更新处理，在FunctionComponent（函数组件）中，会针对新旧fiber进行对比处理生成新fiber。因此此次就详细…...

编程日记 2025/6/25 5:10:16

华为2024年报：鸿蒙生态正在取得历史性突破

华为于2025年03月31日发布2024年年度报告。报告显示，华为经营结果符合预期，实现全球销售收入 8,621 亿元人民币，净利润 626 亿元人民币。2024 年研发投入达到 1,797 亿元人民币，约占全年收入的 20.8%，近十年累计投入的…...

编程日记 2025/6/24 11:09:33

如何在Firefox火狐浏览器里-安装梦精灵AI提示词管理工具

第一步：进入《梦精灵跨平台AI提示词管理工具》官网梦精灵跨平台AI提示词管理助手 - 官网梦精灵是一款专为AI用户打造的跨平台提示词管理插件，支持一键收藏、快速复制、智能分类等功能，适用于即梦、豆包、Kimi、DeepSeek等多个AI平台&…...

编程日记 2025/6/27 4:29:41

【鸿蒙开发】性能优化

语言层面的优化使用明确的数据类型，避免使用模糊的数据类型，例如ESObject。使用AOT模式 AOT就是提前编译，将字节码提前编译成机器码，这样可以充分优化，从而加快执行速度。未启用AOT时，一边运行一边进…...

编程日记 2025/6/25 6:05:56

Makefile与CMake

一、Makefile 核心内容 1. Makefile 基础结构与工作原理三要素： 目标（Target）：要生成的文件或执行的操作（如可执行文件、清理操作）。依赖（Dependency）：生成目标所需的…...

编程日记 2025/6/27 5:06:54

P8803 [蓝桥杯 2022 国 B] 费用报销

P8803 [蓝桥杯 2022 国 B] 费用报销 - 洛谷题目描述小明在出差结束后返回了公司所在的城市，在填写差旅报销申请时，粗心的小明发现自己弄丢了出差过程中的票据。为了弥补小明的损失，公司同意小明用别的票据进行报销，但是公司财…...

编程日记 2025/6/26 4:40:42

11 web 自动化之 DDT 数据驱动详解

文章目录一、DDT 数据驱动介绍二、实战一、DDT 数据驱动介绍数据驱动： 现在主流的设计模式之一（以数据驱动测试） 结合 unittest 框架如何实现数据驱动？ ddt 模块实现数据驱动的意义： 通过不同的数据对同一脚本实现…...

编程日记 2025/6/27 4:50:44

15：00开始面试，15：06就出来了，问的问题有点变态。。。

从小厂出来，没想到在另一家公司又寄了。到这家公司开始上班，加班是每天必不可少的，看在钱给的比较多的份上，就不太计较了。没想到4月一纸通知，所有人不准加班，加班费不仅没有了，薪资还要降40%…...

编程日记 2025/6/27 4:27:16

深入理解浏览器渲染引擎：底层机制与性能优化实战

现代浏览器背后是一个庞大而复杂的系统工程，渲染引擎作为核心模块之一，承担着从解析 HTML/CSS 到最终绘制页面的关键职责。本文将从底层机制出发，系统梳理渲染引擎（如 Blink）工作原理、V8 与渲染流程的协作方式&#x…...

编程日记 2025/6/27 4:50:43

【LeetCode 热题 100】56. 合并区间 —— 一文弄懂排序+遍历经典解法（附Python代码）

📌 题目链接 LeetCode 56. 合并区间 📖 一、引言：区间合并，刷题路上的绊脚石？区间类问题是算法面试中常见的经典题型，尤其是“合并区间”问题，考察你对排序、区间重叠判断及边界处理的理解和编码能力。很多同学在面对这题时，容易卡在：什么时候两个区间算重叠？…...

编程日记 2025/6/22 16:47:33

使用Mathematica绘制Clifford奇异吸引子

Clifford Attractors 是一种由微分方程生成的混沌吸引子，参数a,b,c,d不同会产生不同的分形图案。这类吸引子属于迭代函数系统，通过不断迭代参数方程来生成复杂的图形。其数学基础可能与 Clifford 代数或高维函数理论相关，例如 Clifford 代数…...

编程日记 2025/6/27 4:58:39

各个历史版本mysql/tomcat/Redis/Jdk/Apache下载地址

mysql 各版本下载地址： https://downloads.mysql.com/archives/community/ **************************************************************** tomcat 各版本下载地址： https://archive.apache.org/dist/tomcat/ ********************************…...

编程日记 2025/6/25 15:14:16

全面解析机器学习与深度学习中的模型权重文件格式与应用场景

概述随着机器学习和人工智能技术的飞速发展，高效且安全地存储、共享和部署训练有素的模型的方法变得越来越重要。模型权重文件格式在这个过程中发挥着关键作用。这些格式不仅保存了模型的学习参数，还能够实现可复现性，并且便于在各种不同环…...

编程日记 2025/6/27 4:33:10

鸿蒙OSUniApp 实现的地图定位与导航功能#三方框架 #Uniapp

UniApp 实现的地图定位与导航功能随着移动互联网的发展，地图定位与导航功能已成为众多应用的标配。本文将详细介绍如何在 UniApp 框架下实现地图定位与导航功能，并探讨如何适配鸿蒙系统，助力开发者打造更加流畅的地图体验。前言最近在做一…...

编程日记 2025/6/27 5:11:46

【HarmonyOS 5】鸿蒙星闪NearLink详解

【HarmonyOS 5】鸿蒙星闪NearLink详解一、前言鸿蒙星闪NearLink Kit 是 HarmonyOS 提供的短距离通信服务，支持星闪设备间的连接、数据交互。例如，手机可作为中心设备与外围设备（如鼠标、手写笔、智能家电、车钥匙等）通过星闪进…...

编程日记 2025/6/26 23:37:01

Java并发编程面试题总结

目录线程有哪几种状态?状态如何流转? 创建线程的方式? 多线程有什么应用? 线程池的好处? 线程池的七个参数? 为什么不推荐使用jdk的Executors创建线程池? 线程池的执行流程? 任务拒绝策略有哪些，怎么选择? 线程池的核心线程数和最大线程数怎么设定…...

编程日记 2025/6/27 4:31:58

LAMP项目部署实战

一、LAMP部署前期准备 1.1 关闭防火墙 # systemctl stop firewalld # systemctl disable firewalld 1.2 关闭SELinux SELinux(Security-EnhancedLinux)是美国国家安全局（NSA）对于强制访问控制的实现，是Linux历史上最杰出的新安全子系统。 …...

编程日记 2025/6/27 5:11:47

Dify与n8n全面对比指南：AI应用开发与工作流自动化平台选择【2025最新】

Dify与n8n全面对比指南：AI应用开发与工作流自动化平台选择【2025最新】随着AI技术与自动化工具的迅速发展，开发者和企业面临着多种平台选择。Dify和n8n作为两个备受关注的自动化平台，分别专注于不同领域：Dify主要面向AI应用开发&…...

编程日记 2025/6/27 4:44:48

VBA_NZ系列工具NZ10：VBA压缩与解压工具

我的教程一共九套及VBA汉英手册一部，分为初级、中级、高级三大部分。是对VBA的系统讲解，从简单的入门，到数据库，到字典，到高级的网抓及类的应用。大家在学习的过程中可能会存在困惑，这么多知识点该如何组织…...

编程日记 2025/6/27 4:57:02

EFT不过整改思路与调试经验

EFT是如何影响EUT的： EFT试验是为了验证电气和电子设备对诸如来自切换瞬态过程(切断感性负载、继电器触点弹跳等)的各种类型瞬变骚扰的抗扰度。EFT干扰是在电路中感性负载断开时产生的，它的特点是干扰信号不是单个脉而是一连串的脉冲群。EFT 干扰可以在…...

编程日记 2025/6/27 4:55:39

2.安卓逆向2-adb指令

免责声明：内容仅供学习参考，请合法利用知识，禁止进行违法犯罪活动！ 内容参考于：图灵Python学院工具下载： 链接：https://pan.baidu.com/s/1bb8NhJc9eTuLzQr39lF55Q?pwdzy89 提取码&#xff1…...

编程日记 2025/6/24 9:58:42

VSCode CMake工作流

Foreword 之前看到CMake有这么多选项，感觉不简单，还是看下别人在这里设计了多少东西 CMake 整体来说CMake遵循这样一套结构操作-操作预设（如果有的话）-操作目标（如果有的话）比如 Configure-Configure…...

编程日记 2025/6/27 5:05:08

【上位机——WPF】App.xml和Application类简介

App.xml和Application类简介概述App.xamlApp.xaml.cs 入门代码App.xamlMainWindow.xml Application生命周期窗体的声明周期概述 xaml类型的文件包含两部分，一部分以.xaml扩展名结尾的前端代码，另一部分以.xaml.cs结尾的后端代码，通常我们也…...

编程日记 2025/6/24 23:35:17

MySQL 8.0 OCP 1Z0-908 101-110题

Q101.which two queries are examples of successful SQL injection attacks? A.SELECT id, name FROM backup_before WHERE name‘; DROP TABLE injection; --’; B. SELECT id, name FROM user WHERE id23 oR id32 OR 11; C. SELECT id, name FROM user WHERE user.id (SEL…...

编程日记 2025/6/25 20:53:57

一、问题分析

二、实现步骤

1）初始化种群

2）计算适应度

3）选择操作

4）交叉操作

5）变异操作

三、求解结果

四、总结

相关文章：