禁忌搜索算法(TS算法)求解实例---旅行商问题 (TSP)

目录

  • 一、采用TS求解 TSP
  • 二、 旅行商问题
    • 2.1 实际例子:求解 6 个城市的 TSP
    • 2.2 ==**求解该问题的代码**==
    • 2.3 代码运行过程截屏
    • 2.4 代码运行结果截屏(后续和其他算法进行对比)
  • 三、 ==如何修改代码?==
    • 3.1 减少城市坐标,如下:
    • 3.2 增加城市坐标,如下:
  • 四、 禁忌搜索算法 (Tabu Search, TS) 原理
    • 4.1 TS算法定义
    • 4.2 TS算法算法的基本思想
    • 4.3 TS算法算法的工作原理
    • 4.4 TS算法算法的关键要素
    • 4.5 TS算法算法的优缺点
      • 4.5.1 优点
      • 4.5.2 缺点
    • 4.6 TS算法算法的应用场景

一、采用TS求解 TSP

求解代码在文中,后续会出其他算法求解TSP问题,你们参加数学建模竞赛只需要会改代码即可。

用来对比此专栏的
遗传算法(GA算法)求解实例—旅行商问题 (TSP)
粒子群算法(PSO算法)求解实例—旅行商问题 (TSP)
模拟退火算法(SA算法)求解实例—旅行商问题 (TSP)
蚁群算法(ACO算法)求解实例—旅行商问题 (TSP)
注意每次运行算法得到的结果可能不太一样。

我知道大家对原理性的东西不感兴趣,我把原理性的东西放在后面,大家如果需要写数模论文可以拿去,但是记得需要改一改,要不然查重过不去。

二、 旅行商问题

2.1 实际例子:求解 6 个城市的 TSP

假设有 6 个城市,其坐标如下:

城市X 坐标Y 坐标
01020
13040
22010
34030
41010
55020

目标是找到一个经过所有城市且总距离最短的路径。

2.2 求解该问题的代码

import numpy as np
import random# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[10, 10],[50, 20]
])# 计算两城市之间的欧几里得距离
def calculate_distance(city1, city2):return np.sqrt(np.sum((city1 - city2) ** 2))# 计算总旅行距离
def total_distance(path):distance = 0for i in range(len(path) - 1):distance += calculate_distance(cities[path[i]], cities[path[i + 1]])distance += calculate_distance(cities[path[-1]], cities[path[0]])  # 回到起点return distance# 生成初始解
def generate_initial_solution(num_cities):return list(np.random.permutation(num_cities))# 生成邻域解(通过交换路径中的两个城市)
def get_neighborhood(solution):neighbors = []for i in range(len(solution)):for j in range(i + 1, len(solution)):neighbor = solution.copy()neighbor[i], neighbor[j] = neighbor[j], neighbor[i]neighbors.append(neighbor)return neighbors# 禁忌搜索算法主函数
def tabu_search(cities, tabu_size=10, max_iter=500):num_cities = len(cities)# 初始化禁忌表tabu_list = []# 生成初始解current_solution = generate_initial_solution(num_cities)current_distance = total_distance(current_solution)# 初始化最佳解best_solution = current_solution.copy()best_distance = current_distancefor iteration in range(max_iter):# 生成所有邻域解neighbors = get_neighborhood(current_solution)neighbors_distances = [(neighbor, total_distance(neighbor)) for neighbor in neighbors]# 在禁忌表之外选择最优邻域解next_solution = Nonenext_distance = float('inf')for neighbor, distance in neighbors_distances:if neighbor not in tabu_list and distance < next_distance:next_solution = neighbornext_distance = distance# 更新当前解current_solution = next_solutioncurrent_distance = next_distance# 更新禁忌表tabu_list.append(current_solution)if len(tabu_list) > tabu_size:tabu_list.pop(0)# 更新全局最佳解if current_distance < best_distance:best_solution = current_solution.copy()best_distance = current_distanceprint(f"Iteration {iteration + 1}: Best distance = {best_distance:.2f}")return best_solution, best_distance# 运行禁忌搜索算法
best_path, best_distance = tabu_search(cities)
print("Best path:", best_path)
print("Best distance:", best_distance)

2.3 代码运行过程截屏

在这里插入图片描述

2.4 代码运行结果截屏(后续和其他算法进行对比)

在这里插入图片描述

