基于進(jìn)化粒子群算法的軍事訓(xùn)練計(jì)劃智能優(yōu)化

杜尚華,樊率軍,趙玉建

(國防大學(xué)聯(lián)合作戰(zhàn)學(xué)院,河北石家莊 050000)

軍事訓(xùn)練中的補(bǔ)差訓(xùn)練計(jì)劃生成與優(yōu)化是基層部隊(duì)日常組訓(xùn)的難點(diǎn),其核心問題在于解決對(duì)薄弱訓(xùn)練課目、組訓(xùn)者和參訓(xùn)人員的最優(yōu)化分配,以保證在有效時(shí)間內(nèi)最大限度利用訓(xùn)練場地和裝備器材資源,達(dá)成訓(xùn)練效益最大化,提升官兵整體訓(xùn)練水平。補(bǔ)差訓(xùn)練計(jì)劃優(yōu)化問題可看做是經(jīng)典排課問題的延伸,其在20世紀(jì)70年代已被證明屬于NP完全問題[1]。隨著計(jì)算機(jī)運(yùn)算能力的日益提升,眾多智能優(yōu)化算法被設(shè)計(jì)提出,為補(bǔ)差訓(xùn)練計(jì)劃優(yōu)化問題提供了技術(shù)可行解法。智能優(yōu)化算法的發(fā)展可分為經(jīng)典公式階段和實(shí)踐應(yīng)用階段,前期的優(yōu)化算法主要有拉格朗日松弛法[2]、切割平面法[3]、整數(shù)規(guī)劃法[4]等,其原理是通過公式演算找到局部極值,用以模擬全局最優(yōu)值,算法約束條件較為苛刻,必須具備線性連續(xù)、可微等函數(shù)特點(diǎn);應(yīng)用階段的優(yōu)化算法則通過模擬生物種群習(xí)性設(shè)計(jì)算法框架,代表性的優(yōu)化算法有遺傳算法[5]、蜂群算法[6]、蟻群算法[7]、蛙跳算法[8]、螢火蟲算法[9]、魚群算法[10]、粒子群算法[11]等,其原理是通過偽隨機(jī)變量模擬生物某項(xiàng)生理特征,通過多代演化使局部最優(yōu)解逼近全局最優(yōu)解。此類算法突破了線性約束條件限制,為工程應(yīng)用奠定了技術(shù)基礎(chǔ),但也普遍存在收斂效率低、收斂時(shí)間不確定、易于陷入局部最優(yōu)陷阱等問題。本文在總結(jié)前人研究基礎(chǔ)上,通過對(duì)比分析粒子群算法和遺傳算法的異同,提出融合了生物進(jìn)化特征的進(jìn)化粒子群算法,并將其應(yīng)用于補(bǔ)差訓(xùn)練計(jì)劃優(yōu)化工程實(shí)踐中,實(shí)現(xiàn)了訓(xùn)練計(jì)劃的自動(dòng)生成和智能優(yōu)化。

1 問題描述

補(bǔ)差訓(xùn)練計(jì)劃智能優(yōu)化問題可劃歸排課問題,但又有其獨(dú)立特征,區(qū)別主要在于:1)組訓(xùn)者只在前日制定當(dāng)天的補(bǔ)差訓(xùn)練計(jì)劃,而排課通常為未來數(shù)日課程進(jìn)行統(tǒng)一編排;2)補(bǔ)差訓(xùn)練課目和組訓(xùn)者由組訓(xùn)者手工輸入,而排課通常由規(guī)則限制自動(dòng)生成課目和授課人;3)補(bǔ)差訓(xùn)練計(jì)劃以參訓(xùn)人員歷史成績作為優(yōu)化依據(jù),而排課通常以參訓(xùn)人員選課情況作為優(yōu)化依據(jù)?；诖?補(bǔ)差訓(xùn)練計(jì)劃優(yōu)化問題描述如:算法輸入為組訓(xùn)者手工選定當(dāng)日的訓(xùn)練課目、訓(xùn)練時(shí)間段、組訓(xùn)者。設(shè)組訓(xùn)課目集合為K,訓(xùn)練時(shí)間段集合為T,參訓(xùn)人員集合為R。定義補(bǔ)差訓(xùn)練計(jì)劃的評(píng)估指標(biāo)如下:

