劉 昊,董寧宇,邢 巖

(1.國(guó)防大學(xué)聯(lián)合作戰(zhàn)學(xué)院,河北 石家莊 050000；2.軍委機(jī)關(guān)事務(wù)管理總局,北京 100000; 3.沈陽(yáng)航空航天大學(xué)電子信息工程學(xué)院，遼寧 沈陽(yáng) 111000)

在軍隊(duì)日常訓(xùn)練階段劃分中,入伍訓(xùn)練和專(zhuān)業(yè)訓(xùn)練階段之間通常由補(bǔ)差訓(xùn)練牽引銜接,為提升軍隊(duì)整體作戰(zhàn)能力,針對(duì)性復(fù)訓(xùn)和補(bǔ)訓(xùn)成為彌補(bǔ)戰(zhàn)斗力生成短板的有效手段,而補(bǔ)差訓(xùn)練計(jì)劃的生成和優(yōu)化就是制約軍隊(duì)?wèi)?zhàn)斗力生成的樞紐和瓶頸。補(bǔ)差訓(xùn)練計(jì)劃擬制的難點(diǎn)在于對(duì)參訓(xùn)人員的科學(xué)合理分配,以達(dá)成訓(xùn)練場(chǎng)地、訓(xùn)練器材資源、組訓(xùn)者的綜合利用率最優(yōu)化,以確保在單位時(shí)間內(nèi)最大限度提升單科目整體訓(xùn)練水平。補(bǔ)差訓(xùn)練計(jì)劃的擬制和優(yōu)化問(wèn)題對(duì)算法的實(shí)現(xiàn)要求較高,傳統(tǒng)基于規(guī)則的擬制方法存在生成計(jì)劃占用資源較多、受訓(xùn)和指揮人員匹配難度大、補(bǔ)差科目選擇不合理等諸多問(wèn)題,如何選擇合適的組訓(xùn)科目、如何匹配組訓(xùn)指揮員和受訓(xùn)人員、如何最優(yōu)化訓(xùn)練資源等系列優(yōu)化問(wèn)題均可歸結(jié)為經(jīng)典的課表優(yōu)化問(wèn)題,而課表優(yōu)化問(wèn)題是典型的NP完全問(wèn)題[1],很難在給定時(shí)限內(nèi)找到問(wèn)題的全局最優(yōu)解,因此，專(zhuān)家學(xué)者傾向于使用興起于20世紀(jì)90年代的各種智能優(yōu)化算法解決此類(lèi)問(wèn)題,為軍事訓(xùn)練的補(bǔ)差訓(xùn)練計(jì)劃擬制提供算法支撐。

補(bǔ)差訓(xùn)練計(jì)劃中的仿真類(lèi)智能優(yōu)化算法在特定范圍內(nèi)的使用效果參差不齊,有必要分析各類(lèi)智能優(yōu)化算法的優(yōu)缺點(diǎn)。當(dāng)前的智能優(yōu)化算法主要有模擬物理規(guī)律的模擬退火算法[2]、細(xì)胞膜優(yōu)化算法[3]、量子進(jìn)化算法[4]、禁忌搜索算法[5]等和模擬生物群體行為規(guī)則的螢火蟲(chóng)算法[6]、蛙跳算法[7]魚(yú)群算法[8]、蟻群算法[9]、蜂群算法[10]、布谷鳥(niǎo)算法[11]、粒子群算法[12]、細(xì)菌覓食算法[13]等，以及模擬物種適應(yīng)性特征行為的遺傳算法[14]、貪心算法[15]等。各種智能優(yōu)化算法從各自仿生思維視角切入NP完全問(wèn)題,共同點(diǎn)是利用偽隨機(jī)數(shù)創(chuàng)造具有部分隨機(jī)特征的智能體,通過(guò)對(duì)綜合評(píng)分的比較控制個(gè)體的游走或演化方向,通過(guò)量化累加形成優(yōu)化質(zhì)變,以局部最優(yōu)解趨近全局最優(yōu)解。然而，上述算法也存在易陷入局部最優(yōu)陷阱和收斂代數(shù)不可控的問(wèn)題,基于此，國(guó)內(nèi)外學(xué)者給出了諸多改進(jìn)型智能優(yōu)化算法,嘗試解決上述問(wèn)題。本文以蛙跳算法為參考標(biāo)準(zhǔn),借鑒了遺傳算法中的適者生存思想,在算法中設(shè)計(jì)“超級(jí)個(gè)體剔除”機(jī)制和“自然選擇”機(jī)制,以此為基礎(chǔ)設(shè)計(jì)競(jìng)爭(zhēng)蛙跳算法,并引入補(bǔ)差訓(xùn)練計(jì)劃優(yōu)化實(shí)踐項(xiàng)目中,取得了較好的優(yōu)化效果。

