基于均值聚類的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.