1)平均分:用以衡量訓(xùn)練計(jì)劃下所有參訓(xùn)人員在該訓(xùn)練課目此前1個(gè)月內(nèi)的平均成績,記為T1。

2)參訓(xùn)率:用以衡量訓(xùn)練計(jì)劃下所有參訓(xùn)人員在該訓(xùn)練課目此前1個(gè)月內(nèi)參加訓(xùn)練天數(shù)占該課目訓(xùn)練總天數(shù)的比例,記為T2。

3)優(yōu)秀率:用以衡量訓(xùn)練計(jì)劃下所有參訓(xùn)人員在該訓(xùn)練課目的成績達(dá)到優(yōu)秀成績的比例,記為T3。

4)訓(xùn)練強(qiáng)度:用以衡量訓(xùn)練計(jì)劃下所有參訓(xùn)人員在訓(xùn)練當(dāng)日的累計(jì)疲勞程度,參訓(xùn)課目越多越疲勞,則訓(xùn)練強(qiáng)度指標(biāo)越大,記為T4。

5)同班率:用以衡量訓(xùn)練計(jì)劃下每個(gè)訓(xùn)練課目的參訓(xùn)人員來自相同班級(jí)的程度,班級(jí)越多人員越零散,則同班率指標(biāo)越低,記為T5。

設(shè)補(bǔ)差訓(xùn)練計(jì)劃的綜合評(píng)分為F,則建立數(shù)學(xué)模型如下

(1)

模型描述為:在(K,T)輸入限制條件下,合理調(diào)整R范圍,使T1-4取得最小值,T5取得最大值,并使綜合評(píng)分F(K,T,R)達(dá)到全局最大值?？紤]到補(bǔ)差訓(xùn)練計(jì)劃的工程應(yīng)用性,還應(yīng)引入如下硬約束條件:

1)訓(xùn)練時(shí)間段有沖突的組訓(xùn)課目內(nèi)不得有重復(fù)人員出現(xiàn)。

2)同一組訓(xùn)課目內(nèi)不得有重復(fù)人員出現(xiàn)。

3)從未參加過某課目訓(xùn)練的人員記為不參訓(xùn)該課目。

2 算法構(gòu)建

根據(jù)問題描述,算法要實(shí)現(xiàn)當(dāng)日訓(xùn)練課目、訓(xùn)練時(shí)間段、組訓(xùn)者的手工輸入,通過進(jìn)化粒子群算法實(shí)現(xiàn)參訓(xùn)人員的智能優(yōu)化。即要設(shè)計(jì)3個(gè)子算法:1)課目、組訓(xùn)者排序算法;2)訓(xùn)練計(jì)劃綜合評(píng)分算法;3)智能優(yōu)化算法。算法流程如圖1所示。

圖1 補(bǔ)差訓(xùn)練計(jì)劃優(yōu)化算法流程圖

2.1 課目、組訓(xùn)者排序算法

該算法計(jì)算目的在于為組訓(xùn)者提供手工輸入量化排序結(jié)果,便于找到訓(xùn)練薄弱課目和與該課目對(duì)應(yīng)的最高成績所在班班長(組訓(xùn)者默認(rèn)從各班班長中優(yōu)選)。課目排序參照指標(biāo)為此前1個(gè)月該參訓(xùn)課目的平均優(yōu)秀率,組訓(xùn)者排序參照指標(biāo)為此前1個(gè)月各班人員在該參訓(xùn)課目的平均分。設(shè)此前1個(gè)月內(nèi)共有m個(gè)課目參訓(xùn),參訓(xùn)人員總數(shù)為n,其中第i個(gè)人在第j個(gè)訓(xùn)練課目的平均成績?yōu)閒ij,則其優(yōu)秀率yij計(jì)算公式為

(2)

課目j的優(yōu)秀率Yj計(jì)算公式為

(3)

設(shè)第k個(gè)班級(jí)內(nèi)共有r個(gè)人,則該班平均分Pkj計(jì)算公式為

(4)

2.2 綜合評(píng)分算法

