面向作业车间的自适应非均匀窗口蚁群算法

《面向作业车间的自适应非均匀窗口蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据第15卷第10期209年10月计算机集成制造系统ComputerIntegratedJⅥanufactu“ngSystemsVoI．15No．10Oct．209文章编号：1006—5911(2009)10--1973--06面向作业车间的自适应非均匀窗口蚁群算法黄明，刘鹏飞，梁旭(大连交通大学软件学院，辽宁大连116028)摘要：为纠正作业车间调度问题中蚁群算法搜索周期长、易陷入局部极小值的缺点，提出了一种改进的自适应非均匀窗口蚁群算法。首先，该算法通过自适应调整的非均匀窗口限制蚂蚁的移动范围，在缩短蚂蚁搜索周期的同时及时开辟新的解

2、空间；然后，根据蚂蚁的多态性提出，蚂蚁跳跃窗口策略，赋予算法良好的跳出局部极小的能力；最后，鉴于作业车间调度中一个工件在多个机器上加工的特点，新算法对蚂蚁状态转移概率中的启发函数进行了改进，提高了路径的启发程度。通过对MuthandThompson基准问题的仿真，验证了新算法的收敛性能。关键词：作业车间调度；自适应调整；蚂蚁跳跃窗口；启发函数；蚁群算法中图分类号：TP278文献标识码：AAntcolonyalgorithmorientedtoJobShopschedulingproblembasedonself-adaptiveandune

3、venwindowsHUANGMing，L儿，Peng—fei，LIANGXu(SoftwareTechnologyInstitute，DalianJiaotongUniversity，Dalian16028，China)Abstract：ToovercometheshortcomingsofantcolonyalgorithminfallingintolocalminimumvalueeasilyanditslongsearchcycleforJobShopschedulingproblem，animprovedself-adaptive

4、antcolonyalgorithmbasedondifferentsizewindowwasproposed．Firstly，theself-adaptiveunequalantwindowwasusedtolimitmovementrangesofantsinthenewalgorithm．Thestrategycouldreducethesearchingcycleofantsandfindnewspaceofsolutiontimely．Secondly，thewindowjumpingstrategyofantwaspropose

5、dbyusingthepolymorphiceharaeterisiticsofants．Iten—abledthenewalgorithmwiththegoodabilitytojumpoutofthelocalbest．Finally，consideringthecircumstancesunderwhichajobwasprocessedindifferentmachinesintheJobShopschedulingproblem，illuminatingfunctioninstatetransferprobabilitywasim

6、proved．Itimprovedtheilluminatingdegreeofant’sroute．ThenewalgorithmwassimulatedwiththeMuthandThompsonstandardproblem，andthesimulationresultshowedthattheconvergenceoftheproposedalgorithmwasimprovedsharply．Keywords：JobShopscheduling；self-adaptiveadjusting；antjumpingwindow；ill

7、uminatingfunction；antcolonyal—gorithm0引言蚁群算法(AntColonyAlgorithm，ACO)是由意大利学者Dorigo等人于20世纪90年代初期提出的一种新的仿生类进化算法‘1

8、，是求解作业车间调度问题(Job—shopSchedulingProblem，JSP)的有效方法之一[2]，其优点是算法原理简单，具有较强的鲁棒性，但搜索时间长，容易陷入局部极小点是其最收稿日期：2008—09-23；修订日期：2009一01—12。Received23Sep．2008；accepted12Jan．2009

9、．基金项目：大连市计划资助项目(2007A10GXll0)，辽宁省基金资助项目(20072161)；辽宁省教育厅资助项目(2008092)。Foundationitems：Pro