硕士论文-基于蚁群算法的港口泊位调度优化与仿真.doc

《硕士论文-基于蚁群算法的港口泊位调度优化与仿真.doc》由会员分享，可在线阅读，更多相关《硕士论文-基于蚁群算法的港口泊位调度优化与仿真.doc（60页珍藏版）》请在三一文库上搜索。

1、基于蚁群算法的港口泊位调度优化与仿真分 类 号 密 级 U D C 单位代码 10151 基于蚁群算法的港口泊位调度优化与仿真指 导 教 师职 称教授学位授予单位大连海事大学申请学位级别学科（专业）管理科学与工程论文完成日期2010-5-5答辩日期2010-6-26答辩委员会主席- 45 -Port Berth Scheduling Optimization and Simulation Based on Ant Colony Optimization A thesis Submitted toDalian Maritime UniversityIn partial fulfillment o

2、f the requirements for the degree ofMaster of EngineeringByWang Hui(Management Science and Engineering) Dissertation/Thesis Supervisor: Professor Liu Wei05 2010大连海事大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：本论文是在导师的指导下,独立进行研究工作所取得的成果，撰写成博/硕士学位论文 “基于蚁群算法的港口泊位调度优化与仿真” 。除论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标

3、明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成果。本声明的法律责任由本人承担。学位论文作者签名： 学位论文版权使用授权书本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士学位论文全文数据库（中国学术期刊（光盘版）电子杂志社）、中国学位论文全文数据库（中国科学技术信息研究所）

4、等数据库中，并以电子出版物形式出版发行和提供信息服务。保密的论文在解密后遵守此规定。本学位论文属于： 保 密 在 年解密后适用本授权书。 不保密 （请在以上方框内打“” ）论文作者签名： 导师签名： 日期： 年 月 日摘要在全球贸易经济越来越多的聚焦在中国的同时，为了迅速与国际贸易接轨，中国经济贸易进入快速增长时期。港口也承担起了国内外贸易的重要枢纽。但是随着国内经济贸易迅速发展，对港口的吞吐量及运营能力的要求也越来越高。目前港口的吞吐能力和港口与日俱增的业务量成为目前港口业的主要矛盾。这不仅影响到港口的运营成本以及客户的满意程度，也是影响港口竞争能力的重要因素之一。在港口运营系统中，泊位作为

5、限制港口工作效率、吞吐量的重要环节之一，泊位的调度近年来成为港口管理者以及学者研究的重要内容。因此，如何提高泊位这个环节的运作能力，在现有的有限资源的条件下，尽可能的减少船舶在港时间，增加港口的吞吐能力是本文的主要研究对象。本文采取优化算法与仿真模型相结合的研究方法，根据泊位系统的特点，分析影响船舶停泊时间的因素，引入蚁群算法优化，将泊位调度问题转化为旅行商问题，以所有在港船舶时间最短为目标函数。同时综合考虑了岸桥资源对船舶在港时间的影响，建立数学模型，得到最佳调度方案，缩短船舶在港等待时间总和。同时利用仿真软件ProModel对泊位系统的工作流程建立仿真模型，模拟船舶到港，泊位分配及岸桥卸货

6、整个过程。建立两个仿真模型分别模拟船舶先来先服务的泊位调度方案，以及通过蚁群算法优化得到的最佳泊位调度方案，比较这两种方案船舶在港的时间。再次验证泊位调度优化结果的有效性，同时观察在不同的调度方案下，系统中的资源及各个环节的利用率等数据，以更好的指导港口实际的泊位调度。关键词：港口；泊位调度；蚁群算法；ProModel仿真模拟ABSTRACTWith the attention of global trade and economics focusing on China, international trade and economics of China has turning into

7、a quick developing period in order to meet the pace and need of global economics. Port is one of the most significant nexus connecting the global and domestic economics. However, along with the high speed of the development of international trade and economics, the requirement of the throughput and

