基于蚁群聚类算法的扇区复杂性分析

朱承元，孙辰欣，赵立刚

(1. 中国民航大学空中交通管理学院，天津 300300；2. 民航局空管局空域管理中心，北京 101312)

1 引言

在经济快速发展的大环境下，民航业前景广阔，航班量持续增长，扇区运行环境愈加复杂。由于不同空域单元的运行环境存在差异性，导致空中交通复杂性不同，扇区复杂程度的变化对空中交通管理系统的运行效率和安全性产生较大的影响。因此，如何科学客观分类空域单元的复杂性，成为空域和飞行流量管理的重要基础，也成为空管单位关注的焦点。

Christien.Rapha⊇l等[1]和Arash Yousefi等[2]提炼扇区结构、冲突类型、流量等指标，通过聚类分析不同地区的扇区得到交通运行模式分类。Song Zhuoxi等[3]通过仿真工具对扇区运行情况进行模拟，提取影响空域复杂性的指标。张进等[4]基于空域复杂度度量指标体系分析了空中交通系统的运行特征。复杂性与众多影响因素相关，以上文献度量空域复杂性的指标还未十分完善。Geraldine M Flynn等[5]和Steve Penny等[6]利用决策树和K均值法对空域单元复杂性按高、中、低进行聚类分析，张建平等[7]，赵嶷飞等[8]和丛玮等[9]采用K均值算法分别对终端区的运行品质、交通流运行特性和扇区复杂程度进行聚类分析，上述文献采用传统聚类算法运行效率较高，但K-means算法易受极值影响产生局部最优，对数据量较大的聚类问题会产生较高的难度，并且大多数学者对空域进行简单的定性分析，未对聚类结果进行验证，具有主观随意性。当前，群智能聚类算法的研究受到学者关注，李可[10]通过蚁群算法对航线进行聚类，但缺乏对聚类结果准确性的验证。

因此，在扇区复杂性指标体系的基础上，选择蚁群聚类算法对扇区的复杂性进行聚类分析，利用蚂蚁的生物属性提高全局搜索能力和收敛速度，选择Silhouette指标评估聚类质量，得到扇区复杂性的复杂程度分类，最终通过全空域与机场仿真软件(TAAM,Total Airspace and Airport Modeler)对聚类结果进行验证。

2 扇区复杂性指标与分析

2.1 指标体系

复杂性的相关研究甚多，借鉴已有研究成果[11]，结合空域结构和动态运行特征，提取有利于定量分析空域运行态势的复杂性指标，构建能够反映空域运行特征的复杂性指标体系见表1。

表1 复杂性指标体系

综上，根据空域结构的特点和空域交通运行确定复杂性指标，该指标体系主要功能是深入分析考虑空中交通复杂度与空域状态变化，全面度量空域复杂性，在这一指标体系的基础上，进一步将空中交通复杂性的方法进行更深入研究。

2.2 主成分分析

扇区管制运行态势复杂，考虑因素多，需要结合实际运行选取有效指标进行分析，提炼出能有效表征复杂性的指标，通过主成分分析法(PCA,Principal Components Analysis)精简出可定量分析复杂性的指标。主成分的数学模型如下：

∑=(σij)p=E[(X-E(X))(X-E(X))T]

(1)

(2)

4)样本X的第q个主成分表示为

Yi=li1X1+li2X2+…+lipXp(q=1，2，…，p)

(3)

3 蚁群聚类算法

针对传统K-means算法易产生局部最优解的缺陷，蚁群聚类算法(ACCA,ant colony clustering algorithm)是一种基于种群寻优的搜索算法[12]，蚂蚁利用自身的生物特征属性，通过信息素强度分布式寻优，在搜索过程中不容易陷入局部最优，同时贪婪式搜索有利于快速找出可行解。

3.1 聚类算法流程

蚂蚁在群体进化过程中主要是蚂蚁的记忆、蚂蚁之间的信息交流及群体向目标靠近，最终寻找到食物源。

设X={Xi|Xi=(xi1，xi2，…，xin)|(i=1，2，…，N)是待聚类分析的样品集合，N为样品的特征数，聚类过程可表述如下：

1) 初始分配N个样品各自为一类(ω1，ω2，…，ωN)。

2) 计算类ωi和ωj之间的欧式距离dij。

(4)

(5)

3) 计算各路径上的信息素量。设r为聚类半径，τij(t)是t时刻ωi到ωj路径上残留的信息素量，路径(i，j)上的信息素量定义为

(6)

式中，r=A+dmin+(dmax-dmin)·B，A，B为常量参数，dmin=min(dij)，dmax=max(dij)。

4) 计算类ωi归并到ωj的概率

(7)

式中，S={s|dij≤r，s=1，2，…，j-1，j+1，M}，s代表某一类号，S代表到第j类距离小于等于r的所有类号集合，M为当前的总类数,α表示信息素启发因子，β期望启发因子，ηij(t)=1/dij为启发函数。

5) 判断若Pij(t)≥p0，则ωi归并到ωj邻域，类别数减1。p0为一给定的概率值。

6) 判断是否有归并。若无归并，则停止循环。否则，转2)继续迭代，直至达到最大迭代次数，返回最优解为聚类结果[13]。

3.2 聚类评价指标

由于聚类是无监督学习过程，无法确定某种划分结果是合理有效的，聚类评价指标对数据集本身的内部结构、相似关系和簇类之间的紧凑与疏远关系进行评价[14]，选择Silhouette指标分析评价聚类质量。

