基于均值聚類的KMCPSO艦載機(jī)出庫調(diào)度算法

彭業(yè)飛++張維繼++邵明臣++馮智鑫

摘要：航母艦載機(jī)的出庫調(diào)度效率，在很大程度上決定了整個航母的戰(zhàn)斗力生成。通過研究K均值聚類算法的基本原理，提出基于均值聚類的KMCPSO艦載機(jī)出庫調(diào)度算法。該算法針對粒子群算法在進(jìn)化過程中易出現(xiàn)早熟和尋優(yōu)結(jié)果不穩(wěn)定的缺陷，通過在迭代過程對種群進(jìn)行分群，以提高種群多樣性，從而克服原算法的不足。基于俄羅斯“庫茲涅佐夫”號航母艦載機(jī)出庫任務(wù)，建立艦載機(jī)調(diào)度模型，并用KMCPSO算法進(jìn)行求解。結(jié)果表明，KMCPSO算法能克服上述缺陷，模型有較好的應(yīng)用價值。

關(guān)鍵詞：艦載機(jī)；出庫調(diào)度；均值聚類；粒子群；種群多樣性

中圖分類號： TP312 文獻(xiàn)標(biāo)識碼：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，F(xiàn)ENG 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 概述

調(diào)度是指為了實現(xiàn)某一目的而對共同使用的資源實行時間分配[1]。作為調(diào)度問題的一個子集，車間調(diào)度問題實際上也是一個資源分配問題。問題的求解目標(biāo)主要是找到一組資源并安排到設(shè)備上去，以使作業(yè)可被“最優(yōu)”完成的方案。

艦載機(jī)在航母上的調(diào)度問題是制約艦載機(jī)出動和回收的重要因素。在整個飛行任務(wù)實施過程中，艦載機(jī)的調(diào)運是一個主要的階段，在航空母艦這樣特殊的環(huán)境下，如何快速高效地將艦載機(jī)從機(jī)庫轉(zhuǎn)運到飛行甲板，在很大程度上影響著艦載機(jī)的起降，從而決定了航母戰(zhàn)斗力的形成和提高。以往研究主要集中在飛行甲板調(diào)度方面，運籌學(xué)領(lǐng)域的圖與網(wǎng)絡(luò)分析法、排隊論[2]等研究方法能夠很好地解決這些問題。隨著以粒子群為代表的群智能算法的研究應(yīng)用不斷深入，群智能優(yōu)化算法在資源分配及生產(chǎn)調(diào)度問題[3]的求解方面較其他算法優(yōu)勢明顯，而且能較好地提高問題解的精度。有學(xué)者將艦載機(jī)艦面布放調(diào)度問題轉(zhuǎn)換為帶有約束條件的多目標(biāo)函數(shù)求最小解問題，并基于智能粒子群（PSO）算法對戴高樂航母艦載機(jī)艦面布放調(diào)度問題的解決方法進(jìn)行了研究[4]；也有學(xué)者應(yīng)用柔性流水車間調(diào)度理論對空間約束條件下的艦載機(jī)出庫調(diào)度問題進(jìn)行建模，并基于粒子群算法對問題進(jìn)行求解[5]。針對基本粒子群算法易陷入局部極值、尋優(yōu)結(jié)果不穩(wěn)定等缺陷，本文基于K-Means聚類算法原理，提出KMCPSO（K-Means Cluster Particle Swarm Optimization）優(yōu)化算法，并利用該算法求解艦載機(jī)的出庫調(diào)度問題。

2 KMCPSO算法

基本的粒子群算法通過種群間粒子的相互學(xué)習(xí)，逐漸向最優(yōu)解位置收斂。種群間相互學(xué)習(xí)的基礎(chǔ)是種群的拓?fù)浣Y(jié)構(gòu)，拓?fù)浣Y(jié)構(gòu)的不同會導(dǎo)致粒子的學(xué)習(xí)樣本也不同。如果種群的拓?fù)浣Y(jié)構(gòu)固定不變（靜態(tài)），則在迭代過程中，每個粒子的學(xué)習(xí)樣本都是固定的，如果該粒子陷入局部最優(yōu)解，粒子將會向已陷入局部最優(yōu)解的學(xué)習(xí)樣本學(xué)習(xí)，導(dǎo)致種群陷入局部最優(yōu)解的概率增加[6]。根據(jù)“物以類聚”的自然選擇法則，我們可以設(shè)法把算法運行中單一的種群分為多個種群，這樣即使某個種群出現(xiàn)了早熟收斂，其他的種群還是有機(jī)會繼續(xù)向全局最優(yōu)位置收斂。基于此，本文提出基于K-Means聚類原理的KMCPSO算法。

2.1 K-Means聚類原理