8、capacity of operation is becoming higher then ever before. The principal contradiction of port industry is incompatible of throughput capacity and the increasing service need to the port which will not only affect the cost of port management and the satisfactory of the customer, but also the competi

9、tiveness of the port. In the operation of the port system, berth is one of the most important factors of that related to the efficient of port operation and throughput. Berth scheduling has become an important research these years. The main study object of this paper is focused on improving the capa

10、city of berth operation with limited resource we have now, in order to reduce the overall time vessels spent in the port.This paper utilizes the combination of optimized algorithm and simulation model. According to the specialty of port system, analyzes the factors that affect in-port time and impor

11、ts the Ant Colony Optimization (ACO) to transform the berth scheduling issue into Traveling Salesman Problem (TSP) issue. The objective function is the least in-port time costing of all vessels. At the same time, crane resource is also one influential factor of the in-port time which is also conside

12、red in the optimization. The model was established upon all these factors and the most suitable scheduling solution was suggested by the results.The simulation model tool ProModel is used to establish the simulation system of berth system and simulate the whole process of arriving of vessels, dispat

13、ching berth and unloading by cranes. Two dispatching models which are first come first service strategy and strategy based on ACO are established to compare the in-port time differences. Verify the solution of berth scheduling optimization is effective and observe the utilization of resource and oth

14、er sections in the system under these two models in order to be more useful to direct the practical port operation.Key words: Port; Berth Scheduling; Ant Colony Optimization; ProModel Simulation Model目录第一章 绪论- 1 -1.1 研究背景和意义- 1 -1.2 国内外研究现状- 2 -1.2.1港口泊位调度建模研究现状- 2 -1.2.2系统仿真技术的研究现状- 4 -1.3课题的研究内容和方

15、法- 5 -1.4文章内容安排- 7 -第二章 基本技术方法介绍- 8 -2.1 蚁群优化算法- 8 -2.1.1蚁群优化算法的基本原理及特点- 8 -2.1.2蚁群算法描述- 9 -2.2仿真方法介绍- 12 -2.1.1 港口泊位仿真介绍- 13 -2.1.2 ProModel仿真软件介绍- 14 -第三章 泊位调度算法设计- 16 -3.1基本数学符号- 16 -3.2 数学模型- 16 -3.2.1问题描述- 16 -3.2.2目标函数- 17 -3.2.3 假设约束条件- 17 -3.2.4算法的设计与实现- 18 -3.3 实例仿真- 22 -第四章 泊位调度仿真- 25 -4.1

16、 仿真模型的目标- 25 -4.2 泊位系统仿真模型- 25 -4.2.1模型假设- 25 -4.2.2建立基本模型元素- 25 -4.3仿真模型的设计和实现- 26 -4.3.1基于先来先服务原则分配泊位- 27 -4.3.2基于蚁群算法调度方案分配泊位- 28 -4.4结论分析- 30 -第五章 结论- 30 -5.1 结论- 30 -5.2 本文存在的不足与展望- 31 -5.2.1 本文存在的不足- 31 -5.2.2. 展望- 32 -参考文献- 33 -附录 蚁群算法主要程序代码- 37 -致谢- 45 -基于蚁群算法的港口泊位调度优化与仿真第一章 绪论1.1 研究背景和意义随着经

17、济的发展，全球化的趋势和区域性经济合作、互相促进的趋势愈加明显。各个国家、地区都积极利用一切可能的渠道开展国内外贸易、文化交流等活动。十九世纪以来，各国经济中心城市相机在沿海地区形成，并以港口为中心进行新的经济发展布局。因为港口是一个社会关联度极高的产业，港口的发展繁荣了城市，而中心城市经济的发展又促进了港口的发展。回顾港口的发展历程极其经济、社会、历史地位、作用的变化，我们可以了解到港口与城市的密切关系，港口对城市、区域、腹地经济的发展和社会进步有着重要的作用，而城市、区域、腹地经济的繁荣，是港口得以发展的重要依托。港口作为一个重要的交通枢纽，是连接国内外贸易的重要环节之一。从制造业的角度来

