MapReduce-based ant colony optimization

• Article •

MapReduce-based ant colony optimization

WU Hao, NI Zhi-wei, WANG Hui-ying,

1.School of Management, Hefei University of Technology, Hefei 230009, China; 2.Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education,Hefei University of Technology, Hefei 230009, China;3.Department of Electronics and Information, Anhui Finance & Trade Vocational College, Hefei 230601,China

Online:2012-07-25 Published:2012-07-25

基于MapReduce的蚁群算法

吴昊，倪志伟，王会颖，

1.合肥工业大学管理学院，安徽合肥230009；2.合肥工业大学教育部过程优化与智能决策重点实验室，安徽合肥230009；3.安徽财贸职业学院电子信息系,安徽合肥230601

Abstract

Abstract: The researches on solving problems with Ant Colony Optimization(ACO)distributed parallel under cloud computing were less, and ACO had defects in long search time and convergence in non-optimal solution. When the scale of problem was large, it was too hard to solve. Therefore, MapReduce-based ACO was proposed by using cloud computing to parallel ACO. In this algorithm, dividing conquer and simulated annealing algorithm were merged into ACO to improve the defects. It was also applied to solve large-scale of Traveling Salesman Problem(TSP). The simulation experiment got a well effect and the new solutions of test gr666 were obtained.

Key words: cloud manufacturing, cloud computing, ant colony optimization, divide conquer, simulated annealing algorithm, traveling salesman problem

摘要： 云计算环境下应用蚁群算法分布式并行对问题进行求解的研究较少，且蚁群算法存在搜索时间长和易收敛于非最优解的缺陷，当问题的规模较大时求解困难。为此应用云计算技术将蚁群算法并行化，提出基于MapReduce的蚁群算法。该算法将分治思想和模拟退火算法融入蚁群算法，改进其缺陷，并应用于求解较大规模的旅行商问题。仿真实验取得了较好的效果，且获得了测试实例gr666的新解。

关键词: 云制造, 云计算, 蚁群算法, 分治, 模拟退火算法

CLC Number:

TP301

WU Hao,, NI Zhi-wei,, WANG Hui-ying,,+. MapReduce-based ant colony optimization[J]. .

吴昊,,倪志伟,,王会颖,,+. 基于MapReduce的蚁群算法[J]. .

[1]	. Energy and cost aware method for scheduling workflows in jointcloud cooperation environment [J]. , 2021, 27(9): 2583-2591.
[2]	. Improved simulated annealing algorithm for capacitated vehicle routing problem [J]. , 2021, 27(8): 2260-2269.
[3]	. Task scheduling method for large-scale factory access in cloud and edge collaborative computing architecture [J]. , 2021, 27(8): 2282-2294.
[4]	. Adaptive strategy of cooperative changeover based on simulation evaluation method [J]. , 2021, 27(7): 1918-1928.
[5]	. Equipment support information system integration based on cloud computing [J]. , 2021, 27(7): 1941-1950.
[6]	. Multi-timing production of differentiated products in cloud manufacturing mode [J]. , 2021, 27(6): 1681-1692.
[7]	. Interval hesitant fuzzy double compromise evaluation method for cloud computing deployment evaluation [J]. , 2021, 27(6): 1768-1779.
[8]	. Cloud manufacturing service composition optimization based on reliability and credibility analysis [J]. , 2021, 27(6): 1780-1798.
[9]	. Multi-row facility layout considering material loading/unloading points and handling passages [J]. , 2021, 27(5): 1269-1280.
[10]	. Evaluation of cloud manufacturing service quality evaluation based on intuitionistic fuzzy cosine similarity [J]. , 2021, 27(4): 1128-1134.
[11]	. Multi-type resource scheduling technology based on distributed photovoltaic operation and maintenance [J]. , 2021, 27(3): 787-799.
[12]	. Ant colony labor division algorithm for position selection in circle packing problem [J]. , 2021, 27(12): 3578-3590.
[13]	. Incorporating service scarcity and quality loss into cloud manufacturing service composition [J]. , 2021, 27(12): 3639-3650.
[14]	. Partner selection of complex product value chain in cloud computing [J]. , 2021, 27(12): 3651-3658.
[15]	. Robust collaborative optimization method under mixed uncertainty [J]. , 2021, 27(11): 3282-3290.