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

第32卷第1期Vol. 32 , No.012013年1期Coal TechnologyJanuary ,2013基于蚁群算法的煤炭运输优化方法高攀,郭理(石河子大学信息科学与技术学院，新疆石河子832000)摘要:本文主要以蚁群算法 为基础,求解煤矿运输优化方法,运算出实际生产中较优生产模式。首先对蚁群算法做出了简单的介绍，然后比较仔细的阐述了煤矿问题的数学模型,最后演示了蚁群算法在运输优化问题中的应用。关键词:蚁群算法;煤矿运输;最短路径;运输优化中图分类号:TP311文献标识码:A文章编号:1008 - 8725(2013)01 -0162 -03Coal Transportation Optimization MethodBased on Ant Colony AlgorithmGAO Pan,GUO Li( Information Science and Technology College , Shihezhi University , Shihezhi 832000 ,China)Abstract :This paper is to study the ant colony algorithm based, solving coal transport optimization meth-od, works out in practical production with excellent production mode. First this paper the ant colony algo-rithm made simply introduced, and then the more careful expounds the model of coal mine, finally dem-onstrates the ant colony algorithm of optimization problems in the application.Key Words:ant colony algorithm;Coal transport ;The shortest path; Transportation optimization径上会留下一种称为信息素的挥发性分泌物,而且0前言该分泌物的浓度与路径长短成反比。蚂蚁在选择路蚁群算法主要是通过人工模拟蚂蚁搜索食物的径时 ,对未走过的道路蚂蚁会随机的选择-一条,在过程来求解在给定的运输道路网中寻找出- -条从起行走的过程中释放信息素,若该路径过长，蚂蚁下次始点到目标点之间的最优路径的一种算法。 煤矿业就可以根据信息素 浓度判断,绕过该条路。由于路的发展与人们的生产生活息息相关，而煤矿的运输径经过的蚂蚁越 多,路径越短，信息素气息就越浓问题是煤矿产业中比较重要的环节，因此文中运用烈，蚂蚁可以根 据气息的浓郁程度，选择最优路径。蚁群算法来求解煤矿运输优化问题,在已知的约束这样以信息素为媒介形成了一种信息反馈机制,导下,例如:交通工具的限定、荷载容量的限定以及经致信息素越浓烈的路径,蚂蚁选择的概率越大,这样费的限定等,寻求达到煤矿运输消耗最小的最优路就形成了最短路径。 而且由于信息素是随着时间的推移,会逐渐的变淡,所以当在已经形成的最短路径径,提高煤矿业的运输效率。上出现障碍物时,蚂蚁就不会再选择该路径,将会寻1蚁群算法简介找另外的路径,原先路径上的信息素将会逐渐消散。在寻路过程中,该作用机制必须依靠蚂蚁群来完成，1.1蚁群算法的起源蚁群算法是一种随机搜索算法,与遗传算法、模单个蚂蚁的能力是有限,但是在信息素的交流下,整拟退火算法等模拟进化算法.-样,主要是通过在已个蚁群可以交换路径信息,共同完成最短路径的选知的解组中寻求最优解，是路径规划问题的常用算择。在蚁群算法中,多个主体之间相互合作,对信息进行反馈,让组合优化问题得到很好的解决。法之一。最早由意大利学者M Dofipo等人提出，主13 蚊群算法流程及忧点要是从蚂蚁群体搜索食物的过程和旅行商问题中得在蚁群算法中，主要的算法流程如图1所示,首到启发,人们通过模拟蚂蚁群搜索食物的过程来求先对蚁群进行初始化,根据具体情况选择目标函数;解最短路径问题，故称之为“人工蚁群算法”。随着将主体放置在初始区域,并标记出目标函数对每个时间的发展和对蚁群算法的深人研究,蚂蚁算法也主体的适应度;将适应度转换为信息素,放置在经过被用于解决二次分配问题Job shop 调度问题网的路径 上,其中适应度越高，信息索也越多:然后观络动态路由优化等问题，并取得成功。察主体的行动轨迹,根据信息素和自已的判断选择1.2 蚁群算法原理自然界中,蚂蚁群在寻找食物时总能通过相互路径,在这个过程中信息素会随着时间而消散。蚁群算法只需要对算法模型稍加修改就可以应间的合作找到食物与蚁穴间的最短路径。蚁群算法用于多种求解问题， 采用的分布式算法是一种种群的主要原理是模拟自然界蚂蚁寻找路径的方法。该算法,并且易与其他的方法进行组合,组成混合算原理具体是蚂蚁群寻找食物的过程中,在经过的路法，改善算法的性能，提高计算的准确性和效率。这收稿日期:2012 -02 -15;修订日期:2012-11-16中国煤化工基金项目:教育部社科研究基金( IJAZH001)作者简介:高攀(1981 -),男,安徽灵壁人,讲师,硕士研究生,研究方向:数据结构与,MYHCNMH G .第1期高攀,等:基于蚁群算法的煤炭运输优化方法●163●时刻∞0城市i + 1之间之间所花费的费用,T.为两城之间的运输时间, Mr.为货物在两城之间的运输方式参数,Y"为煤炭在城市i的m种运输方式转换为第1初始化4(1) |「 放置信息激种运输方式间的转换参数, D;"则为运输方式转换的蚂蚁移动”中转费, wn为中转时间,Q为需运煤炭的数量,T为评价40)信 息激素消散煤炭运输过程中的时间限制,N为运输途中所经过的城市总数,G为运输方式的种类,为了更加准确的反映结果的最优性,设定U送达时间外的时间价值系数需满足U > 0。则运输过程中的时间成本为禁止集件L 1+1UEET. + EE二)。其中目标函数即为运输成本即为时间成本及时间补偿成本、[结束]中转费用、运输费用的和的最小值,表示为图1蚊群算法流程图minZ = C.M..E 2 ED"Y"+些特点让蚁群算法与其他算法相比,具有更好的寻优能力,利用的正反馈原理促进了不同个体之间的U(Z 2+ 2二2叭)信息交流,提高了团体协作的工作效率。对运输荷载的相关约束为需运的煤炭数量小于每次运输方式的荷载性能,即2煤炭运输问题数学模型Ci.M;i+1≥Q(i= 1,2,..N-1,N;M = 1,2,2.1煤炭运输问题描述煤炭运输问题的求解是一个复 杂的组合优化问在题设中在任2个相邻城市之间只能选择1种题,需要考虑各行业、各部门的运输条件和运输成运输方式,任- - 城市运输方式只能转换1次，则需要本。用常规的数学方法很难求解，这里主要是采用满足模拟生物进化的蚁群算法来解决。由于煤矿运输问SM =1(i= 1,2，N-1,N)题影响因素复杂,由目标可划分为线性问题与非线性问题，单目标问题和多目标问题。以约束的类型22 =1(i= .,.N-1,N)可分为二维问题或三维问题。这里主要是分析煤炭运输问题的容量的上下限和损耗费用之间的问题。运输时间成本小于限定时间假设煤矿从产地A地运到需求地B,中途经过n个城市,任意两个城市之间又有m种运输方式，每种EEnm+ 2SEw≤r运输方式的费用,承载容量和消耗时间是不同的,在运输方式为0或是1,则整个煤炭运输过程中,约束条件是,在不超过规定时M.= 1间的前提下,选用最优的运输组合方式,使得运输成y?=1或是0本最小,将需要的煤炭量送达目的地。在该数据模型的基础上对全局的可能解进行试2.2数学模型的建立算,计算各种取值的目标函数,由于该类计算的时间ASAR算法,即基于蚁群优化的服务感知路由复杂度和迭算次数繁多的原因，-.般是采用MatLab算法,本算法系统中的蚂蚁大致分为3类,每类都是语言编制煤炭运输的蚁群算法优化计算程序进行计和多媒体感知器网络所提供的一种特定的服务 相对算,最优路径的输出。应的,以对应服务QoS需求为依据,对信息素增量以及局部信息启发因子进行计算。3蚁群算法在运输优化中的应用在数学模型的建立中,前提假设为每个城市必在求解运输优化问题中,要将问题按照考虑要须经过，任一个城市的运输方式只能转换1次,并且素简化为寻求最优路径的问题，将起始条件与目标2个相邻城市之间只能采用1种运输方式，可以由中的过程转化为路径的组成点。这类问题属于静态简单的赋权网络图表示，如图2所示,其中权数即为组合,主要是有n个节点，每个节点必须访问并且只每条路径对目标函数的适应度。能访问1次,而且根据所给的条件放置信息要素,即.从一个城市转移到另一个城市的概率，在文中的煤炭运输求解问题中，信息要素是由城市间转化参数48、、3和运输方式转换参数来确定的。数学模式确定后，v1;， v20依照蚂蚁寻找食物的过程,假定速度恒定的蚂蚁群，3| 6/入3同时从起点出发,模型中的每个节点都遍历,当第1只蚂蚁到达终点时,则求解结束,该蚂蚁的路径即为一v最优路径。主要是利用了蚁群算法的以下特点:(1)蚁群算法的并行性。在蚁群中,每只蚂蚁都同时行动,在速中国煤化工付刻,蚂蚁图2赋权网络图所行走的路径量CN M H C率的前提其中C...是选定第m种运输方式,从城市i与下 ,即蚂蚁选择要足的路时院干定阳凹的,由于特第32卷第1期煤炭技术Vol. 32 ,No.01.2013年1 期Coal TechnologyJanuary ,2013基于CAN总线的煤矿远程监控谢青海,黄亮(河北机电职业技术学院，河北邢台054048)摘.要:针对当前我国国内的煤矿监控系统中存在的不足,设计了-种基于CAN总线的煤矿远程监控系统,并且，就该系统的具体设计方案、智能节点以及通讯接口做了较为详细的阐述,通过实践证明,本文构建的基于CAN总线的煤矿远程监控能够较好的监测煤矿生产的运行状态。关键词:CAN总线;煤矿;远程监控中图分类号:TP274文献标识码:A文章编号:1008 - 8725(2013)01 -0164 -03Based on CAN Bus Coal Mine Remote MonitoringXIE Qing - hai , HUANG Liang( Hebei Institute of Machinery Eletricity , Xingtai 054048 , China)Abstract:The article in view of the current domestic coal mine of the monitor system of deficiency, design a kind of based on CAN bus coal mine remote monitoring system, and the system is the specific de-sign scheme, intelligence and communication interface node, a detailed elaboration , through the practiceof proof, this paper constructed based on CAN bus remote monitoring to better coal mine monitoring inthe process of coal mine production operation.Key Words :CAN bus ;coal mine ;remote monitoring性无法得到保证等各方面的问题。针对当前煤矿远0引言程监控系统之中存在的上述问题,文中提出了一种当前,为了提升我国煤矿的安全生产管理能力,基于CAN总线的煤矿远程监控系统的构建方法,能我国的许多煤矿都构建了自身的监控系统，但是在够较为 直观的监控并且记录进行的工作实际情况，传输的过程中，由于大部分都是选择的串行通信总同时也能够实现瓦斯等环境安全数据的共享,充分线,造成了多主冗余系统无法构建，通讯方式无法选的满足煤矿 安全生产管理的实际需求”。择,以及缺乏统一的规范与通信协议,可靠性与实时殊的正反馈机制,不可走的路径和已走过的路径不寻优性较强且具有发展前景的仿生优化算法,被广重复选,防止寻径问题无解。泛的运用于组合优化求解问题中。但是由于其算法(2)速度--定原理。蚁群算法采用:速度一定本身的局限性,算法的时间复杂度高，迭换次数繁时,路程与时间成正比的基本定理。在规定蚂蚁的多,比较不容易得到全局解,容易陷入局部最优解速度时，引进离散单位时间量即是算法中进行-一次中， 即寻找的最优解不是全局的最优解。所以在组迭代所代表的时间。在此理论的支撑下，可以得到合优化问题的研究中 ,蚁群算法可以与其他的算法第-一个到达目的地的蚂蚁所走的是最优路径。混合,例如遗传算法等,产生越来越多的新型算法，(3)对蚂蚁状态的判断,所有的蚂蚁都是从起在花 费较少时间的基础上,寻求最优的路径,以实现点开始,经过一定的时间后,蚂蚁的状态是确定的，资 源配置的最优化。没有达到路径节点的蚂蚁继续在该路径上前进，而参考 文献:达到路径节点的蚂蚁则是开始以- -定的概率对下一[1周勇.“遗传- -蚁群” 混合算法及其在水量调度中的应用[ D].华公个达到节点的路径进行选择。(4)信息相关性。在蚁群算法中,蚂蚁对路径[2] 杜艳平,尹晓峰 ,刘春煌.采用蚁群算法求解铁路空车调整间题[J1.中国铁道科学2061)19-122的信息是共享的，只要保证至少有- .只蚂蚁选择了[3] 王丰元，。潘福全，张丽霞等定,等.基于交通限制的路网最优路径算最短路行进就能得到最短的路径的全局解。所以在法[J]. 交通运输工程学报,2005(1):92 -95.运输问题求解过程中,要保证足够多的运算，以求到[4] 王旭，张江，崔平远。 一种基于蚁群算法求解路径规划问题的新方法[A]. 2003年中国智能自动化会议论文集(下册)[C].全局解。(5)影响因素较为单一,蚁群算法的时间复杂(责任编辑张欣)度只跟蚂蚁群的数量和最短路径的长度有关。4结语在求解煤炭运输优化问题中，蚁群算法是一种中国煤化工收稿日期:2012 -02 - 15;修订日期:2012-11-06MHCNMH G .作者简介:谢青海( 1980 -),男,河北邢台人,讲师,本科学历,研究方向:远程监控。