18、说，一个国家或地区港口经济的发展和竞争力，越来越影响着其制造业的发展和竞争力。区域工业与临港工业的联动性在增强，工业化进程快的国家或地区，港口经济扩张迅速，同时，港口经济发展快，也对工业化起了有力的促进作用。中国正在成为全球最具竞争力的世界工厂，也正在成为最具吸引力的世界市场。这就意味着从世界各地进口大量的原材料、零部件和消费品。所以每年中国港口数以千万计的集装箱吞吐量是一个必然的趋势，中国已经成为全球航运业争夺的主战场。我国大陆海岸线长达18000多千米，自北向南濒临渤海、黄海、东海和南海，13个沿海省份，约48个沿海城市，因此中国港口的发展，对全国的经济发展及文化交流有着重要的意义。到20

19、10年初，中国大陆的“亿吨大港”已经达到十七个，稳居世界前列。同时，随着物流业近年来的迅速发展，港口间的竞争也愈加激烈。因此，加速港口建设，提高港口工作效率，以提高船舶的利用率和客户的满意度，成为热门研究的问题。港口的服务系统是一个十分复杂的系统，需要各个环节高度协调发展，各种有效资源都应该被合理高效的利用。由于港口的装卸设备都较大型且价格昂贵，增加大量装卸设备来提高港口的物流运作效率并不是管理者的最佳选择。因此如何有效的利用现有的资源，提高设备使用率，合理规划调度，成为了港口服务系统最重要的管理环节。船舶停泊是船舶入港的第一关，是提高港口效率首先要面临的问题，也是衡量一个港口的整体吞吐能力的

20、重要指标，系统中的其他设施都根据港口泊位能力进行相应的配置。船舶到港后，能够在最短时间内靠港卸货，对泊位占用时间越短，货物的周转量也越大，港口的物流效率也会大大增加。为了不使港口的泊位分配成为整个港口系统的“瓶颈”环节，优化港口泊位调度，缩短船舶接受服务的等待时间，同时对泊位系统的工作流程进行仿真，深入了解在某种泊位调度方法下，泊位中各个环节的表现情况，并验证泊位调度的有效性，成为本文研究的重点。1.2 国内外研究现状1.2.1港口泊位调度建模研究现状目前国内外学者针对港口的优化调度问题从不同的角度和层面展开了深入的研究，当前的研究主要包括以下几方面1：泊位分配、岸边吊装设备的规划、港内的车辆

21、调度、堆场空间的分配、堆场起吊设备的调度、闸门资源的分配和码头的整体优化调度。对泊位调度的研究从对象上来看，分为单纯的研究泊位以及把泊位与岸桥或者把整个港口作为一个整体相结合同时研究。从方法上来看，分为通过仿真模拟技术来评价和优化资源调度策略以及通过数学模型的方式来优化最优解。对港口泊位调度系统建立数学模型，求解得出最优解。这种方法的使用有较长的历史，在实际的研究中应用也比较广泛。在通过数学模型来分析优化的研究中，对于泊位单独的研究主要有：Aki Imai采用改进的启发式算法对泊位进行调度分配2。Lai和Shih3提出了一种针对泊位分配问题的启发式算法，这种算法是基于先来先服务(FCFS)的分

22、配策略。Edomal等4也提出了利用排队论对码头泊位分配以及货物处理规划问题建立了模型并且进行了讨论。Imai5等以最小化船舶等待时间为目标，用非线性整数规划模型来分别模拟静态记忆动态码头的泊位调度问题。同时他们也通过研究，证明了在多用户的集装箱码头系统中，在不考虑先来先服务(FCFS)原则的情况下，可以获得较短船舶停泊时间的分配方案，但在这种情况下，会出现某些船舶等待时间过长的情况。Nishimura6等进一步扩展了上面提到的集中模型，综合考虑了水深泊位对泊位调度产生影响的情形，并应用了遗传算法对模型求解。Wang7等设计了应用随机集束搜索算法对泊位分配问题进行求解的方法。李平8等提出利用混