本文設(shè)計(jì)使用熵權(quán)法和理想點(diǎn)法融合的熵權(quán)理想點(diǎn)方法作為多指標(biāo)融合評(píng)分算法,將補(bǔ)差訓(xùn)練計(jì)劃的平均分、參訓(xùn)率、優(yōu)秀率、訓(xùn)練強(qiáng)度、同班率指標(biāo)合并為綜合評(píng)分結(jié)果代入智能優(yōu)化。

2.2.1 評(píng)估指標(biāo)計(jì)算

某項(xiàng)補(bǔ)差訓(xùn)練計(jì)劃中,設(shè)同班率為T,平均分為F,優(yōu)秀率為Y,訓(xùn)練強(qiáng)度為Q,參訓(xùn)率為C;共安排了p個(gè)訓(xùn)練課目,其中第j個(gè)補(bǔ)差班級(jí)內(nèi)的人員數(shù)為nj;此前1個(gè)月內(nèi),課目j共組織考核m次,其中人員i的該課目平均分為fij,則優(yōu)秀率yij計(jì)算公式同公式(2),參訓(xùn)率cij的計(jì)算公式如下

(5)

設(shè)人員i在補(bǔ)差訓(xùn)練中共參與訓(xùn)練xi次,則人員i的訓(xùn)練強(qiáng)度qi計(jì)算公式為

qi=exi-xi

(6)

則補(bǔ)差訓(xùn)練計(jì)劃的各評(píng)估指標(biāo)計(jì)算公式為：

(7)

(8)

(9)

(10)

(11)

2.2.2 多指標(biāo)融合計(jì)算

熵權(quán)法借鑒了自然界熵的概念,引入熵權(quán)重作為各評(píng)估指標(biāo)的權(quán)重,使個(gè)體區(qū)分度大的評(píng)估指標(biāo)獲取更大權(quán)重[12]。設(shè)平均分、參訓(xùn)率、優(yōu)秀率、訓(xùn)練強(qiáng)度、同班率分別對(duì)應(yīng)T1至T5評(píng)估指標(biāo),共有n個(gè)補(bǔ)差訓(xùn)練計(jì)劃參與綜合評(píng)分計(jì)算,則構(gòu)建出評(píng)估指標(biāo)矩陣X,對(duì)應(yīng)的子項(xiàng)xij表示第i個(gè)計(jì)劃中的第j項(xiàng)評(píng)估指標(biāo)值。熵權(quán)重計(jì)算步驟如下:

1)歸一化處理矩陣X,生成歸一化矩陣P。

(12)

2)計(jì)算熵值ej。

(13)

式中,若pij=0,則ej=0。

3)計(jì)算熵權(quán)重tj。

(14)

理想點(diǎn)法構(gòu)思利用評(píng)估指標(biāo)建立多維空間,每個(gè)參評(píng)對(duì)象映射為多維空間中的向量,將最優(yōu)的評(píng)估指標(biāo)值匯總生成正理想點(diǎn)位,最差評(píng)估指標(biāo)值匯總生成負(fù)理想點(diǎn)位,通過計(jì)算每個(gè)參評(píng)對(duì)象和正負(fù)理想點(diǎn)位之間的距離,獲取綜合評(píng)分[13]。融合熵權(quán)重的熵權(quán)理想點(diǎn)法計(jì)算步驟如下:

1)生成正負(fù)理想點(diǎn)位A+和A-。設(shè)歸一化矩陣P值為pij,則最優(yōu)評(píng)估指標(biāo)值pj+和最差評(píng)估指標(biāo)值pj-計(jì)算公式為:

(15)

(16)

2)計(jì)算第i個(gè)補(bǔ)差訓(xùn)練計(jì)劃距離A+和A-的距離d+和d-?？紤]到各評(píng)估指標(biāo)區(qū)分度差異,將熵權(quán)重tj代入,熵權(quán)理想點(diǎn)法計(jì)算公式為:

(17)

(18)

3)計(jì)算各補(bǔ)差訓(xùn)練計(jì)劃的綜合評(píng)分Mi。計(jì)算公式為

(19)

2.3 粒子群算法