K-Means算法屬于劃分式聚類算法，是一個尋找目標(biāo)函數(shù)最小化的過程，目標(biāo)函數(shù)的準(zhǔn)則是使得聚簇內(nèi)部盡可能緊湊，各個聚簇之間盡可能分開，通常采用方差函數(shù)。假設(shè) 數(shù) 據(jù) 集 [X=x1，x2，…xn]，[X1k1=1]是K-Means算法給出的一個K劃分，則[C=c1，c2，…ck]表示K個劃分的中心，式（1）為K-Means算法的目標(biāo)函數(shù)：

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

首先隨機(jī)選取K個點作為初始的聚類中心，然后計算各個點到聚類中心的距離，把數(shù)據(jù)點劃入到離它最近的聚類中心所在的聚簇中，劃分完畢后，對每一個聚簇計算新的聚類中心，然后繼續(xù)進(jìn)行數(shù)據(jù)點劃入過程，直到聚類中心不發(fā)生變化，此時目標(biāo)函數(shù)也收斂到最小。

2.2 KMCPSO算法原理

在傳統(tǒng)的粒子群算法中，由于每個子群的成員都是采用隨機(jī)法確定的，這種的種群構(gòu)建策略會使得算法搜索過程帶有一定的盲目性。粒子的聚合往往通過某種規(guī)則以極值粒子為中心飛向極值粒子所在位置，而當(dāng)群體多樣性喪失時，群體將陷入局部極值點。基于此，我們利用[K]-均值聚類算法進(jìn)行子群的構(gòu)建（K-means Cluster Particle Swarm Optimization，KMCPSO），以解決上述存在的問題。

動態(tài)多種群策略是將種群分成若干個子群，每個子群的成員在搜索過程中不是固定的，而是動態(tài)變化的。對每個子群重新構(gòu)建的規(guī)則是每間隔[t]代（重組間隔代數(shù)），將整個種群重新劃分為若干個子群，這種策略使得每個子群的信息能夠有效的交流，提升粒子跳出局部最優(yōu)解的能力。

利用[K]-均值聚類算法進(jìn)行子群動態(tài)構(gòu)建的步驟如下所示：

[Step1] 設(shè)[TS0=（t1，t2，…，tN）]表示由[N]個粒子[ti=（t1i，t2i，…，tdi）（i=1，2，…，N）]構(gòu)成的初始種群，[tji（i=1，2，…，d）]表示第[i]個粒子的第[j]維；

[Step2] 從[TS0]中隨機(jī)地選取[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] 中的粒子數(shù).

[Step5] 如果 [U′i=Ui]，[i=1，2，…k]輸出 [k]個聚類（[k]個子群） [Ui（i=1，2，…k）]； 否則令[Ui=U′i]，轉(zhuǎn)入 [Step3]

KMCPSO算法流程如圖1所示：

圖1 KMCPSO算法流程

3 艦載機(jī)出庫調(diào)度模型

3.1流程分析

本文以俄羅斯“庫茲涅佐夫”號航母艦載機(jī)出庫任務(wù)為例[7]，研究分析艦載機(jī)作業(yè)時序優(yōu)化?！皫炱澞舴颉碧柡侥傅呐炤d機(jī)出庫調(diào)運設(shè)施主要有牽引車、調(diào)向轉(zhuǎn)盤、升降機(jī)和系留設(shè)施（系留座及系留索具）。俄“庫茲涅佐夫”號航母艦載機(jī)出庫過程中，要涉及機(jī)庫內(nèi)軌道牽引、調(diào)向轉(zhuǎn)盤調(diào)向、飛機(jī)升降機(jī)操作、飛行甲板牽引等過程。每個轉(zhuǎn)向盤和一個升降機(jī)組成一個配套設(shè)備，分別記為一號設(shè)備和二號設(shè)備。圖2為航母出庫調(diào)度時序。

圖 2 艦載機(jī)調(diào)運作業(yè)時序

3.2 條件假設(shè)

本文提出的調(diào)度模型有如下假設(shè)：整個調(diào)度過程中不出現(xiàn)故障；艦載機(jī)的系留、轉(zhuǎn)向、解系留的時間相同，本文將這部分時間忽略；牽引車負(fù)載作業(yè)和空駛作業(yè)速度一定且相等；所有升降機(jī)的升降時間均相等且固定；所有艦載機(jī)的調(diào)度工序均相同；所有艦載機(jī)停機(jī)位已知且固定；在同一時刻，一臺設(shè)備只能保障一架艦載機(jī)；在同一時刻，一架艦載機(jī)只能接受一個階段一臺設(shè)備的保障。

3.3模型建立

假設(shè)航母機(jī)庫內(nèi)共有[x][（i，j=1，2，…x）]架艦載機(jī)需安排調(diào)度，機(jī)庫內(nèi)有[h][（k=1，2，…h(huán)）]個升降機(jī)、[b1]輛牽引車，[c]個轉(zhuǎn)向盤；飛行甲板共有[b2]輛牽引車，[d][（m=1，2，…d）]個飛行甲板停機(jī)位。本文調(diào)度模型的所有參數(shù)說明如下：

