基于均值聚类的KMCPSO舰载机出库调度算法

彭业飞++张维继++邵明臣++冯智鑫

摘要：航母舰载机的出库调度效率，在很大程度上决定了整个航母的战斗力生成。通过研究K均值聚类算法的基本原理，提出基于均值聚类的KMCPSO舰载机出库调度算法。该算法针对粒子群算法在进化过程中易出现早熟和寻优结果不稳定的缺陷，通过在迭代过程对种群进行分群，以提高种群多样性，从而克服原算法的不足。基于俄罗斯“库兹涅佐夫”号航母舰载机出库任务，建立舰载机调度模型，并用KMCPSO算法进行求解。结果表明，KMCPSO算法能克服上述缺陷，模型有较好的应用价值。

关键词：舰载机；出库调度；均值聚类；粒子群；种群多样性

中图分类号： TP312 文献标识码：A 文章编号：1009-3044（2016）01-0009-04

The KMCPSO Aircraft Carrier Outbound Schedule Optimization Based On Mean Clustering

PENG Ye-fei，ZHANG Wei-ji，SHAO Ming-chen，FENG Zhi-xin

（Naval University of Engineering， Wuhan 430033， China）

Abstract：The combat effectiveness of aircraft carrier is largely determined by the Outbound- Scheduling efficiency of the aircraft. After researching the basic principle of K-Means cluster Optimization，the KMCPSO Aircraft Outbound Schedule Optimization has been put forward based on it.The shortcomes of Particle Swarm Optimization have been solved in the evolutionary process of the new Optimization，such as Proning to premature、the optimization result is not stable.The population diversity has been enhanced by dividing populations in the Optimization. The Aircraft scheduling model has been established based on the outbound task of the aircraft carrier "admiral kuznetsov" in Russia. The model is solved by the K-Means Cluster Particle Swarm Optimization. The results show that the optimization can solvel the above defects and the model has good application value.

Key words：Aircraft Carrier； Outbound Schedule；Means Cluster； Particle Swarm； population diversity

1 概述

调度是指为了实现某一目的而对共同使用的资源实行时间分配[1]。作为调度问题的一个子集，车间调度问题实际上也是一个资源分配问题。问题的求解目标主要是找到一组资源并安排到设备上去，以使作业可被“最优”完成的方案。

舰载机在航母上的调度问题是制约舰载机出动和回收的重要因素。在整个飞行任务实施过程中，舰载机的调运是一个主要的阶段，在航空母舰这样特殊的环境下，如何快速高效地将舰载机从机库转运到飞行甲板，在很大程度上影响着舰载机的起降，从而决定了航母战斗力的形成和提高。以往研究主要集中在飞行甲板调度方面，运筹学领域的图与网络分析法、排队论[2]等研究方法能够很好地解决这些问题。随着以粒子群为代表的群智能算法的研究应用不断深入，群智能优化算法在资源分配及生产调度问题[3]的求解方面较其他算法优势明显，而且能较好地提高问题解的精度。有学者将舰载机舰面布放调度问题转换为带有约束条件的多目标函数求最小解问题，并基于智能粒子群（PSO）算法对戴高乐航母舰载机舰面布放调度问题的解决方法进行了研究[4]；也有学者应用柔性流水车间调度理论对空间约束条件下的舰载机出库调度问题进行建模，并基于粒子群算法对问题进行求解[5]。针对基本粒子群算法易陷入局部极值、寻优结果不稳定等缺陷，本文基于K-Means聚类算法原理，提出KMCPSO（K-Means Cluster Particle Swarm Optimization）优化算法，并利用该算法求解舰载机的出库调度问题。

2 KMCPSO算法

