蝙蝠算法結合動態列表在應急救援裝備保障規劃中的應用研究

梁旭 李爽

摘要：針對聯合應急救援環境中裝備資源的精確保障和協同規劃難題，可以采用改進的蝙蝠算法結合動態列表調度的方法，來進行模型構建，采用動態列表的方式對實施保障任務進行篩選，同時引入自適應學習因子來均衡全局搜索和局部搜索能力，最后利用聯合應急救援作為實例進行仿真驗證，該方法能夠實現裝備保障規劃流程的有效管理與優化，對提升應急救援保障能力、降低損失有著重要意義。本文在闡述蝙蝠算法及動態列表概念和總結蝙蝠算法發展歷史的基礎上，以自適應進化二進制蝙蝠算法結合動態列表為例，提出裝備保障規劃中蝙蝠算法總體框架設計，對未來蝙蝠算法在應急保障領域的有關研究具有重要的指導意義和作用。

關鍵詞：蝙蝠算法；動態列表調度；資源保障；任務分配

引言

在應急救援裝備保障協同規劃問題中引入蝙蝠算法并結合動態列表進行精確計算，可以為聯合救援行動提供數量準確且快速高效的裝備保障。在實際的救援災害現場中，保障任務具有不確定性，同時還存在裝備資源占用以及保障任務時序約束等問題，所以全局最優化就成為解決難題所關注的一個焦點。

國內外學者的研究表明，蝙蝠算法在最優路徑和物資裝備調度方面得到了廣泛應用，尤其在應急救援任務中具有重要的應用價值。因為合理的裝備調配方案直接關系到任務執行效率和成功率，而蝙蝠算法能夠在多個因素之間進行權衡和優化，得出最優的裝備調配方案，從而提高救援任務的效率和成功率[1]。

一、蝙蝠算法及動態列表概述

（一）蝙蝠算法及動態列表調度算法定義

蝙蝠算法是一種基于仿生學思想的優化算法，它模擬了蝙蝠在捕食過程中發出超聲波來確定獵物位置的行為。該算法具有全局搜索能力和收斂速度較快的優點，適用于求解復雜的非線性優化問題。

BA算法的基本思路是不斷調整蝙蝠的位置和頻率，以實現對目標函數的最優化搜索。每只蝙蝠都有自己的位置和頻率，并通過發出超聲波來與其他蝙蝠進行信息交流。

在搜索過程中，蝙蝠會根據當前的位置和頻率計算出一個新的位置和頻率，并通過超聲波通知其他蝙蝠。如果某只蝙蝠發現了更優的位置，它會向其他蝙蝠傳遞這個信息，其他蝙蝠也會朝著該位置靠近，從而實現全局搜索。

DLS（Dynamic List Scheduling）動態列表調度算法是一種基于貪心策略的在線任務調度算法。它是動態列表調度算法的一種變體，用于在多處理器系統中對任務進行調度[2]。

DLS算法將任務按照優先級插入到一個任務列表中，并根據當前空閑處理器數量和任務的優先級動態地調整任務的順序。具體來說，當有新的任務到達時，DLS算法會檢查當前空閑處理器數量，如果有空閑處理器，則將任務分配給其中一個處理器執行。否則，算法會從任務列表中選擇一個優先級最低的任務，并將其重新調整位置，以便盡快釋放一個處理器。通過這種方式，DLS算法可以最大化任務的完成數量和完成時間。

（二）蝙蝠算法及動態列表調度算法的發展

蝙蝠算法是一種啟發式優化算法，它基于蝙蝠群體的行為模擬。蝙蝠在捕食時會發出超聲波感知周圍環境和獵物，根據自身位置和速度調整飛行方向和頻率，最終實現捕食目標的目的。該算法由Xin-She Yang于2010年提出，其靈感來源于蝙蝠的行為特點。在20世紀80年代早期，遺傳算法和模擬退火算法成為該算法的發展先驅。隨著自然界動物行為研究和仿生學的興起，基于自然界現象的啟發式算法逐漸被提出并應用于各種優化問題的求解中。在蝙蝠算法的發展過程中，研究者們不斷改進和優化算法的各個方面，如蝙蝠的搜索策略、參數設置、適應度函數等，使得蝙蝠算法在解決實際問題中具有較高的效率和魯棒性。目前，該算法已廣泛應用于工程、經濟、生物等領域的優化問題中，成為了一種重要的求解工具[3]。

