0 引言
运输优化对降低露天矿企业生产成本、提升竞争力具有重要意义[1-2]。随着人工智能技术的发展，智能优化算法被用于求解露天矿运输问题[3]。智能优化算法通常是针对无约束或边界约束优化问题提出的，而在露天矿运输问题中，除了边界约束之外还存在等式约束和不等式约束[4]，其中等式约束为智能优化算法的实施带来困难。因此，必须将智能优化算法与约束处理方法[5-8]相结合才能求解露天矿运输问题。文献[9]利用运输问题的目标函数和约束条件构造霍普菲尔德神经网络，使用遗传算法优化神经网络权值。文献[10]使用多目标优化的思路处理约束条件，利用带双引子的粒子群优化算法求解与运输问题对应的多目标优化问题。上述文献采用不同的智能优化算法和约束处理方法，取得了相应的成果，但存在容易陷入局部最优解的问题。
差分进化算法[11]具有操作简单、求解精度高的优点，是进化计算领域最重要的优化算法之一，已被用于解决换热网络优化[12]、并联机构位置正解[13]、电动汽车排放优化[14]、瓦斯涌出量预测[15]等问题。本文在差分进化算法中引入归一化操作，去掉了运输问题中的等式约束，提出了一种改进差分进化算法，并将其应用于露天矿运输问题的优化计算。
1 露天矿运输问题的数学模型
假设露天矿中存在I个装载点Ai(i=1，2，…，I)和J个卸载点Bj(j=1，2，…，J)；装载点Ai所在采区的开采能力为Pi，m3，卸载点Bj的受矿能力为Qj，m3；从装载点Ai到卸载点Bj的单位运费和运输量分别为Cij，元/m3和xij，m3。从降低运输成本的角度考虑，露天矿运输问题的目标函数可表示为
(1)
式中H(x)为总运费，x=[x11 x12…x1J x21 x22…x2J…xI1 xI2…xIJ]。
考虑到开采能力、受矿能力和运输行为的特点，露天矿运输问题还需满足式(2)—式(4)定义的约束条件，即装载点的矿石需要全部运出，运送到卸载点的矿石量不能大于其受矿能力，从装载点到卸载点的运输量不能为负。
(2)
(3)
xij≥0
(4)
2 差分进化算法
有边界约束的函数优化问题定义为
(5)
式中：f(Z)为目标函数；Z为决策向量；D为决策向量的维数；zd为决策向量的第d维分量；Ld和Ud分别为zd的下界和上界。
设种群大小为N，差分进化算法首先按照随机方式生成初始种群：
(6)
种群的每个个体Z1，Z2，…，ZN均为优化问题(式(5))的一个可能解。在算法运行过程中的每一代，差分进化算法需要执行变异、交叉、选择三类操作，以更新种群中每个个体的位置。
(1) 变异操作。对种群中第n(n=1，2，…，N)个个体Zn，由变异操作生成与Zn对应的变异向量：
Vn=Zr1+F(Zr2-Zr3)
(7)
式中：Zr1，Zr2，Zr3为当前种群中彼此不同的3个个体，并且均不是Zn；F为缩放因子。
变异操作产生的变异向量Vn的某些分量有可能违反边界约束，对于这些分量可取其边界值，即Vn的第d维分量Vnd可进一步按式(8)进行处理。
(8)
(2) 交叉操作。对个体Zn和变异向量Vn进行交叉操作得到试验向量Un，Un的第d维分量为
(9)
式中：R为交叉概率；r4为[0，1]内符合均匀分布的随机数；r5为随机整数，r5∈{1，2，…，N}。
R，r4，r5配合用以控制试验向量Un各分量的来源。
(3) 选择操作。若试验向量Un优于个体Zn，则在下一代种群中用Un代替Zn，否则保持Zn不变，即按式(10)进行选择操作。
(10)
3 改进差分进化算法
3.1 等式约束处理
首先定义
(11)
式中yij为装载点Ai到卸载点Bj的运输量xij占装载点Ai所在采区开采能力Pi的比例。
对yij进行归一化操作，可得
(12)
则
(13)
即理论上式(2)定义的等式约束可自动成立。
然而，实际计算发现，对某个装载点，会有很小的概率出现yij=0的情况，此时应跳过归一化操作。
3.2 非线性优化问题
利用惩罚函数法[5]处理式(3)定义的不等式约束，将式(1)—式(4)定义的露天矿运输问题转化为式(14)定义的仅存在边界约束的非线性优化问题。
(14)
式中：y=[y11 y12…y1J y21 y22…y2J…yI1 yI2…yIJ]；μ为惩罚因子；C为常数，本文取1元/m3。
3.3 算法流程
求解露天矿运输问题的改进差分进化算法流程：
(1) 设置算法参数，包括惩罚因子μ、种群大小N、最大进化代数G、交叉概率R及缩放因子F。
(2) 按随机方式生成初始种群。根据式(12)对种群中每个个体进行归一化操作，利用式(14)计算种群中每个个体对应的目标函数值，找到当前种群中最优个体。令n=1。
(3) 进行变异操作。根据式(7)和式(8)生成变异向量。
(4) 进行交叉操作。根据式(9)得到试验向量。
(5) 进行归一化操作。若试验向量中与某个装载点对应的各分量均为0，转到步骤(7)；否则对试验向量按式(12)进行归一化操作，得到归一化后的个体，利用式(14)计算其目标函数值。
(6) 进行选择操作。若归一化后的个体优于当前种群中的第n个个体，则更新种群中的第n个个体；若归一化后的个体优于最优个体，则更新最优个体。
(7) 令n=n+1。若n≤N，返回步骤(3)。
(8) 若达到最大进化代数，结束优化，输出最优个体；否则令n=1，返回步骤(3)进行下一代优化。
4 算法在露天矿运输问题中的应用
抚顺西露天矿共有9个装载点A1—A9，5个卸载点B1—B5，装载点所在采区的开采能力、卸载点的受矿能力及从装载点到卸载点的单位运费见表1。经试验，改进差分进化算法各参数取值：惩罚因子μ=1 000、种群大小N=100、最大进化代数G=5 000、交叉概率R=0.9、缩放因子F=0.5。
表1 露天矿运输相关数据
Table 1 Data related to open-pit mine transportation
考虑到改进差分进化算法是一种随机优化算法，重复进行100次优化计算，100组优化结果中最优总运费最大值为41 224.93万元，最小值为41 224.01万元，均值为41 224.21万元，标准差为0.19万元，表明改进差分进化算法具有较好的可重复性。
利用文献[9-10]算法和本文算法得到的最优运输量(四舍五入后保留整数部分)见表2。经检验，表2中3组最优运输量均满足式(2)—式(4)定义的约束条件，但文献[9-10]算法得到的最优总运费分别为41 717万元和44 090万元，均大于本文算法得到的最优总运费，表明通过改进差分进化算法得到了更好的运输方案。
表2 不同算法得到的最优运输量
Table 2 Optimal transportation volume of different algorithms
5 结语
改进差分进化算法针对露天矿运输问题中等式约束的特点，引入归一化操作去除了等式约束，有利于跳出局部最优解。应用结果表明，该算法具有较好的可重复性，有利于降低运输成本。
参考文献(References)：
[1] 李桂荣,尹江艳,郝全明.浅谈运筹学在矿业中的应用[J].黄金,2008,29(4):25-27.
LI Guirong,YIN Jiangyan,HAO Quanming.Application study of operational research in mining[J].Gold,2008,29(4):25-27.
[2] 方颜空,张修玉,邬艳礼.九架炉露天矿采掘带单元排土运输方案优化研究[J].矿业研究与开发,2017(11):99-101.
FANG Yankong,ZHANG Xiuyu,WU Yanli.Optimization research on the dumping transportation of cutting zone unit in Jiujialu open-pit mine[J].Mining Research and Development,2017(11):99-101.
[3] 苏楷,门飞.露天矿运输调度问题求解的自适应果蝇优化算法[J].金属矿山,2017，46(11):172-176.
SU Kai,MEN Fei.Adaptive fruit fly optimization algorithm for solving open-pit hauling dispatching optimization problem[J].Metal Mine,2017，46(11):172-176.
[4] 仇旺令,叶义成.露天矿运输问题优化及其算法[J].化工矿物与加工,2005,34(7):25-27.
QIU Wangling,YE Yicheng.Optimization and arithmetic of the open-pit transportation problem[J].Industrial Minerals and Processing,2005,34(7):25-27.
[5] 李宜萱,金治群,程军蕊,等.一种基于AEA算法的改进的惩罚函数法[J].计算机与应用化学,2014,31(12):1479-1484.
LI Yixuan,JIN Zhiqun,CHENG Junrui,et al.Study on an improved penalty function method for constraint problem based on AEA (IAEA) algorithm[J].Computers and Applied Chemistry,2014,31(12):1479-1484.
[6] 刘衍民,牛奔,赵庆祯.求解约束优化问题的多目标粒子群算法[J].计算机应用研究,2011,28(3):851-853.
LIU Yanmin,NIU Ben,ZHAO Qingzhen.Multi-objective particle swarm optimizer for solving constraint optimization problems[J].Application Research of Computers,2011,28(3):851-853.
[7] 刘大莲,张春花,杜金玲.基于种群分类排序的约束优化遗传算法[J].数学的实践与认识,2012,42(8):190-196.
LIU Dalian,ZHANG Chunhua,DU Jinling.An evolutionary algorithm based on classification and sorting for solving constrained optimization problem[J].Mathematics in Practice and Theory,2012,42(8):190-196.
[8] 郭中华,金灵,郑彩英.人工神经网络求解TSP问题的改进算法研究[J].计算机仿真,2014,31(4):355-358.
GUO Zhonghua,JIN Ling,ZHENG Caiying.Study on improved method of neural network to solve TSP[J].Computer Simulation,2014,31(4):355-358.
[9] 鞠兴军,李林,刘光伟.基于遗传算法的神经网络在露天矿卡车调度系统中的应用研究[J].露天采矿技术,2009,24(6):31-33.
JU Xingjun,LI Lin,LIU Guangwei.Application research on truck dispatching system based on neural network of genetic algorithm in surface mine[J].Opencast Mining Technology,2009,24(6):31-33.
[10] 李勇,胡乃联,李国清.基于改进粒子群算法的露天矿运输调度优化[J].中国矿业,2013,22(4):98-101.
LI Yong,HU Nailian,LI Guoqing.Open-pit hauling dispatching optimization based on improved PSO algorithm[J].China Mining Magazine,2013,22(4):98-101.
[11] STORN R,PRICE K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization,1997,11(4):341-359.
[12] 陈家星,崔国民,彭富裕,等.基于种群多样性的改进差分进化算法应用于换热网络优化[J].热能动力工程,2017,32(4):29-37.
CHEN Jiaxing,CUI Guomin,PENG Fuyu,et al.An improved differential evolution algorithm based on population diversity and its application in heat exchanger network synthesis[J].Journal of Engineering for Thermal Energy and Power,2017,32(4):29-37.
[13] 彭程.平面并联机构正解的拥挤差分进化算法求解[J].华北科技学院学报,2016,13(2):94-97.
PENG Cheng.Forward kinematics solutions of the planar parallel mechanism using crowding differential evolution algorithm[J].Journal of North China Institute of Science and Technology,2016,13(2):94-97.
[14] 卜凡靖,王耀南.电动汽车排放的改进差分进化算法[J].智能系统学报,2017,12(1):110-116.
BU Fanjing,WANG Yaonan.Study of electric vehicle emissions by applying modified differential evolution algorithm[J].CAAI Transactions on Intelligent Systems,2017,12(1):110-116.
[15] 王江荣,罗资琴,赵睿.投影寻踪在瓦斯涌出量预测中的应用[J].工矿自动化,2015,41(4):87-89.
WANG Jiangrong,LUO Ziqin,ZHAO Rui.Application of projection pursuit in gas emission prediction[J].Industry and Mine Automation,2015,41(4):87-89.