混合粒子群算法在ETV调度优化中的应用

丁 芳 宋小静

(中国民航大学电子信息与自动化学院 天津 300300)

0 引 言

近年来，随着航空物流的快速发展，国内的许多大型机场建立了自动化货运站,其处理的货物80%是集装货物。由于空中管制等原因，飞机通常在某个时间段内进出港，导致进出库任务较集中。目前国内大型机场由ETV完成出入库的任务，传统ETV采用链式调度策略，制约了运行效率。因此，ETV调度算法的研究对提高机场货运站物流过程的转运效率具有重要的意义。

集装货物在航空货运站的位置和平面示意图如图1所示。图中，集装货物区位于货运站空侧和路侧交接区域；集装货物区有多个IO口。

图1 集装货物区位置

ETV是机场货运区立体仓库中转运集装货物的主要设备，其功能与自动化立体仓库中的堆垛机类似。近年来，许多学者针对机场货运区ETV的优化调度进行了研究。文献[1]采用混合线性模型求解ETV调度问题，将调度过程中消耗最低总能量设为优化目标，并考虑了装载及容量限制等约束条件提高了ETV的工作效率，但是该规划的方法建模困难，对参数敏感，求解大规模问题适应性较差。郭春晖[2]基于五段S型运动模型,提出了改进遗传算法对ETV的调度进行优化,提高了全局寻优能力，但是5段模型忽略了ETV在移动距离较短的情况下达不到最高速度的情况,误差较大。文献[3]在遗传算法中引入小生境模型分析双机ETV调度问题，使得立体仓库的存取效率得到提高。但是改进的遗传算法仍然存在收敛速度慢、需要迭代的次数较多且存在早熟问题。杨玮等[4]采用改进的粒子群算法对多轨道多任务的出入库任务进行优化；邱建东[5]采用NLA-PSO算法对ETV调度系统进行了研究。这些学者[4-5]均采用粒子群算法求解ETV调度问题，但是算法迭代后期缺乏跳出策略，使粒子易陷入局部最优。混沌系统是对初始值极其敏感的非线性动力系统，是介于确定系统和随机系统之间的一种状态，处于混沌状态的粒子可以遍历吸引子附近的所有点，利用混沌系统的伪随机性、遍历性和规律性的特点，混沌优化算法有效地解决了组合优化问题[6]。本文在标准粒子群算法的基础上引入动态自适应策略与混沌思想，以三者融合后的混合粒子群调度算法求解ETV控制系统的调度问题，从而提高了机场货运区ETV的转运效率。

1 ETV调度模型的建立

与传统的立体仓库相比，机场货运区立体仓库在货架的底层分散设置了多个出入库口，使ETV载物台在取到ULD集装货物后不需要运动到巷道端口，就可以在立体货架工作区域内直接出库。

称ETV需要在某个时间段内处理多个任务组成的集合为任务集。ETV处理的任务类型分三种：入库、出库、倒库。建立ETV调度模型的目的是求得一组作业时间最短的任务序列。一个确定的任务序列包括一组排列有序的任务，为便于研究，本文将每个任务的起始和目的货位地址均映射为三维空间中的坐标点。任务序列中有序任务的坐标点依次相连形成的链状结构称为任务链，其中坐标点称为节点，节点间的线段代表ETV在节点间的运行路径。

ETV在完成出入库任务的过程中一般采用复合作业即完成一个任务后可运动到下一个任务的起始地址，而非运动到原点，如图2所示。

图2 ETV调度过程复合作业的方式

图中假设IN为入库口、OUT为出库口、X轴为某货架的列数，Y轴为对应货架的层数，A、B、C、D表示4个随机的货位。其中IN到A是入库任务、B到C是倒库任务、D到A是出库任务。

设ETV在实际工况下的某个任务集为C={C1,C2,…,CN}，C中包含有N个任务，其中入库任务的集合为Ar={Arj}，Arj=[ArajArbj]，Araj表示入库任务的起始货位、Arbj表示入库任务的目的货位；出库任务的集合为Ac={Acj}，Acj=[AcajAcbj]，Acaj表示出库任务的起始货位、Acbj表示出库任务的目的货位；倒库任务的集合为Ad={Adj}，Adj=[AdajAdbj]，Adaj表示倒库任务的起始货位、Adbj表示倒库任务的目的货位。令货位的向量为ζ=[X，Y，Z，λ]，其中X为货架的层数，Y为货架的列数，Z为货架的排数，λ表示货位的载物情况，λ=1表示满载，λ=0表示空载。令入库口的集合为IN={INi},入库口的集合为OUT={OUTi}。

设该任务集生成的某个任务序列映射的任务链节点的个数为M，任务序列的执行时间如下式所示：