1 問(wèn)題描述

補(bǔ)差訓(xùn)練計(jì)劃智能優(yōu)化問(wèn)題可描述為:如何在給定的訓(xùn)練科目、組訓(xùn)者和訓(xùn)練時(shí)間段限制條件下,為每個(gè)訓(xùn)練科目分配參訓(xùn)人員,以實(shí)現(xiàn)同等訓(xùn)練科目下對(duì)最薄弱人員的最佳針對(duì)性訓(xùn)練。為了滿足計(jì)劃的可操作性,還應(yīng)設(shè)計(jì)硬約束條件:一是同一科目?jī)?nèi)不能有重復(fù)人員;二是訓(xùn)練時(shí)間段有重疊的科目?jī)?nèi)不能有重復(fù)人員;三是訓(xùn)練時(shí)間段有重疊的科目?jī)?nèi)不能有重復(fù)組訓(xùn)者。為了描述參訓(xùn)人員的各方面評(píng)估水平,定義評(píng)估指標(biāo)如下:

1)平均分指標(biāo):反映補(bǔ)差訓(xùn)練計(jì)劃中的參訓(xùn)人員在此前1個(gè)月內(nèi)的該科目平均成績(jī)水平,指標(biāo)項(xiàng)分值越低，說(shuō)明參與訓(xùn)練人員對(duì)應(yīng)的訓(xùn)練科目越薄弱。

2)參訓(xùn)率指標(biāo):反映補(bǔ)差訓(xùn)練計(jì)劃中的參訓(xùn)人員在此前1個(gè)月內(nèi)的該科目參訓(xùn)次數(shù)占比水平,指標(biāo)項(xiàng)分值越低，說(shuō)明參與訓(xùn)練的人員對(duì)應(yīng)訓(xùn)練科目參訓(xùn)次數(shù)越少。

3)優(yōu)秀率指標(biāo):反映補(bǔ)差訓(xùn)練計(jì)劃中的參訓(xùn)人員在此前1個(gè)月內(nèi)的該科目考核優(yōu)秀數(shù)占比水平,指標(biāo)項(xiàng)分值越低，說(shuō)明參與訓(xùn)練的人員對(duì)應(yīng)訓(xùn)練科目?jī)?yōu)秀成績(jī)次數(shù)越少。

4)同班率指標(biāo):反映補(bǔ)差訓(xùn)練計(jì)劃中的參訓(xùn)人員來(lái)自同一單位所占比例水平,指標(biāo)項(xiàng)分值越高，說(shuō)明參與訓(xùn)練的人員來(lái)自同一單位的概率越高,人員分布越規(guī)整,訓(xùn)練組織難度越小。

5)疲勞度指標(biāo):反映補(bǔ)差訓(xùn)練計(jì)劃中的參訓(xùn)人員參加訓(xùn)練結(jié)束后的疲勞程度,指標(biāo)項(xiàng)分值越低，說(shuō)明參與訓(xùn)練的人員執(zhí)行補(bǔ)差訓(xùn)練后的參訓(xùn)次數(shù)越少,人員分配越合理。

基于上述定義,設(shè)組訓(xùn)者限定的訓(xùn)練科目集合為K,訓(xùn)練時(shí)間段集合為T(mén),每組補(bǔ)差訓(xùn)練計(jì)劃的參訓(xùn)人員分配集合為R;其中，第i個(gè)補(bǔ)差訓(xùn)練計(jì)劃在向量空間位置為ri,訓(xùn)練科目為ki,訓(xùn)練時(shí)間段為ti;pi表示該計(jì)劃的平均分指標(biāo),ci表示該計(jì)劃參訓(xùn)率指標(biāo),yi表示優(yōu)秀率指標(biāo),bi表示同班率指標(biāo),di表示疲勞度指標(biāo)。則第i個(gè)補(bǔ)差訓(xùn)練計(jì)劃的綜合評(píng)分fi數(shù)學(xué)模型為