基本的粒子群算法通过种群间粒子的相互学习，逐渐向最优解位置收敛。种群间相互学习的基础是种群的拓扑结构，拓扑结构的不同会导致粒子的学习样本也不同。如果种群的拓扑结构固定不变（静态），则在迭代过程中，每个粒子的学习样本都是固定的，如果该粒子陷入局部最优解，粒子将会向已陷入局部最优解的学习样本学习，导致种群陷入局部最优解的概率增加[6]。根据“物以类聚”的自然选择法则，我们可以设法把算法运行中单一的种群分为多个种群，这样即使某个种群出现了早熟收敛，其他的种群还是有机会继续向全局最优位置收敛。基于此，本文提出基于K-Means聚类原理的KMCPSO算法。

2.1 K-Means聚类原理

K-Means算法属于划分式聚类算法，是一个寻找目标函数最小化的过程，目标函数的准则是使得聚簇内部尽可能紧凑，各个聚簇之间尽可能分开，通常采用方差函数。假设 数 据 集 [X=x1，x2，…xn]，[X1k1=1]是K-Means算法给出的一个K划分，则[C=c1，c2，…ck]表示K个划分的中心，式（1）为K-Means算法的目标函数：

[E=l=1kxi∈Xlxl-Cl2] （1）

首先随机选取K个点作为初始的聚类中心，然后计算各个点到聚类中心的距离，把数据点划入到离它最近的聚类中心所在的聚簇中，划分完毕后，对每一个聚簇计算新的聚类中心，然后继续进行数据点划入过程，直到聚类中心不发生变化，此时目标函数也收敛到最小。

2.2 KMCPSO算法原理

在传统的粒子群算法中，由于每个子群的成员都是采用随机法确定的，这种的种群构建策略会使得算法搜索过程带有一定的盲目性。粒子的聚合往往通过某种规则以极值粒子为中心飞向极值粒子所在位置，而当群体多样性丧失时，群体将陷入局部极值点。基于此，我们利用[K]-均值聚类算法进行子群的构建（K-means Cluster Particle Swarm Optimization，KMCPSO），以解决上述存在的问题。

动态多种群策略是将种群分成若干个子群，每个子群的成员在搜索过程中不是固定的，而是动态变化的。对每个子群重新构建的规则是每间隔[t]代（重组间隔代数），将整个种群重新划分为若干个子群，这种策略使得每个子群的信息能够有效的交流，提升粒子跳出局部最优解的能力。

利用[K]-均值聚类算法进行子群动态构建的步骤如下所示：

[Step1] 设[TS0=（t1，t2，…，tN）]表示由[N]个粒子[ti=（t1i，t2i，…，tdi）（i=1，2，…，N）]构成的初始种群，[tji（i=1，2，…，d）]表示第[i]个粒子的第[j]维；

