基于蚁群算法的煤炭运输优化方法

第25卷,第3期中国铁道科学Vol.25 No.30022004年6月CHINA RAILWAY SCIENCEJune, 2004文章编号: 1001-4632 (2004) 03-0126-04基于蚁群算法的煤炭运输优化方法李智(武汉工业学院电气信息工程系，湖北武汉430023)摘要: 蚁群算法是指通过人工模拟蚂蚁搜索食物的过程来求解运输优化问题的一种算法。给出蚁群算法模型及算法步骤。研究- -种带容限制和考虑损耗的煤炭运输数学模型的优化计算，并给出算法步骤。运用蚁群算法对某- -钢铁企业煤埃运输问题进行优化计算,计算结果符合实际生产情况。关键词:铁路运输组织;煤炭运输;蚁群算法;优化计算中圈分类号: U294.15: TP18文献标识码: A力，不仅利用了正反馈原理，在一定程度上加快了1引言进程的速度，而且是一种本质并行的算法，不同个体之间不断进行着信息交流和传递，从而能够相互人工蚂蚁算法是受到人们对自然界中真实蚂蚁协作,有利于发现较好的解。群体行为的研究成果的启发而提出的一种基于种群的模拟进化算法，属于随机搜索算法的-种。最早2蚁群算法由意大利学者M.Dorigo 等人提出，在充分利用蚂蚁群体搜索食物的过程和著名的旅行商问题2.1 蚊群算法原理”(TSP)之间的相似性，通过人工模拟蚂蚁搜索食自然界蚂蚁群体协作行为主要包括:在没有任物的过程求解TSP问题，获得了成功，故称之为何外界指导信息的情况下，蚂蚁群体总是能找到从“人工蚁群算法”，简称“蚁群算法”1。在随后的食物源到巢穴的最短路径;蚁群中个体从事不同的研究中，又成功地将蚂蚁算法应用于二次分配问劳动，群体可以很好地完成个体的劳动分工;蚁群题[2]、Job-shop调度问题[3]、网络动态路由优化4]、中死去蚂蚁的个体可以聚集在一-起,形成相对较大信带频率分配问题[fs!等的求解。的坟墓。受这些蚂蚁群体行为的启迪，Dorigo 等人蚁群算法是一种随机搜索算法，与遗传算法、提出了几类不同的蚂蚁算法模型。其中，对蚂蚁群模拟退火算法等模拟进化算法-样，通过候选解组体总是能找到从食物源到巢穴的最短路径这种情况成的群体在进化过程来寻求最优解6),具有以下特而抽象建立的算法模型被称为蚂蚁系统。理论和实点。践上都证明这种算法模型对求解组合优化问题效果(1)较强的鲁櫸性:对基本蚁群算法模型稍加良好，下面说明蚂蚁系统的生物原型一真实蚂蚁修改，即可应用于其它问题的求解。群体的工作原理。(2)分布式计算:蚁群算法是一种基于种群的研究表明，自然界蚂蚁寻找到从巢穴到食物源算法，具有并行性。的最短路径是通过一种正反馈的机制实现的，单个(3)易于与其它的方法相结合:蚁群算法很容蚂蚁在自己行走的路径下留下一种挥发性分泌物，易与其它的启发式算法相结合,以改善算法的性称之为信息激素，后来的蚂蚁根据前进道路上信息能。数量的多少选择前进方向，在经过一个长的过程诸多研究表明，蚁群算法具有很强的寻优能中国煤化工息激素的量变得较收稿日期: 2003-07-11作者简介:李智(1964-), 男，湖北武汉人，博士研究生,副教授。fYHCNMHG第3期基于蚁群算法的煤炭运输优化方法27大,而蚂蚁越来越多地集中在信息激素量较大的路Or,= Q/L,(3)径上，从而找到了- -条最短路径。Ot,表示第j只在本次循环中吸引强度的增加;蚂蚁行为的实质是简单个体的自组织行为体现Q为正常数,其范围0< Q< 10 000; L,表示本次出来的群体行为，每个蚂蚁行为对环境产生影响，循环中f(x)的增量，定义为f(x+r)-f(x);0≤环境的改变进而对蚁群行为产生控制压力，影响其ρ≤1, 体现强度的持久性。于是，函数f(x)的寻他蚂蚁的行为。通过这种机制，简单的蚂蚁个体可优就借助m个蚂蚁的不断移动来进行:当η≥0以相互影响，相互协作，完成- -些复杂的任务。时,蚂蚁i按概率p。从其邻城i移至蚂蚁j的邻域;自组织使得蚂蚁群体的行为趋向结构化，其原当η≤0时,蚂蚁i做邻域搜索(搜索半径或步长为因就是包含了一个反馈的过程，这也是蚂蚁算法最r),即每个蚂蚁要么转移至其他蚂蚁处，要么进行重要的特征。正反馈是系统演化发展的原因，这个邻域搜索。过程利用了全局信息作为反馈，通过对系统演化过由此可见，当蚂蚁的数量足够多，搜索半径足程中较优解的自增强作用，使得问题的解向着全局够小，这种寻优方式相当于一群蚂蚁对定义区间最优的方向不断进化，最终能有效地获得相对较优[a, b]做穷尽的搜索，逐渐收敛到问题的全局最的解。优解。2.2蚊群算法模型及其实现上述函数优化过程不受优化函数是否连续、是Dorigo等人提出的蚂蚁群体优化的元启发式规否可微等限制，较之经典搜索方法具有明显的优越则较好地描述了蚁群算法的实现过程，其过程可以性和稳定性。表示如下。函数优化问题的蚁群算法步骤: .当没有达到结束条件时，执行以下活动:(1) count←0 (count是迭代步数或搜索次数);(1)蚂蚁的行为，即是蚂蚁在-定的限制条件各τ,和Or,初始化;下寻找一条路径;(2)将m个蚂蚁置于各自的初始邻域;每个(2)轨迹(即信息激素)浓度的挥发;蚂蚁按概率p。移动或做邻域搜索;(3)后台程序，主要是完成单个蚂蚁无法完成(3)计算各个蚂蚁的目标函数Z;(k= 1.2.*，的任务，比如说根据全局信息对信息激素浓度进行m),记录当前的最好解;更新;(4)按强度更新方程修正轨迹强度;达到条件，结束。(5) Ot,修正,count←count + 1;由于最初的蚁群算法思想起源于离散的网络路(6)若count小于预定的迭代次数，则转到步径问题，下面以- -维搜索为例，引申到n维空间的骤(2);函数求解。(7)输出目前的最好解。在函数优化问题中,假定优化函数为:在具体的算法过程中，邻域设定可根据具体优minZ = f(x) x∈[a,b]设m个人工蚂蚁，刚开始时位于区间[a, b]化问题来定，比如一维问题就是直线搜索，二维问题可定义为圆等。搜索半径的大小和所要得到的最的m等分处，蚂蚁的转移概率定义为:优解的精度有关，若问题的局部最优点密集，全局pi =-法.(1)最优解不易得到时， 则必须设置较小的r,蚂蚁个数m则主要和搜索空间(定义域)有关，搜索空其中, P;表示蚂蚁从位置i转移到位置j的概间越大， 所需要的蚂蚁个数越多。率; r,表示蚂蚁j的邻域吸引强度; η表示目标函数差异值，即η。= f,(x)- f;(x);参数a,β∈[1,3煤炭运输问题及数学模型5],该范围的取值是-个经验值，目前尚无理论上中国煤化工+分复杂的过程，的依据。C N MH G同，其数学模型强度更新方程:MH=叫+ 20r,(2)的表达方式也不一-样， 有的甚至是组合优化问题，在数学上属于典型的NP难解问题。这类问题如采128中国铁道科学第25卷用传统的数学方法很难求出其优化解，而蚁群算法炭产地， 5个需求地的情况，从i产地(i = 1,2,3)这一建立在现代优化理论基础上的生物进化算法，到j需求地(j = 1,2,3,4,5) 的运价Cj、损耗费用却能有效地解决此类问题。hj及运输量上限d;分别如表1、表2和表3所示，煤炭运输问题根据目标的类型，可以将问题分运输量的最小限制取0。为线性问题与非线性问题;单目标问题和多目标问衰1运价题。根据约束的类型又可将问题分为二维问题或三产地BB2B需求地/万元(万)-1B. Bs发送量/万t维问题，以及平衡问题和非平衡问题。煤炭运输问题往往都带有容量的上下限和损耗费用。Al10A2本文主要讨论--种带容量限制和考虑损耗的煤As200炭运输数学模型的优化计算。需求量设由产地A;运送煤炭到需求地B,，且损失费用为hj (元),运量的下限为f,(个单位),运量的上表2运输损耗费用限为dy(个单位),并设由A;地运送到B,的煤炭量需求地万元BB2 BBB为x;, (个单位),则带有容量和损耗费用的平衡煤炭A9运输数学模型可描述为:33 10A:minz =(4)_需求量 3_ 5_ 4s.t.=a;i=1,2,,m(5)衰3运输量上限之工需求地万=b, j= 1,2,",n(6)B。 Bf;≤x≤d; i = 1,2,",m;j = 1,2,"",n(7)8[1，xg>0为e =0，x; =0(8)采用MatLab语言编制煤炭运输的蚁群算法优i = 1,2,",m;化计算程序，仿真程序在CPU1133MHz,j = 1,2,,n(9)RAM256MB的PC机上运行，仿真计算结果如表4所示。.xi≥0 Vi,j(10)亵4运输优化结果式(4) ~ (10) 中，诸常数均非负，在编制需求地/万程序时，将下界限制fo≤xg经变量替换x'; =B2 B:B。 B.xj -f,,可以化为非负限制。目标函数式(4) 中的第- -项是总的煤炭运输价;第二项是总的运输损耗费用。式(5)、式(6)是煤炭产地生产量、需求地min2=296 (万元)需求量的约束;式(7)是容量约束;式(8)是当选择某条线路时，就有损耗费用产生的条件约束，目标函数最优值296万元，即合计总费用296当y。=1时，该线路有损失费用产生，反之,无损元, 其中煤炭运输价244万元,损耗费用52万失费用产生;式(9)是平衡条件约束;式(10)元。是决策变量的非负约束。中国煤化工4实例仿真MHCNMHG本文通过采用蚁群算法对含有容量限制和损耗以某钢铁运输企业的实际运输为例。有3个煤费用的煤炭运输问题进行 了求解，计算结果表明结第3期基于蚁群算法的煤炭运输优化方法129论是正确的。工程上的普及应用。仿真过程还表明，蚁群算法求解此类问题，不相信随着蚁群算法等基于生物学原理发展起来需要技术人员具有过多、过深的数学知识，也不论的优化计算 方法研究的不断深人和发展，其应用领优化对象的数学模型是否具有可导、连续等特点，域也会越来越广 泛，各行业的一些复杂难解的工程都能够正确地进行求解，因此，特别适合各行各业实际问题的求解 会变得更加容易。参文献[1] Dorigo M, Bocabeau E, Therala G. Ant Agorthns and Stigmergy [J]. Future Generation Computer System, 2000,16: 851-871.[2] Manieo V, Colomi A. The Ant Systen Applied to the Quadratic Asigmnent Problem [J]. IEEE Trans on Knowledgeand Data Engineering, 199，1 (5): 769-778.[3] Colomi A, Dorigo M, Maniezo V, Trbian M. Ant System for Job-shop Scheduling [J]. Belgian Joumal Operations Re-search Statistic Computation Science, 1994, 34: 39- -53.[4]张素兵， 刘泽民.基于蚂蚁算法的分级QOS路由调度方法[J]. 北京邮电大学学报, 2000, 23 (4): 11-15.[5]Maniezzo V, Carbonaro A. An Ants Heuristic for the Frequency Assignment Problem []. Future Generation ComputerSystem, 2000，16: 927- -935.[6]马良. 来自昆虫世界的寻优策略一蚂蚁算法[J].自然杂志，199, 21 (30): 161- -163.[7] 魏平,熊伟清.用于-般函数优化的蚊群算法[J]. 宁波大学学报，2001, 14 (4): 52--55.[8]李致中,史峰,孙焰, 等.铁道运输管理的数学模型及算法[M]. 武汉:华中理工大学出版社，1995.[9] 谢政,多磊,汤泽澄.带容量限制和手续费用的运输问题[J]. 系统工程, 1998, 16 (5): 25- -30.Optimization Model of Coal TransportationBased on Ant Colony AlgorithmLI Zhi(Department of Electric and Information Enineering, Wuhan Polytechnic University, Wuhan Hubei 430023, China)Abstract: The main idea of Ant Colony Algorithms is to rifially simulate the process of ants seeking food tofind optimal solutions to the transportation problem at hand. Ant Colony Algorithms Model and concrete stepsare introduced in the optimization of a mathematical model of c∞oal transportation problems with volume restric-tion and consideration of loss. Simulation result shows that optimization of coal transportation problems for oneiron & steel enterprise c∞onforms to production reality.Key words: Railway taffic organization; Coal transportation; Ant colony algorithm; Optimization calculation(责任编辑刘卫华)中国煤化工MYHCNMHG