资源描述：
《flow shop问题的蚁群优化调度方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2003年5月系统工程理论与实践第5期 文章编号:100026788(2003)0520065207Flowshop问题的蚁群优化调度方法王笑蓉,吴铁军(浙江大学工业控制技术国家重点实验室,浙江大学智能系统与决策研究所,浙江杭州310027)摘要:提出了一种新颖的蚁群优化算法,用于解决流水作业(flowshop)的优化调度问题L算法中,流水作业调度问题以结点或弧模式有向图表示,人工蚁受有向图上信息素踪迹的指引,在图上搜索并一步步构造出问题的可行解L算法中的信息素踪迹更新过程作为蚁群间的间接通信机制,将引导整个蚁群收敛到问题的优化解L信息素踪迹更新过程中的停
2、滞状态脱离机制以及信息素踪迹限制机制能帮助人工蚁跳出局部最优解L算法局部搜索过程中采用的基于关键路径的邻域结构缩小了问题的搜索空间L与其他算法在Taillard流水作业调度测试问题集上的比较试验表明,本算法性能更优,且具有更强的自适应和鲁棒性L关键词:蚁群优化;进化计算;流水作业调度;邻域搜索中图分类号:TP278文献标识码:AAnAntColonyOptimizationAlgorithmforFlowshopSchedulingWANGXiao2rong,WUTie2jun(NationalLaboratoryofIndustrialControlTe
3、chnology,InstituteofIntelligentSystems&DecisionMaking,ZhejiangUniversity,Hangzhou310027,China)Abstract:AnovelAntColonyOptimizationalgorithmispresentedforflowshopschedulingproblem.Inthealgorithm,theflowshopschedulingproblemisrepresentedbyadirectionalgraph.Guidedbypheromonetrail,eac
4、hartificialanttravelsinthegraphiterativelytoconstructitstourthatrepresentsafeasiblesolution.Thepheromonetrailupdatingprocedureactsasanindirectcommunicationmechanismwithintheantcolony,leadingalltheantstoconvergetogoodtours.Thestagnationstepoutmechanismandthepheromonetraillimitmecha
5、nisminpheromonetrailupdatingprocedurearedevelopedtohelpantssteppingoutofstagnationeffectively.Thecriticalblockbasedneighborhoodstructureoftheprobleminthelocalsearchprocedurereducesthesearchingspaceoftheproblemandincreasestheprobabilityofantsfindinggoodsolutions.Comparisonswithothe
6、rwell2performedalgorithmsonTaillard′sbenchmarkproblemsshowthatthealgorithmproposedinthispaperperformsbetterandhasstrongeradaptabilityandrobustness.Keywords:antcolonyoptimization(ACO);evolutionarycomputing;flowshopscheduling;localsearch1 引言高维的排列流水作业(Flowshop)调度问题由于具有NP2hard或NP2comp
7、lete的计算复杂性,研究人员提出了许多启发式方法L这些启发式方法分为两类:构造型的基于问题的启发式方法(ConstructiveAd2[1]HocHeuristic)和通用型自然启发式方法(Meta2Heuristic)L在前一类方法中,NEH算法的总体性能最[2][3]好L后一类方法有模拟退火SA,遗传算法GA,禁忌搜索TS,最大最小蚂蚁算法MAX2MINAS,在[4][2]一组Taillard标准测试问题集上,Fast2TS算法效果最好,但该算法采用了NEH算法的结果作为初始解L[5]本文在Dorigo的蚁群系统算法(AntColonySystem,
8、ACS)的基础上,提出一种新的蚁群优化算法,用于解决排列流水作业的
