基于遺傳算法的戰時任務搶修過程優化研究

武子榮，陳曼青，崔偉寧

裝甲兵工程學院信息工程系，北京 100072

基于遺傳算法的戰時任務搶修過程優化研究

武子榮，陳曼青，崔偉寧

裝甲兵工程學院信息工程系，北京 100072

目前，我軍的很多保障單位在進行戰時任務搶修過程的規劃時很多都是人工自主決策的，根據之前的情況或經驗來進行資源配置和路徑選擇，最終形成搶修方案，這就存在很大的主觀因素，使得決策不科學，方案不合理等。根據上述狀況，利用遺傳算法來進行任務搶修過程模型的求解，得到搶修過程中的總消耗成本和優化路徑，最后代入實例數據取得實驗結果。仿真結果表明，基于遺傳算法的戰時搶修過程優化確實能夠得到優化的成本消耗并選出優化路徑，得到最優方案。

遺傳算法；戰時搶修；過程優化

隨著仿真技術的不斷發展，傳統的裝備保障模式也受到了這種技術快速發展的影響。仿真技術不但能直觀的將整個保障調配過程顯示出來，同時能夠節省成本，提高效率，易于推廣。如果仿真技術與搶修資源優化調度的相關算法有機地結合到一起，并付諸應用，這將大大地提高保障的水平，同時也會大大地提高保障工作的效率，使得戰損裝備在最短的時間內恢復戰斗力，這對裝備戰斗力的再形成具有較深的影響[1]。

裝備搶修工作高效完成是保證裝備戰斗力的重要因素之一。仿真技術在現代仿真領域的的快速發展并且廣發應用于軍事中，給戰時搶修帶來了很好的發展機遇。裝備的保障工作為充分發揮、維持、恢復和完善裝備作戰技術性能的強有力手段，已經成為決定戰爭勝負的重要因素之一[2]。戰時任務搶修過程中指揮決策、資源的配置、調度以及路徑的選擇等，目前搶修過程基本都是基于人為定制的，因此存在資源配置調度不合理，保障決策不清晰，總體消耗較大等方面的不足[1]。

目前解決這方面的優化問題一般采用智能優化算法進行仿真計算。本文以實際情況為背景，以總體消耗最小為目標，以時間、路程和人員配置以及保障需求量等為基本約束條件，來建立戰時任務搶修過程的數學模型。應用改進的自適應遺傳算法進行模型的求解[2]。最終得到在總消耗最小的目標下的任務搶修方案。

1 戰時搶修過程優化數學模型

在戰場環境下，裝備搶修過程是一項非常復雜的科目，目前還沒有將全部搶修過程按著數學的方法進行模型建立，因為太復雜，根本無法計算，也無法很好的描述建立的模型。因此，為了便于建立模型，也為了便于模型的計算，文章對戰時任務搶修過程進行歸納概括，取其核心，概括為資源的調配和路徑的選擇[3]。

1.1 戰時搶修過程優化問題描述

裝備搶修過程中包含幾個要素，主要有保障單位、物資、搶修分隊、待搶修點、行走路徑、約束條件和目標條件等。戰時搶修過程優化的最終目標。在建立模型前，需要對問題進行一些假設。1）把需要的物資都看成是一種物資；2）保障單位和待搶修點的坐標已知；3）每個待搶修點的物資需求量已知；4）線路的起始和結束位置都在保障單位，每個搶修分隊只保障一條線路；5）行駛道路都是通暢的，不考慮交通堵塞等情況。

為了更加接近實際，還應該滿足時間的要求，為每個待搶修點增加時間約束，增加最早到達時間和最晚到達時間。假如保障單位派出的搶修分隊沒能在規定的時間里到達待搶修點，則會給予相應的懲罰[2]。

1.2 模型建立

1.2.1 模型描述

設現有N個需要進行戰損任務搶修的單位，保障單位有k個搶修分隊，編號分別為（1，2，...K），每個分隊能夠最多攜帶的搶修資源量為Q，每個待搶修單位上報的資源需求量為ir（i表示第i個待搶修點，且 Qri≤max）。假設待搶修點i和待搶修點j直接的路徑長度為dij，路徑長度是通過兩點之間的坐標來計算的，如待搶修點i的位置坐標為，待搶修點j的位置坐標為yj )，則求解路徑長度的公式為：完成待搶修點i的搶修任務需要的時間為 Ti，且待搶修點i的搶修工作最好在時間窗口[ei，li]內開始，若搶修分隊到達待搶修點i的時間早于ei，則分隊需在i處等待，如果到達時間晚于 li，則會處以一定的懲罰，產生代價。

