基于MapReduce的蚁群算法

• 论文 •

基于MapReduce的蚁群算法

吴昊，倪志伟，王会颖，

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

出版日期:2012-07-25 发布日期:2012-07-25

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

摘要/Abstract

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

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

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

中图分类号:

TP301

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

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

[1]	文一凭,王志斌,刘建勋,许小龙,康国胜. 云际协作环境下能耗与成本感知的工作流调度方法[J]. 计算机集成制造系统, 2021, 27(9): 2583-2591.
[2]	尚正阳,顾寄南,王建平. 求解带能力约束车辆路径优化问题的改进模拟退火算法[J]. 计算机集成制造系统, 2021, 27(8): 2260-2269.
[3]	满君丰,赵龙乾,彭成,李倩倩. 云边协同计算架构下大规模工厂接入的任务调度[J]. 计算机集成制造系统, 2021, 27(8): 2282-2294.
[4]	王奕祺,张晓冬. 基于仿真评价方法的适应性合作换线策略[J]. 计算机集成制造系统, 2021, 27(7): 1918-1928.
[5]	李文俊,杨学强,杜家兴. 基于云计算的装备保障信息系统集成[J]. 计算机集成制造系统, 2021, 27(7): 1941-1950.
[6]	尚正阳,顾寄南,潘家保. 考虑LIFO约束的2L-CVRP优化[J]. 计算机集成制造系统, 2021, 27(7): 2134-2143.
[7]	单子丹,李雲竹,盛晨辉. 云制造模式下差异化产品多时序生产优化[J]. 计算机集成制造系统, 2021, 27(6): 1681-1692.
[8]	彭定洪,黄子航,王铁旦,彭勃. 面向云计算部署方案评价的区间犹豫模糊双重妥协评价方法[J]. 计算机集成制造系统, 2021, 27(6): 1768-1779.
[9]	李永湘,姚锡凡,刘敏. 基于可靠性可信性分析的云制造服务组合优化[J]. 计算机集成制造系统, 2021, 27(6): 1780-1798.
[10]	董舒豪,徐志刚,常艳茹,秦开仲,朱建峰,苏开远. 考虑物料装卸点与搬运通道的多行设施布局[J]. 计算机集成制造系统, 2021, 27(5): 1269-1280.
[11]	王婕,耿秀丽. 基于直觉模糊余弦相似度的云制造服务质量评价[J]. 计算机集成制造系统, 2021, 27(4): 1128-1134.
[12]	高鹏,苏雍贺,靳健,谢祥颖,张长志,陶飞. 基于分布式光伏运维的多类型资源调度技术[J]. 计算机集成制造系统, 2021, 27(3): 787-799.
[13]	胡杨,吴锋,王红涛. 考虑稀缺服务与质量损失云制造服务组合问题[J]. 计算机集成制造系统, 2021, 27(12): 3639-3650.
[14]	潘燕华,王克,王平. 云计算环境下复杂产品价值链合作伙伴选择研究[J]. 计算机集成制造系统, 2021, 27(12): 3651-3658.
[15]	杨丽丽,李文龙,孔祥龙,许浩. 混合不确定性鲁棒协同优化设计方法[J]. 计算机集成制造系统, 2021, 27(11): 3282-3290.