23、合优化策略来提高遗传算法的种群多样性，并加速算法的进化过程，用来求解泊位分配问题。Borwn等9以船舶在港总效益最优为目标，建立了分配泊位的模型。Akio和Etsuko等把泊位分配问题分为静态泊位分配和动态泊位分配两个方面，同时还给出了两种分配问题的模型及其求解方法，重点研究利用拉格朗日松弛法解决动态泊位的分配问题。Jean-Franscois Cordeau等总结了泊位分配中的连续系统模型，并且运用禁忌搜索算法对这个连续模型进行了求解。Chen和Hsieh10通过时空网络模型来帮助决策者有效地进行泊位分配，模型中综合考虑了船舶在港、到港和离港的时间，将这个问题转化成一个边约束的普通网络模型，

24、用分支定界法求得了模型的最优解。Park等11利用基于拉格朗日的次梯度算法对泊位分配问题进行了求解。戈闻怡12用遗传算法求解泊位资源配置调度，得到了所有船舶在港时间最短的最优解。Zhou等13利用模糊理论对泊位调度中的不确定性因素进行了初步探索性研究,得到了良好的效果。而对于将泊位与岸桥相结合的研究主要有：Li14等将泊位岸桥调度问题看作一个可以同时处理多个任务的处理机调度问题，并假设所有船舶在系统开始时就已经在港等候停泊，建立了以船舶在港时间最小为目标的模型，提出了启发式算法求解。类似的，Guan15等将泊位岸桥分配问题作为处理机调度问题，优化目标是将带权重的任务完成最小化时间。韩晓龙16等

25、利用回溯算法求解了泊位岸桥配置优化模型。蔡芸17等采用遗传算法求解泊位分配及岸桥的调度问题，目标是所有船舶在港时间最短。周鹏飞18等重点考虑了船舶抵港时间和装卸时间的随机性，建立了面向随机环境的集装箱码头泊位岸桥调度模型。Daganzo1920等将船舶在港的卸货过程划分成几个不同的区域，使用了整数规划模型对静态岸桥的规划问题进行研究，达到了船舶的等待时间最小的目标。随后，又将岸桥调度过程看作成一个开放的生产计划问题，建立了整数规划模型，利用分支定界法求解模型。Bse等21建立了岸桥等待时间最短的模型，并且建立仿真模型来模拟岸边有缓冲区的集装箱码头的工作流程，在给定集装箱装卸序列的要求前提下为桥

26、吊配备了跨越车并确定了相应的作业序列。韩骏等22将泊位调度与岸桥分配这两个相联系的问题进行了系统分析与集成，以船舶在港时间最小为目标，利用免疫遗传算法对泊位与岸桥协调调度问题建立了优化模型，缩短船舶在港停留时间。柴志刚23为了解决缩短船舶在港作业时间而产生的负面效应，提出了一种均衡理念的优化思想。基于集装箱码头的班轮制特点及泊位调度中的不确定性因素影响，建立了综合考虑船舶靠泊位置、靠泊时刻及装卸速度的均衡优化模型。在求解中采取人机交互与自适应遗传算法相结合的方式，设计了相应的优化算法，并通过算例对模型及算法的有效性进行了验证。Young Man Park24针对同时调度规划泊位和岸桥问题，建立

27、了一个混合整数的计算模型。首先确定船的停泊位、泊船的时间以及将与之班配的岸桥数目，用动态规划技术分配每个泊位的岸桥数量。1.2.2系统仿真技术的研究现状目前对现实系统进行仿真的可以分为三种方案25：基于专用的仿真语言或通用过程语言进行开发；选用仿真器；通用过程仿真平台。这三种方案中，第一种方案的优点是建模灵活，但编程较复杂并容易出错；选用仿真器这种方法则相反，虽然简单易用，但却缺少建模的灵活性，适用于功能比较单一的仿真；而通用过程仿真平台这种方法是在前两者的基础上进行二次开发，目前用途比较广泛的方案并且比较成功的方案都有既简单易用又很灵活的特点。例如，Brooks公司研制的AutoMod，Ro

