求解二次指派问题的最优迭代最大最小蚂蚁算法.pdf

《求解二次指派问题的最优迭代最大最小蚂蚁算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、JournalofComputerApplicationsISSNlo01．90812014—01一lO计算机应用，2014，34(1)：199—203C0DENJYIIDUhttp：／／www．joca．cn文章编号：1001—9081(2014)01-0199—05doi：10．11772／j．issn．1001—9081．2014．01．0199求解二次指派问题的最优迭代最大最小蚂蚁算法牟廉明，戴锡笠，李坤，贺灵悦(1．内江师范学院数学与信息科学学院，四川内江641100；2．四川省高等学校数值仿真重点实验室(内江师范学院)，四川内江641100

2、)(通信作者电子邮箱mlianming@163．com)摘要：为提高二次指派问题的求解质量，设计了一个有效的最大最小蚂蚁求解算法。首先，运用最优迭代思想，让每只蚂蚁从当前最优路径中随机地选择位置及其对应的任务作为下一轮迭代的初始值，增强每轮搜索的有效性；其次，采用加入新任务后目标值的增量作为启发式因子来引导状态转移，增加每步搜索的目的性；然后，应用多精英策略来进行信息素更新，增加解的多样性；并设计有效的双重变异技术来提高解的质量，提高算法的收敛速度；最后，应用QAPLIB数据集进行了大量实验，结果表明：该算法在二次指派问题的求解质量和稳定性上显著优于其

3、他算法。关键词：二次指派问题；最优迭代；最大最小蚂蚁算法；双重变异；启发因子中图分类号：TP301．6文献标志码：AOptimaliterativemax-minantsystemforsolvingquadraticassignmentproblemMOULianming'，DAIXili，LIKun，HELingyue(1．CollegeofMat~maticsandInformationScience，NeijiangNormalUniversity，NeijiangSichuan641100，China；2．KeyLaboratoryofNum

4、ericalSimulationofSichuanProvince(NeijiangNormalUniversity)，NeijiangSiehuan641100，China)Abstract：InordertoimprovethequalityofthesolutioninsolvingQuadraticAssignmentProblem(QAP)，aneffectiveMax—MinAntSystem(MMAS)wasdesigned．Firstly，byusingoptimaliterationidea，thelocationanditscorr

5、espondingtaskwereselectedrandomlyfromthecurrentoptimaltourastheinitialvalueofnextiteration，soastoenhancetheefectivenessofeachsearchinginMMAS．Secondly，inordertoincreasethepurposeofthesearchineverystep，theincrementalvalueoftargetfunctionafteraddingnewtaskwasusedastheheuristicfacto

6、rtoguideefectivelythestatetransition．Then，thepheromonewasupdatedbyusingthemulti—elitiststrategysothatitcouldincreasethediversityofthesolution．Andanefectivedouble—mutationtechniquewasdesignedtoimprovethequalityofsolutionandacceleratethealgorithmconvergencespeed．Finally．alargenumb

7、erofdatasetsfromQAPLIBwereexperimented．Theexperimentalresultshowsthattheproposedalgorithmissignificantlybetterthanotheralgorithmsinaccuracyandstabilityonsolvingquadraticassignmentproblem．Keywords：QuadraticAssignmentProblem(QAP)；optimaliteration；Max—MinAntSystem(MMAS)；double—muta

8、tion；heuristicfactor所有排列构成的集合。0引言许多学者对该问题进行了卓有成