基于改進(jìn)二進(jìn)制蝙蝠算法的裝備資源保障規(guī)劃

朱 超，寇 浩，王 洋，李 陽，孟 杰，安 琪

（1.北方自動控制技術(shù)研究所，太原 030006；2.陸軍裝備部駐北京地區(qū)軍事代表局駐太原地區(qū)第二軍事代表室，太原 030006）

0 引言

信息化條件下的戰(zhàn)爭已經(jīng)演變?yōu)榧呒夹g(shù)、高協(xié)同、高機動的裝備資源為一體的聯(lián)合化作戰(zhàn)，因此，在新型作戰(zhàn)背景下裝備資源能否得到精確保障是取得戰(zhàn)爭勝利的關(guān)鍵。裝備資源精確協(xié)同保障本質(zhì)上是利用系統(tǒng)工程與運籌學(xué)的理論和方法，以戰(zhàn)場不同態(tài)勢下的限制情況為約束，對保障資源進(jìn)行精確編組和調(diào)度，通過充分利用最先進(jìn)技術(shù)，快速響應(yīng)保障需求，實時跟蹤保障進(jìn)程，為聯(lián)合作戰(zhàn)行動提供數(shù)量準(zhǔn)確和高效快速的裝備保障。在實際陸戰(zhàn)場環(huán)境中，保障任務(wù)具有不確定性，同時還存在任務(wù)時序邏輯約束以及裝備資源占用沖突等問題。因此，如何在保障任務(wù)執(zhí)行時序、資源需求、保障編組占用沖突和資源平臺能力更新等復(fù)雜約束條件下，把裝備資源精確分配到保障任務(wù)中是求解這類問題的關(guān)鍵也是技術(shù)難點［1］。此類問題已經(jīng)被證明是一個非確定性多項式（NP 難）問題，傳統(tǒng)的求解方法有最優(yōu)解的整數(shù)規(guī)劃、分支定界法、層次分析法和枚舉法等方法，但僅適用于求解小規(guī)模規(guī)劃問題，當(dāng)面對規(guī)模大、約束多、實時性要求高等復(fù)雜條件下的任務(wù)規(guī)劃問題時，利用現(xiàn)有信息平臺很難在短時間內(nèi)作出精確求解?；诖擞袑W(xué)者提出多優(yōu)先級動態(tài)列表規(guī)劃調(diào)度算法，通過任務(wù)優(yōu)先權(quán)系數(shù)以及選擇優(yōu)先權(quán)系數(shù)來規(guī)劃裝備保障流程，這種方法具有快速求解滿意解的優(yōu)點，但是無法保證以穩(wěn)定高概率求解全局最優(yōu)裝備資源分配方案；此外還有結(jié)合遺傳算法或粒子群算法等群智能算法求解這類調(diào)度規(guī)劃問題的方案，雖然取得一定的成果，但是在數(shù)學(xué)模型復(fù)雜度、約束條件數(shù)量上均與實際裝備資源保障需求有較大差距［2］。

蝙蝠算法（BA）是一種將遺傳算法（GA）、粒子群算法（PSO）以及和聲搜索算法（HS）有機結(jié)合的新型算法，已經(jīng)被證明具有更快的收斂速度與更好的全局尋優(yōu)能力，在被提出的短短幾年內(nèi)，就在不同領(lǐng)域內(nèi)被廣泛地使用與驗證，并取得了很好的應(yīng)用效果，同時對于離散子空間尋優(yōu)問題而言，通過對連續(xù)算子采用不同的邏輯函數(shù)離散化映射可以將BA改進(jìn)為二進(jìn)制蝙蝠算法（BBA）［3］。BBA 自被提出之后，由于具有良好的離散尋優(yōu)性能，已經(jīng)在特征選取、子集問題、工作流調(diào)度、背包問題等多個重要工程問題中得到應(yīng)用，但是在實際應(yīng)用中標(biāo)準(zhǔn)BBA 算法同樣存在高維時易陷入局部最優(yōu)、過早收斂，以及全局搜索和局部搜索不能很好平衡的問題［4］。