一些基本的假設：1）目前暫時設置一個搶修保障單位，所有的搶修分隊都是從這里派出，并最后再返回單位；2）每個待搶修點恰好被一個搶修分隊進行搶修保障工作，不會交叉搶修；3）每個搶修分隊的攜帶資源量相同；4）每個待搶修點所需的搶修資源量是已知的[4]。

1.2.2 代價函數

違反時間窗所帶來的代價應該以合適的方式體現出來，避免在進行搶修方案優化時只考慮資源和路徑的優化，而忽略其他的代價。所以用函數的形式來仿真規定的時間窗，這個函數來表示搶修分隊違反規定時間段時的代價。原則就是每一個搶修分隊偏離規定的時間窗越多，其產生的代價也就越大。根據實際情況，代價的多少可能隨著函數曲線增長，本文為了方便計算設置代價隨線性曲線增加。

定義的代價函數表達式如下：

上述公式還可以寫成統一的表達式：

若車輛k在時間窗ei

之前到達待搶修點i，由于統一安排，則分隊會等待，產生的代價為；若搶修分隊在時間窗li之后到達待搶修點i，則搶修任務被延誤，產生延誤的代價為；如果搶修分隊在時間窗內到達，則代價為0[3]。

1.2.3 目標函數

通過上述的分析說明，以任務搶修時產生的總消耗最小化為目標建立靜態模型的目標函數，函數如下：

目標函數表示最小化的總消耗成本。包括兩項：分隊行走路程的消耗成本和所有違反規定時間要求的額外代價消耗。

式（1）表示從保障單位派出搶修分隊數不超過K；

式（2）表示所有待搶修點的需求總量不超過搶修分隊的總物資量；

式（3）表示分隊從待搶修點i到達待搶修點j的時間約束；

式（4）表示整數化的約束，限制只能取0或1；

式（5）表示違反規定時間的額外消耗函數表達式。

1.2.4 參數說明

N：待搶修站點的總數目；

i,j：待搶修點；i，j=（0，l，..，N），i，j=0代表保障單位；

k ：各搶修分隊的編號，k=（1，…，K）；

dij：從搶修點i到搶修點j的行走代價，主要是路程，其中i≠j；

α：分隊行走單位路程的代價；

Q：搶修分隊的最大物資量；

ri：待搶修點i的需求量，且maxdi≤Q；

ei：待搶修點i允許的最早搶修時間；

li：待搶修點i允許的最晚搶修時間；

si：搶修分隊k到達待保障點i時的時刻，其中s0=0；

tij：搶修分隊從待搶修點i到待搶修點j的時間，其中i≠j；

fi：搶修分隊完成待搶修點i的搶修工作所需的時間；

wi：若提前到達待搶修點i則需等待的時間，其中w0=0；

p：分隊提前到達待搶修點等待單位時間的代價；

q：分隊晚于時間窗到達待保障點的單位時候的代價值。

2 算法設計

2.1 編碼解碼

編碼就是遺傳算法用來選擇適當問題模型的解的表達方式，由于遺傳算法的廣泛應用，目前根據不同的問題模型提出了不同的編碼格式，使用比較多的有二進制編碼、實數或整數編碼、字母序列編碼等這幾種。編碼方式的選定取決于實際問題的特點，戰時任務搶修過程優化仿真是一種基于次序優化的問題，為了減少無效解的出現，本文采用序號編碼。比如派出k個搶修分隊，待搶修點為n個，則直接將所有到達的待搶修點以此編碼到一條染色體中，這種使用待搶修點序號排列染色體的編碼方式比較直觀，且保證了每個待搶修點在一次搶修中到達且只到達一次，而且這樣的編碼格式有利于后期的交叉和變異的操作[4]。

解碼是編碼的逆過程，即得到編碼中的值為滿足約束條件的可行解的過程，本文采用的解碼類似路徑構建的過程，將染色體中的基因值按順序插入初始化的路徑中，如果某一基因在插入時導致路徑的一些條件不滿足模型中的約束條件，則開始構造新的路徑，重復上述操作，直到所有的待搶修點都被插入到路徑[4]。

2.2 種群的初始化

種群的規模是會影響優化結果的，當規模較小時，算法的優化性能不太好，而當種群規模較大時，則有較大的時間和空間復雜度。一般對于染色體不大的解設定的種群規模在20-200之間。本文使用隨機生成方法初始化種群，由于編碼時使用整數編碼形式，所以本文采用隨機生成種群規模大小的數目來初始化種群。

2.3 適應度函數

適應度函數一般都是非負的，其值越大越好，個體適應度值越大，表示該個體性能越優良，一般是由目標函數變換得到的。由于本文建立的模型是求最小值，所以把目標函數值的倒數作為個體的適應度值，這樣函數值越小的個體，適應度值也就越大[5]。