(1)

式中:Ti,i+1为任务链中ETV在相邻两个节点之间的行走时间，tM′和ti分别为任务链终节点和第i个节点处ETV载物台与货位间货物转运时间。

ETV的运动是水平方向和垂直方向的复合运动，因此ETV在两货位点间的行走时间应是两种运动时间的较大者：

ETV调度优化问题的实质是在众多可行解的任务序列中，寻求运行时间最短的任务序列，则ETV调度优化的目标函数为：

T=minTμμ=1,2,…,n

(3)

在实际工况下，还需满足以下约束条件：

1) 任务链中入库任务的源货位点必须是入库口，目的货位点不能满载。

Arj(ζa)∈IN且Arj(ζb(λ))≠1

(4)

2) 任务链中出库任务的源货位点不能为空，目的点必须是出库口。

Acj(ζb)∈OUT且Acj(ζa(λ))≠0

(5)

3) 任务链中倒库任务的源货位点不能为空，目的货位点不能满载。

Adj(ζa(λ))≠0且Adj(ζb(λ))≠1

(6)

4) 任务序列中所有任务的合集等于任务集。

Ar∪Ac∪Ad=C

(7)

5) 任务序列中任意两两任务不相交。

As∩Ap=∅s,p∈N

(8)

2 粒子群优化算法及改进

2.1 基本粒子群算法

基本粒子群算法中，假设目标搜索空间为D维空间，粒子群体大小为N，依据Eerhart[7]的带惯性权重因子的改进算法，每个粒子的速度和位置更新的数学表达如下：

式中:w为惯性系数，c1、c2分别为认知系数和社会系数，Pid为单粒子最优适应度，Pig为所有粒子的最优适应度。ETV的适应度函数为式1。

ETV所在立体仓库货位号的形式为：a-b-c。其中，a为货架区域、b为货位层数、c是货位列数，将ETV任务排序形成任务集。为了使货位号和粒子建立联系，需要将三维立体仓库货位号映射为一维数字，按照先按区再按层最后按列的顺序进行映射和逆映射，如下式所示：

nu=(a-1)×5+b+(c-1)×10

(10)

式中:floor为求最小整数计算。

映射后的任务序号按照任务集的顺序排列成一个N维向量，将此向量看作一个工件加工次序，对应N维粒子的一个坐标。粒子每次更新后各坐标分量按照降序排列，对应一个新的加工次序。实例如表1所示。

表1 粒子SMC编码

表1中，新的任务次序为1→6→3→2→5→4。每次更新后按照式(1)计算适应度值，如果适应度值比个体最佳适应度更优则更新个体最佳适应度。如果所得适应度比全局最佳适应度更优，则更新全局最佳适应度。当迭代次数达到最大设定值不再更新时停止运算，此时的全局最佳适应度为粒子群算法的最优解，对应的序列为最优ETV执行序列。

2.2 算法改进

2.2.1加速因子自适应调整策略

针对单机ETV的调度优化问题，标准粒子群算法存在早熟收敛、易陷入局部极值的缺点。为提高粒子的全局与局部搜索的平衡能力，本文算法引入了加速因子的自适应调整策略，使微粒能够在迭代初期扩大整个解空间的搜索范围，在后期增强局部最优解的搜索能力。

认知因子c1和社会因子c2分别用于驱使粒子向自身及全局最佳位置运动。迭代初期c1取较大的值有利于突出自身优势避免早熟，迭代过程中c1值和算法的收敛速度有关，即c1减小得越快收敛速度越快；迭代后期c1减小得越慢越有利于局部挖掘。因此c1应非线性递减，其公式如下所示：

类似地，在迭代初期c2取较小的值可降低其他粒子的影响，提高整个解空间的搜索能力；迭代后期增加c2值可提高群体经验共享能力，有利于局部寻优。因此c2应非线性递增，其公式如下所示：

式中：c1s、c2s分别为c1与c2的初值、c1e、c2e分别为c1与c2的终值。

2.2.2混沌映射

ETV模型为典型的多维PSO模型，多维PSO极易陷入局部寻优且难以跳出。混沌系统是类似随机的一种伪随机运动，具有遍历性、伪随机性及规律性等特点，能在吸引子的邻域不重复地遍历所有的点。利用混沌变量对这些特性进行优化搜索，保持粒子群体的多样性，改善算法的全局寻优能力。

在迭代初期，用混沌序列对种群粒子进行初始化，保证粒子在搜索空间较均匀地遍历性分布[8]，同时，利用混沌算子替代引入动态自适应调整的粒子群算法中的随机数，改善算法的随机性以提高粒子的搜素效率；在迭代中后期，为解决粒子早熟的问题，本文借助混沌算子对粒子的位置扰动对算法进行改进，从而保持群体多样性，克服算法易陷入局部极值的缺点。

