这篇文章中使用的进化多目标算法与自己的研究方向相关，仅对算法部分进行阅读梳理总结。

介绍

本文引入了一个多目标进化优化(EMO)框架来解决问题，本研究的新颖性可以总结如下：

1. 引入了一个EMO框架，可以处理近似的偏好。标度函数及其相应的参数指定了兴趣区间(RoI)。针对EMO框架的替换过程，专门设计了新的拥挤距离，有效地控制了兴趣区间(RoI)的范围，直接影响算法的性能。其主要思想是，使用区间偏好信息来定义兴趣区间(RoI)的范围会比使用用户自定义参数的算法得到更好的解决方案。
2. 提出了一种新的过滤方法来寻找具有代表性的均匀分布解子集，进一步提高了决策者选择具有成本效益的解的能力。
3. 本文提出的EMO算法和滤波过程应用于地面运动和跑道调度综合问题，并附加了与排放对应的目标。

本次求解的问题可以分为地面运动问题(Ground movement problem)和跑道调度问题(Runway scheduling problem)。地面运动问题的优化目标为总滑行时间 $t^{taxi}$，滑行期间总油耗 $f^{taxi}$，滑行期间总排放量 ${\epsilon }^{taxi}$；跑道调度问题的优化目标为总跑道调度延迟时间 $t^{rwy}$，跑道调度总油耗 $f^{rwy}$，跑道调度总排放量${\epsilon }^{rwy}$。

将地面运动问题和跑道调度问题整合为一个多目标优化问题之后，考虑的优化目标为：

1. 总时间 $g_1=t^{taxi}+t^{rwy}$；
2. 总油耗 $g_2=f^{taxi}+f^{rwy}$；
3. 总排放量 $g_3={\epsilon }^{taxi}+{\epsilon }^{rwy}$。

在该多目标优化问题中，决策变量为

1. 离港飞机的起飞时间 $x_i,i\in D$；
2. 每架航班的速度轮廓 $y_i,i\in H$。
   其中D为离港航班的集合，H为所有航班的集合，所以决策向量可表示为 { x 1 , x 2 , … , x ∣ D ∣ , y 1 , y 2 , … , y ∣ H ∣ } \{x_1,x_2,…,x_{|D|} ,y_1,y_2,…,y_{|H|} \} {x1​,x2​,…,x∣D∣​,y1​,y2​,…,y∣H∣​}。

针对机场现实问题，论文还考虑了现实中的经济效益。由于某些单位成本往往是难以确定的，只有近似可用。本文使用一个标量化函数

来评估搜索过程中发现的解决方案 $z_k$ 的总货币成本，${nr}^{obj}$是解决方案的目标数量，$c_m>0$，是每个目标对于货币成本的权重，可以被重写。

EMO框架

1. 在整个EMO框架中，初始种群的解决方案的决策向量随机获取，并计算种群中每个解决方案的目标值$g_1$, $g_2$, $g_3$。
2. 在种群中选择目标函数值较好的解决方案进行遗传操作，以给定的概率，对两个父代解进行两点交叉。
3. 根据变异概率对种群中的每个解的决策向量进行变异操作，并重新计算解决方案的目标值$g_1$, $g_2$, $g_3$。
4. 使用替换程序选择下一代的解决方案替换当前种群。
5. 重复执行选择、交叉、变异、替换程序，直到满足指定数量的迭代次数。
6. 最终使用过滤程序选择出解决方案的一个有代表性的子集供决策者进行选择。

P-EMOA的替换程序

在每一代中，替换程序进行非支配排序以识别非支配前沿。在每一个前沿中，根据目标空间中解的Pareto前沿的优选区域选择生存解。优选区域定义如下：

1. 前沿中最优的解决方案定义为中心点 $z_k$；
2. 被称作特征领域的边界解决方案$z_a^B$以至于为每个目标$g_m$定义如图2所示的区间$[v_m^{min},v_m^{max}]$；
3. 中心点和边界解指定了兴趣区间。
   

