计算机科学 ›› 2014, Vol. 41 ›› Issue (7): 261-265.doi: 10.11896/j.issn.1002-137X.2014.07.054
王诏远,李天瑞,易修文
WANG Zhao-yuan,LI Tian-rui and YI Xiu-wen
摘要: 探讨了蚁群算法的几种并行方式与适用场景以及结合云计算编程框架MapReduce的可行性,并将局部搜索类蚁群优化算法抽象为几个组件,分别与MapReduce框架的几个接口对应实现,从而为该类蚁群优化算法在MapReduce框架下实现并行化提供了一种灵活、扩展性好的解决方案。最后通过旅行商问题的仿真实验验证了所提方法的有效性。
[1] Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[C]∥Proceeding of ECAL91.Paris,France,1991 [2] 段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005 [3] 杨学峰.蚁群算法求解TSP问题的研究[D].吉林:吉林大学,2010 [4] 张建勋,古志民,郑超.云计算研究进展综述[J].计算机应用研究,2010,27(2):429-433 [5] 和亮,冯登国,王蕊,等.基于MapReduce的大规模在线社交网络蠕虫仿真[J].软件学报,2013(7):1666-1682 [6] Dorigo M,Maniezzo V,Colorni A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,1996,26(1):29-41 [7] Dorigo M.Optimization,learning and natural algorithms[D].Politecnico di Milano,Italy,1992 [8] Dorigo M,Maniezzo V,Colorni A.Positive feedback as a searchstrategy[R].Technical report 91-016.Politecnico di Milano,Milano,Italy,1991 [9] Dorigo M,Gambardella L M.Ant colony system:A cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66 [10] Stutzle T,Hoos H H.MAX-MIN ant system[J].Future Generations Computer Systems,2000,16(8):889-914 [11] Chen S,Chien C.Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques[J].Expert Systems with Applications,2011,38(12):14439-14450 [12] Chen S,Chien C.Parallelized genetic ant colony systems for solving the traveling salesman problem[J].Expert Systems with Applications,2011,38(4):3873-3883 [13] Juang C,Lu C,Lo C,et al.Ant colony optimization algorithm for fuzzy controller design and its FPGA implementation[J].IEEE Transactions on Industrial Electronics,2008,55(3):1453-1462 [14] Goldberg D E,Holland J H.Genetic algorithms and machinelearning[J].Machine Learning,1988,3(2):95-99 [15] Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113 [16] White T.Hadoop:the definitive guide[M].O’Reilly,2012 [17] 夏卫雷,王立松.基于 MapReduce 的并行蚁群算法研究与实现[J].电子科技,2013,26(2):146-149 [18] 王会颖,倪志伟,吴昊.求解多维背包问题的MapReduce蚁群优化算法[J].计算机工程,2013(4):248-253 [19] 吴昊,倪志伟,王会颖.基于 MapReduce 的蚁群算法[J].计算机集成制造系统,2012,18(7):1503-1509 [20] 李士勇,陈永强,李研.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2004 [21] 潘巍,李战怀,伍赛,等.基于消息传递机制的MapReduce图算法研究[J].计算机学报,2011(10):1768-1784 [22] Reinelt G.TSPLIB—A traveling salesman problem library[J].ORSA Journal on Computing,1991,3(4):376-384 [23] Gaertner D,Clark K L.On Optimal Parameters for Ant ColonyOptimization Algorithms[C]∥Proceedings of the 2005International Conference on Artificial Intelligence(ICAI 2005).CSREA Press,2005:83-89 [24] Zhang J,Li T,Ruan D,et al.A parallel method for computing rough set approximations[J].Information Sciences,2012,194:209-223 |
No related articles found! |
|