本文圍繞裝備資源與保障任務(wù)協(xié)同分配問題，首先以時效優(yōu)先為目標(biāo)函數(shù)建立數(shù)學(xué)模型，設(shè)計以動態(tài)列表調(diào)度（DLS）算法為主的求解框架，嵌套具有自適應(yīng)進(jìn)化變異操作的二進(jìn)制蝙蝠算法（AMBBA）為選定的保障任務(wù)分配裝備資源，通過在算法尋優(yōu)中引入自適應(yīng)學(xué)習(xí)因子以平衡全局搜索和局部搜索能力。案例仿真結(jié)果表明，本文所提方法可對大規(guī)模裝備資源協(xié)同分配保障問題進(jìn)行精確高效求解。

1 裝備精確協(xié)同保障規(guī)劃描述

1.1 基本概念

聯(lián)合作戰(zhàn)行動中，從目標(biāo)偵察到進(jìn)攻戰(zhàn)斗再到防御戰(zhàn)斗和體系支援，資源保障貫穿整個戰(zhàn)斗序列，因此，資源保障能否及時、準(zhǔn)確、高效，是提升我軍聯(lián)合作戰(zhàn)一體化保障能力的重要環(huán)節(jié)。本文通過提取抽象保障要素，歸納設(shè)計裝備資源保障規(guī)劃模型的描述方式以及求解框架，并根據(jù)實際需求對二進(jìn)制蝙蝠算法進(jìn)行改進(jìn)，嵌套自適應(yīng)進(jìn)化變異操作，結(jié)合實際仿真算例，設(shè)計一種具有通用性的裝備保障規(guī)劃方法。

裝備資源保障規(guī)劃模型的描述包括保障任務(wù)描述和保障資源描述兩大部分。通過分析保障任務(wù)的核心要素，其主要包括所有任務(wù)集的執(zhí)行時序、每一個保障任務(wù)所需的資源類型及數(shù)量、保障點的坐標(biāo)位置及任務(wù)的持續(xù)時間，其時序流程概念圖如圖1 所示。

圖1 保障任務(wù)時序流程

保障任務(wù)時序流程圖中保障任務(wù)的描述為：N項任務(wù)保障集為T={T1，T2，…，TN}，對于?Ti∈T，其屬性包括：任務(wù)的坐標(biāo)位置LTi=（XTi，YTi）；任務(wù)的開始時間STi；任務(wù)的持續(xù)時間CTi；任務(wù)對不同類型資源需求向量DTi={DTi1，DTi2，…，DTiL}，其中，DTil（1≤l≤L）為能夠執(zhí)行Ti所需的第l 項資源，若為0，則表示執(zhí)行Ti不需要此項資源，描述方式如下頁表1 所示。各任務(wù)間的時序約束關(guān)系為Cij，若Ti是Tj的前序任務(wù)，則Cij=0，否則Cij=1；Ti和Tj的直線距離為dij。

表1 保障任務(wù)描述

保障任務(wù)時序流程圖中保障資源具體包括的內(nèi)容由實際場景決定，例如彈藥、軍需、通信器材、維修裝備、醫(yī)用物資等，記包含M 個資源向量的保障資源集為R={R1，R2，…，RM}，對于?Rj∈R，其屬性包括：保障資源的初始坐標(biāo)位置LRj=（XRj，YRj）；保障資源的平均移動速度VRj；保障資源具備的資源能力向量CRj={CRj1，CRj2，…，CRjL}。保障資源和任務(wù)之間分配關(guān)系為Dij，若任務(wù)Ti分配給保障單元Rj執(zhí)行，則Dij=1，否則Dij=0，描述方式如表2 所示。當(dāng)有多項任務(wù)需要同一個保障單元執(zhí)行時，將按照任務(wù)優(yōu)先級排序處理。

表2 保障資源描述