三、 如何修改代码?

这一部分是重中之重,大家参加数学建模肯定是想跑出自己的结果,所以大家只需要把自己遇到的数学问题,抽象成TSP问题,然后修改代码的城市坐标,然后运行即可。

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[10, 10],[50, 20]
])

3.1 减少城市坐标,如下:

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30]
])

3.2 增加城市坐标,如下:

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[30, 40],[20, 10],[10, 10],[50, 20]
])

四、 禁忌搜索算法 (Tabu Search, TS) 原理

4.1 TS算法定义

禁忌搜索算法 (Tabu Search, TS) 是一种基于局部搜索的启发式优化算法,由 Fred Glover 在 1986 年提出。禁忌搜索算法通过维护一个“禁忌表”来记录最近访问过的解或搜索路径,从而避免算法在搜索过程中陷入循环或局部最优解。通过合理的禁忌策略和多样化策略,TS 算法能够跳出局部最优解,找到全局最优解或近似最优解。

4.2 TS算法算法的基本思想

禁忌搜索算法的核心思想是对局部搜索进行改进。传统的局部搜索算法可能会因为陷入局部最优解或搜索循环而难以找到全局最优解。禁忌搜索算法通过在每次迭代中选择当前邻域中的最优解作为下一步搜索方向,并使用一个称为“禁忌表”的数据结构来记录已访问过的解或路径,从而避免回到先前访问过的解。禁忌表的内容会动态更新,以使得搜索能够进行更广泛的探索。

4.3 TS算法算法的工作原理

  1. 初始化

    • 随机生成一个初始解 s 作为当前解。
    • 设置一个空的禁忌表 T 和最大禁忌表长度 L,定义最大迭代次数 max_iter
  2. 生成邻域解

    • 对当前解 s,生成其邻域解集合 N(s)。通常,邻域解是通过对当前解的微小修改(如交换、移位等)生成的多个新解。
  3. 选择最优邻域解

    • 在邻域解集合 N(s) 中,选择一个不在禁忌表中的最佳解 s',使得其目标函数值最优(通常是最小化问题中的最小值)。
    • 若所有邻域解均在禁忌表中,则可以选择一个禁忌解作为当前解。
  4. 更新禁忌表

    • 将新的解 s' 添加到禁忌表 T 中,以避免在未来的搜索过程中重新访问该解。
    • 若禁忌表长度超过最大限制 L,则删除最早加入的解。
  5. 更新当前解和全局最优解

    • 将当前解 s 更新为新解 s'
    • 如果 s' 的目标函数值优于全局最优解 s*,则更新全局最优解 s*
  6. 迭代和终止

    • 重复步骤 2-5,直到达到最大迭代次数 max_iter 或找到满意解为止。

4.4 TS算法算法的关键要素

  1. 禁忌表(Tabu List)

    • 禁忌表是一个用来存储禁忌解的集合,用于防止搜索过程中的循环和回溯。禁忌表的长度 L 通常设定为一个固定值,当禁忌表超过最大长度时,将最早的解移出禁忌表。
  2. 邻域结构

    • 邻域结构决定了每次搜索所能达到的解空间范围。常见的邻域操作有交换、移位、反转等操作。
  3. 禁忌策略

    • 禁忌策略决定了哪些解被列入禁忌表。在一般情况下,禁忌解是根据一定规则选定的,以确保多样化搜索和有效避免循环。
  4. 解的多样化策略

    • 在搜索过程陷入局部最优时,解的多样化策略用于打破停滞状态,推动搜索进入新的区域。

4.5 TS算法算法的优缺点

4.5.1 优点

  • 跳出局部最优:通过禁忌表机制,TS 算法能够有效避免局部最优解,继续在解空间中进行搜索。
  • 灵活性强:TS 算法可以应用于多种优化问题,通过调整邻域结构和禁忌策略,可以针对不同问题进行适应性调整。
  • 易于实现:相较于一些复杂的优化算法,TS 算法较为简单,易于实现。

4.5.2 缺点

  • 计算开销较大:在大规模问题中,生成邻域解和维护禁忌表可能会带来较高的计算开销。
  • 参数敏感:算法性能对禁忌表长度、邻域结构和禁忌策略较为敏感,需要根据具体问题进行调优。
  • 不保证全局最优解:虽然 TS 算法能跳出局部最优,但不能保证一定找到全局最优解。

