基于改進遺傳算法的戰備器材倉庫選址優化問題研究

汪琳，何成銘

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

0 引 言

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

由于野戰地點分布隨機，與現有器材倉庫的距離也并不固定，也就是說，戰時僅靠現有的器材倉庫無法滿足器材保障的需求，必須開設臨時器材倉庫以實現對戰時某一區域的戰場器材需求進行及時、準確、不間斷的保障，確保戰時器材供應保障高效準確、及時穩定。因此，在戰時環境下，臨時器材倉庫選址問題就很有必要進行研究解決。

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

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

綜合上述研究，不難發現過去的研究大多數局限于簡單的定量方法，其中模糊綜合評價法和AHP的使用尤為頻繁，且對于部隊戰時倉庫選址的研究少之又少。本文在對遺傳算法進行改進的基礎上，對戰時器材倉庫選址的定量優化進行了有益探索。

1 陸軍戰時裝備器材選址問題

1.1 問題描述

本文通過設定假定條件，在倉庫選址問題上運用改進遺傳算法在待選戰時倉庫地址中選取最優點建立臨時器材倉庫。

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

為了便于研究，現做出如下假設：

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

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

（3）在選址的條件考慮中，器材通過陸路運輸，僅考慮路途的遠近問題，認為各待選點的自然地理條件均無大差別，不考慮選址點的自然環境；

（4）由于戰時環境多變，無法隨時保障各個戰場與臨時器材倉庫之間、各器材倉庫互相之間信息通信及時、順暢。因此，假設每次器材運輸車出發前往各作戰點時，所承載的器材數必然能夠滿足所有作戰點的需求，且器材運輸車每次出發必經過所有作戰點。

1.2 建立模型

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

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

2 利用改進遺傳算法求解戰時倉庫選址問題

2.1 遺傳算法

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

2.2 求解思路和流程

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

圖1 算法流程圖

算法基本步驟如下：

（1）隨機生成個倉庫待選址點；

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

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

（4）根據累計概率選擇染色體進入新種群；

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

（7）在新群體中選擇適應度值最低的解進行進化逆轉，并決定是否將逆轉產生的新染色體替換入新種群；

（8）檢驗是否達到終止條件，若未達到，則轉步驟3；否則，得出最優解，并從不同待選址點所對應的數個最優解中選出最優和次優所對應的待選址點作為最終的選址點。

2.3 算法詳細設計

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

圖2 染色體編碼示意圖

2.3.2 種群初始化

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

2.3.3 適應度函數

將適應度函數設置為自“倉庫”出發，逐一、無重復經過所有“作戰點”，再回到“倉庫”的總距離的倒數，即：

其中D表示從“作戰點”k到k的距離，表示“倉庫點”。優化的目標就是選擇適應度函數值盡可能大的染色體，適應值越大的染色體越優質，反之越劣質。給出了染色體適應值計算的偽代碼為：

2.3.4 選擇策略

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

對于染色體，設其適應值為F，種群規模為NP，則該染色體的選擇概率P可表示為

2.3.5 改進遺傳算子

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

圖3 同基因交換示意圖

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

%對染色體B進行交叉，操作同上。

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

2.3.6 進化逆轉操作

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

在串中隨機選擇兩點（兩點之間稱為逆轉區域），再將逆轉區域內的子串按反序插入原位置中。如圖4所示，若新生成的染色體適應度優于原染色體，則進行逆轉操作（即進化），否則，不進行逆轉。

圖4 進化逆轉示意圖（r1=2，r2=6）

進化逆轉操作的偽代碼為：

2.3.7 停止準則

當尋優迭代次數達到最大遺傳代數MAXGEN時，尋優結束。

當整個算法循環次數達到總的待選倉庫點數時，算法結束并輸出最優和次優倉庫位置。

3 實例分析

某戰區東南沿海多點同時發生敵方入侵事件，多地局部小規模戰爭一觸即發。臨時器材倉庫選址建設問題迫在眉睫。

目前，已初步統計出戰斗極有可能發生的14處位置坐標，如表1所示。根據前期偵查，發現后方有5處位置可供建設臨時器材倉庫，如表2所示。目前需要以最快的速度確定2個倉庫待建點，以進行臨時器材倉庫的搭建。

表1 可能的作戰地點位置坐標

表2 臨時倉庫待選點位置坐標

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

3.1 參數設置

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

表3 算法參數取值

3.2 算法可行性分析

在表3給出的具體算法參數下，可利用改進遺傳算法得到器材倉庫選址的最優點和次優點，結果如表4所示。結果顯示，采取基于同基因交叉的改進遺傳算法時，在合適的參數取值下收斂速度能夠明顯優于傳統遺傳算法。并且，當參數取值為第2組時，結果最優。

表4 倉庫選址結果

4 結 論

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