决策者可以通过涂刷技术交互地选择中心点和边界解。标量化函数$C^{total}$可以用来寻找中心点和边界解，决策者需要提供 ${\bar{c}}_m^{lower}$, ${\bar{c}}_m$, ${\bar{c}}_m^{upper}$。中心点$z_k$相对于单位成本向量$\bar{c}$具有最小标量函数值：$z^C={\mathrm{argmin}}_{z_k}(C^{total}(z_k,\bar{c}))$。

对于边界解，定义边界单位成本向量 ${\bar{c}}^B$， ${\bar{c}}^B$中使用边界单位成本值，即$c_m={\bar{c}}_m^{lower}$或者$c_m={\bar{c}}_m^{upper}$，这导致上界、下界的组合包含了${nr}^B=2^{{nr}^{obj}}$个边界单位成本向量 ${\bar{c}}^B$。第$a$个${\bar{c}}^B$对应一个使用${\bar{c}}^B$得到最小标量函数的解决方案$z_k$的特征邻居$z_a^B={\mathrm{argmin}}_{z_k}(C^{total}(z_k,{\bar{c}}_a^B))$。

所有的$z^B$定义了兴趣区间，这个区间包含了对于 ${\bar{c}}_m^{lower}$ 和 ${\bar{c}}_m^{upper}$ 之间的任何单元成本向量来说都有最小 $C^{total}(z_k,{\bar{c}}_m)$ 的解决方案。在每一代中，决策者可以更改有标量化函数得到兴趣区间。

新设计的拥挤距离$c{d}_k$

1. 如果解决方案$z_k$是中心点，则$c{d}_k=\infty$以确保它总是被选择进入下一代；否则需要根据$z_k$和$z^C$的关系决定。

如果$v_m^{min}\le g_m(z_k)\le v_m^{max}$，则$z_k$支配$z^C$，记做$z_{k}S{z}^C$。所有支配$z^C$的解$z_k$形成了支配邻域。拒绝域$[v_m^{min},v_m^{max}]$由特征领域决定：$v_m^{min}=\min g_m(z_a^B)$,$v_m^{max}=\max g_m(z_a^B)$。

2. 属于支配邻域的解$z_k$的${cd}_k$为${cd}_k=M+d_k^{cd}$，$d_k^{cd}$是解$z_k$到领域解集的距离 $d_k^{cd}$：
   当$M$设为较大的正数时，${cd}_k$能够确保替换程序按照预期执行。
3. 对于特征邻域之外的解决方案，${cd}_k$ 与 $C^{total}(z_k,\bar{c})$ 成反比。最终，兴趣区间内被选择的解决方案的${cd}_k$ 与 $C^{total}(z_k,\bar{c})$ 都要小。

最终，按照${cd}_k$降序选择解决方案去填充种群。然而，可能有大量的解决方案，而且它们的分布不均匀，使决策局难以作出决定，特别是在目标数目较多的情况下。因此，再次使用填充数据库的相同过滤过程，从$R$ 中获得具有代表性的均匀分布解子集。

Pareto最优解的筛选程序

解决方案的代表性子集能够在选择阶段对决策者有所帮助，并且减少存储在数据库中的解决方案。该过滤程序的主要步骤为：

1. 使用邻域概念：$R\to R^{\ast }$；
2. 使用ξ-启发式方法：$R^{\ast }\to R^{\ast \ast }$。

首先，使用区域概念对R进行筛选得到初始集合$R^{\ast }$。然而，第一步筛选后的解之间的距离可能仍然是不均匀的。因此，在第二步中，利用均匀度测量将$R^{\ast }$进一步细化为$R^{\ast }\to R^{\ast \ast }$。

