基于改進(jìn)遺傳算法的戰(zhàn)備器材倉庫選址優(yōu)化問題研究

汪琳，何成銘

（陸軍裝甲兵學(xué)院 裝備保障與再制造系，北京 100072）

0 引 言

陸軍平時器材使用通常由現(xiàn)有器材倉庫進(jìn)行保障，而戰(zhàn)時器材保障不同于平時保障的固定性。戰(zhàn)時，陸軍器材保障是陸軍部隊(duì)作戰(zhàn)的重要支撐，對整個戰(zhàn)爭進(jìn)程有著重要影響。所以，器材倉庫的選址問題就顯得尤為重要。臨時應(yīng)急器材儲備庫的位置選得好，不僅可以降低運(yùn)輸成本，更重要的是在戰(zhàn)時可以充分發(fā)揮倉庫物資的時效性，使器材倉庫的戰(zhàn)術(shù)作用發(fā)揮更加明顯。

由于野戰(zhàn)地點(diǎn)分布隨機(jī)，與現(xiàn)有器材倉庫的距離也并不固定，也就是說，戰(zhàn)時僅靠現(xiàn)有的器材倉庫無法滿足器材保障的需求，必須開設(shè)臨時器材倉庫以實(shí)現(xiàn)對戰(zhàn)時某一區(qū)域的戰(zhàn)場器材需求進(jìn)行及時、準(zhǔn)確、不間斷的保障，確保戰(zhàn)時器材供應(yīng)保障高效準(zhǔn)確、及時穩(wěn)定。因此，在戰(zhàn)時環(huán)境下，臨時器材倉庫選址問題就很有必要進(jìn)行研究解決。

過去的研究中，關(guān)于倉庫選址問題的解決方法不多。張帥等人依據(jù)微分算法選擇庫區(qū)，引入層次分析法和模糊綜合評判建立選址指標(biāo)體系和建立野戰(zhàn)器材倉庫選址模型，對倉庫位置進(jìn)行優(yōu)化配置。羅耀波等人利用改進(jìn)的遺傳算法解決了帶退貨和軟時間窗的地方物流多倉庫路徑-選址問題。苑德春等人運(yùn)用四元評價（DFGH）理論分析了影響交通戰(zhàn)備器材儲備倉庫選址的主要因素，并建立了相應(yīng)模型。嚴(yán)駿等人提出了一種維修器材倉庫選址模型的魯棒優(yōu)化方法，對定點(diǎn)器材倉庫選址的穩(wěn)定性進(jìn)行了論證。

在對倉庫選址進(jìn)行評價方面，彭飛等人通過建立評價體系，進(jìn)一步利用模糊綜合評價法研究了倉庫選址完成之后的評價問題。邵帥等人還在評價過程中引入了正態(tài)云的概念，對于解決倉庫選址評估問題中的隨機(jī)性和模糊性問題發(fā)揮了一定的作用。辛昱等人提出基于AHP和模糊物元分析法（FMEA）對物流中心選址方案進(jìn)行優(yōu)度評價。

綜合上述研究，不難發(fā)現(xiàn)過去的研究大多數(shù)局限于簡單的定量方法，其中模糊綜合評價法和AHP的使用尤為頻繁，且對于部隊(duì)?wèi)?zhàn)時倉庫選址的研究少之又少。本文在對遺傳算法進(jìn)行改進(jìn)的基礎(chǔ)上，對戰(zhàn)時器材倉庫選址的定量優(yōu)化進(jìn)行了有益探索。

1 陸軍戰(zhàn)時裝備器材選址問題

1.1 問題描述

本文通過設(shè)定假定條件，在倉庫選址問題上運(yùn)用改進(jìn)遺傳算法在待選戰(zhàn)時倉庫地址中選取最優(yōu)點(diǎn)建立臨時器材倉庫。

器材倉庫選址問題可描述為：已知個作戰(zhàn)點(diǎn)（，，…，B）的地理位置（，），（，），…，（x，y）和個（，，…，W）可供選擇建立臨時倉庫的待選點(diǎn)位置（，），（，），…，（a，b），運(yùn)輸車從某一倉庫待選點(diǎn)出發(fā)，將所有作戰(zhàn)點(diǎn)遍歷一次，并回到原待選點(diǎn)，如何選點(diǎn)能夠使得所走路徑最短。

