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

武子榮，陳曼青，崔偉寧

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

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

武子榮，陳曼青，崔偉寧

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

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

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

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

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

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

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

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

1.1 戰(zhàn)時(shí)搶修過(guò)程優(yōu)化問(wèn)題描述

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

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

1.2 模型建立

1.2.1 模型描述

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

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

1.2.2 代價(jià)函數(shù)

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

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

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

若車輛k在時(shí)間窗ei

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

1.2.3 目標(biāo)函數(shù)

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

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

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

式（2）表示所有待搶修點(diǎn)的需求總量不超過(guò)搶修分隊(duì)的總物資量；

式（3）表示分隊(duì)從待搶修點(diǎn)i到達(dá)待搶修點(diǎn)j的時(shí)間約束；

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

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

1.2.4 參數(shù)說(shuō)明

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

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

k ：各搶修分隊(duì)的編號(hào)，k=（1，…，K）；

dij：從搶修點(diǎn)i到搶修點(diǎn)j的行走代價(jià)，主要是路程，其中i≠j；

α：分隊(duì)行走單位路程的代價(jià)；

Q：搶修分隊(duì)的最大物資量；

ri：待搶修點(diǎn)i的需求量，且maxdi≤Q；

ei：待搶修點(diǎn)i允許的最早搶修時(shí)間；

li：待搶修點(diǎn)i允許的最晚?yè)屝迺r(shí)間；

si：搶修分隊(duì)k到達(dá)待保障點(diǎn)i時(shí)的時(shí)刻，其中s0=0；

tij：搶修分隊(duì)從待搶修點(diǎn)i到待搶修點(diǎn)j的時(shí)間，其中i≠j；

fi：搶修分隊(duì)完成待搶修點(diǎn)i的搶修工作所需的時(shí)間；

wi：若提前到達(dá)待搶修點(diǎn)i則需等待的時(shí)間，其中w0=0；

p：分隊(duì)提前到達(dá)待搶修點(diǎn)等待單位時(shí)間的代價(jià)；

q：分隊(duì)晚于時(shí)間窗到達(dá)待保障點(diǎn)的單位時(shí)候的代價(jià)值。

2 算法設(shè)計(jì)

2.1 編碼解碼

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

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

2.2 種群的初始化

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

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

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

2.4 選擇算子

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

2.5 交叉算子

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

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

2.6 變異算子

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

3 模型求解

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

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

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

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

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

圖2 路線規(guī)劃圖

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

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

圖3 算法收斂情況

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

4 結(jié)論

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

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

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

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

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

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

[6]袁爽.改進(jìn)遺傳算法的鐵路物資應(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é)院信息工程系，計(jì)算機(jī)仿真技術(shù)

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

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