在第一步中，只有邻域内没有其他解决方案的解$z_k$被接受。解$z_k$的邻域被定义为每个目标上距离为$\text{τ}$的区域，在该区域内没有支配$z_k$或被解$z_k$支配的解。第一步的步骤如下：
对于R中的每一个解决方案$z_k$：

1. 如果$R^{\ast }$为空，$z_k$被加入到$R^{\ast }$中；否则，进行下一步；
2. $z_k$的目标值$g_m$按照$$\overline{g_m}=\frac{(g_m-g_m^{min})}{(g_m^{max}-g_m^{min})}$$进行归一化，$g_m^{max}$, $g_m^{min}$分别为$R$中第$m$个目标最大值和最小值；
3. $z_k$到$R^{\ast }$中每一个解决方案$z_l$的线性距离$$d_{kl}^{rect}=\sum _{m=1}^{{nr}^{obj}}|\overline{g_m}(z_k)-\overline{g_m}(z_l)|$$
4. 距离$z_k$的线性距离最小的解决方案$z_l^{\ast }$：$$l^{\ast }=\underset{l}{\mathrm{argmin}}(d_{kl}^{rect})$$
5. $z_k$和$z_l$之间的目标值最大差别$$\delta =\underset{m=1,2,...,{nr}^{obj}}{\max }|\overline{g_m}(z_k)-\overline{g_m}(z_l^{\ast })|$$
6. 如果$\text{δ≥τ}$，接受$z_k$并移入到$R^{\ast }$；否则拒绝$z_k$。

过滤过程的第一步依赖于$\tau$的值，有效地控制了存档种群的大小。有两种策略设置$\tau$：

1. 如果固定偏好的解决方案的数量$N^R$，则$$\tau =\frac{1}{(\sqrt[{nr}^{obj}-1]{N^R}+o)}$$初始时$o=0$。如果使用初始的τ获得的解少于$N^R$，可以逐步地增加$o$以至于选够$N^R$个解;
2. 如果给出了两个解决方案在$m$个目标上最小差异$in{c}_m$，则$\tau =\overline{in{c}_m}$，$\overline{in{c}_m}$和$\overline{{\mathbf{g}}_{\mathbf{m}}}$的归一化方式相似。

第一步中的筛选提供了一个良好的初始集合$R^{\ast }$。然而，在某些方面，$R^{\ast }$中的解决方案可能比$\tau$更接近，因为只考虑了最大距离。此外，由于$\delta$不需要严格等于$\tau$，实际上它可以是任何比$\tau$更大或等于$\tau$的值，因此解之间有很大的距离是可能的。因此，在第二步中，需要基于均匀度度量的$\xi$-启发式方法对$R^{\ast }$进行再次筛选。

均匀度的定义如下:对于每个$R^{\ast }$中的解决方案$z_k$，构造两个球体(两个目标时为圆形，或超过3个目标时为超球体)，如图4所示。
第一个球体是在$z_k$和$R^{\ast }$中任何其他解决方案之间构建的最小球体。这个球体的直径表示为$d_k^l$。
第二个球体是可以在$z_k$和$R^{\ast }$中任何其他解决方案之间构建的内部不包含其他解决方案的最大球体。这个球体的直径表示为$d_k^u$。
直径用相应点之间的欧氏距离来计算。

$R^{\ast }$的均匀度$\xi =\frac{{\sigma }_d}{\hat{d}}$ ，其中${\sigma }_d$，$\hat{d}$分别为$R^{\ast }$中所有解决方案的所有直径 { d 1 L , d 2 L , … , d k L } ⋃ { d 1 U , d 2 U , … , d k U } \{d_1^L,d_2^L,…,d_k^L\}⋃\{d_1^U,d_2^U,…,d_k^U\} {d1L​,d2L​,…,dkL​}⋃{d1U​,d2U​,…,dkU​}的标准差和均值。当$\xi =0$时，解决方案服从均匀分布，即所有直径相等。