不同的混沌系统有着不同的最大lyapunov指数，因此有着不同的对初值的敏感程度，文献[9]中指出Tent映射比Logistic映射具有更好的遍历均匀性和更高的搜索效率。Tent混沌映射算子的迭代公式如下所示：

本文将映射算子嵌入到全局最优Pig中对早熟的粒子进行扰动，得到下式：

Pig=Pig×(rn)s

(15)

式中：Pig为全局最优，rn为n次迭代的混沌迭代算子。s为自适应项，当全局最优值超过累加器设定的最大值MAX粒子仍未更新时s=1，否则s=0。通过引入混沌变异，使得陷入局部最优的粒子跳出局部解。

图3为随机与混沌两种方法独自生成范围为0～1的初始粒子，由图可知: 混沌序列法生成的微粒更均匀地分布在整个解空间，有利于提高粒子的搜索效率，更快地获取最优解。

图3 混沌与随机序列初始化粒子对比图

2.2.3粒子不改进及早熟判别机制

粒子群算法在迭代过程中，种群中每个粒子均追随自身历史最优和全局历史最优两个极值点。如果某一粒子搜索到了新的全局最优点，那么其他粒子会迅速地靠近该点，种群的多样性收到影响。如果该点为解空间的局部最优点，各粒子将聚集在该点，产生不改进现象。因此可用种群各粒子之间的离散程度描述粒子不改进现象。本文结合了粒子的平均粒距、适应度方差以及汉明距离作为粒子不改进判断机制，采用粒子连续不改进次数的最大值作为早熟的判别机制，当粒子出现早熟时，利用混沌扰动更新微粒的位置使其跳出当前局部最优，进而搜索解空间的其他区域。

文献[10]使用平均粒距从空间角度描述了粒子之间分布离散程度，其定义如下：

(16)

式中:M为种群大小，L为解空间维数，由式(14)可知平均粒距和种群大小、粒子维数独立，且平均粒距越小粒子越集中。

文献[11-12]使用种群适应度方差从函数值角度描述粒子间个体的聚集程度，其定义如下：

式中:M为种群大小，fi为某粒子适应度，f′为全部粒子适应度的均值，f为归一化因子用来限制适应度方差范围，其定义如下：

当粒子聚集于两个或多个适应度相差不大的极值点时，适应度方差可能小于阈值ε但是平均粒距却不收敛。所以粒子群算法中单独判断粒子聚散不够充分，应当讨论收敛在单极值点附近时粒子的聚散程度，即在满足适应度方差收敛的前提下满足平均粒距收敛。

由于ETV最优解是一维数组，而搜索空间却是连续的，因此可能会出现适应度方差、平均粒距收敛但是ETV解却不收敛的情况。例如ETV的两个粒子坐标及对应的解如表2所示。

表2 粒子编码

表2中两粒子的粒距很小，但此时ETV的解并不收敛。因此针对本文ETV调度序列求解问题时引入汉明距离[13-14]在粒子适应度方差及平均粒距均收敛的情况下，判定序列的相似度，从而判断粒子是否不改进。

汉明距离统计的是两个等长数列之间对应位置出现不同数值的次数用来描述序列之间的相似程度s[15-16]。通过与设定阈值ε相比较，判断序列是否相似，相似度公式如下所示：

评判早熟有多种方法，本文采用粒子连续不改进次数的最大值MAX作为早熟的判别机制，为每个粒子设定一个累加器，迭代过程中粒子不更新则累加器加1，否则置0。当粒子不更新的次数小于累加器设定的最大值时，粒子进行正常搜索；当粒子不更新的次数超过累加器设定的最大值时，对该粒子进行混沌扰动，并对累加器进行复位。

2.2.4改进算法流程

Step1初始化参数。主要有：种群数量M，维度L，加速因子c1、c2，最大迭代次数Nmax，适应度方差阈值d，平均粒距阈值σ，汉明距离阈值ε，累加器最大计次数O，混沌映射初始化粒子。跳转到Step2。

Step2判断是否满足停止条件，如果未达到则跳转到Step3，如果达到则跳转到Step8。

Step3判断粒子有无改进。按照式(6)计算粒子适应度，确定该次迭代的个体、全局最优位置和对应的个体、全局最优值。按照适应度方差、平均粒距、汉明距离公式判断各粒子是否有改进，如果有改进则跳转到Step4，如果无改进则跳转到Step5。

Step4累加器置零，跳转到Step6。