假设某个样本集合具有n个样本点，被聚合为k个类别Ci(i=1，2，…，k)。a(t)为类别C中的样本点t与t相同的群集中其他点的平均距离，b(t)是从第i个点到不同群集中的点的最小平均距离，d(t，Ci)为Cj的样本t到另一个类Ci的所有样本的平均不相似度或距离，则b(t)=min{d(t，Ci)}，其中i=1,2,…,k且i≠j。样本t的Silhouette指标的计算公式如下

(8)

轮廓值范围是[-1，1]，如果样本点的轮廓值越大，则聚类效果更好。

3.3 实例分析

针对扇区复杂性进行聚类时，空域仿真模型的准确性对最终的聚类结果有很大影响，TAAM仿真工具能够还原空域动态运行的全过程。以西安和杭州进近管制扇区作为对象，选择某天的航班计划数据，将航路点、航路、进离场程序及扇区等录入到仿真中，构建空域复杂性模型，并对模型进行校验，空域运行效果与实际相符。

采集扇区复杂性仿真数据用于指标分析，9个扇区作为分析样本，用S1-S9表示，通过对交通流的时空分布进行统计和分析，采集指标分别为Z1～Z16见表2和表3。

表2 静态复杂性指标数据

表3 动态复杂性指标数据

通过PCA分析，静态复杂性前两个主成分贡献率为0.9529+0.047=0.99，累计已达99%以上，提取Z1和Z2两个主成分。动态运行复杂性前三个主成分贡献率计算为0.726+0.164+0.082=0.972，累计已达97%，因此提取了Z6、Z7和Z8三个主成分。

通过主成分分析提取指标数据，得到扇区的复杂性见表4。

表4 主成分分析

综合两类复杂性值对扇区分别通过K-means和ACCA进行对比分析，结果见表5。初始化蚂蚁个数为9，最大迭代次数为50，设置参数A=0.2，B=0.28，α=1，β=1。τij(0)=0，转移概率p0=0.65，样本数为9，当K=2-8之间时，对应不同的Silhouette值如图1。

表5 聚类数据对比

图1 Silhouette指标评价图

从表5和图1中得到，K-means得到的质心大致正确，但不精确，运行时间较长，受质心位置影响容易产生局部最优解；ACCA的质心位置准确，聚类有效性好，时间性能表现的较好。因此，采用的ACCA的聚类效果要比K-means好，分类更加合理。

从评价指标来看，当Silhouette值越大时，聚类效果越好。两种算法对比来看，当K=3时，通过蚁群聚类算法的轮廓值值最大，所以根据扇区复杂性将扇区分为3类，比较符合实际的管制情况。

当K=3时蚁群聚类得到的复杂性结果如图2。

图2 K=3的聚类结果图

根据复杂程度将扇区分为3类，分别为：Sector 3/7(复杂)；Sector2/5/6/8/9(中等)；Sector 1/4(低)。其中：

1)Sector3/7的复杂程度都属于最大值。从静态结构来看，受地理位置的限制，可用空间小，矛盾点较多，可调配的机动空域面积小；从运行状态看，该类扇区航空器分布最为密集，处于进离场的交汇处，大部分航空器处于爬升、下降状态。航空器对之间的平均时间间隔最少，存在潜在冲突多，管制员同时指挥架次较高，造成管制员负荷最大。

2)Sector2/5/6/8/9的复杂程度都属于中等水平。从静态结构来看，扇区面积较大，灵活调配空间，航路汇聚交叉点多；从运行状态看，该类扇区的航空器数量分布较多，产生的冲突较多，对航空器引导机动较多，航空器对之间的时间间隔分布有所提高。

3)Sector1/4的复杂程度属于低水平。从静态结构来看，扇区结构限制较少，航路分布较简单。从运行状态看，扇区内航班流分布最少，航空器对之间的时间间隔最大，航空器之间的冲突较少。

4 仿真验证

TAAM仿真软件中的空域复杂性可视化工具TAAM Viewer能够以3D形式显示模拟输出报告数据。扇区复杂性信息分析航空器在空域运行时的相互作用，以及它对管制员工作负荷和冲突等度量的影响。复杂性信息由扇区颜色的变化显示，可以实时观测到不同时段各个扇区的复杂程度，绿色表示扇区的复杂程度最低，黄色表示扇区复杂程度中等，红色表示扇区复杂程度最高。

如图3和图4所示，将西安和杭州进近管制扇区复杂性投影到一个平面中进行动态显示，连续不断地展示整个空域复杂性的传播。

图3 西安扇区复杂性

图4 杭州扇区复杂性

仿真结果表明，不同时段的扇区颜色变化分类与ACCA聚类结果一致，扇区复杂程度分类结果与聚类结果相符，从客观角度确认了该聚类结果和方法的合理性。

5 结论

在扇区复杂性指标体系的基础上，采用蚁群聚类算法使用信息素强度作为判断函数，实现了扇区的复杂程度分类，表明了ACCA算法的有效性和可靠性，准确地揭示数据间的复杂关系，并通过TAAM仿真软件对聚类结果准确性进行验证。研究成果有助于加强空域系统的运行效率，提升空域运行安全性，为其规划与管理起到决策支持作用。

未来研究中，进一步可以将聚类算法与其他群智能算法结合开展深入研究，构造出更为优良的聚类改进方法，将实现更多指导意义。