28、ckwell公司的Arena，CACI公司开发的Simprocess，ProModel公司的ProModel和Lanner公司的产品Witness的等都是性能很好的仿真软件，目前在各个领域用途均较为广泛26。其中，ProModel(Production Modeling)仿真软件是由美国ProModel公司开发出来用于构造多种生产、服务和系统模型的计算机仿真工具，也是在美国和欧洲使用最广的系统仿真软件之一25。作为当前较流行的一种仿真工具，它能够精确地建立一个经营过程及其资源配置模型，保证模型的随机性、不确定性和相互依赖性，并同时具有为设计者提供连续或离散事件、动态以及随机的分析功能。国外已有

29、采用二维动态仿真技术来研究港口生产系统的运作方式27，以及在港口设计中确定港口资源的合理配置的问题，并已研制出成熟软件，例如澳大利亚的Realtime Business Solutionpty. Ltd推出的港口码头运作仿真软件Xwindow，以集装箱码头为主要仿真对象，利用二维图形对资源配置、堆场规划等问题进行仿真，为港口决策者提供规划依据，并且提高了港口的生产效率。仿真技术在泊位调度方面的研究成果主要有，蔡芸28利用eM-Plant仿真软件建立了以总体船舶在港时间最短为目标的仿真优化模型，生成满足停泊条件和岸桥调度策略的可行分配方案，凭借仿真模型来解决数学模型中的约束条件和岸桥调度问题，当

30、方案不满足约束时，仿真模型终止仿真，调用且返回给遗传算法一个足够大的个体适应度数值，将该方案淘汰，以保证优化结果的可行性。最终得到了包括船舶的停泊时间、停泊位置和为其服务的岸桥数目等要素的优化解。Pasquale Legato 和Rina M.Mazza29运用排队网络模型，采用面向过程的Visual SLAM语言，对港口泊位计划和装卸资源分配进行了研究。唐臣30等也在排队论的基础上，使用Witness仿真软件对集装箱码头的最优泊位数进行研究。鲁子爱31把港口生产视为随机服务系统，建立了模拟港口营运状况的计算机仿真系统。仿真模型中，船舶占用泊位时间根据船舶装卸量、码头泊位装卸效率、气候影响等条

31、件计算确定。在这些研究中，涉及到的一些船舶停泊方面的问题都是在“先到先服务”的基础上，再考虑一些其他的约束条件来提供泊位分配方案，然后依据船舶在港的逗留时间越短越好、泊位利用率越高越好、费用支出越少越好等因素来对各个方案进行评价，选取合理的方案。NamKC等32为韩国釜山Gamman集装箱港口评估今后发展方案，设计了四类仿真场景，采用不同作业策略，优化港口泊位和岸桥数量大小。汪锋33应用Witness仿真软件建立某集装箱码头仿真模型，具体研究在一定吞吐量情况下配备合理泊位数，以及在一定的泊位数的情况下岸桥的合理调度问题，指出了应根据不同的船泊到港密度安排合理的调度方式。1.3课题的研究内容和方

32、法港口泊位61，一般指供一艘船舶停靠系泊的位置，称为一个泊位。具体来说，是指港区内码头岸线供船舶安全靠离、进行作业或停泊所需要的水域和空间。有码头泊位、浮筒泊位、锚地泊位等。船舶在泊位停靠必须满足一定的岸线长度要求以及泊位水深要求，其长度一般为设计船长的120%，接待的船舶越大，泊位就越长，前沿水域就越深。岸桥25，简称桥吊或装卸桥，是集装箱港口使用的最大型的、价格最昂贵的装卸机械。它是港口装卸设备的龙头，主要负责装卸集装箱船舶。泊位调度是指根据码头泊位的数量、使用情况和物理条件为到港船舶或即将到港船舶安排停泊顺序以及泊位停泊。由于泊位是码头的主要稀缺资源，因此在整个港口服务系统中，具有极为重

