蝙蝠算法結(jié)合動(dòng)態(tài)列表在應(yīng)急救援裝備保障規(guī)劃中的應(yīng)用研究

摘要：針對(duì)聯(lián)合應(yīng)急救援環(huán)境中裝備資源的精確保障和協(xié)同規(guī)劃難題，可以采用改進(jìn)的蝙蝠算法結(jié)合動(dòng)態(tài)列表調(diào)度的方法，來進(jìn)行模型構(gòu)建，采用動(dòng)態(tài)列表的方式對(duì)實(shí)施保障任務(wù)進(jìn)行篩選，同時(shí)引入自適應(yīng)學(xué)習(xí)因子來均衡全局搜索和局部搜索能力，最后利用聯(lián)合應(yīng)急救援作為實(shí)例進(jìn)行仿真驗(yàn)證，該方法能夠?qū)崿F(xiàn)裝備保障規(guī)劃流程的有效管理與優(yōu)化，對(duì)提升應(yīng)急救援保障能力、降低損失有著重要意義。本文在闡述蝙蝠算法及動(dòng)態(tài)列表概念和總結(jié)蝙蝠算法發(fā)展歷史的基礎(chǔ)上，以自適應(yīng)進(jìn)化二進(jìn)制蝙蝠算法結(jié)合動(dòng)態(tài)列表為例，提出裝備保障規(guī)劃中蝙蝠算法總體框架設(shè)計(jì)，對(duì)未來蝙蝠算法在應(yīng)急保障領(lǐng)域的有關(guān)研究具有重要的指導(dǎo)意義和作用。關(guān)鍵詞：蝙蝠算法；動(dòng)態(tài)列表調(diào)度；資源保障；任務(wù)分配引言在應(yīng)急救援裝備保障協(xié)同規(guī)劃問題中引入蝙蝠算法并結(jié)合動(dòng)態(tài)列表進(jìn)行精確計(jì)算，可以為聯(lián)合救援行動(dòng)提供數(shù)量準(zhǔn)確且快速高效的裝備保障。在實(shí)際的救援災(zāi)害現(xiàn)場(chǎng)中，保障任務(wù)具有不確定性，同時(shí)還存在裝備資源占用以及保障任務(wù)時(shí)序約束等問題，所以全局最優(yōu)化就成為解決難題所關(guān)注的一個(gè)焦點(diǎn)。國(guó)內(nèi)外學(xué)者的研究表明，蝙蝠算法在最優(yōu)路徑和物資裝備調(diào)度方面得到了廣泛應(yīng)用，尤其在應(yīng)急救援任務(wù)中具有重要的應(yīng)用價(jià)值。因?yàn)楹侠淼难b備調(diào)配方案直接關(guān)系到任務(wù)執(zhí)行效率和成功率，而蝙蝠算法能夠在多個(gè)因素之間進(jìn)行權(quán)衡和優(yōu)化，得出最優(yōu)的裝備調(diào)配方案，從而提高救援任務(wù)的效率和成功率[1]。一、蝙蝠算法及動(dòng)態(tài)列表概述（一）蝙蝠算法及動(dòng)態(tài)列表調(diào)度算法定義蝙蝠算法是一種基于仿生學(xué)思想的優(yōu)化算法，它模擬了蝙蝠在捕食過程中發(fā)出超聲波來確定獵物位置的行為。該算法具有全局搜索能力和收斂速度較快的優(yōu)點(diǎn)，適用于求解復(fù)雜的非線性優(yōu)化問題。BA算法的基本思路是不斷調(diào)整蝙蝠的位置和頻率，以實(shí)現(xiàn)對(duì)目標(biāo)函數(shù)的最優(yōu)化搜索。每只蝙蝠都有自己的位置和頻率，并通過發(fā)出超聲波來與其他蝙蝠進(jìn)行信息交流。在搜索過程中，蝙蝠會(huì)根據(jù)當(dāng)前的位置和頻率計(jì)算出一個(gè)新的位置和頻率，并通過超聲波通知其他蝙蝠。如果某只蝙蝠發(fā)現(xiàn)了更優(yōu)的位置，它會(huì)向其他蝙蝠傳遞這個(gè)信息，其他蝙蝠也會(huì)朝著該位置靠近，從而實(shí)現(xiàn)全局搜索。DLS（DynamicListScheduling）動(dòng)態(tài)列表調(diào)度算法是一種基于貪心策略的在線任務(wù)調(diào)度算法。它是動(dòng)態(tài)列表調(diào)度算法的一種變體，用于在多處理器系統(tǒng)中對(duì)任務(wù)進(jìn)行調(diào)度[2]。DLS算法將任務(wù)按照優(yōu)先級(jí)插入到一個(gè)任務(wù)列表中，并根據(jù)當(dāng)前空閑處理器數(shù)量和任務(wù)的優(yōu)先級(jí)動(dòng)態(tài)地調(diào)整任務(wù)的順序。具體來說，當(dāng)有新的任務(wù)到達(dá)時(shí)，DLS算法會(huì)檢查當(dāng)前空閑處理器數(shù)量，如果有空閑處理器，則將任務(wù)分配給其中一個(gè)處理器執(zhí)行。否則，算法會(huì)從任務(wù)列表中選擇一個(gè)優(yōu)先級(jí)最低的任務(wù)，并將其重新調(diào)整位置，以便盡快釋放一個(gè)處理器。通過這種方式，DLS算法可以最大化任務(wù)的完成數(shù)量和完成時(shí)間。（二）蝙蝠算法及動(dòng)態(tài)列表調(diào)度算法的發(fā)展蝙蝠算法是一種啟發(fā)式優(yōu)化算法，它基于蝙蝠群體的行為模擬。蝙蝠在捕食時(shí)會(huì)發(fā)出超聲波感知周圍環(huán)境和獵物，根據(jù)自身位置和速度調(diào)整飛行方向和頻率，最終實(shí)現(xiàn)捕食目標(biāo)的目的。該算法由Xin-SheYang于2010年提出，其靈感來源于蝙蝠的行為特點(diǎn)。在20世紀(jì)80年代早期，遺傳算法和模擬退火算法成為該算法的發(fā)展先驅(qū)。隨著自然界動(dòng)物行為研究和仿生學(xué)的興起，基于自然界現(xiàn)象的啟發(fā)式算法逐漸被提出并應(yīng)用于各種優(yōu)化問題的求解中。在蝙蝠算法的發(fā)展過程中，研究者們不斷改進(jìn)和優(yōu)化算法的各個(gè)方面，如蝙蝠的搜索策略、參數(shù)設(shè)置、適應(yīng)度函數(shù)等，使得蝙蝠算法在解決實(shí)際問題中具有較高的效率和魯棒性。目前，該算法已廣泛應(yīng)用于工程、經(jīng)濟(jì)、生物等領(lǐng)域的優(yōu)化問題中，成為了一種重要的求解工具[3]。（三）蝙蝠算法結(jié)合動(dòng)態(tài)列表在裝備保障規(guī)劃中的可行性及必要性蝙蝠算法是一種基于自然界蝙蝠行為模式的優(yōu)化算法，可用于解決多個(gè)因素相互影響的問題。而在裝備保障規(guī)劃中，需要考慮裝備要求、數(shù)量、質(zhì)量和費(fèi)用等多個(gè)因素，這些因素之間的關(guān)系復(fù)雜，需要進(jìn)行綜合考慮和優(yōu)化。將蝙蝠算法與DLS動(dòng)態(tài)列表相結(jié)合，可以提高裝備保障規(guī)劃的效率和準(zhǔn)確性。具體來說，蝙蝠算法可用于搜索最佳裝備配置方案，而DLS動(dòng)態(tài)列表則可用于存儲(chǔ)和更新各種方案成本收益信息，以達(dá)到動(dòng)態(tài)規(guī)劃的目的。因此，將蝙蝠算法與DLS動(dòng)態(tài)列表相結(jié)合應(yīng)用于裝備保障規(guī)劃中，不僅可行而且十分必要，能夠提升規(guī)劃效率和準(zhǔn)確性。二、應(yīng)急救援裝備精確協(xié)同保障規(guī)劃描述模型設(shè)計(jì)（一）基本概念在聯(lián)合救援行動(dòng)中，資源保障是貫穿整個(gè)救援流程的關(guān)鍵環(huán)節(jié)。能否及時(shí)、正確、有效提供所需資源，對(duì)于提高應(yīng)急救援的能力至關(guān)重要。為了實(shí)現(xiàn)資源保障的有效規(guī)劃，我們可以將該規(guī)劃模型分為任務(wù)描述和資源描述兩個(gè)部分。在對(duì)保障任務(wù)核心要素進(jìn)行分析的基礎(chǔ)上，該模型主要包括每個(gè)保障任務(wù)所需的資源種類和數(shù)量、保障點(diǎn)的坐標(biāo)位置以及任務(wù)持續(xù)時(shí)間等要素[4]。保障任務(wù)描述為：M項(xiàng)任務(wù)保障集為T={T1，T2……TM}，Ti∈T，其主要包括：任務(wù)開始時(shí)間STi、任務(wù)持續(xù)時(shí)間CTi、任務(wù)坐標(biāo)位置LTi。保障資源描述為：N項(xiàng)任務(wù)保障集為R={R1，R2……RN}，Rj∈R，其主要包括：保障資源的平均移動(dòng)速度VRj資源能力向量CRj以及初始位置LRj。（二）優(yōu)先權(quán)系數(shù)在任務(wù)資源保障問題的求解過程中，存在兩個(gè)難點(diǎn)。第一個(gè)難點(diǎn)是單個(gè)任務(wù)可調(diào)度資源最優(yōu)時(shí)，并不一定能夠得到全局最優(yōu)方案。第二個(gè)難點(diǎn)是在大規(guī)模資源保障問題中，由于需要進(jìn)行多次迭代，算力浪費(fèi)占用時(shí)間較長(zhǎng)。為了解決這些問題，我們可以將總?cè)蝿?wù)完成時(shí)間作為目標(biāo)函數(shù)，并采用優(yōu)先權(quán)系數(shù)對(duì)產(chǎn)生編組爭(zhēng)用等問題進(jìn)行排序，以消除沖突。具體公式如下：根據(jù)保障任務(wù)集關(guān)系圖和任務(wù)優(yōu)先權(quán)定義式，即可計(jì)算每一個(gè)任務(wù)優(yōu)先權(quán)系數(shù)。（三）約束條件可以假設(shè)任務(wù)能夠得到保障，但是為了確保任務(wù)能夠順利完成，需要滿足以下條件：該任務(wù)的前置任務(wù)必須全部完成；協(xié)同任務(wù)需要被統(tǒng)一處理為時(shí)序約束任務(wù)；該任務(wù)所需的全部資源必須被分配并部署到任務(wù)執(zhí)行地點(diǎn)；所有任務(wù)資源的保障能力都不能低于任何一個(gè)任務(wù)資源的保障能力。通過對(duì)這些約束條件的歸納和分析，我們可以將其總結(jié)為任務(wù)資源分配約束、任務(wù)開始時(shí)間約束、任務(wù)完成時(shí)間約束以及任務(wù)資源需求約束。只有在滿足這些條件的前提下，任務(wù)才能夠被保障，并且能夠高效、順利完成。資源分配約束指必須等待保障資源完成一個(gè)任務(wù)后，才能將其分配給下一個(gè)保障任務(wù)。而任務(wù)開始時(shí)間的約束則是，后續(xù)任務(wù)的開始時(shí)間不能早于前面任務(wù)的開始時(shí)間加上它所需的保障時(shí)間[5]。其計(jì)算公式為：式中Xijm表示資源m在完成一個(gè)保障任務(wù)Ti后是否被分配給下一個(gè)任務(wù)Tj。任務(wù)完成時(shí)間約束是指，如任務(wù)分配則為1否則為0，Y′為完成所有保障任務(wù)的最大值。任務(wù)完成時(shí)間約束是指總完成任務(wù)時(shí)間不小于任意任務(wù)完成時(shí)間即該描述問題的目標(biāo)函數(shù)為：Ymin。而資源需求約束則要求資源能力向量中各類型資源的總能力不小于任務(wù)所需對(duì)應(yīng)資源能力數(shù)量，即三、算法（DLS-AMBB）設(shè)計(jì)（一）二次蝙蝠算法資源分配流程針對(duì)所選保障任務(wù)，其最優(yōu)保障資源分配方案是以任務(wù)獲得保障為前提，能滿足實(shí)施時(shí)間最短與所占保障編組最小兩大目標(biāo)。通過尋優(yōu)求解步驟更新全局最優(yōu)解，第一步對(duì)各項(xiàng)初始化參數(shù)進(jìn)行更新，包括任務(wù)選定、資源更新、編組采用狀態(tài)更新以及上圖所示內(nèi)容。第二步元素值代表意義對(duì)應(yīng)保障向量是否被采用，0為未選擇，1為被采用，初始化在隨機(jī)數(shù)值0-1之中產(chǎn)生一個(gè)數(shù)值，當(dāng)產(chǎn)生數(shù)值小于0.5，那么位置為0反之為1，初始解蝙蝠位置由上圖離散化操作公式求得。第三步如初始解存在不可行解，則需要進(jìn)行篩選重構(gòu)，兩個(gè)指標(biāo)判斷初始解是否為不可行解，即選擇的裝備物資無法滿足物資保障需求，還有就是資源沖突也為初始解不可行解。第四步通過更新位置速度計(jì)算公式增加慣性權(quán)重和自適應(yīng)性因子得到新的更新公式進(jìn)行計(jì)算求解，自適應(yīng)性慣性權(quán)重采取遞減算法，最終判斷新解是否為可行解，否則需要重新更新位置速度并離散化。第五步從局部最優(yōu)解中，排列蝙蝠適應(yīng)度值，找到全局最優(yōu)解[6]。（二）算法框架針對(duì)精確協(xié)同保障問題，可采取動(dòng)態(tài)列表調(diào)度配合二次蝙蝠算法聯(lián)合求解，先通過動(dòng)態(tài)列表選出所需要當(dāng)前執(zhí)行的保障任務(wù)，然后通過二次蝙蝠算法對(duì)當(dāng)前所有資源中選出執(zhí)行任務(wù)保障最優(yōu)方案，具體流程圖如圖1所示。（三）仿真算例本文以聯(lián)合應(yīng)急救援保障為例，列出保障任務(wù)及保障資源屬性表。一般情況，為了驗(yàn)證二次蝙蝠算法的有效性，需要與其他基本算法做對(duì)比計(jì)算，仿真環(huán)境通過Matlab軟件實(shí)現(xiàn)，進(jìn)行算法參數(shù)設(shè)置，設(shè)置參數(shù)主要有：算法迭代次數(shù)、種群個(gè)數(shù)、頻率響度、脈沖發(fā)生率、最小脈沖頻率、最大脈沖頻率、慣性權(quán)重最小值最大值。還可通過算法生成最優(yōu)保障任務(wù)甘特圖可視化進(jìn)行對(duì)比，以二次蝙蝠算法結(jié)合動(dòng)態(tài)（DLSAMBBA）算法甘特圖為例，如圖2所示，橫坐標(biāo)為保障時(shí)間，縱坐標(biāo)為資源（1為D1）。在生成甘特圖之后，二次蝙蝠算法結(jié)合列表調(diào)度與基本算法比較6次計(jì)算結(jié)果，比較數(shù)值分別為最優(yōu)解、最差解、平均值、標(biāo)準(zhǔn)差，通過對(duì)比數(shù)據(jù)看算法是否具有較強(qiáng)全局尋優(yōu)和收斂性能并可以提高算法求解速度，最終畫出收斂迭代圖[7]。結(jié)語二次蝙蝠算法是一種改進(jìn)的蝙蝠算法，相比于基本蝙蝠算法，具有更高的搜索性能和更高的收斂速度，將二次蝙蝠算法結(jié)合動(dòng)態(tài)列表調(diào)度應(yīng)用于應(yīng)急救援裝備保障規(guī)劃中主要有以下三點(diǎn)意義：首先，根據(jù)當(dāng)前的裝備需求和資源供給情況，自動(dòng)尋找最優(yōu)的裝備調(diào)度方案，從而提高調(diào)度效率和裝備利用率。其次，在突發(fā)事件發(fā)生時(shí)，需要迅速調(diào)度和分配救援裝備，以滿足不同