粒子群算法由Kennedy和Eberhart在1995年提出,借鑒生物界中鳥群的覓食行為,算法建立多維空間,向空間釋放多個(gè)隨機(jī)個(gè)體,將綜合評(píng)分結(jié)果看作食物,則參評(píng)個(gè)體會(huì)根據(jù)空間中各位置的綜合評(píng)分高低自發(fā)向食物豐沛區(qū)游走,并在多代游走后找到全局最優(yōu)位置[14]。具體算法如下:

Step1:建立D維空間,設(shè)補(bǔ)差訓(xùn)練計(jì)劃共參訓(xùn)m個(gè)課目,第j個(gè)課目參訓(xùn)人數(shù)為nj,則D的維度計(jì)算公式如下

(20)

Step2:設(shè)置初始種群。設(shè)種群中包含1 000個(gè)個(gè)體,個(gè)體內(nèi)部存儲(chǔ)當(dāng)前位置和歷史最優(yōu)位置及其對(duì)應(yīng)分值，其結(jié)構(gòu)體如表1所示。

表1 粒子群個(gè)體結(jié)構(gòu)表

Step3:計(jì)算每個(gè)個(gè)體下一步的游走位置。設(shè)個(gè)體當(dāng)前位置為Xi,Pi為個(gè)體第i次游走遍歷到的最優(yōu)位置,Qi為種群經(jīng)過i次游走的最優(yōu)位置,Vi為個(gè)體第i次游走的步長;r1和r2為[0,1]之間的隨機(jī)實(shí)數(shù)。則個(gè)體第i+1次游走的步長Vi+1計(jì)算公式為

Vi+1=0.5Vi+0.3r1(Pi-Xi)+0.3r2(Qi-Xi)

(21)

個(gè)體的第i+1次游走位置Xi+1計(jì)算公式為

Xi+1=Xi+Vi+1

(22)

Step4:調(diào)用熵權(quán)理想點(diǎn)法計(jì)算該位置的綜合評(píng)分。

Step5:使用冒泡法更新個(gè)體的歷史最優(yōu)評(píng)分位和種群的當(dāng)前最優(yōu)綜合評(píng)分位。

Step6:重復(fù)Step3-Step5。并判斷是否滿足退出條件:種群最優(yōu)評(píng)分的多代差值到達(dá)收斂閾值。滿足退出條件則退出算法,輸出種群最優(yōu)位置及其對(duì)應(yīng)綜合評(píng)分。其算法流程如圖2所示。

圖2 標(biāo)準(zhǔn)粒子群算法流程圖

2.4 量子粒子群算法

粒子群算法雖然在多代游走后能夠使最優(yōu)位置趨向于全局最優(yōu),但也易于陷入局部最優(yōu)陷阱,為解決上述問題,Sun等人提出量子粒子群算法,將量子遷移思想引入個(gè)體位置計(jì)算中,使個(gè)體具備全空間遷移能力,一定程度上解決了全局尋優(yōu)問題[15]。與標(biāo)準(zhǔn)算法相比,量子粒子群算法的步長Vi+1計(jì)算公式為

(23)

設(shè)種群內(nèi)個(gè)體數(shù)目為n,Pij表示種群內(nèi)第j個(gè)個(gè)體在第i次游走后的歷史最優(yōu)位。引入第i次游走的遷移系數(shù)Mi計(jì)算公式為

(24)

設(shè)u為[0,1]之間的隨機(jī)實(shí)數(shù)。位置Xi+1計(jì)算公式為

(25)

算法其余部分同標(biāo)準(zhǔn)粒子群算法。

2.5 遺傳算法

遺傳算法借鑒自然界物種優(yōu)勝劣汰的進(jìn)化機(jī)制,通過構(gòu)建生物種群,模擬出生物的繁殖、變異、適應(yīng)和淘汰進(jìn)程,通過多代進(jìn)化使后代個(gè)體具備更強(qiáng)的適應(yīng)度,取得更高的綜合評(píng)分[16]。具體算法如下:

Step1:設(shè)置初始種群。種群中包含隨機(jī)產(chǎn)生的1000個(gè)個(gè)體。