33、要的影响，直接决定了港口的吞吐量、工作效率。泊位调度理想的结果是船舶不需要等待就可以直接停泊、泊位的利用率达到100%，而这在现实中是不可能达到的。假如由于不可预测的原因，同一时间段内进港船舶较多时，由于泊位数量的限制，船舶就不可避免的要在锚排队等待，而假如泊位的分配不合理，不仅将会造成巨大的经济损失而且会降低港口的竞争力，影响到整个港口未来的发展。为了解决这一“瓶颈”问题，如何提高泊位调度效率，减少船舶等待服务时间是人们一直关注研究的问题。影响泊位调度的主要因素有：船舶相关信息，如到港时间、装卸量等；码头资源情况，如泊位状态、岸桥设备等；物理条件限制，如泊位水深、长度等。目前我国大部分港口泊

34、位调度主要是依靠码头工作人员的经验分配的，或者是由船舶的运营者与港口公司双方的合同规定，在一些现代性国际化的集装箱码头，多采用整数规划或模拟方法，借助智能决策系统来进行码头泊位调度。泊位调度的研究分为离散型和连续型34。离散型的泊位指船舶在停泊时不能同时占用多个泊位，只能停泊在某一个泊位所限定的位置和空间中，受泊位物理条件的限制。连续型泊位是指船舶在停泊时可以同时占用多个泊位停泊。在这种情况下，船舶的停泊将会有更大的选择性，同时对于岸线的要求也更高。另一方面，根据船舶到达时间与泊位分配时间的先后之间的关系，泊位调度还可以分为静态和动态两种。静态调度指在进行泊位分配时，所有需要安排停泊的船舶都已

35、到达港口，这些船舶都将被考虑到下一个停泊时间段中；而动态泊位调度是指泊位分配开始时仍有船舶未到港，但将会在分配时间段中的某时刻到达。本文拟针对船舶靠港“第一关”：停泊，这一动作，研究泊位调度分配的最优方式。在综合考虑船舶本身的条件，包括船长、吃水深度、货运量等条件下，以船舶的总服务时间（包括等待泊位以及卸货时间）最短为目标。由于每个泊位的物理位置不同，船舶停泊后能够为其提供卸货服务的岸桥的数量及状态也不同，因此也影响到船舶的服务时间。我们在研究泊位调度时，应该在考虑泊位空闲的同时，考虑该泊位可用岸桥的数量和状态选择使船舶在港时间最小的泊位停靠，这里在港时间最小包括分配泊位的时间及在该泊位上可用

36、的岸桥的服务时间。若是将两个环节单独调度，先根据最小等待时间为船舶选择泊位停泊，停泊后再等待分配岸桥，则忽视了岸桥的分配对船舶在港时间的影响，造成其他船舶的等待时间加长，具有一定局限性。将岸桥与泊位共同调度则会避免单独调度的局限性，可以使船舶总在港时间更短，并且将提高岸桥的工作效率。因此本文的研究对象是泊位调度以及与泊位相配合的岸桥调度，使得船舶在靠港及卸货过程中，各子系统协同作业。本文拟采用蚁群算法建立数学模型，并利用仿真软件ProModel模拟船舶到港，泊位分配及岸桥卸货整个过程。通过模拟结果分析模型的优劣性，以便求得更符合实际情况的最优解。1.4文章内容安排 本文共分为五章。第一章 绪论