[F]為目標(biāo)函數(shù)，表示艦載機(jī)總調(diào)度完工時間最短的方案；

[Tp（i）]為第[P]套方案位于第[i]停機(jī)位艦載機(jī)的調(diào)度完工時間；

[Ts（i，j，k）]為機(jī)庫內(nèi)第[i]停機(jī)位艦載機(jī)處于第[j]順序到達(dá)第[k]號升降機(jī)的時間；

[Tj（i，j，k）]為機(jī)庫第[i]停機(jī)位艦載機(jī)以第[j]順序到達(dá)第[k]號升降機(jī)的開始轉(zhuǎn)運時間；

[C（i，j+1，k）]為機(jī)庫第[i]停機(jī)位艦載機(jī)以第[j+1]順序到達(dá)第[k]號升降機(jī)的轉(zhuǎn)運時間；

[B（m，j，k）]為以第[j]順序升起后的艦載機(jī)由第[k]號升降機(jī)到第[m]個飛行甲板停機(jī)位的轉(zhuǎn)運時間；

[A[i，k]、][B[m，k]、] [Ci，k]均為常數(shù)矩陣，其中：

[A[i，k]]表示機(jī)庫內(nèi)牽引車由第[i]停機(jī)位行駛到第[k]號升降機(jī)的需用時間；

[B[m，k]]表示飛行甲板上牽引車由第[k]號升降機(jī)行駛到第[m]停機(jī)位的需用時間；

[Ci，k]表示機(jī)庫內(nèi)第[i]停機(jī)位艦載機(jī)到第[k]號升降機(jī)的轉(zhuǎn)運所需時間；

[a（i，j.，k）]表示機(jī)庫內(nèi)第[i]停機(jī)位處于第[j]順序到達(dá)第[k]號升降機(jī)的艦載機(jī)標(biāo)號；

[Tt]為升降機(jī)單程升降所需時間。

綜上所述，艦載機(jī)的出庫調(diào)度模型為：

目標(biāo)函數(shù)：[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）表示目標(biāo)為求取艦載機(jī)總調(diào)度完工時間最短的方案；式（3）表示處于第[i]停機(jī)位的艦載機(jī)轉(zhuǎn)運過程不中斷，保持運轉(zhuǎn)連續(xù)性；式（4）表示不同艦載機(jī)的初始停機(jī)位不同且已知；式（5）表示基于空間約束條件下，第[i]停機(jī)位艦載機(jī)到第[k]號升降機(jī)的轉(zhuǎn)運所需時間已確定；式（6）表示艦載機(jī)保障轉(zhuǎn)運屬于串行工序；式（7）表示考慮串行工序的等待時間，將串行工序的等待時間計算到轉(zhuǎn)運時間內(nèi)；式（8）表示同一設(shè)備不能保障多架艦載機(jī)。

4 基于KMCPSO的艦載機(jī)出庫調(diào)度算法

假設(shè)某航母機(jī)庫內(nèi)有2輛牽引車，2個轉(zhuǎn)向盤，2臺升降機(jī)，飛行甲板有2輛牽引車。先需將機(jī)庫內(nèi)的20架艦載機(jī)調(diào)度到飛行甲板執(zhí)行任務(wù)。

4.1 粒子的編碼和解碼

本文采用二維粒子進(jìn)行編碼，第一維20個向量表示20架艦載機(jī)的轉(zhuǎn)運作業(yè)次序，在1到20之間取隨機(jī)數(shù)，數(shù)值越小的，作業(yè)次數(shù)越靠前；第二維20個向量表示用于分配20架艦載機(jī)的轉(zhuǎn)向轉(zhuǎn)盤，在取值為1或2。表1給出了粒子的編碼形式（隨機(jī)產(chǎn)生）。

表1 粒子的兩維編碼

[停機(jī)位＼&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＼&停機(jī)位＼&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＼&]

根據(jù)粒子的編碼，可以將艦載機(jī)進(jìn)行資源分配和作業(yè)調(diào)度（即解碼過程）：一號設(shè)備5→15→13→7→1→20→3→12→19→11；二號設(shè)備2→10→6→16→4→18→14→17→2→9。

4.2 實驗結(jié)果與分析

本文以20架艦載機(jī)的出庫調(diào)度為例，數(shù)據(jù)由文獻(xiàn)[5]提供。表2給出了艦載機(jī)在機(jī)庫內(nèi)轉(zhuǎn)運、飛行甲板轉(zhuǎn)運的時間和牽引車在機(jī)庫內(nèi)空駛的時間等部分?jǐn)?shù)據(jù)，其中，機(jī)庫內(nèi)轉(zhuǎn)運表示艦載機(jī)從停機(jī)位分別轉(zhuǎn)運到兩套轉(zhuǎn)向盤所需時間參數(shù)，飛行甲板轉(zhuǎn)運表示艦載機(jī)從升降機(jī)處轉(zhuǎn)運至指定飛行甲板停機(jī)位所需時間參數(shù)，庫內(nèi)空駛表示牽引車從升降機(jī)返程會艦載機(jī)停機(jī)位所需時間參數(shù)（表2中的數(shù)據(jù)僅供參考，以實際轉(zhuǎn)運時間為準(zhǔn)）。

