工件排序的改进蚁群算法优化.pdfVIP

上 海理 工 大 学 学报 第 33卷 第4期 J．UniversityofShanghaiforScienceandTechnology Vo1．33 No．4 2011 文章编号：1007—6735(2011)04—0362—05 工件排序的改进蚁群算法优化 王欣盛， 马 良 (上海理工大学 管理学院) 摘要：就工件排序 问题中的一种类型设计了融合局部改进策略的蚁群算法进行求解，并用Delphi 在计算机上实现了相应的算法软件．经大量算例测试，获得了较好的效果，验证了算法的可行性和 有效性． 关键词：排序 问题；蚁群算法；组合优化 中图分类号：022 文献标志码 ：A hImp．prroovveeddaannttccoolloonnyyopottiimm iizz~atttiioonn t’orSsCchheedduulliinngporroobblleem WANGXin—sheng， MALiang (UniversityofShanghaifo ScienceandTechnology，Shanghai200093，China) Abstract：Combinedwiththelocalsearchingstrategy，anantcolonyoptimizationalgorithm was proposedforakindofschedulingproblems．Thealgorithm iscodedinDelphiandrunsonmicrocom． purer．Bysolvingseriesofexperimentalexamples，themodifiedalgorithm wastestedandvalidated withsatisfactoryresultsachieved．Thecomputationalresultsprovethefeasibilityandeffectiveness ofthealgorithm forsolvingschedulingproblems． Keywords~schedulingproblem ；antcolonyalgorithm ；sombinatorialoptimization 工件排序问题_1]是组合优化中的著名难题，由 本文主要针对一类工件排序问题设计了一种改 于其一般情形下的NP(nondeterminsticpolynomi— 进的蚁群算法，并在计算机上实现了相应的软件程 a1)难解性，人们一直在不断地对其进行研究．而排 序 ，经大量算例测试，获得 了较好的效果． 序问题在现实中的应用，如航班着陆排序、汽车组装 线排序等，更是对人们的 日常生活和工作有着重大 1 问题概述 的影响． 自20世纪90年代以后，来 自自然界的仿生类 考虑单工序、多品种、多机器工件加工排序 问 算法开始引起人们的关注，尤其是在解决组合优化 题，即有多个品种的工件，其中，每个工件只有一道 难题方面，得到了一系列的尝试和深入研究．其中， 加工工序，众多工件同时在多台加工机器上并行加 源 自生物世界的蚁群算法在近十几年里获得了长足 工，具体描述为： 的发展l2j． 收稿Et期：2010—06—09 作者简介：王欣盛(1988一)，男，本科．研究方向：系统科学．E-mail：wangxsh42@126．corn 马 良(联系人)，男，教授．研究方向：智能优化．E—mail：maliang@usst．edu．cn 第4期 王欣盛，等 ：工件排序的改进蚁群算法优化 363 有 件工件 ，Y台不同种类的机器，每个工件 下的轨迹信息素越多，轨迹强度就越强，也越容易 可以在任何一台机器上加工，第 i件工件在第