基于MATLAB的混合型蚁群算法求解旅行商问题VIP免费

2005.9总第102期RCA4文章编号：1005-8451（2005）09-0004-04收稿日期：2005-01-06作者简介：尹晓峰，在读博士研究生；刘春煌，研究员。第14卷第9期Vol.14No.9研究与开发RESEARCHANDDEVELOPMENT计算机应用RAILWAYCOMPUTERAPPLICATION铁路达或出发的，按照客车、无调中转、有调中转、到达解体和自编始发的顺序进行接发车作业；对于解体作业，作为出发列车车流来源的车组所在车列按车组被编入出发列车的出发时刻排序，其余按到达时刻排序被编入列车出发时间最早的车列解体优先级最高。编组作业的优先级按出发列车的出发时刻依次递减；若同时出发，则最先集结完毕的优先级较高。3结束语本文提出了一种利用计算机仿真技术自动编制车站调度作业计划的方法。该方法具有以下特点：（1）车站作业过程的模拟可以计划时段内任一时刻为起始点，反复进行模拟，且模拟时间可伸缩，滚动编制作业计划。计划的编制不再拘泥于实际作基于MATLAB的混合型蚁群算法求解旅行商问题尹晓峰，刘春煌（铁道科学研究院电子计算技术研究所，北京100081）摘要：蚁群算法是受自然界中蚁群搜索食物行为启发而提出的一种智能优化算法，通过介绍蚁群觅食过程中基于信息素的最短路径的搜索策略，给出基于MATLAB的蚁群算法在旅行商问题中的应用，针对蚁群算法存在的过早收敛问题，加入2-opt方法对问题求解进行局部优化。计算机仿真结果表明，这种混合型蚁群算法对求解旅行商问题有较好的改进效果。关键词：旅行商问题；组合优化；蚁群算法；改进中图分类号：U29-39文献标识码：AHybridapproachbasedonAntColonySystemforsolvingtravelingsalesmanproblemYINXiao-feng,LIUChun-huang(InstituteofComputingTechnology,ChinaAcademyofRailwaysSciences,Beijing100081,China)Abstract:Antalgorithmshavebeeninspiredbythebehaviorofrealantcolonies,inparticular,bytheirforagingbehavior.Itwasintroducedthemainideaofthisdistributedalgorithmwhichwastheindirectcommunicationofantsbasedonpheromonetrails,proposedcodeswritteninMATLAB.Computersimulationshowdthatapplyahybridapproachofantalgorithmwith2-optcouldefficientlyfindbetterminimumbeyondprematureconvergencefortravelingsalesmanproblem.Keywords:travelingsalesmanproblem;combinatorialoptimization;antcolonyalgorithm;improvement蚁群算法（antcolonyalgorithm）首先由意大利科学家M.Dorigo等人提出，称为蚁群系统（antsystem,AS）。在求解二次分配、图着色问题、车辆调度、集成电路设计以及通信网络负载问题的处理中都取得了较好的结果。旅行商问题（TSP,TravelingSalesmanProblem）业中分班计划、阶段计划和调车作业计划3步编制的形式，编制更为灵活。（2）在作业计划的编制过程中，当需要对计划进行调整时，结束当前的模拟进程，以调整时刻为模拟起点，重新进行模拟，制定作业计划，实现计划的调整，编调合一。这样做加大了计算机的工作量，但减少了计划调整时的人工工作量，而且调整是对后续计划的重新编制，从而加大了计划的可调范围。参考文献：[1]杨浩，何世伟.铁路运输组织学[M].北京：中国铁道出版社，2001.[2]杨肇夏.计算机模拟及其应用[M].北京：中国铁道出版社，1999.[3]齐欢，王小平.系统建模与仿真[M].北京：清华大学出版社，2004.2005.9总第102期RCA5被认为是一个基本问题，是在1859年由威廉·汉密尔顿爵士首次提出的。所谓TSP问题是指：有N个城市，要求旅行商到达每个城市各一次，且仅一次，并回到起点，且要求旅行路线最短。这是一个典型的优化问题，对一个具有中等顶点规模的图来说，精确求解也是很复杂的，计算量随着城市个数的增加而呈指数级增长，即属于所谓的NP问题。TSP在工程领域有着广泛的应用，并常作为比较算法性能的标志。如网络通讯、货物运输、电气布线、管道铺设、加工调度、专家系统、柔性制造系统等方面，都是TSP广泛应用的领域。求解算法包括贪婪法（GM）、极小代数法（MA）、模拟退火法（SA）和遗传算法（GA）等。而应用蚁群算法求解旅行商问题是近年来研究的新方向，由于其并行性与分布性，特别适用于大规模...