(1)

式中,ki∈K,ti∈T,ri∈R,F為綜合評(píng)分集合,fi∈F。

2 算法構(gòu)建

智能優(yōu)化算法的算法模塊具備通用性,主要由參數(shù)錄入、向量空間建立、綜合評(píng)分和智能優(yōu)化等部分組成,各部分之間緊密結(jié)合,用以實(shí)現(xiàn)具體工程實(shí)踐問(wèn)題的優(yōu)化解決。參數(shù)錄入模塊由組訓(xùn)者在補(bǔ)差訓(xùn)練前手工確定訓(xùn)練科目、組訓(xùn)者和訓(xùn)練時(shí)間段等環(huán)境限制變量;向量空間建立部分在參訓(xùn)人員和訓(xùn)練科目基礎(chǔ)上建立能夠區(qū)分補(bǔ)差訓(xùn)練計(jì)劃的空間向量,記為二維數(shù)組V(K,R);綜合評(píng)分部分實(shí)現(xiàn)對(duì)空間向量中的對(duì)應(yīng)位置vi(ki,ri)綜合評(píng)分計(jì)算,以評(píng)估該位置在空間中的重量;智能優(yōu)化模塊使用相關(guān)仿真類(lèi)算法實(shí)現(xiàn)空間位置的特征隨機(jī)游走,通過(guò)多方向試探找到特征在空間中的最佳點(diǎn)位。算法流程如圖1。

圖1 智能優(yōu)化算法通用流程圖

2.1 標(biāo)準(zhǔn)蛙跳算法

標(biāo)準(zhǔn)蛙跳算法模擬自然界蛙群的生活規(guī)律,蛙群被分割在各自獨(dú)立的小池塘中,各池塘內(nèi)的青蛙個(gè)體共享塘內(nèi)資源,最差評(píng)分個(gè)體可通過(guò)蛙跳轉(zhuǎn)移至周邊高分位置,如蛙跳范圍內(nèi)無(wú)法找到高分位置,則判定青蛙死亡,引入新的青蛙個(gè)體;并模擬蛙群繁殖季節(jié)的聚集交配行為,定期將蛙群打亂重組,以防陷入局部最優(yōu)。標(biāo)準(zhǔn)蛙跳算法流程圖如圖2所示。

圖2 標(biāo)準(zhǔn)蛙跳算法流程圖

(2)

(3)

2.2 競(jìng)爭(zhēng)蛙跳算法

通過(guò)對(duì)標(biāo)準(zhǔn)蛙跳算法分析可知,其核心是通過(guò)蛙跳操作使低分個(gè)體向周邊空間的高分位置跳躍,并通過(guò)定期拆分合并種群操作防止算法陷入局部最優(yōu),通過(guò)多代推演使最優(yōu)個(gè)體綜合評(píng)分逼近全局最優(yōu)位置。但算法有兩個(gè)智能優(yōu)化算法的通用缺陷。一是易陷入局部最優(yōu)陷阱。由于算法解決的問(wèn)題屬于復(fù)雜非線性不連貫問(wèn)題,導(dǎo)致空間中的點(diǎn)位分布不連續(xù),對(duì)于偶然出現(xiàn)的局部最優(yōu)點(diǎn)位,算法會(huì)促使周邊個(gè)體向該位置跳躍,進(jìn)而陷入局部最優(yōu)陷阱。二是迭代效率低問(wèn)題。由于組內(nèi)的蛙跳操作只針對(duì)最低分個(gè)體Xw執(zhí)行,若Xw已經(jīng)陷入低分區(qū)域而未達(dá)到刪除程度,算法會(huì)對(duì)Xw頻繁執(zhí)行蛙跳操作,造成系統(tǒng)資源的浪費(fèi)?；诖?本文設(shè)計(jì)了競(jìng)爭(zhēng)蛙跳算法,其思想是將遺傳算法中的超級(jí)個(gè)體剔除機(jī)制和自然選擇機(jī)制引入標(biāo)準(zhǔn)蛙跳算法,為種群中的個(gè)體賦予自然壽命和淘汰系數(shù),通過(guò)自然壽命實(shí)現(xiàn)超級(jí)個(gè)體剔除,以防超級(jí)個(gè)體破壞算法的全局尋優(yōu)環(huán)境;通過(guò)合并種群后的淘汰系數(shù)判定,剔除對(duì)全局尋優(yōu)毫無(wú)意義的冗余個(gè)體。如圖3所示。壽命項(xiàng)存儲(chǔ)青蛙經(jīng)歷過(guò)合并種群的次數(shù);淘汰系數(shù)以個(gè)體在生命期內(nèi)蛙跳操作次數(shù)為上限;個(gè)體位置的空間向量用二維整數(shù)數(shù)組存儲(chǔ)。