37、。说明本文的研究问题的背景及研究意义，确定本文的研究内容及研究方法，并且确定本文的技术路线。详细介绍了目前针对泊位调度问题、仿真模型等方面的国内外研究现状。第二章 基本技术方法介绍。详细介绍本文中将用到的泊位调度优化模型蚁群算法的原理、特点及算法描述；仿真模型的基本概念、方法及本文中用到的ProModel软件的应用及基本元素。第三章 泊位调度优化。重点论述了蚁群算法求解泊位调度的步骤，设定目标函数、模型的假设约束条件、具体的参数设定及模型求解步骤。将数据代入模型中，求得最优解，分析结论。 第四章 泊位调度仿真。使用ProModel仿真模型，对泊位调度及岸桥分配的整个过程进行仿真模拟。设计符合实

38、际情况的各种基本元素，建立仿真逻辑模型，模拟泊位调度及岸桥分配的处理过程。并且根据第三章中蚁群算法模型求得的最优分配策略，对实际情况进行模拟。分析结果。第五章 结论。分析本文得到的泊位调度模型求得的最优解以及泊位调度仿真结果，总结在研究过程中发现的问题及不足以及对未来的研究的展望。第二章 基本技术方法介绍2.1 蚁群优化算法2.1.1蚁群优化算法的基本原理及特点20世纪90年代意大利学者MDorigo，VManiezzo，AColorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法 蚁群算法，是群智能理论研究领域的一种主要算法35。用该方法求解旅

39、行商(TSP)问题、分配问题、车间调度问题(job-shop)、车辆路由问题、图着色问题和网络路由问题等36，取得了较好的试验结果虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题，尤其是离散优化问题方面有一定优势，这表明它是一种有发展前景的算法这种方法能够被用来解决大多数优化问题或者能够转化为优化求解的问题。蚁群算法37是对自然界蚂蚁的寻找路径的方式进行模拟得出的一种仿生算法。这种算法区别于传统的编程模式，它的主要优势在于，有效的避免了冗长的编程和筹划过程，算法本身是基于一定的规则，随机运行来寻找最优解。也就是说，当蚁群最开始找到目标的时候，路径几乎不可能是最优的，甚至可能是

40、包含了很多错误的选择，结果非常不理想的。但是，蚁群算法可以通过蚂蚁寻找食物的时候释放信息素的原理，不断地去修正原来的路线，使所有经过的路径越来越短，由于这种原理，算法被执行的时间越长，所获得的路径就越可能接近最优路径。这种寻径方式类似于我们以前经常用到的通过大量的数据、实验，对结果进行总结分析，最终形成最佳路径的过程。这实际上是类似算法的一个自我学习的过程。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体性的行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来

41、者选择该路径的概率就越大。基于自然界中蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题。在人工蚁群中，我们把具有简单功能的工作单元作为蚂蚁。二者的相似之处表现在，两者都是优先选择信息素浓度较大的路径。较短路径的信息素浓度高，所以能够逐渐被所有蚂蚁选择，也就是产生了最终的优化结果。两者的区别表现在人工蚁群具有一定的记忆能力，能够记住已经访问过的节点而不重复访问。同时，人工蚁群在选择下一条路径的时候是按一定算法规律有意识的寻找最短路径，并不是盲目的。蚂蚁选择下一个目标，向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可到达节点的概率，

42、比较并按照这个概率实现一步移动，反复几个过程之后，越来越接近最优解。蚂蚁在寻找路径的过程中，或者找到一个解后，会评价这个解或解的一部分的优化程度，并把这个解的评价信息保存在相关的信息素中。信息素的更新方式有两种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，这是模拟了自然蚁群的信息素随时间挥发的过程；二是增强，在评价值较好的路径上增加信息素。这种优化过程的本质在于蚁群算法的三个独特机制：选择机制、更新机制和协调机制。所谓选择机制是指信息素残留越多的路径，被蚂蚁选择的概率越大；更新机制表示的是路径上的信息素会随着蚂蚁经过次数的增加而增长，而与此同时也会随时间的以一定的速率有一部分挥发；