（三）蝙蝠算法結合動態列表在裝備保障規劃中的可行性及必要性

蝙蝠算法是一種基于自然界蝙蝠行為模式的優化算法，可用于解決多個因素相互影響的問題。而在裝備保障規劃中，需要考慮裝備要求、數量、質量和費用等多個因素，這些因素之間的關系復雜，需要進行綜合考慮和優化。將蝙蝠算法與DLS動態列表相結合，可以提高裝備保障規劃的效率和準確性。具體來說，蝙蝠算法可用于搜索最佳裝備配置方案，而DLS動態列表則可用于存儲和更新各種方案成本收益信息，以達到動態規劃的目的。因此，將蝙蝠算法與DLS動態列表相結合應用于裝備保障規劃中，不僅可行而且十分必要，能夠提升規劃效率和準確性。

二、應急救援裝備精確協同保障規劃描述模型設計

（一）基本概念

在聯合救援行動中，資源保障是貫穿整個救援流程的關鍵環節。能否及時、正確、有效提供所需資源，對于提高應急救援的能力至關重要。為了實現資源保障的有效規劃，我們可以將該規劃模型分為任務描述和資源描述兩個部分。在對保障任務核心要素進行分析的基礎上，該模型主要包括每個保障任務所需的資源種類和數量、保障點的坐標位置以及任務持續時間等要素[4]。

保障任務描述為：M項任務保障集為T={T1，T2……TM}，Ti∈T，其主要包括：任務開始時間STi、任務持續時間CTi、任務坐標位置LTi。

保障資源描述為：N項任務保障集為R={R1，R2……RN}，Rj∈R，其主要包括：保障資源的平均移動速度VRj資源能力向量CRj以及初始位置LRj。

（二）優先權系數

在任務資源保障問題的求解過程中，存在兩個難點。第一個難點是單個任務可調度資源最優時，并不一定能夠得到全局最優方案。第二個難點是在大規模資源保障問題中，由于需要進行多次迭代，算力浪費占用時間較長。為了解決這些問題，我們可以將總任務完成時間作為目標函數，并采用優先權系數對產生編組爭用等問題進行排序，以消除沖突。具體公式如下：

根據保障任務集關系圖和任務優先權定義式，即可計算每一個任務優先權系數。

（三）約束條件

可以假設任務能夠得到保障，但是為了確保任務能夠順利完成，需要滿足以下條件：該任務的前置任務必須全部完成；協同任務需要被統一處理為時序約束任務；該任務所需的全部資源必須被分配并部署到任務執行地點；所有任務資源的保障能力都不能低于任何一個任務資源的保障能力。

通過對這些約束條件的歸納和分析，我們可以將其總結為任務資源分配約束、任務開始時間約束、任務完成時間約束以及任務資源需求約束。只有在滿足這些條件的前提下，任務才能夠被保障，并且能夠高效、順利完成。資源分配約束指必須等待保障資源完成一個任務后，才能將其分配給下一個保障任務。而任務開始時間的約束則是，后續任務的開始時間不能早于前面任務的開始時間加上它所需的保障時間[5]。其計算公式為：

式中Xijm表示資源m在完成一個保障任務Ti后是否被分配給下一個任務Tj。任務完成時間約束是指，如任務分配則為1否則為0，Y′為完成所有保障任務的最大值。任務完成時間約束是指總完成任務時間不小于任意任務完成時間即該描述問題的目標函數為：Ymin。而資源需求約束則要求資源能力向量中各類型資源的總能力不小于任務所需對應資源能力數量，即

三、算法（DLS-AMBB）設計

（一）二次蝙蝠算法資源分配流程

針對所選保障任務，其最優保障資源分配方案是以任務獲得保障為前提，能滿足實施時間最短與所占保障編組最小兩大目標。