超級(jí)個(gè)體:個(gè)體的分值處于局部最優(yōu)位置,且多代跳躍后依舊沒(méi)有找到更好的位置,對(duì)周邊的青蛙個(gè)體產(chǎn)生吸附效應(yīng)。

冗余個(gè)體:個(gè)體所在的位置周邊分值相對(duì)較低,對(duì)于算法的全局尋優(yōu)無(wú)任何影響,其存在只會(huì)降低計(jì)算效率。

圖3 競(jìng)爭(zhēng)蛙跳算法流程圖

具體算法如下:

Step1:設(shè)置初始種群。按照隨機(jī)算法產(chǎn)生初始個(gè)體,并控制變異概率產(chǎn)生數(shù)量規(guī)模為n的初始種群,其中每個(gè)個(gè)體均可對(duì)應(yīng)空間向量的具體解。

Step2:尋找最優(yōu)個(gè)體Xq。通過(guò)綜合評(píng)分算法計(jì)算所有個(gè)體在空間中的綜合評(píng)分結(jié)果,通過(guò)比較排序定位最優(yōu)個(gè)體。

Step3:通過(guò)拆分操作將種群拆分為m個(gè)子群。具體操作為:首先，將所有個(gè)體按綜合評(píng)分排序,然后按評(píng)分由高至低依次放入m個(gè)分組中,保證各組綜合評(píng)分之和相差不大。

Step4:定位第j組中的最低評(píng)分個(gè)體Xw和最高評(píng)分個(gè)體Xb,Xb壽命+1。

Step6:重復(fù)步驟4、5,直至j=m。

Step7:拆散各組合并為種群,更新綜合評(píng)分,標(biāo)記最高評(píng)分個(gè)體Xq,并輸出最高分值。

Step8:計(jì)算所有個(gè)體的淘汰系數(shù)。

Step9:刪除淘汰系數(shù)超過(guò)閾值的個(gè)體。

Step10:隨機(jī)產(chǎn)生新個(gè)體補(bǔ)充種群,使種群數(shù)量n維持不變。

Step11:重復(fù)步驟2～10,引入結(jié)束條件判定:若最優(yōu)個(gè)體Xq綜合評(píng)分在10代內(nèi)無(wú)提升,則退出。

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

綜合評(píng)分算法是智能優(yōu)化算法和補(bǔ)差訓(xùn)練計(jì)劃優(yōu)化工程實(shí)際結(jié)合的建模算法,由于補(bǔ)差訓(xùn)練計(jì)劃分值不連續(xù)、參訓(xùn)人員來(lái)源不同等特點(diǎn),本文引入熵權(quán)理想點(diǎn)法作為多指標(biāo)綜合評(píng)分算法。

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

按照問(wèn)題描述階段的定義,評(píng)估指標(biāo)由平均分指標(biāo)P、參訓(xùn)率指標(biāo)C、優(yōu)秀率指標(biāo)Y、同班率指標(biāo)B、疲勞度指標(biāo)D組成。設(shè)訓(xùn)練計(jì)劃數(shù)量為n,其中，第i個(gè)訓(xùn)練計(jì)劃中共安排了z個(gè)訓(xùn)練科目,第e個(gè)考核科目中,受訓(xùn)人數(shù)為ne;其中，第g個(gè)人在對(duì)應(yīng)考核科目中的平均分為fge,共組織過(guò)hge次科目考核。則第g個(gè)人在科目e中的優(yōu)秀率yge計(jì)算公式為

