《电子测量技术杂志》发表论文赏析

基于Spark的并行k均值聚类模拟退火算法求解MMTSP

来源:电子测量技术杂志2022年第20期北京时间:

作者:孙鉴,李昊,刘凇佐,刘品,陈攀,雷冰冰

单位:1.北方民族大学,计算机科学与工程学院,宁夏 银川 750021; 2.图像图形智能处理国家民委重点实验室, 宁夏 银川 750021

摘要:多起点闭回路多旅行商问题是旅行商问题的扩展。针对这个问题文中提出了一种基于Spark框架的并行k均值聚类模拟退火算法。该算法首先采用k均值聚类算法将所有城市分类,然后对应每个类建立一个旅行商问题,并通过一种改进的模拟退火算法对旅行商问题求解,MMTSP的解由这些类的最短路径之和计算得出。所提算法采用先聚类再执行模拟退火算法的求解策略可以极大的缩减模拟退火的搜索空间,并且由于Spark框架可以将聚类算法分好的若干类并行求解,从而更快的得到MMTSP问题的最优解。选取TSPLIB数据库中若干测试实例进行仿真实验,对求解精度和运行时间两个方面进行测试,与其他几种相关算法进行对比实验。实验结果表明,与目前FCMPGA、IPGA、IWO等算法相比,求解精度提高了5%~40%,求解效率上对比其他算法提升1~5倍,尤其在K值较大时表现更优。

关键词:多旅行商问题;旅行商问题;k均值聚类;模拟退火算法

基金资助:国家自然科学基金项目(62062002,62102201);宁夏自然基金(2022AAC03289,2022AAC03245,2021AAC03034)北方民族大学中央高校基本科研业务费专项资金(FWNX09);北方民族大学校级一般项目(2021XYZJK01)

2022年20期其他文献查阅:

一款适用于5G通信频段的限幅滤波结构的设计

冲击波压力在分叉管道内的传播规律

多相电驱重构型车载充电系统绕组开路故障诊断与容错控制

多场景下的人体跌倒检测方法及应用

基于信息年龄的变电站业务无线接入选择算法

基于树莓派的EtherCAT主站设计与性能分析

基于脑电样本熵功率谱的VR诱发晕动症分析

基于Spark的并行k均值聚类模拟退火算法求解MMTSP

ADS-B技术在低空空域安全中应用的现状与展望

基于新型趋近律的PMSM反演滑模控制

改进蝗虫优化算法 在模糊神经网络PID控制中的研究

基于变截止频率的梯形离散磁链观测控制系统

基于单目深度估计和校准参数的距离测算方法

改进指数趋近律的炒药机模糊滑模温度控制方法

数据异质场景下的联邦学习模型校正与聚合

融合混合注意力和改进YoloX的铁路落石检测方法

基于Shuffle-Unet的视网膜血管分割研究

基于嵌入注意力机制的UNet-DB_ECA网络检测金具研究

基于图像增广与迁移学习的输电线路金具 多目标实时检测方法

改进ORB-SLAM2算法的关键帧选取及地图构建研究

基于深度学习的脊椎CT图像分割

应用于远距离视觉定位系统的特征图案研究

时间反转SH0波跨焊缝检裂纹缺陷研究

基于FPGA的金属异物检测系统设计

填文献完整题目 获取完整文献

填写需求
联系方式
注:学术顾问会在1小时内联系您,请留意!