求解旅行商问题的基于类 Kruskal 的混合粒子群算法
Release Time:2019-03-10 Hits:
Indexed by: Journal Article
Date of Publication: 2014-06-25
Journal: 运筹与管理
Included Journals: CSCD、ISTIC、PKU
Volume: 23
Issue: 3
Page Number: 30-37
ISSN: 1007-3221
Key Words: 运筹学;混合粒子群算法;Kruskal;Greedy Heuristic;Lin-Kernighan;旅行商问题
Abstract: 本文针对求解旅行商问题的标准粒子群算法所存在的早熟和低效的问题，提出一种基于 Greedy Heuristic的初始解与粒子群相结合的混合粒子群算法（ SKHPSO ）。该算法通过本文给出的类Kruskal算法作为Greedy Heuristic的具体实现手段，产生一个较优的初始可行解，作为粒子群中的一员，然后再用改进的混合粒子群算法进行启发式搜索。 SKHPSO的局部搜索借鉴了Lin-Kernighan邻域搜索，而全局搜索结合了遗传算法中的交叉及置换操作。应用该算法对TSPLIB中的典型算例进行了算法测试分析，结果表明：SKHPSO可明显提高求解的质量和效率。