裝備保障任務(wù)分配建模與DLS-BCIWBA算法求解

王堅浩, 張 亮, 史 超, 車 飛, 張鵬濤

(空軍工程大學(xué)裝備管理與無人機工程學(xué)院, 陜西 西安 710051)

0 引 言

裝備精確保障的實質(zhì)是指運用系統(tǒng)工程的理論和方法,通過精細、精確籌劃和運用裝備保障資源、保障力量,使其在準(zhǔn)確的時間、地點完成裝備保障任務(wù)。裝備精確保障要求對各類裝備設(shè)施、器材、備件等資源和專業(yè)人員進行整合和編組,以保障單元的形式分配給具體的保障任務(wù),屬于一類典型的任務(wù)分配問題[1]。求解此類任務(wù)分配問題,整數(shù)規(guī)劃、分支定界法和枚舉法等精確求解方法無法滿足實時性要求;而基于動態(tài)列表規(guī)劃的啟發(fā)式方法[2-4]求解效率較高,但都是采用基于貪心策略的局部搜索策略,因此得到的任務(wù)分配方案未必是最優(yōu)方案;文獻[5-6]結(jié)合啟發(fā)式智能優(yōu)化算法提出了混合任務(wù)分配方法,首先通過動態(tài)列表規(guī)劃 (dynamic list scheduling,DLS)選擇需要執(zhí)行的任務(wù),其次針對選定任務(wù)分配平臺(編組)問題的實質(zhì)為多維0/1背包問題的特點,采用全局搜索遺傳算法(genetic algorithm,GA)和量子遺產(chǎn)算法(quantum genetic algorithm,QGA)相結(jié)合的混合啟發(fā)式智能優(yōu)化算法,但并未考慮任務(wù)執(zhí)行質(zhì)量約束,然而在實際任務(wù)執(zhí)行過程中,如果任務(wù)執(zhí)行質(zhì)量過低,則任務(wù)執(zhí)行效果將遠低于期望效果;文獻[7]針對裝備保障任務(wù)分配問題,提出了基于優(yōu)先排序和離散粒子群優(yōu)化(particle swarm optimization,PSO)的混合任務(wù)分配方法。近年來,蝙蝠算法(bat algorithm,BA)[8]也應(yīng)用于此類任務(wù)分配問題,且相比于GA和PSO具有更快的收斂速度和更好的全局尋優(yōu)能力[9-10],但也存在算法后期收斂速度較慢、收斂精度不高、易陷入局部最優(yōu)等問題。

本文首先建立了裝備精確保障協(xié)同任務(wù)分配問題的數(shù)學(xué)模型,設(shè)計了以DLS算法為主的求解框架,嵌套具有混沌搜索策略和入侵雜草算子的二進制混沌入侵雜草蝙蝠算法(binary chaotic invasive weed bat algorithm,BCIWBA)為選定任務(wù)分配保障單元。首先利用BA的全局尋優(yōu)能力和迭代初期快速收斂性進行全局搜索;然后選取部分最優(yōu)個體融合入侵雜草生長繁殖、空間擴散和競爭生存機制進行局部搜索,并通過學(xué)習(xí)因子和慣性權(quán)重的自適應(yīng)協(xié)同更新以平衡探索和開發(fā)能力,結(jié)合脈沖頻率、響度、發(fā)生率變化區(qū)間的混沌搜索避免早熟收斂;最后通過案例仿真證明本文所提任務(wù)分配方法的有效性。

1 問題描述

1.1 基本概念

圖1 任務(wù)間的時序關(guān)系Fig.1 Sequential relationship of tasks

保障單元:擁有各類裝備設(shè)施、器材、備件等保障資源和專業(yè)人員的保障力量的編組,是保障任務(wù)的直接執(zhí)行者。記包含M個單元的保障單元集為U={U1,U2,…,UM},對于?Uj∈U,其屬性包括:保障單元的初始地理坐標(biāo)位置LUj=(XUj,YUj);保障單元平均移動速度VUj;保障單元具備的初始保障能力向量CUj={CUj1,CUj2,…,CUjL},CUjl為保障單元Uj第l項保障能力值,若CUjl=0,則表示保障單元Uj不具備第l項保障能力。

1.2 保障單元能力損耗及更新模型

保障過程中,保障單元執(zhí)行任務(wù)會造成其保障能力的損耗,因此,在保障單元執(zhí)行完某一任務(wù)后,應(yīng)對其保障能力進行如下更新:

,l∈[1,L]

(1)

(2)

則更新后的保障單元能力值為

(3)

1.3 協(xié)同任務(wù)分配目標(biāo)函數(shù)

當(dāng)保障單元執(zhí)行完成任務(wù)分配方案,其任務(wù)執(zhí)行時間即為