Step2:計(jì)算1 000個(gè)體的綜合評(píng)分。

Step3:個(gè)體淘汰。首先刪除壽命超過上限的個(gè)體,其次依據(jù)“高分個(gè)體淘汰概率小,低分個(gè)體淘汰概率大”的原則使用輪盤法優(yōu)選個(gè)體,最終優(yōu)選出100個(gè)個(gè)體。

Step4:種群繁殖變異。使用輪盤法挑選出高分個(gè)體作為父代個(gè)體,然后以千分之一的概率使其參訓(xùn)人員發(fā)生變異,產(chǎn)生與父代個(gè)體相似的子代個(gè)體,最終使種群規(guī)模達(dá)到1 000。

Step5:重復(fù)Step2-Step4。并判斷是否滿足退出條件:種群最優(yōu)個(gè)體綜合評(píng)分是否收斂。滿足退出條件則退出算法,輸出最優(yōu)個(gè)體及其對(duì)應(yīng)綜合評(píng)分。

通過上述算法分析可以發(fā)現(xiàn),粒子群算法和遺傳算法作為智能優(yōu)化算法具有較多相似點(diǎn),如建立初始種群、設(shè)置隨機(jī)變量、隨機(jī)變異游走、以局部最優(yōu)收斂至全局最優(yōu)等。區(qū)別主要在于:1)遺傳算法可以在最優(yōu)個(gè)體的基礎(chǔ)上不斷回溯變異,粒子群算法作為隨機(jī)游走算法無法回溯,這就造成了粒子群算法較遺傳算法更容易陷入局部最優(yōu)陷阱;2)遺傳算法的變異是隨機(jī)行為,粒子群算法的變異受個(gè)體最優(yōu)和全局最優(yōu)解的制約,使隨機(jī)行為可控,這就造成了遺傳算法收斂效率相比粒子群算法更低。

2.6 進(jìn)化粒子群算法

圖3 進(jìn)化粒子群算法流程圖

具體算法如下:

Step1-Step4:同量子粒子群算法。

Step6:補(bǔ)充新個(gè)體。使用輪盤法挑選出高分個(gè)體的歷史最高分值位置,在此位置產(chǎn)生子代個(gè)體,最終使種群規(guī)模達(dá)到1 000。

Step7:更新個(gè)體和種群的最優(yōu)評(píng)分位置。

Step8:重復(fù)Step3-Step7。并判斷是否滿足退出條件:種群最優(yōu)位置評(píng)分值是否收斂。滿足退出條件則退出算法,輸出種群最優(yōu)位置及其對(duì)應(yīng)綜合評(píng)分。

3 仿真實(shí)驗(yàn)

為了檢驗(yàn)遺傳算法、粒子群算法、量子粒子群算法、進(jìn)化粒子群算法等4種智能優(yōu)化算法在補(bǔ)差訓(xùn)練計(jì)劃智能優(yōu)化中的性能,本文依托工程實(shí)例項(xiàng)目設(shè)計(jì)開發(fā)“軍事訓(xùn)練分析系統(tǒng)”中的“補(bǔ)差訓(xùn)練模塊”,模塊整體界面如圖4所示。

圖4 補(bǔ)差訓(xùn)練智能優(yōu)化模塊整體界面

計(jì)算機(jī)配置:Intel酷睿雙核T7300 2.0 GHz中央處理器;3 G內(nèi)存;32位Win7操作系統(tǒng);vc6.0系統(tǒng)開發(fā)環(huán)境。

3.1 各智能優(yōu)化算法收斂性比較

實(shí)驗(yàn)設(shè)計(jì)使用統(tǒng)一的補(bǔ)差訓(xùn)練計(jì)劃評(píng)估指標(biāo)(平均分、參訓(xùn)率、訓(xùn)練強(qiáng)度、優(yōu)秀率、同班率)和綜合評(píng)分算法(熵權(quán)理想點(diǎn)法),演化相同代數(shù)(650代),各智能優(yōu)化算法的各代最優(yōu)個(gè)體綜合評(píng)分結(jié)果如圖5所示。

圖5 各智能優(yōu)化算法各代綜合評(píng)分結(jié)果

