python实现大规模邻域搜索(LNS)求解旅行商问题(TSP)

这篇具有很好参考价值的文章主要介绍了python实现大规模邻域搜索(LNS)求解旅行商问题(TSP)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 大规模邻域搜索算法

参考《Handbook of Metaheuristics (Third Edition)》中的Large neighborhood search章节, 建议直接阅读英文原版

1.1. LNS定义

大规模邻域搜索(LNS) 属于超大邻域搜索(Very Large-Scale Neighborhood Search, VLNS)的一类,随着算例规模的增大,邻域搜索算法的邻域规模呈指数增长或者当邻域太大而不能在实际中明确搜索时 (the neighborhood it searches grows exponentially with the instance size or if the neighborhood is simply too large to be searched explicitly in practice),我们把这类邻域搜索算法(Neighborhood Search, NS)归类于VLNS;

1.2. LNS邻域

  • 邻域搜索算法关键在于邻域结构的选择,即邻域定义的方式。通常来讲,邻域越大,局部最优解就越好,获得的全局最优解就越好。同时,邻域越大,每次迭代搜索邻域所需的时间也越长。

  • 在大规模邻域搜索算法中,邻域由一种破坏(destroy)和一种修复(repair)算子隐式定义(the neighborhood is defined implicitly by a destroy and a repair method)。destroy算子会破坏当前解的一部分(变成不可行解),repair算子会对被破坏的解进行重建(重新变成可行解),相当于一个邻域动作变换动作。破坏算子通常包含随机性的元素,以便在每次调用destroy方法时破坏解的不同部分(The destroy method typically contains an element of stochasticity such that different parts of the solution are destroyed in every invocation of the method)。

  • x x x的邻域 N ( x ) N(x) N(x)就可以定义为:首先利用destroy算子破坏解 x x x,然后利用repair算子重建解 x x x,从而得到的一系列解的集合(The neighborhood N(x) of a solution x is then defined as the set of solutions that can be reached by first applying the destroy method and then the repair method)。

  • LNS算法不会搜索一个解的整个邻域(entire neighborhood),而只是对该邻域进行采样(samples)搜索; (按照算法流程,只定义一种detory和repair方式,虽然detory里有随机部分,但也不包含整个邻域)

1.3. LNS框架

  • 伪代码

python实现大规模邻域搜索(LNS)求解旅行商问题(TSP)

在LNS中只定义一种破坏和修复算子,所以破坏和修复算子的定义很重要,直接决定了能搜索到的当前解x的邻域。如果邻域太小,那么局部最优解的质量就一般,因为有些空间没搜索到。如果邻域太大,又缺少带点启发式信息方向搜索。所以Ropke在论文《An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows》定义了多种破坏和修复算子,提出来自适应大规模邻域搜索(Adaptive Large Neighborhood Search, ALNS)的框架,有空总结写一篇关于ALNS的文章。

2. 旅行商问题TSP

  • 旅行商问题(Travelling Salesman Problem, TSP),通俗而言它是指对于给定的一系列城市和每对城市之间的距离,找到访问每一座城市仅一次并回到起始城市的最短回路。建立不同的建模方式会有不同的求解方式,比如Dantzig-Fulkerson-Johnson模型、Miller-Tucker-Zemlin模型、Commodity Flow、最短路径等;(这里不再赘述,注意TSP问题各种形式的变种)

3. python代码示例及结果

  • python代码
import random
import numpy as np
from copy import deepcopy
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']

class Solution:
    # 使用符号编号表示一个访问路径route
    def __init__(self):
        self.route = []
        self.cost = 0  # 解对应的总成本

class Lns_tsp(object):
    def __init__(self, distance, num_node):
        self.distance = distance
        self.num_node = num_node

    def get_route_cost(self, route):
        # 计算成本的函数
        cost = 0
        for i in range(1, len(route)):
            cost += self.distance[route[i-1]][route[i]]
        return cost

    def destroy_operator(self, solution, num_destroy):
        # 破坏算子: 随机选择num_destroy个不重复的破坏点(即删除num_destroy个城市)
        destroy_node_bank = []  # 保存被删除的城市节点
        while len(destroy_node_bank) < num_destroy:
            n = random.randint(0, self.num_node-1)
            while n in destroy_node_bank:
                n = random.randint(0, self.num_node-1)
            destroy_node_bank.append(n)
            solution.route.remove(n)
        return solution, destroy_node_bank

    def repair_operator(self, solution, destroy_node_bank):
        # 修复算子: 贪婪插入,插入到成本最小的位置
        for n in destroy_node_bank:
            #计算将n插入各个位置的成本
            insert_list = np.full(len(solution.route), 0)
            for i in range(0, len(solution.route)):
                insert_list[i] = self.distance[solution.route[i-1]][n] + self.distance[n][solution.route[i]] - self.distance[solution.route[i]][solution.route[i-1]]

            greedy_index = np.where(insert_list == min(insert_list))[0][0]

            solution.route.insert(greedy_index, n)
        return solution

