全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

一种面向对象的多角色蚁群算法及其TSP问题求解

DOI: 10.13195/j.kzyjc.2013.1173, PP. 1729-1736

Keywords: 蚁群算法,面向对象,多角色,k-均值,旅行商问题,2-Opt

Full-Text   Cite this paper   Add to My Lib

Abstract:

蚁群算法的改进大多从算法本身入手或与其他算法相结合,未充分利用待解决问题所包含的信息,提升效果较为有限.对此,提出一种面向对象的多角色蚁群算法.该算法充分利用旅行商问题(TSP)对象的空间信息,采用??-均值聚类将城市划分为不同类别;同时,对蚁群进行角色划分,不同角色的蚁群针对城市类别关系执行各自不同的搜索策略,增强了蚁群的搜索能力,较大幅度地提高了求解质量.每进行一次迭代,仅各角色最优个体进行信息素更新,防止算法退化为随机的贪婪搜索.将精英策略与跳出局部最优相结合可避免算法的停滞.50个经典TSP实例仿真实验表明:所提出的算法可以在较少的迭代次数内获得或非常接近于问题的已知最优解;对于大规模TSP问题所得结果也远超所对比的算法.

References

[1]  Verma O P, Kumar P, Hanmandlu M, et al. High dynamic range optimal fuzzy color image enhancement using artificial ant colony system[J]. Applied Soft Computing, 2012, 12(1): 394-404.
[2]  Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem[J]. IEEE Trans on Evolutionary Computation, 1997, 1(1): 53-66.
[3]  Tang J, Ma Y, Guan J, et al. A Max-min ant system for the split delivery weighted vehicle routing problem[J]. Expert Systems with Applications, 2013, 40(18): 7468-7477.
[4]  Bullnheimer B, Hartl R F, Strauss C. A new rank based version of the ant system: A computational study[J]. Central European J for Operations Research and Economics, 1999, 7(1): 25-38.
[5]  Lutuksin T, Pongcharoen P. Best-worst ant colony system parameter investigation by using experimental design and analysis for course timetabling problem[C]. The 2nd Int Conf on Computer and Network Technology. Bangkok, 2010: 467-471.
[6]  孟祥萍, 片兆宇, 沈中玉, 等. 基于方向信息素协调的蚁群算法[J]. 控制与决策, 2013, 28(5): 782-786.
[7]  (Meng X P, Pian Z Y, Shen Z Y, et al. Ant algorithm based on direction-coordinating[J]. Control and Decision, 2013, 28(5): 782-786.)
[8]  Zhao N, Wu Z, Zhao Y, et al. Ant colony optimization algorithm with mutation mechanism and its applications[J]. Expert Systems with Applications, 2010, 37(7): 4805-4810.
[9]  郭蕴华, 袁成. 一种异步航迹关联的变异蚁群算法[J]. 电子学报, 2012, 40(11): 2200-2205.
[10]  (Guo Y H, Yuan C. A mutation ant colony algorithm for the asynchronous track correlation[J]. Acta Electronic Sinica, 2012, 40(11): 2200-2205.)
[11]  Cecilia J M, García J M, Nisbet A, et al. Enhancing data parallelism for ant colony optimization on gpus[J]. J of Parallel and Distributed Computing, 2013, 73(1): 42-51.
[12]  黎自强, 田茁君, 王奕首, 等. 求解平衡约束圆形Packing 问题的快速启发式并行蚁群算法[J]. 计算机研究与发展, 2012, 49(9): 1899-1909.
[13]  (Li Z Q, Tian Z J, Wang Y H, et al. A fast heuristic parallel ant colony algorithm for circles packing problem with the equilibrium constraints[J]. J of Computer Research and Development, 2012, 49(9): 1899-1909.)
[14]  李擎, 张超, 陈鹏, 等. 一种基于粒子群参数优化的改进蚁群算法[J]. 控制与决策, 2013, 28(6): 873-878.
[15]  (Li Q, Zhang C, Chen P, et al. Improved ant colony optimization algorithm based on particle swarm optimization[J]. Control and Decision, 2013, 28(6): 873-878.)
[16]  Huang C L, Huang W C, Chang H Y, et al. Hybridization strategies for continuous ant colony optimization and particle swarm optimization applied to data clustering[J]. Applied Soft Computing, 2013, 13(3): 3864-3872.
[17]  Chiang C W, Lee W P, Heh J S. A 2-Opt based differential evolution for global optimization[J]. Applied Soft Computing, 2010, 10(4): 1200-1207.
[18]  饶卫振, 金淳, 陆林涛. 考虑边位置信息的求解ETSP 问题改进贪婪算法[J]. 计算机学报, 2013, 36(4): 836-850.
[19]  (Rao W Z, Jin C, Lu L T. An improved greedy algorithm with information of edges’ location for solving the euclidean traveling salesman problem[J]. Chinese J of Computers, 2013, 36(4): 836-850.)
[20]  周永权, 黄正新, 刘洪霞. 求解TSP 问题的离散型萤火虫群优化算法[J]. 电子学报, 2012, 40(6): 1164-1170.
[21]  (Zhou Y Q, Huang Z X, Liu H X. Discrete glowworm swarm optimization algorithm for TSP problem[J]. Acta Electronic Sinica, 2012, 40(6): 1164-1170.)
[22]  张长胜, 孙吉贵, 欧阳丹彤. 一种自适应离散粒子群算法及其应用研究[J]. 电子学报, 2009, 37(2): 299-304.
[23]  (Zhang C S, Sun J G, Ouyang D T. A self-adaptive discrete particle swarm optimization algorithm[J]. Acta Electronic Sinica, 2009, 37(2): 299-304.)

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133