1.2 任務(wù)優(yōu)先權(quán)系數(shù)

該模型求解過程存在兩個難點：第1 個是單任務(wù)最優(yōu)與總?cè)蝿?wù)最優(yōu)之間協(xié)調(diào)的問題，即如果保證每一個任務(wù)基于當(dāng)前可用調(diào)度資源集是最優(yōu)選擇時，則對于總?cè)蝿?wù)的執(zhí)行保障而言并不一定是全局最優(yōu)的方案；第2 個難點是對于選定的當(dāng)前執(zhí)行任務(wù)，如果為了實現(xiàn)該任務(wù)的全局最優(yōu)保障，在理論上是可以求解得到的，但是當(dāng)面對大規(guī)模保障資源問題時，算法尋優(yōu)勢必需要迭代許多次，會造成算力的占用甚至浪費，即使求解得出，也并不能保證所有任務(wù)執(zhí)行完畢后時間上的全局最優(yōu)?；谏鲜銮闆r，本文以總?cè)蝿?wù)完成時間為總目標(biāo)函數(shù)，對于單任務(wù)的保障尋優(yōu)過程而言，著重考慮對算法過程進(jìn)行優(yōu)化改進(jìn)，在迭代同等次數(shù)的基礎(chǔ)上提高結(jié)果的準(zhǔn)確性［5］。

對于指定的一組保障資源需要執(zhí)行多項任務(wù)時會產(chǎn)生編組爭用問題，導(dǎo)致任務(wù)的執(zhí)行時序違背保障任務(wù)順序依賴和執(zhí)行約束關(guān)系，因此，需要對生成的解進(jìn)行沖突消解。當(dāng)任務(wù)編組對保障資源產(chǎn)生爭用沖突時，按照任務(wù)優(yōu)先權(quán)系數(shù)進(jìn)行排序，依次消解沖突，首先滿足優(yōu)先級較高的任務(wù)。任務(wù)優(yōu)先權(quán)系數(shù)的影響因素主要包括任務(wù)持續(xù)時間、直接后續(xù)任務(wù)數(shù)量及其優(yōu)先權(quán)系數(shù)，其值越大，表示其任務(wù)優(yōu)先級越高，具體的計算公式如下：

其中，PTi為任務(wù)Ti的優(yōu)先權(quán)系數(shù)，OUT（i）為任務(wù)Ti的直接后續(xù)任務(wù)集，如果沒有直接后續(xù)任務(wù)集，則優(yōu)先權(quán)系數(shù)等于任務(wù)執(zhí)行時間。根據(jù)保障任務(wù)集概念關(guān)系圖和任務(wù)優(yōu)先權(quán)系數(shù)定義表達(dá)式，即可計算得到每一個任務(wù)的優(yōu)先權(quán)系數(shù)。

1.3 約束條件

本文假設(shè)某一任務(wù)能被保障但還需要具備處理這一任務(wù)的所有條件，這些條件包括：

1）這一任務(wù)的所有前導(dǎo)任務(wù)都已處理完畢；

2）由于協(xié)同任務(wù)之間互為必要條件，對于此情況統(tǒng)一處理成前后時序約束任務(wù)；

3）分配給這一任務(wù)的所有保障資源都已部署到達(dá)該任務(wù)的執(zhí)行地點；

4）所有的保障資源能力之和不小于任一保障任務(wù)所需的資源能力。

基于上述條件，可以提取歸納為資源與任務(wù)的分配約束、任務(wù)開始時間約束、任務(wù)的資源需求約束以及所有任務(wù)完成時間約束。分配約束包括保障任務(wù)按優(yōu)先權(quán)系數(shù)大小執(zhí)行，以及保障資源必須完全執(zhí)行完一個保障任務(wù)后才能執(zhí)行下一個任務(wù)；任務(wù)開始時間約束指的是，后序任務(wù)的開始執(zhí)行時間不小于前序任務(wù)的開始執(zhí)行時間與其所需保障時間之和，具體計算公式如下：