實(shí)驗(yàn)結(jié)果表明:在進(jìn)化相同代數(shù)時(shí),遺傳算法綜合評(píng)分效果最差,量子粒子群法和本文設(shè)計(jì)的進(jìn)化量子粒子群法效果最好,標(biāo)準(zhǔn)粒子群法效果居中;相比較而言,本文設(shè)計(jì)的進(jìn)化量子粒子群法能夠利用淘汰和繁殖時(shí)機(jī)達(dá)成個(gè)體分值的突變陡增,使群體綜合評(píng)分整體上升,該特性也存在于遺傳算法的統(tǒng)計(jì)圖中,標(biāo)準(zhǔn)粒子群法和量子粒子群法不具備此特性。

3.2 各智能優(yōu)化算法結(jié)果比較

分析各智能優(yōu)化算法達(dá)成綜合評(píng)分收斂的代數(shù)統(tǒng)計(jì)情況,對(duì)比分析如表2所示。

表2 各智能優(yōu)化算法收斂代數(shù)統(tǒng)計(jì)表

實(shí)驗(yàn)結(jié)果表明:相比較而言,進(jìn)化量子粒子群法在收斂代數(shù)和收斂分值上均要優(yōu)于主流智能優(yōu)化算法。

3.3 各智能優(yōu)化算法效率比較

在進(jìn)化相同代數(shù)時(shí),分別選取2-10個(gè)訓(xùn)練課目,分析各智能優(yōu)化算法的計(jì)算耗時(shí)如圖6所示。

實(shí)驗(yàn)結(jié)果表明:遺傳算法的計(jì)算耗時(shí)最短,進(jìn)化量子粒子群法的計(jì)算耗時(shí)最長,10課目時(shí)的耗時(shí)差異為14.75 s。相比于傳統(tǒng)的手工擬制補(bǔ)差訓(xùn)練計(jì)劃,各智能優(yōu)化算法的計(jì)算耗時(shí)都在可容忍范圍內(nèi)。

3.4 補(bǔ)差訓(xùn)練計(jì)劃結(jié)果分析

通過上述實(shí)驗(yàn)分析,本文設(shè)計(jì)的進(jìn)化量子粒子群法綜合性能較其他對(duì)比智能優(yōu)化算法優(yōu)化效果更顯著,將該算法代入補(bǔ)差訓(xùn)練計(jì)劃智能優(yōu)化模塊,得到補(bǔ)差訓(xùn)練計(jì)劃如表3所示。

表3 補(bǔ)差訓(xùn)練計(jì)劃示例

4 結(jié)束語

本文結(jié)合遺傳算法和粒子群算法的優(yōu)化原理,設(shè)計(jì)出兼具遺傳算法優(yōu)勢的進(jìn)化粒子群算法,并將其引入補(bǔ)差訓(xùn)練計(jì)劃工程應(yīng)用中,通過和同類智能優(yōu)化算法的綜合對(duì)比,驗(yàn)證了該算法的有效性,并實(shí)現(xiàn)了補(bǔ)差訓(xùn)練計(jì)劃的智能優(yōu)化。創(chuàng)新點(diǎn)有:1)根據(jù)補(bǔ)差訓(xùn)練計(jì)劃工程實(shí)際,設(shè)計(jì)了符合工程特點(diǎn)的熵權(quán)理想點(diǎn)法作為多指標(biāo)融合評(píng)分算法；2)設(shè)計(jì)出兼具遺傳算法優(yōu)勢的進(jìn)化粒子群算法,通過實(shí)驗(yàn)證明了該算法較標(biāo)準(zhǔn)粒子群算法和遺傳算法收斂效率更高,能有效避免個(gè)體在游走中陷入局部最優(yōu)陷阱；3)將算法引入工程項(xiàng)目實(shí)踐中,使用效果相比于人工擬制訓(xùn)練計(jì)劃提升明顯。進(jìn)化粒子群算法作為智能優(yōu)化算法,具有原理易懂、結(jié)構(gòu)簡單的特征,不僅用于補(bǔ)差訓(xùn)練計(jì)劃的智能優(yōu)化,具有廣泛的智能優(yōu)化應(yīng)用前景。