基于MapReduce的蚁群算法[]-大数据文档资料.pptx

文章编号：1006-5911(2012)07-1503-07

基于MapReduce的蚁群算法

吴昊1,2,倪志伟1,2,王会颖1,2,3+

(1.合肥工业大学管理学院，安徽合肥230009;

2.合肥工业大学教育部过程优化与智能决策重点实验室，安徽合肥230009;

3.安徽财贸职业学院电子信息系，安徽合肥230601)

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

关键词：云制造；云计算；蚁群算法；分治；模拟退火算法；旅行商问题

中图分类号：TP301文献标志码：A

MapReduce-basedantcolonyoptimization

WUHao1,2,NIZhi-wei1,2,WANGHui-ying1,2,3+

(1.SchoolofManagement,HefeiUniversityofTechnology,Hefei230009,China;

2.KeyLaboratoryofProcessOptimizationandIntelligentDecision-making,MinistryofEducation,

HefeiUniversityofTechnology,Hefei230009,China;

3.DepartmentofElectronicsandInformation,AnhuiFinanceTradeVocationalCollege,Hefei230601,China)Abstract:TheresearchesonsolvingproblemswithAntColonyOptimization(ACO)distributedparallelundercloudcomputingwereless,andACOhaddefectsinlongsearchtimeandconvergenceinnon-optimalsolution.Whenthescaleofproblemwaslarge,itwastoohardtosolve.Therefore,MapReduce-basedACOwasproposedbyusingcloudcomputingtoparallelACO.Inthisalgorithm,dividingconquerandsimulatedannealingalgorithmweremer-gedintoACOtoimprovethedefects.Itwasalsoappliedtosolvelarge-scaleofTravelingSalesmanProblem(TSP).Thesimulationexperimentgotawelleffectandthenewsolutionsoftestgr666wereobtained.

Keywords:cloudmanufacturing;cloudcomputing;antcolonyoptimization;divideconquer;simulatedannealingal-gorithm;travelingsalesmanproblem

收稿日期：2012-01-18;修订日期：2012-04-14。Received18Jan.2012;accepted14Apr.2012.

基金项目：国家863计划资助项目(2011AA040501);国家社会科学基金资助项目(10CGL024);安徽省教育厅自然科学重点资助项目(KJ2011A006)。Founda