$\xi$-启发式方法使用$R$中较好的解决方案$z_l$替换$R^{\ast }$中的解决方案$z_k$来重新定义$R^{\ast }$。$\xi$-启发式方法基于差异的绝对值$|d_i^L-\hat{d}|$和$|d_i^U-\hat{d}|$来替换解决方案。$|d_i^L-\hat{d}|$和$|d_i^U-\hat{d}|$越小，代表着$d_i^L$和$d_i^U$越接近近似$\hat{d}$的理想值。对于R中的每一个解决方案$z_k$，$\xi$-启发式方法步骤如下：

1. 由欧氏距离得出$R^{\ast }$中距离$z_k$最近的解决方案$z_l$；
2. $z_k$暂时加入$R^{\ast }$，$z_l$暂时从$R^{\ast }$中移除；
3. 计算$z_k$和相关点之间的直径$d_k^L$,$d_k^U$；
4. 如果$|d_k^L-d|<|d_l^L-d|\wedge |d_k^U-d|<|d_i^U-d|$，则$z_k$被接受加入$R^{\ast }$，$z_l$被移出；否则$z_k$被拒绝，$z_l$重新加入$R^{\ast }$；
5. $R$中所有的解决方案被测试之后，$R^{\ast \ast }=R^{\ast }$。

实验设置

EMO框架使用Python的Inspyred包实现。EMO框架的终止条件为50代，种群中个体数量为50。两点交叉的交叉概率为1；随机更改一个基因编码的变异操作的概率为0.1。对比算法：没有偏好信息的NSGAⅡ、MOEA/D、有偏好信息的NSGAⅢ。

结论

本文针对综合优化问题：

• 提出了一种带有偏好信息和筛选过程的多目标进化优化框架。这个问题结合了机场地面移动和跑道调度问题；
• 提出的方法在主要国际枢纽机场的数据上进行了测试；
• 提出的进化框架解决了两个具有挑战性的任务：
  1)将近似或不确定的偏好信息表示为每个目标单位的经济价值的区间；
  2)在Pareto前沿上找到均匀分布的解。

为了应对第一个挑战，在进化算法的替换过程中，新设计的拥挤距离考虑了滑行延误和燃油消耗的单位成本范围，以控制RoI的范围。在进化过程中对兴趣区域范围的有效控制成功地提高了算法的收敛性。这种改进具有实际意义，因为可以在总时间、燃料消耗和排放量上找到更好的解决方案。

本文提出的筛选过程解决了第二个挑战。筛选过程被用来选择速度轮廓的一个均匀分布的子集，和从兴趣区间中选择解决方案呈现给决策者。实验强调了均匀分布的解决方案对于节省成本的重要性。
计算实验表明，机场可以从采用所提出的决策支持方法中受益。

为了进一步研究，本文提出的后验筛选方法可以嵌入EMO中，在进化过程中选择均匀分布的解。另外，将不确定性系统地纳入偏好信息的想法也值得重视。例如，不确定性可以用模糊值表示。最后，在处理像机场运营这样的现实问题时，不仅要找到最优的解决方案，而且还要找到具有鲁棒性的解决方案(鲁棒的针对出租车时间、出发时间和到达时间的偏差)。为了达到这个目标，稳健优可以包含在搜索算法中。

个人理解

简单阅读完该论文之后，对于文中提到了一些定义、公式并没有完全理解，只是对论文算法的思想有了大致的了解。就算法框架而言，本文所提出的P-EMOA类似于NSGAⅡ算法，对于遗传算子没有特殊变化，比较重要的地方是对NSGAⅡ算法中的拥挤距离进行了重新设计，即在下一代的解决方案的挑选方式上进行了改变，而Pareto前沿的筛选程序是在进化算法框架遗传操作迭代过程之外，是对最终结果的进一步筛选出均匀分布的解决方案以供决策者选择，减轻决策者的选择负担，对于均匀分布的解能够有助于节省成本这一点没太理解。

论文原文：
Preference-based evolutionary algorithm for airport surface operations