(4)

設(shè)參訓(xùn)率為cge,相應(yīng)計(jì)算公式為

(5)

設(shè)不考慮訓(xùn)練科目,該人的訓(xùn)練疲勞度指標(biāo)qg對(duì)應(yīng)計(jì)算公式為

(6)

通過(guò)公式可知,疲勞度指標(biāo)公式為指數(shù)增長(zhǎng)指標(biāo),若hge的數(shù)量增大,則qg對(duì)應(yīng)增幅呈指數(shù)級(jí)增長(zhǎng),因此，在實(shí)際使用中每個(gè)人的訓(xùn)練次數(shù)不能過(guò)高,否則算法無(wú)法承受。該補(bǔ)差訓(xùn)練計(jì)劃的平均分評(píng)估指標(biāo)P計(jì)算公式為

(7)

同班率評(píng)估指標(biāo)B計(jì)算公式為

(8)

優(yōu)秀率評(píng)估指標(biāo)Y計(jì)算公式為

(9)

疲勞度評(píng)估指標(biāo)D計(jì)算公式為

(10)

參訓(xùn)率評(píng)估指標(biāo)C計(jì)算公式為

(11)

2.3.2 多指標(biāo)評(píng)分算法

熵權(quán)重[16]是熱力學(xué)概念,若空間中的微?；靵y程度越大,則熵值越大,對(duì)應(yīng)于指標(biāo)評(píng)估中可理解為:樣本評(píng)估指標(biāo)間的偏差值越大,則熵權(quán)重越大,由此可將熵權(quán)重看作衡量評(píng)估指標(biāo)包含信息量的參考標(biāo)準(zhǔn)。理想點(diǎn)法[17]的計(jì)算原理為:將參評(píng)樣本的評(píng)估指標(biāo)看作空間特征向量,則可將樣本對(duì)應(yīng)于空間中的特定點(diǎn)位,取所有評(píng)估指標(biāo)的最優(yōu)值產(chǎn)生正理想點(diǎn)A+,取最差值產(chǎn)生負(fù)理想點(diǎn)A-,各樣本計(jì)算與A+和A-之間的空間距離d+和d-,由此求出樣本i在多維空間中的評(píng)分值fi。設(shè)n個(gè)補(bǔ)差訓(xùn)練計(jì)劃參與評(píng)分,建立矩陣Xn5(1≤i≤n),評(píng)估指標(biāo)數(shù)為5(P、B、Y、D、C)。具體算法為:

Step1:矩陣歸一化。由于各評(píng)估指標(biāo)的分值大小差異較大,因此，通過(guò)歸一化將各評(píng)估指標(biāo)簡(jiǎn)化為小于1的分布概率值,生成歸一化矩陣U,其中，元素uij計(jì)算公式為

(12)

Step2:計(jì)算第j個(gè)評(píng)估指標(biāo)的熵值qj。

(13)

特殊情況,若uij=0,則規(guī)定qj=0。

Step3:計(jì)算第j項(xiàng)評(píng)估指標(biāo)的熵權(quán)重zj。

(14)

Step4:計(jì)算理想點(diǎn)空間向量。

(15)

(16)

Step5:計(jì)算理想點(diǎn)空間距離。

(17)

(18)

Step6:計(jì)算綜合評(píng)分。

(19)

3 仿真分析

仿真實(shí)驗(yàn)依托工程項(xiàng)目“軍事訓(xùn)練成績(jī)分析系統(tǒng)”中的相關(guān)訓(xùn)練模塊檢測(cè)競(jìng)爭(zhēng)蛙跳算法應(yīng)用于補(bǔ)差訓(xùn)練計(jì)劃優(yōu)化的有效性,通過(guò)將其融入補(bǔ)差訓(xùn)練模塊,達(dá)成工程實(shí)踐應(yīng)用目的,并同標(biāo)準(zhǔn)智能優(yōu)化算法比較,檢查分析算法的優(yōu)缺點(diǎn)。數(shù)據(jù)來(lái)源為北部戰(zhàn)區(qū)某部隊(duì)新兵營(yíng)訓(xùn)練數(shù)據(jù),選取新兵訓(xùn)練3個(gè)月11個(gè)組訓(xùn)科目的登記成績(jī)錄入系統(tǒng)形成初始訓(xùn)練數(shù)據(jù);智能優(yōu)化硬件性能為:Intel酷睿2.4 GHz處理器,4 G運(yùn)行內(nèi)存,Win7 32位操作系統(tǒng),VC6.0編譯環(huán)境;為了提升訓(xùn)練計(jì)劃優(yōu)化體驗(yàn)效果,設(shè)置進(jìn)化代數(shù)上限為300代,淘汰系數(shù)為5,種群規(guī)模數(shù)為1000個(gè),個(gè)體壽命上限為3代。系統(tǒng)模塊的整體界面如圖4所示。

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