為了便于研究，現(xiàn)做出如下假設(shè)：

（1）出于戰(zhàn)時器材倉庫的臨時性，單一倉庫儲存的器材種類可能不能滿足所有戰(zhàn)場需求，需要至少建立2個或以上的臨時器材倉庫，本文假設(shè)從5個待選地點(diǎn)中選擇2個建立倉庫即可滿足需求；且為保障安全性，5個待選位置均處于戰(zhàn)場后方，最終選取的2個器材倉庫必須保持一定距離；

（2）凡是某一器材倉庫中存在某種類型的器材，則該器材必然能滿足所有戰(zhàn)場的某次器材需求；

（3）在選址的條件考慮中，器材通過陸路運(yùn)輸，僅考慮路途的遠(yuǎn)近問題，認(rèn)為各待選點(diǎn)的自然地理?xiàng)l件均無大差別，不考慮選址點(diǎn)的自然環(huán)境；

（4）由于戰(zhàn)時環(huán)境多變，無法隨時保障各個戰(zhàn)場與臨時器材倉庫之間、各器材倉庫互相之間信息通信及時、順暢。因此，假設(shè)每次器材運(yùn)輸車出發(fā)前往各作戰(zhàn)點(diǎn)時，所承載的器材數(shù)必然能夠滿足所有作戰(zhàn)點(diǎn)的需求，且器材運(yùn)輸車每次出發(fā)必經(jīng)過所有作戰(zhàn)點(diǎn)。

1.2 建立模型

將一個倉庫待選點(diǎn)和所有作戰(zhàn)點(diǎn)記為頂點(diǎn)集，各頂點(diǎn)間的邊集記為，則和組成圖=(,)。各頂點(diǎn)間的距離(V,V)已知，設(shè)：

其中f表示遍歷一次的總路徑，(V,V)表示從第個作戰(zhàn)點(diǎn)到達(dá)第+1個作戰(zhàn)點(diǎn)的距離，表示臨時倉庫。式（1）、式（2）表示對每個點(diǎn)而言，有且僅有一條邊進(jìn)和一條邊出；式（3）則保證了沒有任何子回路解的產(chǎn)生。

2 利用改進(jìn)遺傳算法求解戰(zhàn)時倉庫選址問題

2.1 遺傳算法

遺傳算法的基本思想是根據(jù)問題的目標(biāo)函數(shù)構(gòu)造一個適值函數(shù)，對一個由多個解（每個解對應(yīng)一個染色體）構(gòu)成的種群進(jìn)行評估、選擇、遺傳運(yùn)算，經(jīng)多代繁殖，獲得適應(yīng)值最好的個體作為問題的最優(yōu)解。其通常包含“產(chǎn)生一個初始種群”“根據(jù)問題的目標(biāo)函數(shù)構(gòu)造適值函數(shù)”“根據(jù)適應(yīng)值的好壞不斷選擇和繁殖”以及“若干代后得到適應(yīng)值最好的個體為最優(yōu)解”這四個大步驟。

2.2 求解思路和流程

本文中求解器材倉庫選址最優(yōu)方案的總體思路是，在計算過程中，針對每一個待選址點(diǎn)，將其等同于各個作戰(zhàn)點(diǎn)，相當(dāng)于從原來的個點(diǎn)轉(zhuǎn)為從+1個點(diǎn)中去尋找最優(yōu)路線，從而將問題簡化為多個TSP問題。利用遺傳算法求解出最優(yōu)路徑，以此作為從該待選址出發(fā)，運(yùn)輸車走遍所有作戰(zhàn)點(diǎn)，并返回原待選址點(diǎn)的最短路徑；將每個待選址點(diǎn)都求出最短路徑后，對比選出最優(yōu)者和次優(yōu)者作為最終器材倉庫的選址位置。圖1為算法流程圖。

圖1 算法流程圖

算法基本步驟如下：

（1）隨機(jī)生成個倉庫待選址點(diǎn)；

（2）生成初始解種群：利用initPop()函數(shù)生成隨機(jī)初始種群；

（3）利用適應(yīng)度函數(shù)fitness()計算種群中每個染色體的適應(yīng)度值，并按適應(yīng)度值進(jìn)行排序，計算每個染色體的累計概率；

（4）根據(jù)累計概率選擇染色體進(jìn)入新種群；

