求解露天矿低碳运输调度问题的改进灰狼优化算法

门飞，蒋欣

(平顶山工业职业技术学院 计算机与软件工程学院， 河南 平顶山 467000)

0 引言

在露天矿生产中，运输过程会排放大量的碳，运输能耗约占露天矿总能耗的60%[1]，运输费用约占总生产费用的50%[2]。露天矿低碳运输调度优化成为促进露天矿高效生产、减少碳排放量和运输费用的关键环节。

露天矿低碳运输调度问题可看作是在满足露天矿生产的约束条件下，求解露天矿碳排费用和运输费用之和最小的多目标优化问题。近年来，许多学者采用仿生算法求解露天矿运输调度问题，如自适应果蝇优化算法(Adaptive Fruit Fly Optimization Algorithm，AFOA)[2]、基于差分的生物地理学算法[3]、粒子群算法[4]、模拟退火算法[5]、差分进化算法[6]、遗传算法(Genetic Algorithm，GA)[7]、蚁群算法[1，8]等。然而，上述算法存在全局寻优能力较差、需调节参数较多的问题。

灰狼优化(Grey Wolf Optimization，GWO)算法是一种通过模仿灰狼种群社会阶层和猎食过程而提出的仿生算法，该算法需要调节的参数较少、较易编程实现、全局寻优能力较强[9-10]，已被应用于求解流水线车间调度[11]、函数优化[12-13]、多层传感器训练[14]和电力系统优化[15]等问题。然而，随着GWO算法的迭代进化，灰狼种群的多样性逐步减少，算法陷入局部最优的概率增加，导致局部寻优能力减弱，难以均衡全局寻优能力和局部寻优能力。本文在GWO算法中引入迁移操作，并且根据不同的灰狼自适应调整其迁移概率，提出了一种改进的GWO(An Improved Grey Wolf Optimization，AGWO)算法，并将其应用于求解露天矿低碳运输调度问题。

1 露天矿低碳运输调度问题数学模型

在实际的露天矿生产过程中，多个采矿场往往同时开展采矿工作，然后将矿石分别运输至不同的破碎场进行破碎工作。各个采矿场到破碎场的运输距离不同，因此，运输过程产生的碳排费用和运输费用也会不同。露天矿低碳运输调度问题的本质是寻找碳排费用和运输费用之和的最小值。

(1) 碳排费用。卡车在第i(i=1，2，…，I，I为采矿场个数)个采矿场Mi和第j(j=1，2，…，J，J为破碎场个数)个破碎场Dj之间的运输过程中，需要从采矿场Mi满载至破碎场Dj，然后空载返回采矿场Mi。因此，碳排费用为

(1)

(2)

露天矿低碳运输调度问题的数学模型为

(3)

式(3)为目标函数，式(4)—式(9)为约束条件。式(4)和式(5)表示卡车装载量不应超过开采量和破碎量；式(6)表示每辆卡车最终必须返回至出发时的采矿场；式(7)表示运载卡车的数量应该在卡车总数之内；式(8)表示卡车不能从一个采矿场到另一个采矿场；式(9)表示变量约束。

2 算法原理

2.1 GWO算法

灰狼是以群居为主的食肉动物，种群内具有不同的社会阶层，从上至下依次分为α，β，δ，ω层。每个阶层的灰狼负责相应的猎食工作：α层为灰狼领导层，统管种群内各种事务；β层为灰狼管理层，辅佐α层规划猎食事务；δ层为灰狼普通层，负责遵守α，β层的指示；ω层为灰狼底层，负责听从α，β，δ层的命令[16-17]。

GWO算法的基本思想：灰狼种群在追捕猎物过程中，灰狼首先根据猎物的味道等信息逐步地接近猎物，构建包围圈；然后，其他灰狼在α，β，δ层灰狼的带领下，逐渐缩小包围圈；最后，灰狼种群有组织地对猎物发动攻击，直至捕获到猎物[18-19]。GWO算法求解问题的一般步骤：① 初始化算法参数和种群方位；② 计算适应度函数值；③ 灰狼种群进行包围操作；④ 灰狼种群进行狩猎操作；⑤ 灰狼种群进行攻击操作；⑥ 当满足终止准则，输出结果。