其中，xijm為資源m 在保障完Ti后是否被分配給Tj，若是則為1，否則為0，Y'為所有任務(wù)完成時間的上界（一般設(shè)為較大值）。

任務(wù)的資源需求約束指的是，執(zhí)行當(dāng)前任務(wù)的所有資源能力向量之和中的每一種類型的資源能力都不小于該任務(wù)對應(yīng)類型所需的資源能力數(shù)量，即

所有任務(wù)的完成時間約束，指的是總完成時間Y 不小于任意任務(wù)的完成時間，因此，該問題的總目標(biāo)函數(shù)即為：minY。

2 DLS-AMBBA 規(guī)劃算法

2.1 算法框架

針對前述中裝備資源保障規(guī)劃問題，采用DLS和AMBBA 結(jié)合進(jìn)行求解。通過DLS 算法從待定任務(wù)集中選擇當(dāng)前需要處理的任務(wù)，再通過AMBBA 從當(dāng)前可用資源集中選擇可供當(dāng)前選定任務(wù)執(zhí)行保障的最優(yōu)分配方案，具體的求解流程圖如圖2 所示。

圖2 DLS-AMBBA 算法流程圖

2.2 基于AMBBA 的資源分配

對于選定的保障任務(wù)而言，最優(yōu)的保障資源分配方案就是在任務(wù)得到保障的基礎(chǔ)上，能夠滿足執(zhí)行時間最短和占用保障編組最少兩個目標(biāo)，具體的尋優(yōu)求解步驟如下：

步驟1 對各項參數(shù)初始化設(shè)置。包括蝙蝠種群規(guī)模Sn，最大迭代次數(shù)Mmax，脈沖頻率最小值fmin和最大值fmax，脈沖響度A，脈沖發(fā)生率r，同時包括對當(dāng)前執(zhí)行任務(wù)的選定、當(dāng)前可用保障資源集的更新，以及對于每一個保障編組當(dāng)前被采用狀態(tài)的更新。

步驟2 蝙蝠位置的二進(jìn)制離散化操作。對于每只蝙蝠而言，其包含的每個元素的值為0 或1，代表的意義是在保障資源集中對應(yīng)的保障資源向量是否被采用，1 為被采用保障，0 為未被選擇，由此構(gòu)成的一組解即為被選取的一個或多個保障資源向量的集合。初始條件下蝙蝠位置的離散化方式為在（0-1）之間產(chǎn)生一個隨機數(shù)，若隨機數(shù)小于0.5，則該位置為0，相反該位置為1。在初始解產(chǎn)生之后蝙蝠位置的離散化方式均選擇V 型邏輯函數(shù)映射實現(xiàn)離散化操作［6］，具體的計算公式如下：

步驟3 初始解的篩選。對于此類大規(guī)模離散優(yōu)化求解問題而言，隨機生成的初始解中存在部分不可行解，即不滿足該保障過程的某些約束條件，如果不對其進(jìn)行篩選重構(gòu)，一方面會降低后續(xù)過程的尋優(yōu)效率；另一方面會影響計算精度及求解穩(wěn)定性，因此，初始解的合理構(gòu)建非常重要。

以下通過兩個指標(biāo)來保證初始解為可行解，一是將當(dāng)前初始解映射到可供選擇分配的保障資源集中，如果選擇的裝備資源無法滿足當(dāng)前所執(zhí)行的保障任務(wù)的需求，則該解為初始不可行解，重新回到步驟2 中重構(gòu)；另一個是判斷當(dāng)前初始解中是否選擇了已經(jīng)被標(biāo)記為采用狀態(tài)的保障資源，如果選擇了已經(jīng)被采用的保障資源，則該解由于資源爭用沖突同樣為初始不可行解，同樣回到步驟2 中重構(gòu)。