(4)

裝備精確保障協(xié)同任務(wù)分配以最小化任務(wù)執(zhí)行時間為目標(biāo),則目標(biāo)函數(shù)為

(5)

1.4 協(xié)同任務(wù)分配約束分析

協(xié)同任務(wù)分配問題的約束條件包括:①任務(wù)-保障單元分配約束;②任務(wù)時序邏輯約束;③任務(wù)執(zhí)行質(zhì)量約束。

(1) 任務(wù)-保障單元分配約束

每一項任務(wù)成功執(zhí)行至少需要分配一個保障單元,即滿足

(6)

(2) 任務(wù)時序邏輯約束

/VUj

(7)

若保障單元Uj在執(zhí)行Ti之前執(zhí)行的最后一項任務(wù)為Tj,則其到達任務(wù)Ti所在位置的時間為

/VUi+ETj

(8)

任務(wù)Ti的開始時間STi不小于先導(dǎo)任務(wù)Tk結(jié)束時間ETk和分配給其的所有保障單元的到達時間TITij之間的最大值,因此有

(9)

(3) 任務(wù)執(zhí)行質(zhì)量約束

保障單元執(zhí)行任務(wù)Ti的質(zhì)量定義為

(10)

式中,‖RTi‖為任務(wù)Ti能力需求類型的數(shù)量;CRil表示任務(wù)Ti的第l項能力需求滿足度,可以利用其獲得的保障能力CUjl與能力需求DTjl的比值表示,即

(11)

保障單元集執(zhí)行所有任務(wù)的平均質(zhì)量定義為

(12)

式中,Qavg∈[0,1],Qavg越大,保障單元集執(zhí)行所有任務(wù)的質(zhì)量越好。

保障單元集執(zhí)行所有任務(wù)的平均質(zhì)量Qavg必須高于某一下限閾值φ,否則將導(dǎo)致任務(wù)執(zhí)行效果遠遠低于期望效果,即滿足

Qavg≥φ

(13)

1.5 協(xié)同任務(wù)分配數(shù)學(xué)模型

因此,以最小化TIT為目標(biāo),協(xié)同任務(wù)分配問題模型為

(14)

2 DLS-BCIWBA任務(wù)分配算法

2.1 算法流程

本文針對協(xié)同任務(wù)分配問題(14),提出了一種基于DLS和BCIWBA的協(xié)同任務(wù)分配算法,主要包含兩個環(huán)節(jié),基于DLS的任務(wù)選擇和基于BCIWBA的保障單元分配,DLS-BCIWBA算法流程如圖2所示。

圖2 DLS-BCIWBA算法流程Fig.2 Flow chart of DLS-BCIWBA

2.2 基于DLS的任務(wù)選擇

其主要步驟如下:

步驟1定義過程變量:可執(zhí)行任務(wù)集Tready、已執(zhí)行任務(wù)集Tcomplete和空閑保障單元集Ufree;

步驟2初始化所有任務(wù)的優(yōu)先權(quán)系數(shù)和保障單元能力向量;

步驟3更新Tcomplete任務(wù)執(zhí)行時間,如果Tcomplete=?則跳過;

步驟4在前導(dǎo)任務(wù)已完成任務(wù)中,選擇優(yōu)先權(quán)系數(shù)最大的一項任務(wù);

步驟5為該任務(wù)在空閑保障單元集Ufree中選擇一項資源以滿足任務(wù)能力需求;

步驟6可執(zhí)行任務(wù)集Tready和空閑保障單元集Ufree和保障單元能力更新;

步驟7判斷是否所有任務(wù)已完成分配,如果是則終止算法,否則轉(zhuǎn)入步驟2。

當(dāng)任務(wù)Ti的所有直接前導(dǎo)任務(wù)都已執(zhí)行完成,該任務(wù)Ti便進入可執(zhí)行任務(wù)集Tready,在Tready中根據(jù)任務(wù)優(yōu)先權(quán)系數(shù)依次分配保障單元,計算任務(wù)優(yōu)先權(quán)系數(shù)的依據(jù)主要包括任務(wù)持續(xù)時間、直接后續(xù)任務(wù)數(shù)量及其優(yōu)先權(quán)系數(shù)[6],任務(wù)優(yōu)先權(quán)系數(shù)越大,表示任務(wù)優(yōu)先級越高,任務(wù)優(yōu)先權(quán)系數(shù)定義為

(15)

式中，PTi為任務(wù)Ti的優(yōu)先權(quán)系數(shù);OUT(i)為任務(wù)Ti的直接后續(xù)任務(wù)集。

2.3 基于BCIWBA的保障單元分配

2.3.1 基本二進制蝙蝠算法

