首页 > 编程语言 >禁忌搜索算法（TS算法）求解实例---旅行商问题 (TSP)

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

时间：2024-09-16 09:53:56浏览次数：11  
标签：distance 10 TS 搜索算法 禁忌 --- 算法 solution

目录

一、采用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 = 0
    for 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_distance

    for iteration in range(max_iter):
        # 生成所有邻域解
        neighbors = get_neighborhood(current_solution)
        neighbors_distances = [(neighbor, total_distance(neighbor)) for neighbor in neighbors]
        
        # 在禁忌表之外选择最优邻域解
        next_solution = None
        next_distance = float('inf')
        for neighbor, distance in neighbors_distances:
            if neighbor not in tabu_list and distance < next_distance:
                next_solution = neighbor
                next_distance = distance

        # 更新当前解
        current_solution = next_solution
        current_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_distance

        print(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)：优化多辆车在多个配送点的路径。
  • 生产调度与资源分配：如工作车间调度、工厂生产排程、任务分配等。
  • 网络设计与路由优化：优化计算机网络或物流网络中的节点连接和路由路径。
  • 组合优化问题：如背包问题、图着色问题、设备布局问题等。

标签：distance,10,TS,搜索算法,禁忌,---,算法,solution
From： https://blog.csdn.net/qq_63913621/article/details/142298846

相关文章

  • 蚁群算法（ACO算法）求解实例---旅行商问题 (TSP)
    目录一、采用ACO求解TSP二、旅行商问题2.1实际例子：求解6个城市的TSP2.2==**求解该问题的代码**==2.3代码运行过程截屏2.4代码运行结果截屏（后续和其他算法进行对比）三、==如何修改代码？==3.1减少城市坐标，如下：3.2增加城市坐标，如下：四、蚁群算法(AntColonyOp......
  • C++数据结构-二叉树的三种遍历方法（进阶篇）
    1.遍历简介：树作为非线性数据结构，在我们取出数据时就需要设计遍历，所谓遍历，就是按照一定的规则性，将数据结构中的所有数据全部依次访问，而二叉树本身并不具有天然的全局次序，故为实现遍历，需通过在各节点与其孩子之间约定某种局部次序，间接地定义某种全局次序，这便是我们常规定的先序......
  • C++数据结构-二叉树的存储方法（基础篇）
    1.简介根据前文的介绍，我们知道了二叉树的性值，其就是一种每一个结点中只允许拥有左右孩子（或为空）的树，这种数据结构在我们的实际设计中非常常用，如前文提到的STL中的set集合，其底层就是一颗标准的红黑树（二叉树的一种），我们这里以创建一颗二叉树并实现通过特定的插入顺序和读取顺序达......
  • WEB-API+.NET+CRUD+SSMS(VS2022)
    1.使用VS2022创建一个web-api项目，根目录如下：其中TestCode.cs写model实体类，Controller编写控制器2.实体类Item，编写对应的属性点击查看代码publicclassItem{[Required]publicintId{get;set;}[Required]publicintFieldID{get;set;}......
  • Linux内存管理知识-一篇文章了解堆和栈区别（进阶篇）
    前面已经介绍过，栈是由编译器在需要时分配的，不需要时自动清除的变量存储区。里面的变量通常是局部变量、函数参数等。堆是由malloc()函数分配的内存块，内存释放由程序员手动控制，在C语言为free函数完成。栈和堆的主要区别有以下几点：（1）管理方式不同栈编译器自动管理，无需程序员手......
  • ORA-600 16703故障再现---惜分飞
    联系：手机/微信(+8617813235971)QQ(107644445)标题：ORA-60016703故障再现作者：惜分飞©版权所有[未经本人同意,不得以任何形式转载,否则有进一步追究法律责任的权利.]从第一次发现ORA-60016703(警告：互联网中有oracle介质被注入恶意程序导致—ORA-60016703)至今已经7年多时间......
  • Zero-Shot，One-Shot，Few-Shot，In-Context Learning
    Zero-Shot，One-Shot，Few-Shot，In-ContextLearninghttps://blog.csdn.net/weixin_44212848/article/details/139902394In-ContextLearning定义：In-contextlearning是一种在不显式微调模型权重的情况下，通过给模型提供相关的上下文信息（例如提示或样本）来实现模型性能提升的方法。GPT......
  • 上周热点回顾（9.9-9.15）
    热点随笔：· 秋天希望的田野，九月最后的救园：终身会员计划 (博客园团队)· 41岁的大龄程序员，苟着苟着，要为以后做打算了 (Tobin)· 关于.NET在中国为什么工资低的分析 (迅捷网络[来送福利])· .NET9的新亮点：AI就绪，拥抱她 (张善友)· 45岁大龄程序员自述：我居然还苟在程序......
  • C++-练习-40
    题目：编写一个程序，她每次读取一个单词，知道用户只输入q。然后，该程序指出有多少个单词以元音大头，而多少个单词以辅音大头，还有多少个单词不属于着两类。源代码：#include<iostream>#include<cctype>//元音:A、E、I、O、Uintmain(){ usingnamespacestd; charword[20];......
  • Cisco Jabber 15.0 发布下载 - 面向企业的多合一通信工具
    CiscoJabber15.0(Andriod,iOS,macOS,Windows)-面向企业的多合一通信工具即时消息、语音和视频通话、语音邮件、桌面共享、会议和在线状态请访问原文链接：https://sysin.org/blog/cisco-jabber-15/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.org思科Jabber......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99