3.1 算法收斂性分析

本文以熵權(quán)理想點(diǎn)法為多指標(biāo)綜合評(píng)分算法，設(shè)定退出條件為:最優(yōu)個(gè)體綜合評(píng)分在20代內(nèi)無(wú)提升，以標(biāo)準(zhǔn)蛙跳算法為參照智能優(yōu)化算法,對(duì)比分析兩種算法收斂情況如圖5所示。

圖5 算法收斂情況分析

通過(guò)對(duì)比兩種算法的各代最優(yōu)個(gè)體分值統(tǒng)計(jì)評(píng)分情況,檢查算法的收斂性,通過(guò)實(shí)驗(yàn)可知,兩種算法均能在多代后實(shí)現(xiàn)緩慢收斂,但競(jìng)爭(zhēng)蛙跳算法的收斂代數(shù)明顯小于標(biāo)準(zhǔn)算法,并且收斂分值相對(duì)更高,且由于引入超級(jí)個(gè)體剔除機(jī)制,競(jìng)爭(zhēng)蛙跳算法可自主跳出局部最優(yōu)陷阱,向周邊的位置主動(dòng)尋優(yōu),全局尋優(yōu)能力較標(biāo)準(zhǔn)蛙跳算法明顯增強(qiáng)。

3.2 最優(yōu)個(gè)體評(píng)估指標(biāo)比較

為了判斷兩種智能優(yōu)化算法形成最優(yōu)個(gè)體的內(nèi)部結(jié)構(gòu)差異,取各自形成的最優(yōu)個(gè)體，分析其各項(xiàng)評(píng)估指標(biāo)的性能,比較結(jié)果如表1所示。

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

實(shí)驗(yàn)結(jié)果表明:評(píng)估分值分別優(yōu)化了2.71%、13.16%、6.01%、13.79%、0%。

3.3 完成收斂代數(shù)及耗時(shí)比較

兩種智能優(yōu)化算法完成收斂的代數(shù)及其耗時(shí)統(tǒng)計(jì)如表2所示。

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

實(shí)驗(yàn)結(jié)果表明:競(jìng)爭(zhēng)蛙跳算法的收斂代數(shù)更少,收斂總耗時(shí)和也比標(biāo)準(zhǔn)蛙跳算法更低,而且，在單代耗時(shí)上，競(jìng)爭(zhēng)蛙跳算法并沒(méi)有比標(biāo)準(zhǔn)蛙跳算法耗時(shí)更多,因此,競(jìng)爭(zhēng)蛙跳算法兼具了收斂高效和時(shí)間高效雙重特性,相比標(biāo)準(zhǔn)蛙跳算法具備更明顯的優(yōu)勢(shì)。

4 結(jié)束語(yǔ)

本文借鑒了遺傳算法的算法特征,將其融入蛙跳算法中,在算法設(shè)計(jì)中,自主設(shè)計(jì)了融入“自然選擇”機(jī)制和“超級(jí)個(gè)體剔除”機(jī)制的競(jìng)爭(zhēng)蛙跳算法,并在仿真實(shí)驗(yàn)中驗(yàn)證了其有效性。仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性和工程實(shí)用性,解答了預(yù)設(shè)的問(wèn)題描述。在工程實(shí)際項(xiàng)目中,引入了智能優(yōu)化算法并實(shí)現(xiàn)了人機(jī)結(jié)合條件下的智能算法輔助應(yīng)用,提升了組訓(xùn)者作業(yè)效率,降低了工作難度。