求解旅行商问题的离散人工蜂群算法

《求解旅行商问题的离散人工蜂群算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第25卷第5期2016年10月运筹与管理0PERATl0NSRESEARCHANDMANAGEMENTSCIENCEV01．25，No．5Oct．2016求解旅行商问题的离散人工蜂群算法段渊1，向毅2，陈刚3(1．广东科技学院基础部，广东东莞523083；2．广东白云学院基础部，广东广州510450；3广东科技学院计算机系，广东东莞523083)摘要：本文提出了一种新的求解旅行商问题(TSP)的离散人工蜂群算法(DABC)。以基本人工蜂群算法为框架，采用路径编码的方式，综合运用离散交叉算子，逆转算子，免疫算子和单／多步2-

2、opt算子以帮助雇佣蜂，观察蜂和侦察蜂产生新食物源。选择TSPLIB中典型的TSP实例进行仿真实验，运用多项性能指标对DABC算法进行评估。实验结果表明本文算法是解决TSP问题的一种非常有效的新方法。关键词：运筹学；离散人工蜂群算法；组合优化；旅行商问题中图分类号：0229文章标识码：A文章编号：1007—3221(2016)05—014l-06doi：10．12005／orms．2016．0174ADiscreteArtificialBeeColonyAlgorithmforTravelingSalesmanProble

3、mDUANYuanl，XIANGYi2，CHENGan93(1．DepartmentofBasicCourses，GuangdongUniversityofScienceandTechnology，Dongguan523083，China；2．DepartmentofBasicCourses，GuangdongBaiyunUniversity，Guangzhou510450，China；3．DepartmentofComputerSciences，GuangdongUniversityofScienceandTechnol

4、ogy，Dongguan523083，China)AbstractiThispaperproposesanewdiscreteartificialbeecolony(DABC)algorithmforsolvingtravelingsales-manproblems(TSP)．TheDABCisbasedonthebasicABCalgorithm，anditsyntheticallyutilizesthediscretecrossoveroperator，inverseoperator，immuneoperatorand

5、single／muhiplesteps2-optoperatortohelptheem-ployedbees，onlookerbeesandscoutbeesproducenewfoodsources．TypicalTSPinstancesareselectedfromTSPLIBinordertoconductthesimulationexperiment．TheDABCisevaluatedbyusingsomeperformancemet-rics，anditisshownbytheexperimentalresul

6、tsthattheproposedalgorithmisaquiteeffectivenewapproachforhandlingTSPproblems．Keywords：operationalresearch；discreteartificialbeecolonyalgorithm；combinatorialoptimization；travelingsalesmanproblem0引言人工蜂群算法(ABC)是由Karaboga和Basturk提出的一种模拟蜜蜂采蜜过程的智能优化算法⋯。在算法中，整个蜂群包含三种不同的蜜

7、蜂，分别为：雇佣蜂(employedbees)，观察蜂(onlookerbees)和侦察蜂(scoutbees)。在执行过程中，每个食物源被编码成一个“解”，并赋予一个适应度。首先，由每个雇佣蜂根据其所对应的解(食物源)及该解的“邻居”，产生一个新的解。如果新解的适应度高于原来的解，则用新解替换旧解，否则丢弃新解。然后，每个观察蜂根据雇佣蜂提供的食物源信息(即适应度)采用轮盘赌的方式选择一个食物源，运用与雇佣蜂类似的机制试着改善该食物源。最后，如果某个食物源在连续“limit”次迭代中都没有得到提高，则其对应的雇佣蜂转化为

8、侦察蜂。侦察蜂会根据搜索空间产生一个可行的随机解¨’”。重复上述过程，直到终止条件得到满足。人工蜂群算法最初是为解决连续优化问题而提收稿日期：2014-10-10基金项目：广东省教育厅创新人才项目(自然科学类2014KQNcx236)作者简介：段渊，男，硕士，副教授，研究方向：运筹与控制，智能信息分析与