表2 艦載機(jī)調(diào)度時間參數(shù)（單位：秒）

[艦載機(jī)庫

內(nèi)停機(jī)位＼&庫內(nèi)轉(zhuǎn)運＼&飛行甲板轉(zhuǎn)運＼&牽引車庫內(nèi)空駛＼&1號

設(shè)備＼&2號

設(shè)備＼&1號

設(shè)備＼&2號

設(shè)備＼&1號

設(shè)備＼&2號

設(shè)備＼&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＼&]

參數(shù)設(shè)置位為：迭代次數(shù)[Gmax=500]；種群規(guī)模[m=20]，學(xué)習(xí)因子[c1=c2=2]，慣性權(quán)重[ω]最大值0.9，最小值0.4，分群間隔代數(shù)為100。

利用KMCPSO算法可以求解得到調(diào)度總用時最短的轉(zhuǎn)運方案為：一號設(shè)備2→13→4→5→3→11→15→14→11→12；二號設(shè)備20→18→6→10→8→9→7→17→16→19。

20架艦載機(jī)出庫最短用時2926s（48.7min，僅供參考），比初始隨機(jī)方案調(diào)度（3600s，隨機(jī)分配）節(jié)省時間近700s，占總用時23.9%，因此調(diào)度優(yōu)化具有較大應(yīng)用價值。最優(yōu)方案對應(yīng)的甘特圖如圖3所示：

圖3 艦載機(jī)出庫調(diào)度甘特圖

分別基于KMCPSO算法和原始粒子群算法（PSO）[8]對艦載機(jī)調(diào)度模型進(jìn)行求解，每種算法各運行10～50次。表3給出了最優(yōu)運轉(zhuǎn)方案的結(jié)果比較。

表3 調(diào)度方案結(jié)果比較

[運行次數(shù)＼&算法＼&調(diào)度方案＼&調(diào)度用時＼&

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的調(diào)度算法總用時均比PSO用少，且每次運行結(jié)果均較穩(wěn)定，表明了本文提出的算法較好的克服了易陷入局部極值、尋優(yōu)結(jié)果不穩(wěn)定等缺陷，具有較好的實用性和應(yīng)用價值。

5 結(jié)論

為減小艦載機(jī)從機(jī)庫轉(zhuǎn)運到飛行甲板的調(diào)度時間，實現(xiàn)作戰(zhàn)資源的高效分配，本文利用KMCPSO算法建立了KMCPSO艦載機(jī)調(diào)度模型，并運用實例進(jìn)行了仿真實驗。仿真結(jié)果證明，采用KMCPSO算法能較好地解決PSO算法易陷入局部極值、尋優(yōu)結(jié)果不穩(wěn)定等缺陷，具有較好的實用性和應(yīng)用價值?，F(xiàn)代戰(zhàn)爭對航空母艦的戰(zhàn)斗力提出了更高要求，如何快速有效地解決艦載機(jī)的調(diào)度問題，使得航空母艦?zāi)軌蚋玫剡m應(yīng)未來高科技戰(zhàn)爭需求，是下一步值得深入研究的工作。

參考文獻(xiàn)：

[1] 夏蔚軍，吳智銘，張偉，等.微粒群優(yōu)化在Job-shop調(diào)度中的應(yīng)用[J].上海交通大學(xué)學(xué)報，2005，39（3）：381-385.

[2] 《運籌學(xué)》教材編寫組. 運籌學(xué)[M]. 北京： 清華大學(xué)出版社， 2008： 251-25.

[3] 王萬良， 吳啟迪. 生產(chǎn)調(diào)度智能算法及其應(yīng)用[M]. 北京： 科學(xué)出版社， 2007：114-121.

[4] 司維超，韓維，史瑋韋. 基于PSO算法的艦載機(jī)艦面布放調(diào)度方法研究[J].航空學(xué)報，2012，36（11）：45-47.

[5] 王云翔，畢玉泉，楊茂勝，等. 基于空間約束的艦載機(jī)出庫調(diào)度[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ī)調(diào)運作業(yè)流程優(yōu)化研究[J]. 科學(xué)技術(shù)與工程，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.