2.2 AGWO算法

在GWO算法中，灰狼种群根据当前最优灰狼的方位更新方位。然而，随着迭代次数的增加，大部分灰狼种群逐步聚集在当前最优灰狼附近，若当前最优灰狼的方位不是全局最优，则易陷入局部最优，无法快速寻找到全局最优。因此引入迁移操作构成AGWO算法，赋予灰狼自适应的迁移概率，由迁移操作重新生成的灰狼能更靠近全局最优，改善种群的多样性，降低陷入局部最优的概率，促使快速收敛至全局最优。AGWO算法求解问题的步骤如下。

(1) 初始化算法参数和种群方位。假定Xh=(Xh1,Xh2,…,XhL)为第h(h=1，2，…，N，N为灰狼种群大小)个灰狼的方位。初始化方位信息时，第h个灰狼的第d(d=1，2，…，L，L为搜索空间维度)维方位为

Xhd=Xmind+(Xmaxd-Xmind)rand()

(10)

式中：Xmind，Xmaxd分别为第h个灰狼的第d维方位的最小值、最大值；rand()为区间[0，1]的随机数。

(2) 计算适应度函数值。适应度函数值反映了灰狼寻找最优的能力，通常由目标函数转换而来。适应度函数值较低则说明该灰狼所在方位较好。AGWO算法在迭代进化时，适应度函数值较低的灰狼方位被保留，同时带领适应度函数值较高的灰狼逐步地靠近猎物。

(3) 包围操作。猎食开始时，灰狼种群先构建包围圈，接着逐步包围猎物。包围操作如下：

D=|CXp(t)-X(t)|

(11)

X(t+1)=Xp(t)-AD

(12)

A=2arand()-a

(13)

C=2rand()

(14)

式中：D为灰狼与猎物的距离向量；C为摆动因子向量；Xp(t)为第t代猎物的方位向量；X(t)，X(t+1)分别为第t，t+1代灰狼的方位向量；A为参数向量；a为收敛因子，a从2线性递减至0，表示灰狼种群逐渐缩小包围圈。

(4) 狩猎操作。基于α，β，δ层灰狼的适应度函数值，灰狼种群更新方位：

Dα=|C1Xα-Xp|

(15)

Dβ=|C2Xβ-Xp|

(16)

Dδ=|C3Xδ-Xp|

(17)

X1=Xα-A1Dα

(18)

X2=Xβ-A2Dβ

(19)

X3=Xδ-A3Dδ

(20)

X(t+1)=(X1+X2+X3)/3

(21)

式中：Dα，Dβ，Dδ分别为α，β，δ层灰狼与猎物的距离向量；C1，C2，C3分别为α，β，δ层灰狼的摆动因子向量；Xα，Xβ，Xδ分别为α，β，δ层灰狼的方位向量；Xp为猎物的方位向量；X1，X2，X3分别为α，β，δ层灰狼更新后的方位向量；A1，A2，A3分别为α，β，δ层灰狼的参数向量。

(5) 攻击操作。攻击操作主要通过收敛因子a逐渐递减完成。根据式(13)可知，随着算法的迭代进化，a线性递减为0，A逐渐递减为0，灰狼种群方位逐渐接近猎物方位。当灰狼种群与猎物方位相同时，表示灰狼成功捕获猎物，完成攻击操作。

(6) 迁移操作。每个灰狼生成一个 [0，1]的随机数，若该随机数小于迁移概率，则对该灰狼进行迁移操作；否则转至步骤(7)。

Pmh=Pm1(fmin+fh)/(fmax-fmin)

(22)

式中：Pmh为第h个灰狼的迁移概率；Pm1为标准迁移概率；fmin，fmax分别为适应度函数的最小值、最大值；fh为第h个灰狼的适应度函数值。