4.6 TS算法算法的应用场景

  • 旅行商问题 (TSP):寻找经过所有城市的最短路径。
  • 车辆路径问题 (VRP):优化多辆车在多个配送点的路径。
  • 生产调度与资源分配:如工作车间调度、工厂生产排程、任务分配等。
  • 网络设计与路由优化:优化计算机网络或物流网络中的节点连接和路由路径。
  • 组合优化问题:如背包问题、图着色问题、设备布局问题等。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/428155.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

游戏如何对抗定制挂

近年来&#xff0c;游戏安全对抗强度相比以往更加激烈&#xff0c;具体表现在“定制挂”趋势显著。在近期收集的近万款外挂样本中&#xff0c;定制挂约占比78%&#xff0c;常见的内存修改器、变速器等通用作弊手段占比正在下降。 所谓定制挂&#xff0c;是指针对某款游戏单独开…

初写MySQL四张表:(2/4)

今天&#xff0c;我们来写第二张表。因着这四张表以及后续有相应的拓展&#xff0c;这四张环环相扣&#xff0c;所以还未写出第一张表的同学&#xff0c;可以看完第一张表&#xff0c;再来此处&#xff1a; 初写MySQL四张表:(1/4)-CSDN博客 好&#xff0c;今日表格有三张&…

easy-es动态索引支持

背景 很多项目目前都引入了es&#xff0c;由于es弥补了mysql存储及搜索查询的局限性&#xff0c;随着技术的不断迭代&#xff0c;原生的es客户端使用比较繁琐不直观&#xff0c;上手代价有点大&#xff0c;所以easy-es框架就面世了&#xff0c;学习成本很低&#xff0c;有空大…

记忆化搜索专题——算法简介力扣实战应用

目录 1、记忆化搜索算法简介 1.1 什么是记忆化搜索 1.2 如何实现记忆化搜索 1.3 记忆化搜索与动态规划的区别 2、算法应用【leetcode】 2.1 题一&#xff1a;斐波那契数 2.1.1 递归暴搜解法代码 2.1.2 记忆化搜索解法代码 2.1.3 动态规划解法代码 2.2 题二&#xff1…

vue-使用refs取值,打印出来是个数组??

背景&#xff1a; 经常使用$refs去获取组件实例&#xff0c;一般都是拿到实例对象&#xff0c;这次去取值的时候发现&#xff0c;拿到的竟然是个数组。 原因&#xff1a; 这是vue的特性,自动把v-for里面的ref展开成数组的形式&#xff0c;哪怕你的ref名字是唯一的&#xff01…

后台数据管理系统 - 项目架构设计-Vue3+axios+Element-plus(0916)

接口文档: https://apifox.com/apidoc/shared-26c67aee-0233-4d23-aab7-08448fdf95ff/api-93850835 接口根路径&#xff1a; http://big-event-vue-api-t.itheima.net 本项目的技术栈 本项目技术栈基于 ES6、vue3、pinia、vue-router 、vite 、axios 和 element-plus http:/…

6.C++程序中的基本数据类型

数据类型是指在C中用于声明不同类型变量或函数的一个系统或抽象或者是一个分类&#xff0c;它决定了变量存储占用的内存空间以及解析存储的位模式。其实数据类型可以理解为固定内存大小的别名&#xff0c;是创建变量的模具&#xff0c;具体使用哪种模具&#xff08;包括自定义&…

Python安装不再难!全平台保姆级教程带你轻松搞定!

Python介绍 Python是一种功能强大且灵活的编程语言&#xff0c;被广泛应用于各个领域。以下是Python在不同应用领域的一些常见用途&#xff1a; 网络开发 Python提供了丰富的库和框架&#xff0c;使其成为网络开发的理想选择。诸如Django、Flask和Pyramid等框架可以帮助开发人员…

一张图解析FastAdmin中的表格列表(bootstrap-table)的功能(备份)

功能描述 请根据图片上的数字索引查看对应功能说明。 1.菜单名称和描述 默认生成的CRUD是没有菜单名称和描述显示的&#xff0c;如果需要显示则可以修改权限管理->菜单规则&#xff0c;给对应菜单的添加上备注信息后即可显示&#xff0c;支持HTML 2.TAB过滤选项卡 在一键…

Linux之CentOS 7.9-Minimal部署Oracle 11g r2 安装实测验证(桌面模式)

