改进型蚁群算法在jobshop问题中的应用

《改进型蚁群算法在jobshop问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华东理工大学学报(自然科学版)Vol.32No.4466JournalofEastChinaUniversityofScienceandTechnology(NaturalScienceEdition)2006204文章编号:100623080(2006)0420466205改进型蚁群算法在JobShop问题中的应用陈知美,顾幸生(华东理工大学自动化研究所,上海200237)摘要:应用改进型蚁群算法解决车间作业调度问题。在原有标准蚁群算法的基础上采用了新的状态转移规则,讨论了各种不同的轨迹更新规则对仿真结果的影响,

2、并通过统计数据验证了改进型蚁群算法优于标准的蚁群优化算法。由于算法中的参数对算法的求解效率和求解结果都有一定的影响,所以对此也进行了初步的研究,得到了运行较好的参数取值范围。关键词:蚁群算法;车间作业调度问题;状态转移规则;轨迹更新规则中图分类号:O224文献标识码:AApplicationofImprovedAntColonySystemtoJobShopSchedulingProblemCHENZhi2mei,GUXing2sheng(ResearchInstituteofAutomation,EastChin

3、aUniversityofScienceandTechnology,Shanghai200237,China)Abstract:Thenoveltransitionruleandthedifferentpheromonereinforcementrulesarediscussedinthispaperwhenantcolonysystemsareappliedtominimizingthemake2spaninjobshopschedulingprob2lem.Thestatisticresultsverifyth

4、atimprovedantcolonysystemsaremoreefficientthanthestandardantcolonysystem.Thealgorithmparametersettingsseemtoplayacrucialroleinitsefficiencyanddeterminethequalityofsolutions,sosomestatisticanalysisforparametertuningisgiven.Keywords:antcolonysystem;jobshopschedu

5、lingproblem;nodetransitionrule;pheromonerein2forcementrule蚁群算法(AntColonyAlgorithm)来源于对自问题的特点,着重研究了新的状态转移规则与各种然界中蚂蚁能够找到从蚁巢到食物源的最短路径并不同的轨迹更新规则在具体求解过程中的有效性,能够适应环境变化情况的研究,是人们受到生物进并对算法中的参数对算法的求解效率和求解结果的化机理的启发提出的许多用以解决优化复杂问题的影响进行了探讨。方法之一。这种90年代初期才提出的新型进化算法[1]的第一个应用是

6、著名的旅行商问题(TSP)。1蚁群优化算法流程本文使用蚁群算法解决JobShop问题,针对该蚁群系统的算法表述如下:k只蚂蚁被随机或收稿日期:2005204219均匀地放在各个节点上。蚂蚁k要选择一个节点作基金项目:国家自然科学基金项目(60274043);国家高技术发展计划为移动目标时,Tabu表中的节点也就是蚂蚁k已经项目(2002AA412610)访问过的节点,不能作为下一步选择的节点。蚂蚁的作者简介:陈知美(19802),女,江苏南京人,硕士,研究方向:生产计划与调度,智能优化。转移可能性是能见度G(x,y

7、)和轨迹强度S(x,y)的通讯联系人:顾幸生,E2mail:xsgu@ecust.edu.cn增函数,也就是说,路径越近能见度越大,越容易被第4期陈知美,等:改进型蚁群算法在JobShop问题中的应用467选择;路径通过的蚂蚁越多,则边上留下的外激素越STij——工件i在生产单元j上的操作开始时gl多,轨迹强度就越强,同样也容易被选择。这些外激间。下标ig表示工件i的第g道工序,jl表示生产单素既会随通过的蚂蚁数量增加而增加,也会随时间元j的第l步操作;的流逝而按一定的函数关系消失。因为最短路径通Tij——工件i在

8、生产单元j上的完成时间。下gl过的蚂蚁数量较多,所以其上外激素的积累速度将标ig表示工件i的第g道工序,jl表示生产单元j比其他路径快。经过多次循环后,所有蚂蚁所走的路的第l步操作。就必然相同,也就得到最佳路径。具体流程如下:2.2模型建立(1)初始化各个参数。如蚂蚁数目、能见度、轨车间作业调度的最基本约束条件是:顺序约迹强度等;束——每道工序必须在它前面的