2.4 選擇算子

選擇算子是從父代中選擇優良的個體組成新的種群，進行繁殖得到下一代的操作。選擇算子的好壞直接影響了下代種群的優劣，是影響算法優化結果的重要的部分。個體被選中的概率跟其適應度值的大小有關，個體適應度值越大，被選中概率越大。遺傳算法選擇策略有輪盤賭法、錦標賽法等多種，本文采用的是輪盤賭法，即基于適應度比例的選擇策略，個體被選中的概率為，其中Fi為個體i的適應度值；N為種群個體數目。對于父代適應度值本來就很大的個體，可以不經過概率選擇，直接用來繁殖下一代，這樣能夠更進一步的保留種群的優良特性，這就是精英選擇策略。將輪盤賭法融入精英選擇策略，能夠保證最優父代個體順利進行繁殖，提高算法效率[5]。

2.5 交叉算子

交叉算子是將選擇到的兩個個體進行部分染色體交換重組，來產生新的個體。由于模型編碼采用的是分隊序號排列編碼，為了適合其編碼的格式，交叉方法采用父串部分區域交叉的方法。交叉過程如圖1所示。

圖1 部分區域交叉過程圖

2.6 變異算子

本文根據前面部分的設計，采用部分區域倒置法進行變異操作。具體的設計過程是隨機選擇染色體上的兩個變異點，然后將變異點間的基因進行位置倒置，進而得到新的個體[6]。

3 模型求解

以某部實戰演練時各部參加戰斗時的地理位置和戰損搶修時的需求量等為本次仿真優化的原始數據。如表1所示。

表1 各單位的詳細數據

搶修分隊行走單位路程的代價為8，搶修分隊早到等待的代價0.5，晚到的代價1.5。遺傳算法中的各個參數為：種群規模50，交叉概率0.5，變異概率1.5，進化代數為500。

按著上述的實驗數據進行模型求解，使用MATLAB進行10次實驗，得到最優解為4625.85，分隊數為6個，最優解時的進化代數為112代。

實驗結果的路線規劃圖如圖2所示。

圖2 路線規劃圖

由圖2，可以得出優化的路線，如表2所示。

表2 搶修優化路線

圖3 算法收斂情況

圖3是算法運行時的迭代優化情況，可見算法收斂的速度比較快，實驗數據為112代時收斂到最優解，算法性能較好。

4 結論

本文通過對戰時任務搶修的描述，分析了戰時搶修的特點，建立了比較符合實際情況的數學模型，設置了必要的約束條件，使得模型更加符合實際，設計了性能較好的遺傳算法求解模型得到了較為理想的實驗結果，在一定程度上都能輔助決策者制定搶修優化方案。

[1]馬懿，盧昱，陳立云，等.戰時裝備維修保障力量優化調度問題研究[J].計算機工程與應用，2012，8：8-11.

[2]孫寶琛，賈希勝，程中華.戰時裝備維修保障資源優化模型[J].火力與指揮控制，2013，6：159-162.

[3]王銳，李羚偉，郭波，等.一種基于多目標多約束的戰時搶修力量調度[J].兵工自動化，2010，1：34-37.

[4]袁春，郭立濱，雍岐東，等.基于遺傳算法的油料裝備維修保障資源調度研究[J].物流技術，2011，1：148-150.

[5]王煥坤，劉藝，楊宏偉.改進型遺傳算法在戰時維修器材配置中的應用[J].四川兵工學報，2011，11：63-66.

[6]袁爽.改進遺傳算法的鐵路物資應急調度研究與應用[D].蘭州交通大學，2014.

Study on the Optimization of Wartime Repair Process Based on Genetic Algorithm

Wu Zirong，Chen Manqing，Cui Weining
Department of Information Engineering, Academy of Armored Forces Engineering ,Beijing,100072

At present, many of our security units are artificial autonomous decision-making in the process of wartime repair, according to the situation or experience to make resource allocation and path selection, and ultimately form a repair program, which has a large subjective factors, and the decision is not scientific, unreasonable and so on. According to the above conditions, using genetic algorithm to carry out tasks repair process model to solve and get the repair process of total cost and optimizing path and the substitution instance data obtained experimental results. The simulation results show that the optimization of the process of the repair process based on genetic algorithm can be optimized and the optimized path can be obtained.

Genetic algorithm; wartime repair; process optimization

TP3

A

1674-6708（2015）145-0124-04

武子榮，碩士研究生，裝甲兵工程學院信息工程系，計算機仿真技術

陳曼青，副教授，裝甲兵工程學院信息工程系，計算機仿真技術

崔偉寧，講師，裝甲兵工程學院，計算機應用技術