前言: 发个之前的库存… Linux之CentOS 7.9-Minimal部署Oracle 11g r2 安装实测验证(桌面模式) 本次验证的是CentOS_7_Minimal-2009桌面模式来部署Oracle 11g r2,大家可根据自身环境及学习来了解。 环境:下载地址都给你们超链好了 1、Linux系统镜像包: 1.1 CentOS-7-x86_…

Linux 删除文件不释放空间问题处理

背景&#xff1a; 服务器磁盘空间已经达到100%&#xff0c;删除存放日志路径下的文件后&#xff0c;发现空间并未释放&#xff01; 原因&#xff1a;在linux系统中&#xff0c;通过rm删除文件将会从文件系统的文件夹结构上解除链接(unlink)然后删除&#xff0c;然而假设文件是被…

探索Python的Excel世界:openpyxl的魔法之旅

文章目录 探索Python的Excel世界&#xff1a;openpyxl的魔法之旅背景&#xff1a;为什么选择openpyxl&#xff1f;什么是openpyxl&#xff1f;如何安装openpyxl&#xff1f;简单的库函数使用方法场景应用&#xff1a;openpyxl在实际工作中的应用常见bug及解决方案总结 探索Pyth…

如何利用视觉分析实现扬尘检测

随着城市化和工业化进程的加速&#xff0c;扬尘污染已成为全球各大城市面临的环境问题之一。建筑施工、道路交通以及工业活动产生的扬尘不仅影响空气质量&#xff0c;严重时还会引发呼吸道疾病&#xff0c;威胁公众健康。传统的扬尘检测手段多为传感器、采样仪等设备&#xff0…

【Echarts】vue3打开echarts的正确方式

ECharts 是一个功能强大、灵活易用的数据可视化工具&#xff0c;适用于商业报表、数据分析、科研教育等多种场景。那么该如何优雅的使用Echarts呢? 这里以vue3为例。 安装echarts pnpm i echarts封装公用方法 // ts-nocheck import * as echarts from echarts; // 我们这里借…

【C++指南】inline内联函数详解

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《C指南》 期待您的关注 目录 引言 C为什么引入了inline来替代C语言中的宏 inline的基本用法 定义inline函数 inline的优势与…

IO模型---BIO、NIO、IO多路复用、AIO详解

本篇将想给详细解释一下什么是BIO、NIO、IO多路复用以及AIO~ 同步的阻塞(BIO)和非阻塞(NIO)的区别 BIO&#xff1a;线程发来IO请求后&#xff0c;一直阻塞着IO线程&#xff0c;需要缓冲区这边数据准备好之后&#xff0c;才会进行下一步的操作。 举个&#x1f330;&#xff1…

HarmonyOS应用开发者基础认证

目录 一、判断二、单选三、多选 一、判断 1、HarmonyOS提供了基础的应用加固安全能力&#xff0c;包括混淆、加密和代码签名能力。正确 2、可以通过ohpm uninstall 指令下载指定的三方库。错误 3、支持模块化开发是指一个应用通常会包含多种功能&#xff0c;将不同的功能特性…

【读书笔记-《30天自制操作系统》-23】Day24

本篇内容依然比较简单&#xff0c;主要是优化窗口功能以及开发定时器应用程序。首先是优化窗口的切换功能&#xff0c;实现通过键盘和鼠标切换窗口&#xff0c;然后是实现通过鼠标关闭窗口。接着实现不同窗口输入状态的切换&#xff0c;最后是实现定时器的API与应用程序。 1.…

Windows Server2016多用户登录破解

使用场景 很多时候&#xff0c;公司开发和测试运维会同时登录同一台windows服务器进行查询、更新、维护等操作&#xff0c;本文就来介绍一下Windows2016配置多人远程桌面登录实现&#xff0c;感兴趣的可以了解一下。 操作流程 &#xff08;1&#xff09;首先桌面需要安装远程…

旅行社区应该如何规划?

近年来&#xff0c;旅游行业逐渐恢复&#xff0c;包括微度假、精致露营、康养旅游、乡村民宿等旅游模式。用户旅游支出、旅游人次逐渐恢复&#xff0c;旅游收入仍待提升。 那么旅游社区应该如何搭建&#xff0c;内容如何规划呢&#xff1f; 我们了解到&#xff0c;很多旅游网…