武子榮，陳曼青，崔偉寧

裝甲兵工程學(xué)院信息工程系，北京 100072

基于遺傳算法的戰(zhàn)時任務(wù)搶修過程優(yōu)化研究

武子榮，陳曼青，崔偉寧

裝甲兵工程學(xué)院信息工程系，北京 100072

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

遺傳算法；戰(zhàn)時搶修；過程優(yōu)化

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

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

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

1 戰(zhàn)時搶修過程優(yōu)化數(shù)學(xué)模型

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

1.1 戰(zhàn)時搶修過程優(yōu)化問題描述

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

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

1.2 模型建立

1.2.1 模型描述

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

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

1.2.2 代價函數(shù)

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

定義的代價函數(shù)表達式如下：

上述公式還可以寫成統(tǒng)一的表達式：

若車輛k在時間窗ei

之前到達待搶修點i，由于統(tǒng)一安排，則分隊會等待，產(chǎn)生的代價為；若搶修分隊在時間窗l(fā)i之后到達待搶修點i，則搶修任務(wù)被延誤，產(chǎn)生延誤的代價為；如果搶修分隊在時間窗內(nèi)到達，則代價為0[3]。

1.2.3 目標函數(shù)

通過上述的分析說明，以任務(wù)搶修時產(chǎn)生的總消耗最小化為目標建立靜態(tài)模型的目標函數(shù)，函數(shù)如下：

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

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

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

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

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

式（5）表示違反規(guī)定時間的額外消耗函數(shù)表達式。

1.2.4 參數(shù)說明

N：待搶修站點的總數(shù)目；

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 算法設(shè)計

2.1 編碼解碼

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

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

2.2 種群的初始化

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

2.3 適應(yīng)度函數(shù)

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

2.4 選擇算子

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

2.5 交叉算子

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

圖1 部分區(qū)域交叉過程圖

2.6 變異算子

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

3 模型求解

以某部實戰(zhàn)演練時各部參加戰(zhàn)斗時的地理位置和戰(zhàn)損搶修時的需求量等為本次仿真優(yōu)化的原始數(shù)據(jù)。如表1所示。

表1 各單位的詳細數(shù)據(jù)

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

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

實驗結(jié)果的路線規(guī)劃圖如圖2所示。

圖2 路線規(guī)劃圖

由圖2，可以得出優(yōu)化的路線，如表2所示。

表2 搶修優(yōu)化路線

圖3 算法收斂情況

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

4 結(jié)論

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

[1]馬懿，盧昱，陳立云，等.戰(zhàn)時裝備維修保障力量優(yōu)化調(diào)度問題研究[J].計算機工程與應(yīng)用，2012，8：8-11.

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

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

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

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

[6]袁爽.改進遺傳算法的鐵路物資應(yīng)急調(diào)度研究與應(yīng)用[D].蘭州交通大學(xué)，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

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

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

崔偉寧，講師，裝甲兵工程學(xué)院，計算機應(yīng)用技術(shù)