进港航班排序是指在满足最小安全时间间隔的前提下，优化进港航班降落序列和降落跑道以使进港航班的延误达到最小。进港航班排序能够有效地减少航班延误，减少经济损失，提高跑道利用率，因此在终端区管制和优化中有着十分重要的意义。

进港航班排序是一个典型的NP–C（nondetermi-nistic polynomial-complete）问题；该问题的解空间十分庞大，且对参数（航班数量、跑道数量等）十分敏感^[1]。针对该NP-C问题，国内外的相关学者提出了一些行之有效的算法，比如时间提前算法^[2]（TA: time advanced）、约束位置交换^[3]（CPS: constrained position shift）、模糊评判法^[4]、分支定界法^[5]等。FCFS（first come first serve）算法按照预计到达时间为航班安排降落序列并分配跑道；该算法操作简单，常被用作比较基准。

随着群智能优化算法的快速发展，更多的研究人员利用智能算法对单跑道或多跑道进港航班排序问题进行了研究，比如文献[6–7]提出的改进遗传算法（GA: genetic algorithm）、文献[8]提出的改进分布估计算法（EDA: estimation of distribution algorithm）、文献[9]提出的线性微分递减模拟退火粒子群算法（LDD-SA-PSO: simulated annealing particle swarm optimization with linear differential decrease）等。

DE（differential evolution）作为群智能优化算法的一个重要分支，是由Storn和Price针对实参优化问题而提出的一种全局优化算法^[10–11]，它与GA有着相似的原理，如变异、交叉、选择操作；DE控制参数少（种群规模NP、缩放因子F和交叉概率CR），收敛速度快，简单易实现，是一种十分有效的启发式进化算法。目前，DE已经广泛应用于函数优化、神经网络优化、工业控制、图像处理等众多科研和工程领域^[12–14]。

然而DE与其它进化算法一样容易陷入局部最优，存在早熟收敛现象。为了提高DE的优化性能且使控制参数的选择独立于优化问题，许多学者提出了改进的DE算法。文献[15]提出了一种FAdE（fuzzy adaptive dE）算法，该算法利用模糊逻辑控制来调节控制参数F和CR，但是不易确定它们的模糊隶属函数。文献[16]提出的jDE算法对多数测试函数都能获得良好的优化效果，但控制参数F_i和CR_i的调节缺乏进化过程的指导，具有一定的盲目性。文献[17]提出的SaDE（self-adaptive DE）实现了变异模式和控制参数的自适应，且F和CR服从正态分布。文献[18]提出的JADE算法采用了一种新的变异模式和控制参数自适应策略。文献[19]提出的CoDE（composite DE）将3种变异模式与3组固定的控制参数随机组合。文献[20]提出的DMPSADE（self-adaptive DE with discrete mutation control parameters）虽然整体优化性能要优于参与对比的其它DE算法，但计算过程过于复杂，计算量较大。

为提高DE的优化性能和实用性能，作者采用精英存档策略和控制参数自适应策略，提出一种精英存档自适应微分进化算法（EASaDE）。选用9个常用于优化比较的Benchmark函数对EASaDE、基本DE、jDE^[16]、SaDE^[17]、JADE^[18]、CoDE^[19]、DMPSADE^[20]进行对比分析；实验结果表明EASaDE具有很高的全局探索能力和局部开发能力。

为进一步验证EASaDE的有效性和实用性，将EASaDE应用于多跑道进港航班排序问题，并与其它不同的优化算法（FCFS、GA^[6]、EDA^[8]、LDD-SA-PSO^[9]）进行比较。实验结果表明EASaDE是一种求解多跑道进港航班排序问题的有效方法。

1 多跑道进港航班排序模型

作者采用的多跑道机场模型为平行跑道模型，且其运行模式为独立平行仪表进近模式。假定在某段时间内，有N架航班 $\{ {f_1},{f_2}, \cdots ,{f_N}\} $ 需要按一定顺序降落在R条跑道上， $E_i^r$ 和 $S_i^r\left( {1 \le i \le N, 1 \le r \le R} \right)$ 分别表示航班f_i到达跑道r的预计降落时间（ETA: estimated time of arrival）和实际降落时间（STA: scheduled time of arrival）。根据国际民航组织的规定，降落在同一条跑道上的紧邻航班应当满足最小尾流时间间隔 $T_i^{i - 1}$ (前机 ${f_{i - 1}}$ 和后机f_i)，如表1所示，其中，H、M和L分别表示航班的机型为重型，中型和轻型。多跑道进港航班排序如图1所示（双跑道示例）。