43、协调机制是指蚂蚁之间事实上是通过这种信息素的分泌来实现彼此之间的通信，共同工作的。蚁群算法通过候选解组成群体来寻求最优解的进化过程，它包含两个基本的阶段38：适应阶段和协作阶段。在适应阶段，各个候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。蚁群算法正是充分利用了选择、更新和协调的优化机制，即通过个体之间的信息交流与相互协作最终找到最优解，使它具有很强的发现较优解的能力。2.1.2蚁群算法描述为了说明蚂蚁系统模型，首先引入旅行商问题39。旅行商问题就是指定几个或n个城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。为模拟实际蚂蚁的行

44、为，首先引入如下记号：m蚁群中蚂蚁数量；bi(t)t时刻位于城市i的蚂蚁的个数，m=；dij两城市之间的距离；ij边(i,j)的能见度，反应由城市i转移到城市j的启发程度，这个数值在蚂蚁系统的运行中不改变；ij边(i,j)上的信息素轨迹强度；ij蚂蚁k在边(i,j)上留下的的单位长度轨迹信息素量；蚂蚁k的转移概率，j是尚未访问的城市。每只蚂蚁都是具有如下特征的简单主体：（1）在从城市i到城市j的运动过程中或是在完成一次循环后，蚂蚁在边(i,j)上释放一种物质，称为信息素轨迹；（2）蚂蚁概率的选择下一个将要访问的城市，这个概率是两城市间距离和连接两城市的路径上存有轨迹量的函数；（3）为了满足问题

45、的约束条件，在完成一次循环以前，不允许蚂蚁选择已经访问过的城市。初始时刻，各条路径上的信息素量相等，设ij(0)=C（C为常数）。蚂蚁k (k=1,2,3,m)在运动过程中根据各条路径上的信息素量决定转移方向。蚂蚁系统所使用的状态转移规则被称为随机比例规则，它给出了位于城市i的蚂蚁k选择移动到城市j的概率。在t时刻，蚂蚁k在城市i选择城市j的转移概率 (t) 为：(t)= (2.1)其中allowedk=0,1,n-1表示蚂蚁k下一步允许选择的城市。与之对应的是禁忌表tabuk，表中记录了蚂蚁k已经走过的城市，蚂蚁k在本次循环当中将不再访问tabu表中的城市。ij为能见度因素，和为两个参数，分

46、别反映了蚂蚁在运动过程中所累计的信息以及启发信息在蚂蚁选择路径中的相对重要性。当本次循环结束以后，禁忌表中的数据将被用来计算该蚂蚁所建立的城市访问方案（即蚂蚁所经过的路径长度）。之后，禁忌表被清空，该蚂蚁出发时又可以自由的进行选择。经过n个时刻，蚂蚁完成一次循环，各路径上信息素量根据下式调整ij(n+1)=ij(t)+ij(t,t+1) (2.2)ij(t,t+1)= (2.3)其中，表示第k只蚂蚁在时刻(t,t+1)留在路径(i,j)上的信息素量，信息素的值是根据蚂蚁表现的优劣程度而决定的。蚂蚁经过的路径长度越短，信息素相应的释放的就越多；ij(t,t+1)表示本次循环中路径(i,j)的信息

47、素量的增量；(1-)表示的是信息素轨迹的衰减系数，通常情况下，设置系数1，目的是为了避免路径上轨迹量的无限累加。在蚁群系统中，只有获得全局最优解的蚂蚁才允许释放信息素，这样做的目的是为了使搜索的过程更具有指导性。也就是说，蚂蚁的搜索将主要集中在当前循环位置所找出的最好路径的区域内。全局更新在所有蚂蚁都完成它们的路径后执行，应用下式对所建立的路径进行更新：(r,s)(1-)(r,s)+ (r,s) (2.4)如果(r,s)全局最优路径 否则 (r,s)= (2.5)其中为到目前为止找出的全局最优路径。目前常用的信息素量更新模型有以下几种：（1） 蚁密模型： 其他第k只蚂蚁经过边(i,j) = (2.6)式中，Q为常量；（2） 蚁量模型：其他第k只蚂蚁经过边(i