通過尋優求解步驟更新全局最優解，第一步對各項初始化參數進行更新，包括任務選定、資源更新、編組采用狀態更新以及上圖所示內容。第二步元素值代表意義對應保障向量是否被采用，0為未選擇，1為被采用，初始化在隨機數值0-1之中產生一個數值，當產生數值小于0.5，那么位置為0反之為1，初始解蝙蝠位置由上圖離散化操作公式求得。第三步如初始解存在不可行解，則需要進行篩選重構，兩個指標判斷初始解是否為不可行解，即選擇的裝備物資無法滿足物資保障需求，還有就是資源沖突也為初始解不可行解。第四步通過更新位置速度計算公式增加慣性權重和自適應性因子得到新的更新公式進行計算求解，自適應性慣性權重采取遞減算法，最終判斷新解是否為可行解，否則需要重新更新位置速度并離散化。第五步從局部最優解中，排列蝙蝠適應度值，找到全局最優解[6]。

（二）算法框架

針對精確協同保障問題，可采取動態列表調度配合二次蝙蝠算法聯合求解，先通過動態列表選出所需要當前執行的保障任務，然后通過二次蝙蝠算法對當前所有資源中選出執行任務保障最優方案，具體流程圖如圖1所示。

（三）仿真算例

本文以聯合應急救援保障為例，列出保障任務及保障資源屬性表。一般情況，為了驗證二次蝙蝠算法的有效性，需要與其他基本算法做對比計算，仿真環境通過Matlab軟件實現，進行算法參數設置，設置參數主要有：算法迭代次數、種群個數、頻率響度、脈沖發生率、最小脈沖頻率、最大脈沖頻率、慣性權重最小值最大值。還可通過算法生成最優保障任務甘特圖可視化進行對比，以二次蝙蝠算法結合動態（DLSAMBBA）算法甘特圖為例，如圖2所示，橫坐標為保障時間，縱坐標為資源（1為D1）。

在生成甘特圖之后，二次蝙蝠算法結合列表調度與基本算法比較6次計算結果，比較數值分別為最優解、最差解、平均值、標準差，通過對比數據看算法是否具有較強全局尋優和收斂性能并可以提高算法求解速度，最終畫出收斂迭代圖[7]。

結語

二次蝙蝠算法是一種改進的蝙蝠算法，相比于基本蝙蝠算法，具有更高的搜索性能和更高的收斂速度，將二次蝙蝠算法結合動態列表調度應用于應急救援裝備保障規劃中主要有以下三點意義：首先，根據當前的裝備需求和資源供給情況，自動尋找最優的裝備調度方案，從而提高調度效率和裝備利用率。其次，在突發事件發生時，需要迅速調度和分配救援裝備，以滿足不同任務需求。通過動態列表調度的方式，可以實時更新任務和資源信息，而二次蝙蝠算法的快速搜索能力可以幫助快速尋找最優的調度方案，從而實現及時響應。最后，通過二次蝙蝠算法的預測能力，可以根據歷史數據和趨勢，預測未來可能出現的裝備需求，從而幫助應急管理部門做好裝備儲備和調度準備工作，提高應急響應能力。綜上所述，將二次蝙蝠算法結合動態列表調度應用于應急救援裝備保障規劃中，可以提高應急裝備精確保障的效率和質量[8]。

參考文獻

[1]崔東文，金波.蝙蝠算法-投影尋蹤模型在旱災評估中的應用——以文山州為例[J].人民珠江，2016，37（09）：26-30.

[2]張斯嘉，郭建勝，鐘夫，等.基于蝙蝠算法的多目標戰備物資調運決策優化[J].火力與指揮控制，2016，41（01）：58-61.

[3]馬祥麗，張惠珍，馬良.蝙蝠算法在物流配送車輛路徑優化問題中的應用[J].數學的實踐與認識，2015，45（24）：80-86.

[4]李良良.量子蝙蝠算法在無人潛航器航路規劃中的應用[J].電腦編程技巧與維護，2022，441（03）：126-127+131.

[5]程春英，劉娜仁.蝙蝠算法的研究進展[J].電腦知識與技術，2016，12（24）：187-188+198.

[6]周翔翔，姚佩陽，張杰勇，等.一種基于DLS和ACO的平臺資源規劃方法[J].計算機科學，2012，39（06）：98-103.

[7]王藝霖.混合蝙蝠算法及其在調度管理中的應用研究[D].東華大學，2022.

[8]許德剛，趙萍.蝙蝠算法研究及應用綜述[J].計算機工程與應用，2019，55（15）：1-12+31.