def plot_best_vales_iteration(best_values_record):
    # 绘制最优解随着迭代变化的趋势
    plt.figure()
    plt.plot([i+1 for i in range(len(best_values_record))], best_values_record)
    plt.xlabel('迭代次数')
    plt.ylabel('最优值')
    plt.show()

def plot_route(route, city_location):
    plt.figure()
    # 绘制散点
    x = np.array(city_location)[:, 0]  # 横坐标
    y = np.array(city_location)[:, 1]  # 纵坐标
    plt.scatter(x, y, color='r')
    # 绘制城市编号
    for i, txt in enumerate(range(1, len(city_location) + 1)):
        plt.annotate(txt, (x[i], y[i]))
    # 绘制方向
    x0 = x[route]
    y0 = y[route]
    for i in range(len(city_location) - 1):
        plt.quiver(x0[i], y0[i], x0[i + 1] - x0[i], y0[i + 1] - y0[i], color='b', width=0.005, angles='xy', scale=1,
                   scale_units='xy')
    plt.quiver(x0[-1], y0[-1], x0[0] - x0[-1], y0[0] - y0[-1], color='b', width=0.005, angles='xy', scale=1,
               scale_units='xy')

    plt.xlabel('横坐标')
    plt.ylabel('纵坐标')
    plt.show()

if __name__ == '__main__':
    ############## 算例和参数设置 ############################
    # 城市节点的位置信息,一行代表一个城市的横坐标及纵坐标
    city_location = [[ 94,  99],
           [ 66,  67],
           [ 14,  78],
           [ 95,  56],
           [ 68,   9],
           [ 26,  20],
           [ 51,  67],
           [ 39,  39],
           [  5,  55],
           [ 12,  33],
           [ 55,  85],
           [ 98,  46],
           [ 36,  39],
           [ 65, 100],
           [ 57,  89],
           [ 88,  24],
           [ 53,  96],
           [ 91,  41],
           [ 32,  69],
           [ 38,  38],
           [ 38,  39],
           [ 85, 100],
           [  7,  37],
           [ 85,  96],
           [ 89,  48],
           [ 85,  35],
           [ 32,  29],
           [ 31,  25],
           [ 20,  17],
           [ 75,  21],
           [ 74,  29],
           [  6,  32],
           [ 20,  81],
           [ 62,   1],
           [ 11,  48],
           [  1,  69],
           [ 99,  70],
           [ 20,  27],
           [ 25,  42],
           [  6,  31],
           [ 78,  24],
           [ 42,  39],
           [ 83,  30],
           [ 94,  10],
           [ 90,  37],
           [ 76,  73],
           [  9,  56],
           [ 39,  33],
           [ 74,  15],
           [ 77,  14]]

    num_node = len(city_location)  # 城市节点的数量
    iter_num = 300  # 迭代次数
    random.seed(3)  # 随机种子
    num_destroy = int(num_node*0.2) # 破坏程度

    # 计算距离成本矩阵 distance, 直接使用欧式距离
    distance = np.full((num_node, num_node), 0)
    for i in range(num_node):
        for j in range(num_node):
            distance[i][j] = ((city_location[i][0]-city_location[j][0])**2+(city_location[i][1]-city_location[j][1])**2)**0.5

    ############## 产生初始解 ############################
    solution = Solution()
    solution.route = [i for i in range(num_node)]  # 按照节点编号依次相连构成初始解也可随机产生
    lns = Lns_tsp(distance, num_node)
    solution.cost = lns.get_route_cost(solution.route) # 计算初始解对应的目标成本
    best_solution = deepcopy(solution)  # 初始化最优解=初始解
    best_values_record = [0 for i in range(iter_num)]  # 初始化保存最优解的集合

    ############## 执行LNS ############################
    for n_gen in range(iter_num):
        tem_solution = deepcopy(solution)
        # 执行破坏修复算子,得到临时解
        tem_solution, destroy_node_bank = lns.destroy_operator(tem_solution, num_destroy)
        tem_solution = lns.repair_operator(tem_solution, destroy_node_bank)
        # 计算临时解的目标值
        tem_solution.cost = lns.get_route_cost(tem_solution.route)

        # 接受标准:如果临时解比当前解好,直接接受;且更新最优解
        if tem_solution.cost < best_solution.cost:
            solution = deepcopy(tem_solution)
            best_solution = deepcopy(tem_solution)
        best_values_record[n_gen] = best_solution.cost

    ############## 绘制结果 ############################
    plot_best_vales_iteration(best_values_record)
    plot_route(best_solution.route, city_location)
  • 结果
    python实现大规模邻域搜索(LNS)求解旅行商问题(TSP)