航班f_i的延误时间d_i可定义为：

${d_i} = S_i^r - \min \{ E_i^r\}$

(1)

多跑道进港航班排序优化目标就是让所有进港航班的总延误时间D_i达到最小，即

$\min {D_i} = \min \sum\limits_{i = 1}^N {(S_i^r - \min \{ E_i^r\} } )$

(2)

约束条件：

$S_i^r - \min \{ E_i^r\} \ge 0$

(3)

$S_i^r - \min \{ E_i^r\} \le {d_{\max }}$

(4)

$S_i^r - S_{i - 1}^r \ge T_i^{i - 1}$

(5)

式（3）表明航班f_i不能提前降落，式（4）限定航班f_i的延误时间不能超过规定的最大延误时间d_max，式（5）表明同一跑道上前后紧邻降落的航班 ${f_{i - 1}}$ 和f_i应当满足最小尾流时间间隔 $T_i^{i - 1}$ 。

当跑道数量 $R = 1$ 时，本节构建的模型将转化为单跑道进港航班排序问题。当 $R \ge 2$ 时，该模型适合用于跑道运行模式为独立进近的情况。由于未考虑相邻航班降落在不同跑道上的侧向时间间隔，因此该模型并不适合用于跑道运行模式为相关进近的情况。

2 EASaDE算法 2.1 基本DE算法

考虑D维实数空间 $S \subset {{\rm{R}}^D}$ 为待优化问题 $\min f(x)$ 的搜索空间。NP个D维实数向量 ${\mathit{\boldsymbol{X}}}_i^t = \{ x_{i1}^t,x_{i2}^t, \cdots ,x_{iD}^t\}$ $\in S$ 构成一代种群 ${{\mathit{\boldsymbol{X}}}^t} = \{ {\mathit{\boldsymbol{X}}}_{\rm{1}}^t,{\mathit{\boldsymbol{X}}}_{\rm{2}}^t, \cdots ,{\mathit{\boldsymbol{X}}}_{NP}^t\} $ ，其中： $i = 1,2,$ $ \cdots , NP; t = 0,1,2, \cdots ,T$ 。那么基本DE的变异、交叉以及选择操作可表示为：

1）变异。对于种群中的每个个体 ${\mathit{\boldsymbol{X}}}_i^t$ ，按照式（6）生成变异向量， ${\mathit{\boldsymbol{V}}}_i^{t + 1} = [v_{i1}^{t + 1},v_{i2}^{t + 1}, \cdots ,v_{iD}^{t + 1}]$ 。

${\mathit{\boldsymbol{V}}}_i^{t + 1} = {\mathit{\boldsymbol{X}}}_{r1}^t + F \cdot ({\mathit{\boldsymbol{X}}}_{r2}^t - {\mathit{\boldsymbol{X}}}_{r3}^t)$

(6)

式中，r1、r2、r3为 $[1,NP]$ 之间的随机整数且， $r1 \ne r2 \ne $ $r3 \ne i$ 。缩放因子F是一个介于 $[0,2]$ 之间的实数。

2）交叉。为提高种群的多样性，按式（7）生成交叉向量 ${\mathit{\boldsymbol{U}}}_i^{t + 1} = [u_{i1}^{t + 1},u_{i2}^{t + 1}, \cdots ,u_{iD}^{t + 1}]$ 。