BA的優(yōu)化過程可以理解為蝙蝠群體從無序到有序的演化過程,在問題的解空間中,每個解都是一只蝙蝠,蝙蝠通過調(diào)整頻率、響度和脈沖發(fā)生率等參數(shù),追隨當(dāng)前適應(yīng)度值最高的蝙蝠,直至尋找到全局最優(yōu)解。因此,BA可視為標(biāo)準(zhǔn)PSO和由脈沖響度、脈沖發(fā)生率控制的集中局部搜索的一種均衡組合算法;此外,如果不更新蝙蝠速度,固定脈沖響度和脈沖發(fā)生率,BA又可以認(rèn)為是一種簡化的和聲搜索(harmony search,HS)算法[11]。為了實現(xiàn)BA由連續(xù)域向二進制離散域的拓展,二進制蝙蝠算法(binary bat algorithm,BBA)應(yīng)運而生[12],其算法流程如下。

步驟1初始化蝙蝠種群速度vi、位置xi和頻率fi、響度Ai和脈沖發(fā)生率ri(i=1,2,…,n)。

步驟2通過調(diào)整頻率產(chǎn)生新解(解即是蝙蝠位置),并更新速度和位置。

更新方式:

fi=fmin+(fmax-fmin)β

(16)

(17)

(18)

步驟3蝙蝠位置的二進制離散化操作。

BBA離散化操作實現(xiàn)標(biāo)準(zhǔn)BA由連續(xù)域向二進制離散域拓展,總結(jié)以往文獻中提出的離散化方式,除就近取整或四舍五入方式外,主要采用V型[12]、S型[13]和T型[14]邏輯函數(shù)映射實現(xiàn)離散化操作:

(20)

(21)

步驟4根據(jù)脈沖響度和發(fā)生率選擇局部最優(yōu)解。

(22)

(23)

選擇局部最優(yōu)解的偽代碼可表示如下:

end if

end if

步驟5排列所有蝙蝠適應(yīng)度值,更新當(dāng)前全局最優(yōu)解。

步驟6根據(jù)迭代次數(shù)判斷終止準(zhǔn)則。若滿足t>tmax,則算法終止,否則返回步驟2～步驟5。

2.3.2 BCIWBA算法

從當(dāng)前空閑保障單元集Ufree中為選定的任務(wù)分配保障單元,其實質(zhì)是多維0/1背包問題。基于多維0/1背包問題的特點和BBA算法流程,本文提出了一種BCIWBA算法,與標(biāo)準(zhǔn)BBA相比,BCIWBA主要在以下3個方面進行改進。

(1) 脈沖頻率、響度和發(fā)生率變化區(qū)間混沌搜索

BBA中脈沖頻率往往在頻率變化區(qū)間隨機取值,可能導(dǎo)致速度的變化陷入局部區(qū)間,甚至?xí)黄取巴盵15];此外,根據(jù)脈沖響度和脈沖發(fā)生率選擇局部最優(yōu)解的過程,當(dāng)蝙蝠的脈沖發(fā)生率逐漸增大后,進行鄰域搜索的機會將越來越小,算法易陷入局部最優(yōu)。

混沌是一種普遍的非線性現(xiàn)象,具有遍歷性、隨機性與確定性相統(tǒng)一的特點,為此,本文采用自適應(yīng)折疊混沌搜索方法,通過混沌遍歷脈沖頻率、響度和發(fā)生率變化區(qū)間,使得蝙蝠脈沖頻率、響度和發(fā)生率得到充分變化,具體設(shè)計如下:

(24)

(25)

(26)

(27)

(2) 慣性權(quán)重和學(xué)習(xí)因子自適應(yīng)協(xié)同更新

BBA雖然具有較強的全局搜索能力,但只是一味的向當(dāng)前群體最優(yōu)蝙蝠個體方向聚集,并按照式(17)和式(18)動態(tài)調(diào)整蝙蝠個體的飛行速度和位置,當(dāng)所有蝙蝠個體聚集在當(dāng)前最優(yōu)個體附近,導(dǎo)致與最優(yōu)個體差異較小時,蝙蝠個體的速度和位置更新越來越小,逐漸趨向同一化,從而使得蝙蝠種群個體多樣性大大降低,容易陷入局部最優(yōu)。

因此,為了增加種群的多樣性,改變將所有蝙蝠均引導(dǎo)飛向當(dāng)前最優(yōu)蝙蝠個體的方式,本文將蝙蝠速度更新方式設(shè)計如下:

(28)

慣性權(quán)重選取非線性遞減慣性權(quán)重控制方案:

ωinital-ωfinal)

(29)

式中,k1∈Z+;ωinital和ωfinal為慣性權(quán)重初值和終值。

學(xué)習(xí)因子更新設(shè)計如下:

(30)

式中,k2∈Z+;ηinital為學(xué)習(xí)因子初值。