python实现大规模邻域搜索(LNS)求解旅行商问题(TSP)文章来源地址https://www.toymoban.com/news/detail-480215.html

到了这里,关于python实现大规模邻域搜索(LNS)求解旅行商问题(TSP)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 利用Python进行大规模数据处理

    前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 随着数据量的不断增长,大规模数据处理变得越来越重要。在这个领域,Hadoop和Spark是两个备受关注的技术。本文将介绍如何利用Python编程语

    2024年04月24日
    浏览(39)
  • etcd实现大规模服务治理应用实战

         导读 :服务治理目前越来越被企业建设所重视,特别现在云原生,微服务等各种技术被更多的企业所应用,本文内容是百度小程序团队基于大模型服务治理实战经验的一些总结,同时结合当前较火的分布式开源kv产品etcd,不仅会深入剖析ectd两大核心技术Raft与boltdb的实

    2024年02月12日
    浏览(48)
  • Python cudf库详解:加速大规模数据处理

    📚 个人网站:ipengtao.com 随着数据规模的不断增大,高效处理大规模数据成为数据科学和机器学习中的一个重要挑战。 cudf 库作为GPU加速的DataFrame库,为Python用户提供了在处理大数据集时显著提升性能的可能性。本文将深入介绍 cudf 库的使用方法,涵盖其基本概念、常用功能

    2024年02月21日
    浏览(52)
  • 大规模数据量下ES如何实现高性能检索?

    ElasticSearch,是基于Lucene库的搜索引擎。它提供了一个分布式、多租户的全文搜索引擎,具有HTTP web接口和无模式JSON文档。根据DB引擎排名,Elasticsearch是最受欢迎的企业搜索引擎。ES的特点是分布式、高扩展以及近实时。那么,大规模数据量下ES是如何实现高性能检索的呢? 说

    2024年02月16日
    浏览(105)
  • 如何实现Web3去中心化云计算的大规模采用?

    随着区块链技术的迅猛发展,Web3去中心化云计算正在逐渐崭露头角。 它以分布式、安全和透明的特点,为用户和企业提供了许多独特的优势。 然而,要实现Web3去中心化云计算的大规模采用,仍然面临着一些挑战。本文将探讨这些挑战,并提出一些关键的解决方案,以推动

    2024年02月07日
    浏览(57)
  • 虚拟现实与虚拟现实:如何实现大规模多用户互动

    虚拟现实(Virtual Reality, VR)是一种使用计算机生成的3D环境来模拟或扩展现实世界的技术。它通过使用特殊的头戴式显示器和输入设备,让用户感觉自己在一个完全不同的环境中。虚拟现实技术的应用范围广泛,包括游戏、娱乐、教育、医疗、军事等领域。 虚拟现实与虚拟现实

    2024年02月20日
    浏览(46)
  • 【天衍系列 01】深入理解Flink的 FileSource 组件:实现大规模数据文件处理

    Apache Flink 是一个流式处理框架,被广泛应用于大数据领域的实时数据处理和分析任务中。在 Flink 中,FileSource 是一个重要的组件,用于从文件系统中读取数据并将其转换为 Flink 的数据流。本文将深入探讨 FileSource 的工作原理、用法以及与其他数据源的比较。 FileSource 是 Fli

    2024年02月21日
    浏览(52)
  • 阿里云化身“智能云管”,助力中国联通首次实现大规模平台自主运维

    中国联通阿里飞天平台运维团队首次实现大规模平台自主运维,阿里云 TAM 团队化身“智能云管”,携手中国联通开启运维合作新模式。 近日,中国联通阿里飞天平台运维团队(以下简称“联通阿里 MSP 团队”)首次独立进行联通 5 个专有云平台的一线运维工作,问题自解决

    2023年04月20日
    浏览(51)
  • LightFM:一款开源推荐系统框架,可以轻松实现大规模矩阵分解,快速、高效地处理大型矩阵

    作者:禅与计算机程序设计艺术 LightFM 是由 Yelp 开发的一款开源推荐系统框架,可以轻松实现大规模矩阵分解。该项目基于 TensorFlow 和 Keras 框架,可以快速、高效地处理大型矩阵。它具有以下特点: 提供了一种简单的方法来训练矩阵分解模型,即通过定义项间的交互矩阵和用

    2024年02月10日
    浏览(49)
  • Spring Boot与Apache Kafka实现高吞吐量消息处理:解决大规模数据处理问题

    现代数据量越来越庞大对数据处理的效率提出了更高的要求。Apache Kafka是目前流行的分布式消息队列之一。Spring Boot是现代Java应用程序快速开发的首选框架。综合使用Spring Boot和Apache Kafka可以实现高吞吐量消息处理。 Apache Kafka采用分布式发布-订阅模式具有高度的可扩展性和可

    2024年02月05日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包