（5/6）分別按照交叉、變異概率，在新種群中隨機(jī)選擇兩個解，進(jìn)行相應(yīng)操作；并決定是否將交叉、變異產(chǎn)生的新染色體替換入新種群；

（7）在新群體中選擇適應(yīng)度值最低的解進(jìn)行進(jìn)化逆轉(zhuǎn)，并決定是否將逆轉(zhuǎn)產(chǎn)生的新染色體替換入新種群；

（8）檢驗(yàn)是否達(dá)到終止條件，若未達(dá)到，則轉(zhuǎn)步驟3；否則，得出最優(yōu)解，并從不同待選址點(diǎn)所對應(yīng)的數(shù)個最優(yōu)解中選出最優(yōu)和次優(yōu)所對應(yīng)的待選址點(diǎn)作為最終的選址點(diǎn)。

2.3 算法詳細(xì)設(shè)計

本文編碼方式為順序編碼，即用1到的自然數(shù)來編碼，其中“0”表示臨時器材倉庫的位置；1到則表示可能發(fā)生戰(zhàn)爭的作戰(zhàn)地點(diǎn)。圖2表示了倉庫待選點(diǎn)與作戰(zhàn)點(diǎn)總數(shù)的染色體編碼的一種情況示例。

圖2 染色體編碼示意圖

2.3.2 種群初始化

在完成染色體編碼之后，必須產(chǎn)生一個初始種群作為起始解。本文選擇從含有120個隨機(jī)個體的群體中尋找最優(yōu)解進(jìn)入初始種群，組成含80個染色體的初始解空間。

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

將適應(yīng)度函數(shù)設(shè)置為自“倉庫”出發(fā)，逐一、無重復(fù)經(jīng)過所有“作戰(zhàn)點(diǎn)”，再回到“倉庫”的總距離的倒數(shù)，即：

其中D表示從“作戰(zhàn)點(diǎn)”k到k的距離，表示“倉庫點(diǎn)”。優(yōu)化的目標(biāo)就是選擇適應(yīng)度函數(shù)值盡可能大的染色體，適應(yīng)值越大的染色體越優(yōu)質(zhì)，反之越劣質(zhì)。給出了染色體適應(yīng)值計算的偽代碼為：

2.3.4 選擇策略

其次，一個場景內(nèi)，需要各式各樣，年代和狀況各有不同的建筑，這對于保證區(qū)域的地價水平有重要作用。區(qū)域內(nèi)需要有大型企業(yè)對產(chǎn)業(yè)起到引領(lǐng)作用，因此需要高端商業(yè)區(qū)域；同時區(qū)域也需要考慮小型企業(yè)、個人工作室的需求，因此需要相對老舊的房屋場所。同樣多樣化的房屋可以保證地租水平的穩(wěn)定，減少居民必要支出，釋放消費(fèi)潛力。在許多對文化創(chuàng)意產(chǎn)業(yè)的研究中都發(fā)現(xiàn)，地租水平是影響文化創(chuàng)意產(chǎn)業(yè)發(fā)展的重要因素，差異化的地租，對建立多樣化人群的社交網(wǎng)絡(luò)有重要影響。

對于染色體，設(shè)其適應(yīng)值為F，種群規(guī)模為NP，則該染色體的選擇概率P可表示為

2.3.5 改進(jìn)遺傳算子

對于交叉算子，創(chuàng)新性的提出了同基因交換方式進(jìn)行交叉。對于兩個選定的染色體和，隨機(jī)選取兩個切點(diǎn)和（＞0，＜），逐個比較兩切點(diǎn)之間的子串，進(jìn)行同基因交換。以為例，若其子串第一個位置的基因在的子串中能找到相同基因且處于r（r＜）位置，則改變中該基因的位置為r，并將原先處于r位置的基因調(diào)整至子串的第一個位置；若無法找到相同基因，則不改變該基因的位置。同樣的，將與未進(jìn)行交叉操作前的進(jìn)行同基因交換。若產(chǎn)生的新染色體優(yōu)于父輩，則將其替換入新種群。圖3為染色體交叉示例，經(jīng)過同基因交換后的染色體不會產(chǎn)生不合法編碼。

圖3 同基因交換示意圖

下文給出了改進(jìn)遺傳算法交叉策略與變異策略的偽代碼：

%對染色體B進(jìn)行交叉，操作同上。