(3) 融合入侵雜草生長繁殖、空間擴散和競爭生存機制的局部搜索

BBA與大多數(shù)啟發(fā)式智能優(yōu)化算法一樣存在后期收斂速度較慢、收斂精度不高、易陷入局部最優(yōu)等問題,特別是針對高維任務(wù)分配問題,而入侵雜草優(yōu)化(invasive weed optimization,IWO)算法[17]簡單,具有很強的局部搜索能力,因此在局部搜索過程中通過融合入侵雜草生長繁殖、空間擴散和競爭生存機制避免陷入局部最優(yōu)。

IWO算法基于個體適應(yīng)度即任務(wù)執(zhí)行時間進行生長繁殖,選取適應(yīng)度值排名前n/10個蝙蝠個體,各個蝙蝠的繁殖個數(shù)計算如下:

(31)

空間擴散階段蝙蝠個體在其父代附近以正態(tài)分布隨機擴散,正態(tài)分布標(biāo)準(zhǔn)差σ遞減變化過程如下:

(32)

式中,σinital和σfinal為標(biāo)準(zhǔn)差初值和終值;k3∈Z+為非線性調(diào)合指數(shù)。

IWO算法競爭生存機制是通過與預(yù)先設(shè)定的種群數(shù)量n比較來實現(xiàn)的,當(dāng)?shù)^程中種群數(shù)量大于n時,將種群中的父代和子代個體按照適應(yīng)度值排序,適應(yīng)度值排名前n個個體作為下一代種群。

3 仿真算例

以聯(lián)合作戰(zhàn)裝備精確保障想定為例,保障任務(wù)間時序邏輯約束關(guān)系如圖1所示,保障任務(wù)集為T={T1,T2,…,T18},保障單元集為U={U1,U2,…,U20},保障任務(wù)集平均執(zhí)行質(zhì)量下限閾值φ=0.8,保障單元各項保障能力的損耗系數(shù)ωl均設(shè)置為0.1,保障任務(wù)和保障單元屬性如表1和表2所示。

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

表2 保障單元屬性

續(xù)表2

為了體現(xiàn)仿真算例實驗的有效性,通過對3種算法分別運行30次仿真計算實驗所得到目標(biāo)函數(shù)值(任務(wù)執(zhí)行時間TIT)的最優(yōu)值、最差值、均值、標(biāo)準(zhǔn)方差和平均運行時間來考察算法性能,3種算法性能比較如表3所示。其中DLS-BCIWBA算法最優(yōu)解對應(yīng)的任務(wù)-保障單元分配方案如表4所示。

表3 3種算法優(yōu)化性能比較

由仿真實驗結(jié)果可知,基于DLS-BCIWBA算法的協(xié)同任務(wù)分配方法具有較好的最優(yōu)值、均值和方差,而且算法平均耗時稍短,因此相比于DLS-GA和DLS-QGA,基于DLS-BCIWBA算法的協(xié)同任務(wù)分配方案更為緊湊,時效性更優(yōu)。

從統(tǒng)計學(xué)角度對3種算法優(yōu)化性能進行比較,3種算法30次獨立運行實驗盒須圖如圖3所示。圖3中，盒代表指標(biāo)的四分位差,盒越短,數(shù)據(jù)越集中;盒中的橫線代表數(shù)據(jù)的中位數(shù),對于任務(wù)執(zhí)行時間指標(biāo),中位數(shù)越小越好;盒上端的上須代表數(shù)據(jù)的最大值,盒下端的下須代表數(shù)據(jù)最小值,超出上下須的數(shù)據(jù)用“+”表示,代表該數(shù)據(jù)為異常值。由圖3可知,基于DLS-BCIWBA算法的協(xié)同任務(wù)分配方法在統(tǒng)計意義上能夠得到全局最優(yōu)、穩(wěn)定性最優(yōu)和任務(wù)執(zhí)行時間最為緊湊的任務(wù)分配方案。

表4 最優(yōu)任務(wù)-保障單元分配方案

圖3 3種算法優(yōu)化性能盒須圖Fig.3 Optimization performance boxplot of three algorithms

4 結(jié) 論

本文針對裝備精確保障協(xié)同任務(wù)分配問題,建立了以最小化任務(wù)執(zhí)行時間為目標(biāo)的數(shù)學(xué)模型,提出了一種DLS-BCIWBA混合任務(wù)分配方法,通過DLS選擇所需執(zhí)行的任務(wù),設(shè)計BCIWBA為選定任務(wù)分配保障單元。裝備精確保障協(xié)同任務(wù)分配案例仿真結(jié)果表明,基于DLS-BCIWBA算法的任務(wù)分配方法可以有效解決時序邏輯任務(wù)分配問題。