[Step2] 从[TS0]中随机地选取[n（n

[Step3] 对[?ti∈TSt]，计算两点间的欧氏距离 [d（ti，sh）=ti-sh]，[（h=1，2，…N）] 如果满足条件： [d（ti，sh）={mind（ti，sh）h=1，2，…N}]， 那么将[ti]属于第[Ui]类， 按此方法将[TSt] 中所有粒子分配完。

[Step4] 重新计算聚类中心[U′i=（1n）ts∈Uits，（s=1，2，…，ni）]；[ni] 表示[Ui] 中的粒子数.

[Step5] 如果 [U′i=Ui]，[i=1，2，…k]输出 [k]个聚类（[k]个子群） [Ui（i=1，2，…k）]； 否则令[Ui=U′i]，转入 [Step3]

KMCPSO算法流程如图1所示：

图1 KMCPSO算法流程

3 舰载机出库调度模型

3.1流程分析

本文以俄罗斯“库兹涅佐夫”号航母舰载机出库任务为例[7]，研究分析舰载机作业时序优化。“库兹涅佐夫”号航母的舰载机出库调运设施主要有牵引车、调向转盘、升降机和系留设施（系留座及系留索具）。俄“库兹涅佐夫”号航母舰载机出库过程中，要涉及机库内轨道牵引、调向转盘调向、飞机升降机操作、飞行甲板牵引等过程。每个转向盘和一个升降机组成一个配套设备，分别记为一号设备和二号设备。图2为航母出库调度时序。

图 2 舰载机调运作业时序

3.2 条件假设

本文提出的调度模型有如下假设：整个调度过程中不出现故障；舰载机的系留、转向、解系留的时间相同，本文将这部分时间忽略；牵引车负载作业和空驶作业速度一定且相等；所有升降机的升降时间均相等且固定；所有舰载机的调度工序均相同；所有舰载机停机位已知且固定；在同一时刻，一台设备只能保障一架舰载机；在同一时刻，一架舰载机只能接受一个阶段一台设备的保障。

3.3模型建立

假设航母机库内共有[x][（i，j=1，2，…x）]架舰载机需安排调度，机库内有[h][（k=1，2，…h）]个升降机、[b1]辆牵引车，[c]个转向盘；飞行甲板共有[b2]辆牵引车，[d][（m=1，2，…d）]个飞行甲板停机位。本文调度模型的所有参数说明如下：

[F]为目标函数，表示舰载机总调度完工时间最短的方案；

[Tp（i）]为第[P]套方案位于第[i]停机位舰载机的调度完工时间；

[Ts（i，j，k）]为机库内第[i]停机位舰载机处于第[j]顺序到达第[k]号升降机的时间；

[Tj（i，j，k）]为机库第[i]停机位舰载机以第[j]顺序到达第[k]号升降机的开始转运时间；

[C（i，j+1，k）]为机库第[i]停机位舰载机以第[j+1]顺序到达第[k]号升降机的转运时间；

[B（m，j，k）]为以第[j]顺序升起后的舰载机由第[k]号升降机到第[m]个飞行甲板停机位的转运时间；

[A[i，k]、][B[m，k]、] [Ci，k]均为常数矩阵，其中：

[A[i，k]]表示机库内牵引车由第[i]停机位行驶到第[k]号升降机的需用时间；

[B[m，k]]表示飞行甲板上牵引车由第[k]号升降机行驶到第[m]停机位的需用时间；

[Ci，k]表示机库内第[i]停机位舰载机到第[k]号升降机的转运所需时间；

[a（i，j.，k）]表示机库内第[i]停机位处于第[j]顺序到达第[k]号升降机的舰载机标号；

[Tt]为升降机单程升降所需时间。

综上所述，舰载机的出库调度模型为：

目标函数：[F=minmax1≤i≤nTP（i）] （2）

[St：Ti=TS（i，j，k）+Bm，k+Tt1≤i，j≤n，1≤m≤d，1≤k≤h]（3） [a（i，j，k）≠a（l，j，k）1≤l≤n] （4）

[TS（i，j，k）-Tj（i，j，k）=Ci，k] （5）

[Tj（l，j+1，k）>Ts（i，j，k）] （6）

[Ts（i，j+1，k）=Ts（v，j，k）+2×B（m，j，k），Av，k+C（i，j+1，k）≤2×B（m，j，k）Ts（v，j，k）+Av，k+C（i，j+1，k），Av，k+C（i，j+1，k）>2×B（m，j，k）+T1

[Ts（i，j，k）>Ts（l，m，k）orTs（i，j，k）

式（2）表示目标为求取舰载机总调度完工时间最短的方案；式（3）表示处于第[i]停机位的舰载机转运过程不中断，保持运转连续性；式（4）表示不同舰载机的初始停机位不同且已知；式（5）表示基于空间约束条件下，第[i]停机位舰载机到第[k]号升降机的转运所需时间已确定；式（6）表示舰载机保障转运属于串行工序；式（7）表示考虑串行工序的等待时间，将串行工序的等待时间计算到转运时间内；式（8）表示同一设备不能保障多架舰载机。

4 基于KMCPSO的舰载机出库调度算法

假设某航母机库内有2辆牵引车，2个转向盘，2台升降机，飞行甲板有2辆牵引车。先需将机库内的20架舰载机调度到飞行甲板执行任务。

4.1 粒子的编码和解码

本文采用二维粒子进行编码，第一维20个向量表示20架舰载机的转运作业次序，在1到20之间取随机数，数值越小的，作业次数越靠前；第二维20个向量表示用于分配20架舰载机的转向转盘，在取值为1或2。表1给出了粒子的编码形式（随机产生）。

表1 粒子的两维编码

[停机位＼&1＼&2＼&3＼&4＼&5＼&6＼&7＼&8＼&9＼&10＼&粒子位置Xi1＼&12.6＼&-14.9＼&16.5＼&5.29＼&-16.1＼&-8.86＼&1.88＼&18.3＼&18.6＼&-13.7＼&粒子位置Xi2＼&1＼&2＼&1＼&2＼&1＼&2＼&1＼&2＼&2＼&2＼&停机位＼&11＼&12＼&13＼&14＼&15＼&16＼&17＼&18＼&19＼&20＼&粒子位置Xi1＼&18.8＼&18.3＼&-0.585＼&12.0＼&-14.3＼&-3.13＼&16.6＼&11.7＼&18.4＼&16.2＼&粒子位置Xi2＼&1＼&1＼&1＼&2＼&1＼&2＼&2＼&2＼&1＼&1＼&]

根据粒子的编码，可以将舰载机进行资源分配和作业调度（即解码过程）：一号设备5→15→13→7→1→20→3→12→19→11；二号设备2→10→6→16→4→18→14→17→2→9。

4.2 实验结果与分析

本文以20架舰载机的出库调度为例，数据由文献[5]提供。表2给出了舰载机在机库内转运、飞行甲板转运的时间和牵引车在机库内空驶的时间等部分数据，其中，机库内转运表示舰载机从停机位分别转运到两套转向盘所需时间参数，飞行甲板转运表示舰载机从升降机处转运至指定飞行甲板停机位所需时间参数，库内空驶表示牵引车从升降机返程会舰载机停机位所需时间参数（表2中的数据仅供参考，以实际转运时间为准）。

表2 舰载机调度时间参数（单位：秒）

[舰载机库

内停机位＼&库内转运＼&飞行甲板转运＼&牵引车库内空驶＼&1号

设备＼&2号

设备＼&1号

设备＼&2号

设备＼&1号

设备＼&2号

设备＼&1＼&231＼&327＼&46＼&99＼&31＼&127＼&2＼&241＼&306＼&59＼&86＼&41＼&106＼&3＼&259＼&286＼&76＼&69＼&59＼&86＼&4＼&279＼&367＼&91＼&57＼&79＼&67＼&5＼&278＼&367＼&107＼&41＼&78＼&67＼&6＼&297＼&347＼&151＼&55＼&97＼&47＼&7＼&316＼&230＼&163＼&66＼&116＼&30＼&8＼&345＼&344＼&181＼&83＼&145＼&44＼&9＼&348＼&348＼&121＼&50＼&148＼&48＼&10＼&357＼&357＼&138＼&53＼&157＼&57＼&]

参数设置位为：迭代次数[Gmax=500]；种群规模[m=20]，学习因子[c1=c2=2]，惯性权重[ω]最大值0.9，最小值0.4，分群间隔代数为100。

利用KMCPSO算法可以求解得到调度总用时最短的转运方案为：一号设备2→13→4→5→3→11→15→14→11→12；二号设备20→18→6→10→8→9→7→17→16→19。

20架舰载机出库最短用时2926s（48.7min，仅供参考），比初始随机方案调度（3600s，随机分配）节省时间近700s，占总用时23.9%，因此调度优化具有较大应用价值。最优方案对应的甘特图如图3所示：

图3 舰载机出库调度甘特图

分别基于KMCPSO算法和原始粒子群算法（PSO）[8]对舰载机调度模型进行求解，每种算法各运行10～50次。表3给出了最优运转方案的结果比较。

表3 调度方案结果比较

[运行次数＼&算法＼&调度方案＼&调度用时＼&

10

＼&KMCPSO

＼&一号 11→5→4→12→2→13→15→1→14→3

二号 7→19→20→6→9→10→16→18→8→17＼&2947＼&PSO

＼&一号 11→5→2→1→14→4→12→15→13→3

二号 9→19→10→16→6→7→8→20→18→17＼&3632＼&

20

＼&KMCPSO

＼&一号 5→3→15→2→14→12→4→11→13→1

二号 7→17→6→20→19→10→18→8→16→9＼&2929＼&PSO

＼&一号 15→1→2→5→12→13→3→11→4→14

二号 19→8→9→7→10→6→18→17→16→20＼&3032＼&

30

＼&KMCPSO

＼&一号 2→13→11→15→4→3→12→14→11→5

二号 7→16→20→8→6→9→18→17→10→19＼&2930＼&PSO

＼&一号 2→13→4→5→3→11→15→14→11→12

二号 20→18→6→10→8→9→7→17→16→19＼&3023＼&

40

＼&KMCPSO

＼&一号 2→13→4→5→3→11→15→14→11→12

二号 20→18→6→10→8→9→7→17→16→19＼&2926

＼&PSO

＼&一号 13→15→1→11→19→14→8→3→18→5→2

二号 4→6→9→7→20→12→10→17→16＼&3127＼&

50

＼&KMCPSO

＼&一号 1→3→13→2→5→12→14→15→11→4

二号 19→8→16→17→9→10→18→6→20→7＼&2984＼&PSO

＼&一号 2→5→12→14→3→15→18→19→11→4→13→6

二号 16→11→7→20→9→10→17→8＼&3032＼&]

由表3可以看出，基于KMCPSO的调度算法总用时均比PSO用少，且每次运行结果均较稳定，表明了本文提出的算法较好的克服了易陷入局部极值、寻优结果不稳定等缺陷，具有较好的实用性和应用价值。

5 结论

为减小舰载机从机库转运到飞行甲板的调度时间，实现作战资源的高效分配，本文利用KMCPSO算法建立了KMCPSO舰载机调度模型，并运用实例进行了仿真实验。仿真结果证明，采用KMCPSO算法能较好地解决PSO算法易陷入局部极值、寻优结果不稳定等缺陷，具有较好的实用性和应用价值。现代战争对航空母舰的战斗力提出了更高要求，如何快速有效地解决舰载机的调度问题，使得航空母舰能够更好地适应未来高科技战争需求，是下一步值得深入研究的工作。

参考文献：

[1] 夏蔚军，吴智铭，张伟，等.微粒群优化在Job-shop调度中的应用[J].上海交通大学学报，2005，39（3）：381-385.

[2] 《运筹学》教材编写组. 运筹学[M]. 北京： 清华大学出版社， 2008： 251-25.

[3] 王万良， 吴启迪. 生产调度智能算法及其应用[M]. 北京： 科学出版社， 2007：114-121.

[4] 司维超，韩维，史玮韦. 基于PSO算法的舰载机舰面布放调度方法研究[J].航空学报，2012，36（11）：45-47.

[5] 王云翔，毕玉泉，杨茂胜，等. 基于空间约束的舰载机出库调度[J].指挥控制与仿真，2015，37（1）：83-85.

[6] Hong～li Xu ，Xu Qian， liang Zhang. Study of ACO Algorithm Optimization Algorithm Based on Improved Tent Chaotic Mapping Journal of Information &Computational Science. EI 9：6 （2012） ：1653-1660.

[7] 杨炳恒，王海东，韩峰，等. 舰载机调运作业流程优化研究[J]. 科学技术与工程，2010，10（22）：53-55.

[8] Kennedy J， Eberhart C. Particle swarm optimization [C]. In Proceedings of IEEE International Conference on Neural Networks， Washington， 1995： 1942-1948.