粒子群算法在TSP中的应用及其LabVIEW实现

关注
粒子群算法在TSP中的应用及其LabVIEW实现www.shan-machinery.com

第 44卷第 4期 2018年 8月 信 息 化 研 究 Informatization Research V01.44 No.4 Aug.2018 粒子群算法在 TSP中的应用及其 LabVIEW 实现 蒋冬梅 (盐城工学院电气工程学院,盐城,224051) 摘 要:旅行商问题(Traveling Salesman Problem,TSP)是一种经典的、受到广泛研究的组合优化 问题之一。粒子群优化算法(Particle Swarm Optimization,PSO)是一种基于群体的进化算法,算法通 过微粒间的相互作用来发现复杂搜索空间中的最优区域。文章在前人工作的基础上,对标准PSO算法 进行了改进,引入交换子和交换序的概念,将 PSO算法应用于求解 TSP问题,并在 LabVIEW 平台下 实现。实验结果表明,改进的粒子群算法可以应用于TSP问题,且具有精度高的优点。 关键词:粒子群优化算法;旅行商问题;LabVIEW 中图分类号:TP391.4 O 引 言 旅行商问题(TSP)自1932年K.Menger提出 以来,已引起各领域许多研究者的兴趣。它是一 个典型的 NP完全问题,也是组合优化中研究最多 的问题之一,但至今尚未彻底解决。很多研究领 域出现的复杂优化问题可以被抽象概括为 TSP加 以求解,例如车辆路由问题、车间作业调度问题 等,因此找到能够有效解决 TSP的方法在理论上 和实际应用中都很有价值。 粒子群优化算法 (Particle Swarm Optimiza— tion,PSO)_1]是一种基于群体的进化算法,算法通过 微粒间的相互作用来发现复杂搜索空间中的最优区 域。由于粒子群算法在函数优化等领域有广阔的应 用前景,所以自算法提出以来,引起了相关领域众多 学者的关注和研究,成为演化计算研究的热点。 PSO算法已经被证明是一种有效的优化方法,并且 广泛应用于函数优化、神经网络训练以及模糊系统 控制等领域。 标准的PSO算法在求解旅行商问题时,容易 出现早熟和收敛速度慢的缺点。针对此问题,文 收稿 日期 :2018—05—05 · 24 · 章在前人工作的基础上,对标准 PSO算法进行了 改进,引入交换子和交换序的概念,将 PSO算法 应用于求解 TSP问题。实验结果表明,改进的粒 子群算法可以应用于 TSP问题,且具有精度高的 优点 。 1 TSP数学模型 设给定 N个城市的集合{C ,C ,⋯,CN),每两个 城市 Cj直接的距离为d( Cj),则旅行商问题定 义为 寻 找 一个 排 列 32一 (z1,z2,⋯,XN),五 ∈ {1,2,⋯,N),使得排列z的路径长度值最小,即: N-1 L( )一∑d(c Cx )+d(c .) (1) 2一 l 且满足 V i∈{1,2,⋯,』\,}, ∈ {1,2,⋯,N),使 得 — i。 这里设定每个城市之间都是连通的,且相邻城 市之间的距离与路径无关 ( ( , )一d(xj,五), 1≤ i, ≤ N)。每个城市只能被经过一次,且保证 被经过一次。目标函数为 L(z)。显然,算法的优化 目标是 minL(z) (2) 旅行商问题同样对应一些现实问题,例如应 第 44卷第 4期 蒋冬梅:粒子群算法在 TSP中的应用及其 LabVIEW 实现 ·研究与设计 · 用于物流行业中,如何确定最短路线、减少时间和 成本开支。因此,对旅行商问题进行研究有着重 要意义

https://www.shan-machinery.com