求解TSP问题的离散型萤火虫群优化算法

被引：75

作者：

周永权 ^{[1
,2
]}

黄正新 ^{[1
,3
]}

刘洪霞 ^{[1
]}

机构：

[1] 广西民族大学信息科学与工程学院

[2] 广西混杂计算与集成电路设计分析重点实验室

[3] 右江民族医学院网络中心

来源：

电子学报 | 2012年 / 40卷 / 06期

关键词：

萤火虫群优化算法; 离散萤火虫群算法; TSP问题; 2-Opt;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

基于求解TSP问题,提出一种离散型萤火虫群优化(DGSO)算法,该算法结合TSP问题特点,给出一种有效编码和解码方法,并定义适合编码的个体间距离计算公式和编码更新公式.同时,为增强算法求解TSP问题的局部搜索能力,加快算法的收敛速度,算法使用了操作简单的2-Opt优化算子.最后,通过对10个TSP问题进行仿真实验,实验结果表明本文提出的算法是在种群规模较小,迭代次数较少的情况下就可以收敛到已知最优解.在大规模TSP算例中算法获得的最优值与理论最优值的误差也在1%以下.

引用

页码：1164 / 1170

页数：7

共 10 条

[1] 基于混合粒子群优化算法的旅行商问题求解 [J].

俞靓亮 ;

王万良 ;

介婧 .

计算机工程, 2010, 36 (11) :183-184+187

[2] 一种自适应离散粒子群算法及其应用研究 [J].

张长胜 ;

孙吉贵 ;

欧阳丹彤 .

电子学报, 2009, 37 (02) :299-304

[3] 基于并行人工免疫算法的大规模TSP问题求解 [J].

戚玉涛 ;

焦李成 ;

刘芳 .

电子学报, 2008, (08) :1552-1558

[4] 解旅行商问题的一个新的遗传算法 [J].

韩丽霞 ;

王宇平 .

系统工程理论与实践, 2007, (12) :145-150

[5] 一种基于构建基因库求解TSP问题的遗传算法 [J].

杨辉 ;

康立山 ;

陈毓屏 .

计算机学报, 2003, (12) :1753-1758

[6] 针对模糊需求的VRP的两种2-OPT算法 [J].

祝崇隽 ;

刘民 ;

吴澄 ;

吴晓冰 .

电子学报, 2001, (08) :1035-1037

[7] Robot Algorithms for Localization of Multiple Emission Sources [J].

Mcgill, Kathleen ;

Taylor, Stephen .

ACM COMPUTING SURVEYS, 2011, 43 (03)

[8]

Glowworm swarm optimisation: a new method for optimising multi-modal functions[J] . K.N. Krishnanand,D.,Ghose.Int. J. of Computational Intelligence Studies . 2009 (1)

[9] Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions [J].

Krishnanand K.N. ;

Ghose D. .

Swarm Intelligence, 2009, 3 (2) :87-124

[10] Particle swarm optimization-based algorithms for TSP and generalized TSP [J].

Shi, X. H. ;

Liang, Y. C. ;

Lee, H. P. ;

Lu, C. ;

Wang, Q. X. .

INFORMATION PROCESSING LETTERS, 2007, 103 (05) :169-176

← 1 →