上述兩個篩選指標(biāo)，只要有一個不滿足就需要重新構(gòu)建該初始解，如此保證每一個初始解都為可行解。如果循環(huán)Q 次以后，仍然沒有完全產(chǎn)生可行初始解，說明可供選擇的資源向量已經(jīng)無法完成當(dāng)前任務(wù)，此時需要把所有標(biāo)記為使用狀態(tài)的資源釋放，同時更新時間序列與標(biāo)記狀態(tài)，重新進(jìn)行優(yōu)化分配。

步驟4 蝙蝠位置和速度更新。通過調(diào)整頻率產(chǎn)生新解（解即蝙蝠位置），并更新速度和位置，具體的計算公式如下：

式中，fi，fmin和fmax分別為蝙蝠i 當(dāng)前時刻的脈沖頻率及其最小值和最大值，β∈［0，1］；xgbestd為第d 維當(dāng)

其中，k1∈Z+，ωmin和ωmax分別是慣性權(quán)重最小值與最大值［7］，通過式（6）計算得到蝙蝠的位置后，再通過式（4）將其離散化操作。此時仍需對產(chǎn)生的新解進(jìn)行一次可行性判斷，如果滿足步驟3 中所述的兩個判別指標(biāo)，則新解為可行解，可繼續(xù)優(yōu)化迭代，否則需要重新更新一次蝙蝠位置和速度并進(jìn)行離散化操作。

3 仿真算例

以聯(lián)合作戰(zhàn)行動中保障任務(wù)為例，各保障任務(wù)時序約束如圖1 所示，保障任務(wù)屬性與保障資源屬性如表3 和表4 所示。

表3 保障任務(wù)屬性表

表4 保障資源屬性表

為了驗證所提AMBBA 算法的有效性，本文將其分別與基本BBA 和GA 算法進(jìn)行對比計算，仿真環(huán)境為i7-77003.60 GHz 的CPU，內(nèi)存為4 G，采用Matlab 軟件編程實現(xiàn)，算法參數(shù)設(shè)置如下：算法迭代次數(shù)為1 000 次，種群個數(shù)設(shè)置為30，頻率響度為0.25，脈沖發(fā)生率為0.1，最小脈沖頻率為0，最大脈沖頻率為2，慣性權(quán)重最小值為0.2，最大值為0.9，采用本文算法得到的最優(yōu)保障任務(wù)甘特圖與采用GA 算法計算得出的最優(yōu)保障任務(wù)甘特圖如圖3 和圖4 所示。

圖3 DLS-AMBBA 規(guī)劃甘特圖

圖4 DLS-GA 規(guī)劃甘特圖

為了體現(xiàn)本文所提算法的有效性，通過對比3種不同算法計算10 次的結(jié)果，綜合分析比較計算出的最優(yōu)解、最差解、平均值、標(biāo)準(zhǔn)差和平均求解時間來體現(xiàn)算法性能，具體數(shù)據(jù)對比如表5 所示。

表5 3 種算法性能比較表

通過分析比較表中的數(shù)據(jù)，可以發(fā)現(xiàn)AMBBA算法在尋找最優(yōu)解的能力上優(yōu)于其他兩個算法，而且計算時間極大縮減，說明本文所提方法具有較強的全局尋優(yōu)和收斂性能，同時能夠極大地提高求解速度，其中，AMBBA 算法在求解過程中的收斂迭代圖如圖5 所示。

圖5 AMBBA 收斂迭代圖

4 結(jié)論

本文針對聯(lián)合作戰(zhàn)環(huán)境下的裝備資源精確保障協(xié)同規(guī)劃問題，考慮以所有保障任務(wù)完成時間最短為適應(yīng)度函數(shù)，提出了DLS-AMBBA 規(guī)劃方法，通過DLS 選擇當(dāng)前需要保障的任務(wù)，再采用AMB BA 為選定任務(wù)選擇保障資源。聯(lián)合作戰(zhàn)保障行動案例仿真結(jié)果表明，所提方法可對大規(guī)模裝備資源協(xié)同分配保障問題進(jìn)行精確高效求解。