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

王堅(jiān)浩, 張 亮, 史 超, 車 飛, 張鵬濤

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

0 引 言

裝備精確保障的實(shí)質(zhì)是指運(yùn)用系統(tǒng)工程的理論和方法,通過精細(xì)、精確籌劃和運(yùn)用裝備保障資源、保障力量,使其在準(zhǔn)確的時(shí)間、地點(diǎn)完成裝備保障任務(wù)。裝備精確保障要求對(duì)各類裝備設(shè)施、器材、備件等資源和專業(yè)人員進(jìn)行整合和編組,以保障單元的形式分配給具體的保障任務(wù),屬于一類典型的任務(wù)分配問題[1]。求解此類任務(wù)分配問題,整數(shù)規(guī)劃、分支定界法和枚舉法等精確求解方法無法滿足實(shí)時(shí)性要求;而基于動(dòng)態(tài)列表規(guī)劃的啟發(fā)式方法[2-4]求解效率較高,但都是采用基于貪心策略的局部搜索策略,因此得到的任務(wù)分配方案未必是最優(yōu)方案;文獻(xiàn)[5-6]結(jié)合啟發(fā)式智能優(yōu)化算法提出了混合任務(wù)分配方法,首先通過動(dòng)態(tài)列表規(guī)劃 (dynamic list scheduling,DLS)選擇需要執(zhí)行的任務(wù),其次針對(duì)選定任務(wù)分配平臺(tái)(編組)問題的實(shí)質(zhì)為多維0/1背包問題的特點(diǎn),采用全局搜索遺傳算法(genetic algorithm,GA)和量子遺產(chǎn)算法(quantum genetic algorithm,QGA)相結(jié)合的混合啟發(fā)式智能優(yōu)化算法,但并未考慮任務(wù)執(zhí)行質(zhì)量約束,然而在實(shí)際任務(wù)執(zhí)行過程中,如果任務(wù)執(zhí)行質(zhì)量過低,則任務(wù)執(zhí)行效果將遠(yuǎn)低于期望效果;文獻(xiàn)[7]針對(duì)裝備保障任務(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è)計(jì)了以DLS算法為主的求解框架,嵌套具有混沌搜索策略和入侵雜草算子的二進(jìn)制混沌入侵雜草蝙蝠算法(binary chaotic invasive weed bat algorithm,BCIWBA)為選定任務(wù)分配保障單元。首先利用BA的全局尋優(yōu)能力和迭代初期快速收斂性進(jìn)行全局搜索;然后選取部分最優(yōu)個(gè)體融合入侵雜草生長(zhǎng)繁殖、空間擴(kuò)散和競(jìng)爭(zhēng)生存機(jī)制進(jìn)行局部搜索,并通過學(xué)習(xí)因子和慣性權(quán)重的自適應(yīng)協(xié)同更新以平衡探索和開發(fā)能力,結(jié)合脈沖頻率、響度、發(fā)生率變化區(qū)間的混沌搜索避免早熟收斂;最后通過案例仿真證明本文所提任務(wù)分配方法的有效性。

1 問題描述

1.1 基本概念

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

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

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

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

,l∈[1,L]

(1)

(2)

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

(3)

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

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

(4)

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

(5)

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

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

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

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

(6)

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

/VUj

(7)

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

/VUi+ETj

(8)

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

(9)

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

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

(10)

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

(11)

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

(12)

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

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

Qavg≥φ

(13)

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

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

(14)

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

2.1 算法流程

本文針對(duì)協(xié)同任務(wù)分配問題(14),提出了一種基于DLS和BCIWBA的協(xié)同任務(wù)分配算法,主要包含兩個(gè)環(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í)行時(shí)間,如果Tcomplete=?則跳過;

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

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

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

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

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

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

BBA離散化操作實(shí)現(xiàn)標(biāo)準(zhǔn)BA由連續(xù)域向二進(jìn)制離散域拓展,總結(jié)以往文獻(xiàn)中提出的離散化方式,除就近取整或四舍五入方式外,主要采用V型[12]、S型[13]和T型[14]邏輯函數(shù)映射實(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ù)分配保障單元,其實(shí)質(zhì)是多維0/1背包問題。基于多維0/1背包問題的特點(diǎn)和BBA算法流程,本文提出了一種BCIWBA算法,與標(biāo)準(zhǔn)BBA相比,BCIWBA主要在以下3個(gè)方面進(jìn)行改進(jìn)。

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

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

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

(24)

(25)

(26)

(27)

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

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

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

(28)

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

ωinital-ωfinal)

(29)

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

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

(30)

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

(3) 融合入侵雜草生長(zhǎng)繁殖、空間擴(kuò)散和競(jìng)爭(zhēng)生存機(jī)制的局部搜索

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

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

(31)

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

(32)

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

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

3 仿真算例

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

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

表2 保障單元屬性

續(xù)表2

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

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

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

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

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

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

4 結(jié) 論

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