基于遗传算法的神经网络在露天矿卡车调度系统优化中的应用研究

，姜箭21辽宁工程技术大学资源与环境工程学院，辽宁阜新(123000)2平庄煤业（集团）有限公司西露天煤矿，内蒙古赤峰(024076)E-mail：[e-mail]摘要：本文介绍了神经网络和遗传算法两种优化方法的算法原理、特点和实现，在它们优势互补的条件下，提出了一种新的集成求解方法，利用遗传算法很强的全局搜索能力来弥补神经网络容易陷入局部最优的优化方法，给出了算法流程。最后以抚顺西露天矿的长远总体规划问题为例，说明该方法具有很好的解决卡车调度系统优化问题的能力，为今后求解类似问题提供了一个很好的研究方法。关键词：遗传算法；神经网络；卡车调度优化中图分类号：TD8041．引言露天矿卡车实时优化调度系统是上世纪70年代后期电子通信技术与计算机技术相结合的产物。露天矿卡车实时优化调度系统的研发及其应用已经将近半个世纪的时间了，目前世界上已有50多个大型露天矿装备了这种系统，已在国外100多个主要基于卡车(或电铲——卡车)为运输工具的露天矿得到了成功应用，并取得了显著的经济效益。建立计算机控制卡车调度系统可以较大幅度提高矿山设备利用效率及整体产量；便于实时监控设备的运行状态与及时故障排查、维修；有利于矿石开采质量的搭配与调度控制；形成矿山生产过程的实时信息管理及决策支持系统；提升大型运转设备的使用效率、降低燃料和备件消耗。2．遗传算法、神经网络简介2.1遗传算法简介遗传算法是根据生物进化思想，根据“适者生存”和“优胜劣汰”的原则，而启发得出的一种全局优化算法，解决各种优化计算问题[1]。它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。但是，由于遗传算法常用定长的字符串来表达问题，因此很难用它来描述层次化的问题、也就不能描述计算机程序，从而缺乏动态可变性，只有改变问题的表达方法才可以解决这种问题；同时，它在理论和应用技术上也存在着许多不足和缺陷，其数学基础显得极为薄弱，因为它只是对“优胜劣汰”自然法则的模拟。缺乏深刻且具有普遍意义的理论分析。虽然遗传算法在运输方面有过成功的应用，但是以上的缺陷限制了遗传算法在运输问题上的应用[2]。2.2神经网络简介人工神经网络（ArtificialNeuralNetworks，ANN），简称“神经网络”,它是作为对人脑最简单的一种抽象和模拟，是对人类大脑的一种物理结构上的模拟，以使系统具有人脑的某些智能。以神经网络求解大系统多目标规划问题，可以有效地克服传统动态规划计算方法所存在的“维数灾”问题，由于神经网络的并行计算结构，使得其计算求解速度几乎与动态规划问题的维数无关，这对于卡车实时调度系统优化问题尤其重要，这里所给出的神经网络具有全集成化的特征，结构简洁、紧凑、高效，适宜于硬件实现及实际应用。但是，神经网络作为一种数学方法毕竟是对人脑的一种模拟，还远远达不到人脑的思维功能，存在的缺点主要有：不适合于高精度计算、学习问题没有根本解决；目前没有很完善的学习方法，经验参数太多。然而神经网络优化方法有易陷入局部极小点和处理罚函数困难等固有缺点。2.3神经网络与遗传算法的集成神经网络和遗传算法作为很好的优化方法，它们各自的特点决定了它们是以后解决优化问题的方向所在。这里所指的神经网络与遗传算法的结合是指用遗传算法取代ANN的权值的学习。ANN的学习是按照某种组合性能指标，在可能的网络空间上，搜索具有最优性能的网络形势，ANN的性能曲面一般很复杂，可能的处理单元数目及连接是无界的，因而曲面无限大，处理单元数目离散取值，导致网络性能非连续，故性能曲面不可微，但对于神经网络来说，遗传算法所处理的每个个体是单独的一个网络，所涉及的参数即网络节点之间的连接权值均为实数，同时神经网络的结构参数一般是整数型的，而遗传算法可以方便的表示逻辑值和实数值，因此遗传算法在神经网络的优化中得到了广泛的应用[3]。3.卡车调度系统优化总体算法流程(1)确定片车调度系统优化对象，并且将优化目标及其约束转化成Hopfield神经网络的能量函数。(2)产生初始种群，随机产生N个染色体数字串，组成初始种群，其中每个染色体表示一种参数组合对应的神经网络模型；随机产生一组权重值，利用某种编码方案对每个权重值进行编码。将网络中的权重值依次排列构成编码链。每个编码链代表网络的一种权重分布状态，一组编码链则代表一组不同权重值的神经网络。(3)选定网络结构和学习规则。(4)计算对应的神经网络的误差函数，从而给出遗传算法所需的适应度函数，误差愈小适应度值愈高。(5)选择若干适应度函数值最大的个体构成父本。(6)利用选择、交叉、变异遗传操作运算，产生出新一代群体。(7)新种群满足性能评价标准或到达给定代数，转到9)，否则转到4)重复执行，使权重值分布不断进化，直至达到训练目标为止。(8)将达到训练目标的权重代入神经网络进行网络训练，直到网络达到稳定的平衡点。(9)结束。4．工程实例以抚顺西露天矿为例，抚顺西露天矿共有12台电铲，其中正常工作口里有9台电铲分布在九个不同的开采区，剥离出来的矿石和岩土需要排放到两个不同地方的排土场以及三个不同的煤矿石卸载加工中心，保证开采工作能正常进行。我们分别命名九个不同的铲区分别为：,,21UU…,9U开采量经测算分别为：820,980,670,1850,2100,350,430,460,540987654321=========uuuuuuuuu，5个不同的卸料点分别为：54321,,,,VVVVV,其处理能力分别为450,750,680,3420,285054321=====vvvvv万m3，从iU（i=1，2，…9）到jV（j=1，2，…5）的运价是ijC（元/m3）。表1抚顺西露天矿铲、卸点基本参数统计表6-1得知，∑==++++++++=91820082098067018502100350430460540iiu万m3，∑==++++=51835065075068034202850iiv万m3，即∑∑==9151iiiivu，可见该问题属于运输不平衡问题。为了将该不平衡问题转化为平衡问题，这里增加一个虚拟的采点10U,并假设其运价等同于铲点9U运往各个卸点的运价，这样就使得铲点开采量和卸点处理量相同[4]，即∑∑===10151iiiivu。则该问题经过上述转化后就可以描述如下：（1-1）运用遗传——Hopfield神经网络模型进行求解，当网络达到平衡点时可得决策变量最优解X及其最优值Y，网络训练平衡点如下图1所示。=1.0e+003*0.00000.54000.00000.00000.00000.46000.00000.00000.00000.00000.00000.42000.01000.00000.00000.00000.00000.35000.00000.00000.00002.10000.00000.00000.00001.49000.36000.00000.00000.00000.00000.00000.00000.67000.00000.90000.00000.00000.08000.00000.00000.00000.27230.00000.54770.00000.00000.04770.00000.1023即x12=540，x21=460，x32=420，x33=10，x43=350，x52=2100，x61=1490，x62=360，x74=670，x81=900，x84=80，x93=272.3，x95=547.7，x10，3=47.7，x10，5=102.3其余都为零，求得z=423,640,000元。其中xij，i=1,2,…10；j=1,2,…5是50个决策变量，表示铲点iu到卸点jv的总运输量。就是说在此情况下可使得总运输费用z最小为423，640，000元，其他情况的调度将会使得费用大于423，640，000元，但是还须扣除虚拟铲点10u的运输费用（47.7*3.7+102.3*4.6）*1.0e+004=6，470，700元，即423,640,000-6,470,700=417,169,300元，则实际最小总运费为4,171693亿元。针对上述问题，采用遗传算法-神经网络模型进行训练，当到达网络平衡稳定点时，一个到达平衡点的训练轨迹如图6-2所示。整个网络训练最终会达到网络能量最小的状态，即网络的稳定状态，所有网络训练到达平衡状态点的轨迹如下图6-3所示。针对以上问题，如果使用传统的方法，很明显该问题有50个决策变量，将容易陷入“维数灾”导致问题无法顺利解决。同样使用其它优化方法得到的结果可能是局部最优解，导致错误，也有可能得到相同的结果，但是其它的方法要复杂得多，而且费时、费力。．总结本文对遗传算法和神经网络只是进行了粗浅的研究，文中还存在种种不足之处；但是提出的基于遗传算法的神经网络方法，很好的结合了遗传算法全局搜索能力的优点和Hopfield网络局部搜索能力强的优势，相对地弥补了各自的缺点，为遗传算法和神经网络这两大领域的研究工作提供了一定的价值，同时也为以后可能出现的其他领域复杂问题的优化提供了一个很好的研究方法。参考文献[1]孙艳丰,王重托.遗传算法在优化问题中的研究进展[J].控制与决策.1996.11[2]陈国良.遗传算法及其应用[M].北京：人民邮电出版社,1996年.[3]李春时.遗传算法在神经网络设计重的应用[J].大连民族学院学报,2002年.[4]曹鲁寅,罗斌,钦明浩.用遗传算法求解最短路径问题[J].合肥土业大学学报,1996.9.ResearchonGA-NeuralnetworkoptimizationofsurfaceminetruckdispatchingsystemLiuGuangwei1，JiangJian21.CollegeofResourceandEnvironmentEngineering,LiaoningTechnicalUniversity,Fxuxin,Liaoning(123000)2.PingzhuangCoalGroupLtd.Co,Chifeng,Neimenggu(024076)AbstractThispaperintroducedalgorithms,characteristicsandrealizeofthetwooptimizationwhicharetheneuralnetworksandgenetic.Accordingtotheconditionsoftheircomplementarystrengths,anewmethodisbeenraised,thatiscalledGA-Hopfieldnetwork,whichisanoptimaloptimization,usingstrongglobalsearchcapabilityofGAtocompensateHopfieldnetworkvulnerableforshortcomingofthelocal,andthengivingthealgorithmsprocess.BytheoptimizationactualresearchontheFushunWesternSurfaceMinedispatchsystemandplanninglong-termgeneralproduction,itnote