變異策略采取隨機(jī)選取某一染色體的兩個位置和，將兩位置上的值進(jìn)行互換：

2.3.6 進(jìn)化逆轉(zhuǎn)操作

為改善遺傳算法的局部搜索能力，在選擇、交叉、變異之后引進(jìn)連續(xù)多次的進(jìn)化逆轉(zhuǎn)操作。

在串中隨機(jī)選擇兩點(diǎn)（兩點(diǎn)之間稱為逆轉(zhuǎn)區(qū)域），再將逆轉(zhuǎn)區(qū)域內(nèi)的子串按反序插入原位置中。如圖4所示，若新生成的染色體適應(yīng)度優(yōu)于原染色體，則進(jìn)行逆轉(zhuǎn)操作（即進(jìn)化），否則，不進(jìn)行逆轉(zhuǎn)。

圖4 進(jìn)化逆轉(zhuǎn)示意圖（r1=2，r2=6）

進(jìn)化逆轉(zhuǎn)操作的偽代碼為：

2.3.7 停止準(zhǔn)則

當(dāng)尋優(yōu)迭代次數(shù)達(dá)到最大遺傳代數(shù)MAXGEN時，尋優(yōu)結(jié)束。

當(dāng)整個算法循環(huán)次數(shù)達(dá)到總的待選倉庫點(diǎn)數(shù)時，算法結(jié)束并輸出最優(yōu)和次優(yōu)倉庫位置。

3 實(shí)例分析

某戰(zhàn)區(qū)東南沿海多點(diǎn)同時發(fā)生敵方入侵事件，多地局部小規(guī)模戰(zhàn)爭一觸即發(fā)。臨時器材倉庫選址建設(shè)問題迫在眉睫。

目前，已初步統(tǒng)計出戰(zhàn)斗極有可能發(fā)生的14處位置坐標(biāo)，如表1所示。根據(jù)前期偵查，發(fā)現(xiàn)后方有5處位置可供建設(shè)臨時器材倉庫，如表2所示。目前需要以最快的速度確定2個倉庫待建點(diǎn)，以進(jìn)行臨時器材倉庫的搭建。

表1 可能的作戰(zhàn)地點(diǎn)位置坐標(biāo)

表2 臨時倉庫待選點(diǎn)位置坐標(biāo)

染色體編碼為從0-14-0的順序編碼（0表示倉庫點(diǎn)），表示器材保障路徑為從倉庫點(diǎn)出發(fā)，遍歷所有作戰(zhàn)點(diǎn)后返回倉庫。

3.1 參數(shù)設(shè)置

由于在不同種群大小、尋優(yōu)代數(shù)以及交叉變異概率下，改進(jìn)遺傳算法的計算速率有所不同，甚至在待選倉庫點(diǎn)較多的情況下，不合適的計算參數(shù)為得到最優(yōu)解可能累積產(chǎn)生極大計算負(fù)擔(dān)。因此，本文為改進(jìn)遺傳算法設(shè)置可能的參數(shù)取值如表3所示，以便從中選出可能的最優(yōu)參數(shù)選擇。

表3 算法參數(shù)取值

3.2 算法可行性分析

在表3給出的具體算法參數(shù)下，可利用改進(jìn)遺傳算法得到器材倉庫選址的最優(yōu)點(diǎn)和次優(yōu)點(diǎn)，結(jié)果如表4所示。結(jié)果顯示，采取基于同基因交叉的改進(jìn)遺傳算法時，在合適的參數(shù)取值下收斂速度能夠明顯優(yōu)于傳統(tǒng)遺傳算法。并且，當(dāng)參數(shù)取值為第2組時，結(jié)果最優(yōu)。

表4 倉庫選址結(jié)果

4 結(jié) 論

戰(zhàn)時器材倉庫選址問題面臨作戰(zhàn)任務(wù)的重要性和器材供應(yīng)的緊迫性，在通過以定性為主的方法（如模糊綜合評價法）得出幾個待選址點(diǎn)后，需要快速進(jìn)行更準(zhǔn)確的選擇。本文通過改進(jìn)遺傳算法，對交叉算子提出了同基因交叉的改進(jìn)思路，給出了戰(zhàn)時倉庫精確選址的一種解法，為未來戰(zhàn)場應(yīng)急倉庫選址提供可行途徑，為提升戰(zhàn)場器材保障效率提供了參考依據(jù)。