将迁移操作融入GWO算法，并且根据灰狼的适应度函数值动态地修正其迁移概率。一方面，对于较优灰狼(适应度函数值较低)，较小的Pmj可以保留较优灰狼的方位，避免算法错过全局最优，提升了全局寻优能力。另一方面，对于较差灰狼(适应度函数值较高)，较大的Pmj确保了较差灰狼可以被重新分配，分配后的灰狼可位于全局最优的周围，丰富了灰狼种群的多样性，加强了算法局部寻优能力，能快速地寻找到全局最优。

(7) 终止准则。当AGWO算法迭代至指定的进化代数，输出结果；否则转至步骤(2)。

3 仿真分析

为验证AGWO的有效性，以某露天矿实际运输调度数据为例，将AGWO应用于求解露天矿低碳运输调度问题，与AFOA，GWO，GA进行比较分析。

该露天矿包含10个采矿场和5个破碎场，采矿场至破碎场的距离见表1。卡车数量K=40辆；每辆卡车的装载量lk=40 t；卡车空载时单位距离油耗量yij1=0.08 L/(km·t)；卡车满载时单位距离油耗量yij2=0.22 L/(km·t)；燃油转化为CO2的单位转化率γ=2.65 kg/L；CO2的单位排放成本B3=0.25元/kg；每辆卡车的固定启用成本B1=20元/辆；每辆卡车的单位燃油成本B2=7.99元/L。

表1 采矿场至破碎场的距离Table 1 Distances between mining area and crushing station km

AGWO和GWO相关参数：搜索空间维度L=20，灰狼种群大小N=100，进化代数G=100。AGWO中的标准迁移概率Pm1=0.25。AFOA和GA参数设置分别与文献[2]和文献[7]中相同。为减少算法的时间复杂度，本文将露天矿运输调度的目标函数作为适应度函数。采用Matlab仿真露天矿低碳运输调度问题的求解。

AGWO，AFOA，GWO，GA的进化曲线如图1所示，可看出AGWO的寻优精度和寻优速度均优于其他算法。这是由于AGWO在初期继承了GWO较强的全局寻优能力，可以较快地聚集到全局最优附近；在后期灰狼种群逐渐集中在最优灰狼周围，此时迁移操作和自适应的迁移概率能够保留较优灰狼方位，重新分配较差的灰狼到新方位，从而降低了AGWO陷入局部最优的概率。

图1 不同算法的进化曲线Fig.1 Iterative curves of different algorithms

露天矿在实际运输中需要36辆卡车。根据式(1)—式(3)，结合表1和露天矿运输相关参数可知，露天矿的实际运输距离为1 882.227 km，运输费用为5 271.698元，碳排费用为374.093元，综合费用为5 645.791元。分别基于AGWO，AFOA，GWO，GA的露天矿低碳运输调度的碳排费用和运输费用见表2。可看出与实际运输数据相比，采用AGWO求解的运输距离减少了492.086 km，卡车数量减少了10辆，运输费用节省了1 419.531元，碳排费用节省了97.802元，综合费用节省了1 517.333元，采用AFOA，GWO，GA求解的综合费用分别节省了967.972，598.695，427.970元。由此可见，采用AGWO优化露天矿运输调度可有效提高运输效率，减少碳排费用和运输费用。

表2 不同算法下露天矿低碳运输调度结果对比Table 2 Comparison of open-pit mine low-carbon transportation scheduling results under different algorithms

4 结语

AGWO算法在GWO算法的基础上引入迁移操作，并且根据灰狼的适应度函数值自适应调整灰狼的迁移概率，提升了算法局部寻优能力，促使算法能够较快寻找到全局最优，均衡了全局寻优能力和局部寻优能力；将AGWO算法用于求解露天矿低碳运输调度问题，提高了寻优精度与寻优速度，有效提高了运输效率，减少了碳排费用和运输费用。