粒子群优化算法求解旅行商问题

粒子群优化算法求解旅行商问题

黄岚，王康平，周春光，庞巍，董龙江, 彭利

吉林大学计算机科学与技术学院，长春 130012

收稿日期:2003-07-10 修回日期:1900-01-01 出版日期:2003-10-26 发布日期:2003-10-26
通讯作者: 周春光

Particle Swarm Optimization for Traveling Salesman Problems

HUANG Lan, WANG Kang-ping, ZHOU Chun-guang, PANG Wei, DONG Long-jiang, PENG Li

College of Computer Science and Technology, Jilin University, Changchun 130012, China

Received:2003-07-10 Revised:1900-01-01 Online:2003-10-26 Published:2003-10-26
Contact: ZHOU Chun-guang

摘要/Abstract

摘要： 首先介绍粒子群优化的搜索策略与基本算法, 然后通过引入交换子和交换序的概念, 构造一种特殊的粒子群优化算法, 并用于求解旅行商问题. 实验表明了在求解组合优化问题中的有效性.

关键词: 粒子群优化算法, 旅行商问题, 组合优化

Abstract: This paper introduces the basic algorithm and search strategies of particle swarm optimization (PSO), via presenting the concepts of swap operator and swap sequence an algorithm of a kind of special particle swarm optimization is constructed and then proposes its application to traveling salesman problems(TSP). The experiments show the new PSO can achieve good results.

Key words: particle swarm optimization, traveling salesman problem, combinatorial optimization

中图分类号:

TP31

黄岚，王康平，周春光，庞巍，董龙江, 彭利. 粒子群优化算法求解旅行商问题[J]. J4, 2003, 41(04): 477-480.

HUANG Lan, WANG Kang-ping, ZHOU Chun-guang, PANG Wei, DONG Long-jiang, PENG Li. Particle Swarm Optimization for Traveling Salesman Problems[J]. J4, 2003, 41(04): 477-480.

[1]	蒋成, 郭向坤. 基于路径贡献度评判的双种群蚁群算法TSP问题求解分析方法[J]. 吉林大学学报(理学版), 2025, 63(6): 1694-1700.
[2]	史丰源, 欧阳丹彤, 张立明. 足够接近的旅行商问题研究综述[J]. 吉林大学学报(理学版), 2025, 63(1): 114-0123.
[3]	高铭晗, 王丽敏, 黄锐露, 张宇飞, 李明洋. 屋型拓扑粒子群优化算法与工程优化问题求解[J]. 吉林大学学报(理学版), 2024, 62(6): 1384-1390.
[4]	赵红梅, 肖明, 白宇, 王磊. 面向用户偏好的动态网页数据交互式查询算法[J]. 吉林大学学报(理学版), 2024, 62(2): 417-0422.
[5]	王晓瑜, 刘红卫, 王婷, 丁玉婉, 游海龙. 基于半定规划的多约束图划分问题[J]. 吉林大学学报(理学版), 2023, 61(3): 540-546.
[6]	隋振, 张天星, 吴涛, 陈华锐. 基于多种群空间映射遗传算法的立体仓库储位优化[J]. 吉林大学学报(理学版), 2022, 60(1): 127-0134.
[7]	于生宝, 房钰, 高丽辉, 刁庶. 基于改进粒子群优化算法的可控发射电流频率SHEPWM控制方法[J]. 吉林大学学报(理学版), 2020, 58(5): 1207-1214.
[8]	袁开银, 王峰. 基于指标选择和加权融合的无线传感器网络安全风险评估[J]. 吉林大学学报(理学版), 2020, 58(4): 937-943.
[9]	金晓民, 张丽萍, 李慧静. 控制活动轮廓演化的快速图像分割方法[J]. 吉林大学学报(理学版), 2020, 58(3): 639-644.
[10]	史肖冰, 郭德贵, 曹捷. 基于自适应Hata模型的无线电发射源定位方法[J]. 吉林大学学报(理学版), 2020, 58(1): 109-112.
[11]	郭玉洁, 张强, 袁和平. 一种双种群协同多目标粒子群优化算法及应用[J]. 吉林大学学报(理学版), 2019, 57(5): 1155-1162.
[12]	刘帅, 刘元宁, 庄述鑫, 侯铭楷, 陈静, 张水涵. 自适应优化Log-Gabor滤波器与动态径向基函数神经网络的虹膜识别[J]. 吉林大学学报(理学版), 2019, 57(2): 331-338.
[13]	张淑华, 李平. 基于组合智能算法的无线网络信道分配机制[J]. 吉林大学学报(理学版), 2019, 57(1): 139-144.
[14]	杨雪, 董红斌, 董宇欣. 改进的量子粒子群优化算法对多维多选择背包问题的求解[J]. 吉林大学学报(理学版), 2018, 56(6): 1461-1468.
[15]	王宏志, 姜方达, 周明月. 基于粒子群优化的认知无线电功率分配算法[J]. 吉林大学学报(理学版), 2018, 56(6): 1483-1487.