Step5累加器加一，如果累加器数字小于最大计次O则跳转到Step6，否则累加器置零跳转到Step7。

Step6非线性位置更新。按照式(10)-式(11)进行迭代，然后跳转到Step2。

Step7混沌扰动。按照式(13)进行迭代，然后跳转到Step2。

Step8结束并输出最优结果。

3 实例仿真与结果分析

某机场ETV设计参数为：Vimax=2 m/s、Vjmax=0.33 m/s、aimax=0.5 m/s2、ajmax=0.3 m/s2、Ji=1 m/s3、Jj=0.5 m/s3、ULD货位长度和高度均为3.75 m、共有45列5层货位。空侧I/O口有7个，路侧I/O口为6个。模型以空侧为入口，路侧为出口为例进行研究。以式3为目标函数，选取文献[5]中的样本调度任务集如表3所示。

表3 任务集

为尽可能地弱化比较结果的随机性和提高比较结果的可信度,目标函数用本文及对比算法分别计算10次并将10次结果的平均值作为评价指标进行对比，如下式所示：

式中:record记录了10次平均结果。

针对ETV的调度问题，首先将标准粒子群算法与遗传算法、模拟退火及蚁群算法三中经典的调度算法进行对比，寻优曲线如图4所示。

图4 粒子群算法与其他经典算法的迭代寻优曲线

由对比图可知遗传算法、模拟退火、蚁群算法在求解ETV调度问题的过程中都存在易早熟、易陷入局部最优的缺陷，且遗传算法收敛速度太慢。标准粒子群算法相比其他几种算法收敛速度快、寻优效果好，因此本文在标准粒子群算法的基础上研究改进的调度算法能够最大化地提高ETV的转运效率。

为验证本文改进粒子群算法的有效性，将本文算法的结果与标准的粒子群算法(PSO)、非对称线性调节粒子群算法(NsLF-PSO)[17]、非线性学习因子粒子群算法(NLA-PSO)[5]、混沌粒子群算法(IACPSO)[18]对比。本文改进算法各参数设置为：种群规模M=40；惯性权重w=0.9；认知因子c1的初值为c1s=2.5，终值为c1e=1；社会因子c2的初值为c2s=0.5，终值为c2e=2.25；k1和k2均为π/4，k为1；最大迭代次数为3 000。标准PSO的惯性权重w=0.9，c1、c2为2。NsLF-PSO的最大粒子速度Vmax为1。NLA-PSO的c1s为2.5、c1e为1、c2s为0.5、c2e为2.25，k1和k2均为π/4，k为1。为保证比较结果更加客观公正，对比算法的种群规模与最大迭代次数分别设定为40和3 000。所有算法均使用表3所示任务集实验10次并求取平均值作为一次最优解。其结果如表4和图5、图6所示。

表4 不同算法寻优结果对比

图5 ETV目标函数不同算法的迭代寻优曲线

图6 改进PSO与链式调度最优解对比图

由表4可以看出，和标准的粒子群算法、非对称线性调节粒子群算法、非线性学习因子粒子群算法及混沌粒子群算法相比，本文算法在求解ETV调度问题时最优解的平均值最小，表明改进的的粒子群算法寻优效果最好；最优解标准差最小，说明改进算法稳定性最好。由图5可以看出，相比其他算法，本文算法收敛速度快，且在迭代中后期其他算法陷入停滞而本文算法持续更新，说明本文算法能够较好地防止早熟收敛，具有较强的全局搜索能力。由图6可以明显看出，本文改进算法的最优解很大幅度上优于传统链式调度算法，且由表4数据可以计算出，本文改进算法相比传统链式调度平均最优解的任务调度时间缩短了15.6%，说明本文算法在实际应用中能够较好地解决ETV转运效率低的问题。

4 结 语

研究机场货运区ETV调度算法对于提高机场货运站货物处理能力具有重要意义，是满足日益增长的航空货运量的有效途径。本文对机场货运区ETV的调度问题进行了研究，建立了ETV的调度模型并提出了混合粒子群调度算法。引入非线性自适应策略对参数进行自适应调整，利用混沌系统的伪随机性、遍历性和规律性的特点对粒子进行初始化使粒子能够均匀分布，提高粒子的搜索效率。通过改进的粒子早熟判别机制并利用混沌扰动使陷入局部最优的粒子能够进行位置更新，增加了粒子种群迭代末期的多样性，有效地避免粒子早熟收敛，提高了算法的全局搜索能力，加快了算法的收敛速度。最后经过实例仿真验证了本文算法对比其他算法在求解ETV调度问题上具有较好的收敛性、稳定性、寻优性，相比传统调度能够更大化的提高ETV的转运效率。