$u_{ij}^{t + 1} = \left\{ \begin{array}{l}\!\!\!\! v_{ij}^{t + 1},\;\;\;ran{d_{ij}} \le CR\;\;{\mathop{\rm or}\nolimits} \;\;j = {j_{{\mathop{\rm rand}\nolimits} }};\\\!\!\!\! x_{ij}^t,\;\;\;\;ran{d_{ij}} > CR\;{\mathop{\rm and}\nolimits} \;j \ne {j_{{\mathop{\rm rand}\nolimits} }}\;\;\end{array} \right.$

(7)

式中， $CR \in [0,1]$ 为交叉概率， $ran{d_{ij}}$ 为[0, 1]均匀分布的随机数， ${j_{{\mathop{\rm rand}\nolimits} }}$ 为 $[1,D]$ 之间的随机整数，它确保 ${\mathit{\boldsymbol{U}}}_{\mathop{\rm i}\nolimits} ^{t + 1}$ 至少从 ${\mathit{\boldsymbol{V}}}_{\mathop{\rm i}\nolimits} ^{t + 1}$ 中获取一个元素，避免进化停滞。

3）选择。DE采用贪婪的选择策略，可描述为：

${\mathit{\boldsymbol{X}}}_i^{t + 1} = \left\{ \begin{array}{l}\!\!\!\! {\mathit{\boldsymbol{U}}}_i^{t + 1}\;,\;\;f({\mathit{\boldsymbol{U}}}_i^{t + 1}) < f({\mathit{\boldsymbol{X}}}_i^t);\\\!\!\!\! {\mathit{\boldsymbol{X}}}_i^t\;\;\;,\;\;\;\;{\rm otherwise}\;\end{array} \right.$

(8)

当且仅当交叉向量 ${\mathit{\boldsymbol{U}}}_i^{t + 1}$ 的适应值小于目标向量 ${\mathit{\boldsymbol{X}}}_i^t$ 的适应值，新个体 ${\mathit{\boldsymbol{X}}}_i^{t + 1}$ 才被设置为 ${\mathit{\boldsymbol{U}}}_i^{t + 1}$ ；否则， ${\mathit{\boldsymbol{X}}}_i^{t + 1}$ 保持 ${\mathit{\boldsymbol{X}}}_i^t$ 进入下一代。

2.2 EASaDE

全局探索和局部开发这对矛盾制约着DE的优化性能。全局探索表示搜索解空间内不同区域的能力，局部开发表示接近最优解的能力。文献[21]认为DE的局部开发能力强，而全局探索能力弱，从而易陷入局部最优，出现早熟收敛。导致早熟收敛的根本原因是随着种群的不断进化，多样性快速下降。因此通过控制种群多样性，可以有效提高全局探索能力，使算法跳出局部最优解。

DE有多种变异模式，每一种变异模式都有自身的特点，有的强调全局探索能力，而有的强调局部开发能力。DE/rand/1/bin和DE/best/1/bin的变异模式分别为：

${\mathit{\boldsymbol{V}}}_i^{t + 1} = {\mathit{\boldsymbol{X}}}_{r1}^t + F \cdot ({\mathit{\boldsymbol{X}}}_{r2}^t - {\mathit{\boldsymbol{X}}}_{r3}^t)$

(9)

${\mathit{\boldsymbol{V}}}_i^{t + 1} = X_{{\rm{best}}}^t + F \cdot ({\mathit{\boldsymbol{X}}}_{r1}^t - {\mathit{\boldsymbol{X}}}_{r2}^t)$

(10)

由式（9）可知，DE/rand/1/bin的变异向量 ${\mathit{\boldsymbol{V}}}_i^{t + 1}$ 由3个互不相同的随机个体组成，这样有利于保持种群的多样性，因而全局探索能力强，但收敛速度较慢。由式（10）可知，DE/best/1/bin的变异向量 ${\mathit{\boldsymbol{V}}}_i^{t + 1}$ 由 ${\mathit{\boldsymbol{X}}}_{{\mathop{\rm best}\nolimits} }^t$ （当前种群中最优个体）作引导，因此局部搜索能力强，收敛速度快，但容易陷入局部最优解。

受DE/rand/1/bin和DE/best/1/bin两种变异模式的启发，作者提出一种精英存档自适应微分进化算法（EASaDE）。精英存档的基本原理是：将当前种群Pop中的个体按其适应值从小到大进行排序，用一个外部存档保存当前较优的个体（适应值较小），称之为精英种群P；另外一个外部文档保存剩余的个体，称为非精英种群Q。P和Q满足 $P \cup Q = Pop$ 且 $P \cap Q =\phi $ 。假定P的大小为N_e，则Q的大小为 $NP - {N_{\rm e}}$ 。EASaDE仍采用DE/rand/1/bin的变异模式，但参与变异的个体 ${{\mathit{\boldsymbol{X}}}_{r1}}$ 和 ${{\mathit{\boldsymbol{X}}}_{r2}}$ 来自P，而 ${{\mathit{\boldsymbol{X}}}_{r3}}$ 来自Q，由此可得EASaDE的变异操作，如式（11）所示。

${\mathit{\boldsymbol{V}}}_i^{t + 1} = {\mathit{\boldsymbol{X}}}_{r1,t}^P + F \cdot ({\mathit{\boldsymbol{X}}}_{r2,t}^P - {\mathit{\boldsymbol{X}}}_{r3,t}^Q)$

(11)

当P的大小 ${N_{\mathop{\rm e}\nolimits} } = NP$ 或 ${N_{\rm e}} = 0$ 时，参与变异操作的个体 ${{\mathit{\boldsymbol{X}}}_{r1}}$ 、 ${{\mathit{\boldsymbol{X}}}_{r2}}$ 和 ${{\mathit{\boldsymbol{X}}}_{r3}}$ 将从P或Q中随机选择，此时EASaDE的变异操作退化为DE/rand/1/bin的变异操作。当P的大小 ${N_{\mathop{\rm e}\nolimits} } = 1$ 时，个体 ${{\mathit{\boldsymbol{X}}}_{r1}}$ 来自P，相当于 ${\mathit{\boldsymbol{X}}}_{{\mathop{\rm best}\nolimits} }^t$ ，而 ${{\mathit{\boldsymbol{X}}}_{r2}}$ 和 ${{\mathit{\boldsymbol{X}}}_{r3}}$ 来自Q，此时EASaDE的变异操作退化为DE/best/1/bin的变异操作。过大的N_e有利于保持种群多样性，但影响EASaDE的局部搜索能力，不利于收敛；过小的N_e不利于保持种群多样性，影响EASaDE的全局探索能力；本文建议 ${N_{\rm e}} \in [0.3,\;0.5] \cdot NP$ ，详见3.3。

由此可见，该精英存档策略综合了DE/rand/1/bin和DE/best/1/bin两种变异模式分别具有全局探索能力和局部开发能力的优点，因此在保持种群多样性的同时，也确保了EASaDE的收敛性能。

随着种群进化，每当生成新的个体，就需要更新精英种群P和非精英种群Q，更新采用贪婪选择策略，即生成的新个体 ${\mathit{\boldsymbol{U}}}_i^{t + 1}$ 比父代个体 ${\mathit{\boldsymbol{X}}}_i^t$ 更优时进行更新。更新操作存在以下2种情况：

1）如果 ${\mathit{\boldsymbol{U}}}_i^{t + 1}$ 对应的父代个体 ${\mathit{\boldsymbol{X}}}_i^t$ 已经存在于精英种群P，则直接用 ${\mathit{\boldsymbol{U}}}_i^{t + 1}$ 替换 ${\mathit{\boldsymbol{X}}}_i^t$ ；

2）如果 ${\mathit{\boldsymbol{U}}}_i^{t + 1}$ 对应的父代个体 ${\mathit{\boldsymbol{X}}}_i^t$ 不在精英种群P中，且 ${\mathit{\boldsymbol{U}}}_i^{t + 1}$ 优于P中最差的个体 ${\mathit{\boldsymbol{X}}}_{{\mathop{\rm worst}\nolimits} }^t$ （适应值最大），则用 ${\mathit{\boldsymbol{U}}}_i^{t + 1}$ 替换 ${\mathit{\boldsymbol{X}}}_{{\mathop{\rm worst}\nolimits} }^t$ ，同时将非精英种群Q中对应于 ${\mathit{\boldsymbol{U}}}_i^{t + 1}$ 的父代个体 ${\mathit{\boldsymbol{X}}}_i^t$ 替换为 ${\mathit{\boldsymbol{X}}}_{{\mathop{\rm worst}\nolimits} }^t$ ；否则，不更新P和Q。

由于控制参数自适应能够有效地克服固定参数带来的不足，使算法更具有实用性，因此，EASaDE采用一种新的控制参数自适应策略。即每个个体都拥有自己的控制参数（F_i和CR_i），且F_i和CR_i将根据个体进化停滞代数而自适应调整，如式（12）和（13）所示。

$F_i^{t + 1} = \left\{ \begin{array}{l}\!\!\! F_i^t,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;s{t_i} < ST;\\\!\!\! {F_{\rm min}} + {r_1} \cdot ({F_{\max }} - {F_{\rm min}}),\;\;\;s{t_i} \ge ST\end{array} \right.$

(12)

$CR_i^{t + 1} = \left\{ \begin{array}{l}\!\!\! CR_i^t,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;s{t_i} < ST;\\\!\!\! C{R_{\min}} + {r_2} \cdot (C{R_{\max }} - C{R_{\min }}),\;s{t_i} \ge ST\end{array} \right.$

(13)

式中，整数ST为指定的阈值， $s{t_i}$ 为个体 ${\mathit{\boldsymbol{X}}}_i^t$ 的进化停滞代数， ${F_{\max}}$ 和 ${F_{\min}}$ 分别为缩放因子F的上下限， $C{R_{\max}}$ 和 $C{R_{\min}}$ 分别为交叉概率CR的上下限， $F_{\mathit{\boldsymbol{i}}}^{\mathit{\boldsymbol{t}}}$ 和 $CR_{\mathit{\boldsymbol{i}}}^{\mathit{\boldsymbol{t}}}$ 分别为个体 ${\mathit{\boldsymbol{X}}}_i^t$ 的第t代缩放因子和交叉概率，r₁和r₂为[0, 1]之间的随机数。根据文献[16, 22]的建议，设置 ${F_{\min}} = 0.1$ ， ${F_{\max}} = 0.8$ ， $C{R_{\min }} = 0.4$ ， $C{R_{\max}} = 1.0$ 。在所有实验中，设置 $ST = 3$ 。

式（12）和（13）表明：进化过程中，如果任何个体连续ST代不能生成新的更优个体，则表明该个体当前的控制参数不合适而应当重新设置。反之，则认为该个体当前的控制参数是合适的而应当保留进入下一代。控制参数 $F_i^t$ 和 $CR_i^t$ 的更新在变异操作之前，从而新的控制参数将影响到下一代个体的变异、交叉和选择操作。

3 EASaDE的性能分析 3.1 Benchmark测试函数

为检验EASaDE的优化性能，本文选取9个常用于优化算法对比的Benchmark函数进行实验分析，如表2所示，其中，D为测试函数的维度，S为搜索空间， ${f_{\rm{min}}}$ 为全局最优解； ${f_1} - {f_3}$ 为单峰函数，其他为多峰函数。

3.2 与基本DE和其它改进的DE比较

将EASaDE与基本DE^[10–11]、（DE/rand/1/bin、DE/best/1/bin）和jDE^[16]进行对比。根据文献[11]的建议，设置NP=100，独立实验次数为30。根据文献[23]的建议，对于DE/rand/1/bin，设置F=0.5和CR=0.1；对于DE/best/1/bin，设置F=0.7和CR=0.9。jDE的参数设置具体见文献[16]。对于EASaDE，精英种群的大小N_e= 30，初始参数 $F_i^0$ 和 $CR_i^0$ 分别从[0.1,0.8]和[0.4,1.0]取随机数。最大进化代数以及30次实验所求最优解的均值（Mean）和标准差（STD）如表3所示。同时，图2给出了部分函数的进化曲线。

从表3和图2中，可以看出EASaDE具有更高的收敛精度和更快的收敛速度。这主要是因为EASaDE综合了DE/rand/1/bin和DE/best/1/bin的优点，在保持较快收敛速度的同时，有效地避免了算法陷入局部最优解，提高了求解精度。此外，表3中的标准差也表明EASaDE具有更好的鲁棒性。

为进一步检验EASaDE的优化性能，将其与SaDE^[17]、JADE^[18]、CoDE^[19]和DMPSADE^[20]进行比较。EASaDE的参数设置不变，最大进化代数为3 000，其他算法参见相应的文献。设置 $NP = 100$ ，独立实验次数为50（注意：本实验中f₉的搜索区间为[-100, 100]）。50次实验所求最优解的均值（Mean）和标准差（STD）如表4所示。

从表4中，可以看出：与SaDE、JADE、CoDE和DMPSADE相比，除函数f₇外，EASaDE求得的最优解均值和标准差明显更优。这是由于在进化过程中，EASaDE通过实时调节种群的多样性，使得算法的全局探索能力得到了显著增强，进而所求得的最优解具有更高的精度。

3.3 参数对EASaDE性能的影响

精英种群的大小N_e对EASaDE的性能有着重要的影响，但如何针对不同优化问题，选择合适的N_e才是研究的重点。为此，本节通过设置不同的 ${N_{\rm e}} = \lambda \cdot NP$ 来进一步研究其对EASaDE的影响，从而确定N_e的取值范围，其中 $\lambda \in [0.1,0.9]$ ，步长为0.1。利用Friedman和Kruskal-wallis统计检验对不同 $\lambda $ 所求得的平均最优解进行分析，参数设置同3.2。表5给出了 $\lambda $ 取不同值时的统计检验结果。

从表5可以看出：当 $\lambda < 0.3$ 或 $\lambda > 0.5$ 时，利用Friedman和Kruskal-wallis所求得的平均秩均较大，这表明了EASaDE在 $\lambda $ 取当前值时的优化效果较差。这主要是由于较小的 $\lambda $ 使得EASaDE更侧重于DE/best/1/ bin变异模式，从而易出现早熟收敛，求解精度不高；而较大的 $\lambda $ 使得EASaDE更侧重于DE/rand/1/bin变异模式，导致在有限的进化代数内收敛速度较慢，从而致使所求得的最优解较差。因此，较小或较大 ${N_{\rm e}}$ 的都将降低EASaDE的优化性能。相比之下，当 $\lambda \in $ [0.3,0.5]时，EASaDE能够表现出较好的优化效果。因此建议 ${N_{\rm e}} \in [0.3,\;0.5] \cdot NP$ 。

4 EASaDE求解多跑道进港航班排序

为验证EASaDE求解多跑道进港航班排序的有效性和实用性，选用西安咸阳国际机场11:00～11:20的28架进港航班作为实验对象，将EASaDE与FCFS、GA^[6]、EDA^[8]和LDD-SA-PSO^[9]进行对比实验。咸阳机场采用平行双跑道，跑道号（RWY）为05和23。实验参数如下：种群规模 $NP = 80$ ，最大进化代数为200，精英种群的大小 ${N_{\rm e}} = 40$ ，EASaDE的参数见3.2，其它算法参见具体文献。表6给出了进港航班的原始数据和优化结果，其中，ETA（05）和ETA（23）分别表示航班在跑道05和23上的预计降落时间。

从表6可以看出，与FCFS、GA、EDA和LDD-SA-PSO相比，EASaDE所求得的总延误时分别减少了42.9%、14.1%、12.4%和7.6%。EASaDE的优化结果明显优于其他4种算法。因此应用EASaDE求解多跑道进港航班排序能够有效地降低总延误时间，减少航班延误带来的经济损失。

为了多角度分析算法的性能，对表6进行整理，得到表7；其中“跑道变更航班数量”列中的统计结果是以FCFS为基准。

由表7可以得出：

1）从总完成时间角度出发，EASaDE优化后的航班在跑道05和23上都能在较短的时间内完成降落，提高了跑道的吞度量。

2）从双跑道降落的航班数量出发，EASaDE和GA优化的结果均为14∶14，双跑道得到了充分的利用。

3）从跑道变更航班数量出发，与FCFS相比，EASaDE和GA安排航班降落的跑道变动最小，有利于减轻管制员的调度压力。

综上所述，EASaDE的整体优化性能要优于FCFS、GA、EDA和LDD-SA-PSO，EASaDE是一种求解多跑道进港航班排序问题的有效方法。

5 结　论

本文提出了一种精英存档自适应微分进化算法（EASaDE），该算法通过实时调节种群的多样性，避免了早熟收敛，有效地提高了算法的收敛精度、收敛速度和鲁棒性。应用EASaDE求解多跑道进港航班排序问题的优化结果也进一步表明了EASaDE的有效性和实用性。

随着民航运输量的快速增长，一些大型机场开始使用3条或3条以上的跑道。利用EASaDE求解时存在运算时间过长问题，如何提高运算效率，需要进一步的研究。