网站首页 公文大全 个人文档 实用范文 讲话致辞 实用工具 心得体会 哲学范文 总结范文 范文大全 报告 合同 文书 信函 实用
  • 汇报体会
  • 节日庆典
  • 礼仪
  • 毕业论文
  • 评语寄语
  • 导游词
  • 口号大全
  • 其他范文
    • 百花范文网 > 实用范文 > 其他范文 > 求解TSP的变邻域蝙蝠算法

    求解TSP的变邻域蝙蝠算法

    时间：2023-01-28 17:00:08来源：百花范文网本文已影响人

    朱德鑫，蔡延光

    （广东工业大学自动化学院，广东广州，510006）

    旅行商问题(Traveling Salesman Problem，TSP)是一个经典的NP-hard组合优化问题。该问题具有重要的工程应用价值，在车间调度、物流运输等领域都有其应用。

    蝙蝠算法(BA)是一种受启发于蝙蝠觅食行为的算法，最早由Yang Xin-she于2010年提出。自然界中蝙蝠利用自身独特的生物结构，通过超声波探测的信息定位周围环境和猎物，以进行规划飞行路线和捕食猎物。蝙蝠算法就是模仿此类行为而创造的一种新型群体智能优化算法。目前在车间调度、工程优化等领域中均得到应用。

    本文提出一种变邻域蝙蝠算法(VNBA)，在传统蝙蝠算法上混合三种变邻域策略改善算法局部特性，同时加入惯性权重平衡算法前期的全局搜索和后期的局部搜索，改善传统算法易陷入局部最优的困境。

    旅行商问题可以描述为：一名销售员需要去往N个城市进行销售，已知各个城市的具体位置以及城市与城市间的具体距离，现需要规划一条路线，使得该路线能够经过每一个城市，且每个城市仅被经过一次，并最终回到出发点，同时总行程最短。假设遍历所有城市后形成的路线为：，则最短路径的求解为：

    其中，式（1）表示最小化路程，式（2）表示两个城市间的距离。

    2.1 蝙蝠速度和位置更新

    蝙蝠算法的速度、位置更新公式如式(3)(4)(5)所示。其中β∈[0, 1]是从均匀分布中抽取的随机量。fmin和fmax代表种群脉冲频率上下限，fi代表第i只蝙蝠个体的脉冲频率，x*则代表当前代数下全局最优的蝙蝠所处位置，表示t+1时刻下蝙蝠个体的位置和速度。

    2.2 蝙蝠响度和发射频更新

    当蝙蝠最优解更新时，调整蝙蝠个体响度A和发射频r：

    2.3 变邻域策略

    虽然在求解较为复杂的组合优化问题上，蝙蝠算法具有较好的全局搜索能力，但在求解后期时，蝙蝠算法容易出现收敛精度较低和陷入局部极值的问题，为此加入三个邻域策略，以提高算法的搜索性能。

    （1）2-opt策略

    （2）exchange策略

    （3）insert策略

    在变邻域蝙蝠算法的迭代过程中，为使局部搜索性能更优，搜索空间更为多样性，将同时使用以上三种策略，在对当前某个蝙蝠个体的解Xi使用某一邻域搜索后产生新解Xnew，若新解比原解更优则替换掉原解且在当前邻域中继续搜索，否则保留原解进入下一个邻域搜索，达到设定的迭代次数后，停止邻域搜索并保留邻域搜索最优解。

    2.4 惯性权重

    由蝙蝠算法速度更新公式可知，当蝙蝠算法的速度更新时，会将当前蝙蝠与全局蝙蝠对比更新以此达到加快收敛速度的目的，但这也容易让蝙蝠算法陷入局部最优，为了平衡好算法的全局和局部的搜索能能力，使得蝙蝠算法能够在算法搜索的前期能有更好的全局寻优能力，在算法搜索的后期能有更好的局部寻优能力，此处在蝙蝠速度更新中加入惯性权重ω，加入惯性权重后的公式如式(8)：

    其中ω的设置为了契合旅行商问题，将其离散化，具体权重ω如式(9)：

    其中，t为算法当前迭代次数，T为全局最大迭代次数。由式子可知，在算法前期，惯性权重较小，增强全局搜索能力，后期惯性权重大，使得与上一代蝙蝠的关联性增大，提升局部搜索能力。

    2.5 算法步骤

    在蝙蝠算法中加入三种变邻域优化策略和惯性权重后，VNBA算法步骤如下：

    Step1：初始化变邻域蝙蝠算法种群。

    Step2：通过计算个体适应值找出蝙蝠种群中的最优蝙蝠蝙蝠，并记录对应个体的位置及其适应度值。

    Step3：根据公式(1)(9)(3)更新每一只蝙蝠的脉冲频率fi、速度vi和位置xi，求解当前每只蝙蝠对应的适应度值，并与上一代的适应度值做比较，保留更优的个体。

    Step4：随机生成一个随机数R1，若R1大于ri，则将全局搜索的最优蝙蝠个体进行三种变邻域搜索，否则保留原来的最优蝙蝠个体。

    Step5：再随机生成一个随机数R2，若该数R2小于当前蝙蝠个体的响度Ai且新个体的适应度优于原个体的适应度时，则接受Step4中的个体解。同时更新个体i的响度A以及其脉冲发射率ri，否则不对其响度以及脉冲发射率进行更新。

    Step6：计算全部个体对应的适应度值并作对比排序，寻找到当代全局最优解。

    Step7：重复步骤Step3到Step6，直到迭代次数超过最大迭代次数时停止迭代，并且输出全局最优解。

    实验选取5组TSP标准算例作为实验算例，并与遗传算法(GA)和蚁群算法(ACO)作对比。VNBA算法参数为：种群大小N=100，脉冲频率fmin=0，fmax=1、脉冲响度A=0.9、脉冲发射率ri=0.9、常数α=0.9，γ=0.9、惯性权重ωmin=0.2，ωmax=1；
    GA算法参数为：种群大小N=100，变异概率Pm=0.05、交叉概率Pc=0.95、代沟GGAP=0.9；
    ACO算法参数参数为：种群大小N=100，信息素因子α=1，启发函数因子β=5，信息素挥发因子ρ=0.1，信息素释放总量Q=1。每组算例测试20次。

    由表1可知，VNBA算法Oliver30和Att48能找出最优解，其优化后的路径如图1、2所示。在求解50个点以上的TSP算例时，VNBA也能寻找到较优的解，且误差都在5%以内。同时VNBA的在各个算例的最优解都要优于GA、ACO算法的解，证明VNBA在求解TSP问题时的全局寻优性能更优。同时VNBA在各个算例中的平均解也更优，且平均解和最优解的差距较小，证明了VNBA算法也有较好的求解稳定性。

    表1 各算法性能对比分析

    图1 VNBA优化后的Oliver30路径图

    图2 VNBA优化后的Att48路径图

    猜你喜欢 响度算例邻域 基于混合变邻域的自动化滴灌轮灌分组算法农业工程学报(2022年7期)2022-07-09一种自适应响度补偿算法在音频重放中的应用无线互联科技(2022年2期)2022-04-20含例邻域逻辑的萨奎斯特对应理论逻辑学研究(2021年3期)2021-09-29融合t-分布随机邻域嵌入与自动谱聚类的脑功能精细分区方法波谱学杂志(2021年3期)2021-09-07听力学名词释义(2)听力学及言语疾病杂志(2020年2期)2020-05-20降压节能调节下的主动配电网运行优化策略电子技术与软件工程(2018年10期)2018-07-16提高小学低年级数学计算能力的方法速读·中旬(2018年4期)2018-04-28数字电视节目响度标准化的探讨演艺科技(2017年8期)2017-09-25论怎样提高低年级学生的计算能力读写算·教研版(2016年10期)2016-06-08试论在小学数学教学中如何提高学生的计算能力读写算·教研版(2016年6期)2016-03-28

    相关热词搜索：邻域 求解 蝙蝠

    • 范文大全
    • 说说大全
    • 学习资料
    • 语录
    • 生肖
    • 解梦
    • 十二星座
    最新文章

    推荐访问

    求解 蝙蝠 蝙蝠与雷达优秀教学设计 蝙蝠侠小丑经典语录 蝙蝠侠黑暗骑士语录 蝙蝠和雷达优质课 蝙蝠和雷达名师教学设计 蝙蝠和雷达名师教案 蝙蝠和雷达第六课 蝙蝠和雷达（教案） 邻域

    本文求解TSP的变邻域蝙蝠算法由百花范文网整理提供，版权归原作者、原出处所有。

    Copyright © 百花范文网 All Rights Reserved.