基于遺傳算法的裝備采購決策優(yōu)化研究

雷紹雍，劉靖旭

(1.戰(zhàn)略支援部隊信息工程大學(xué)研究生院，河南 鄭州450001；2. 戰(zhàn)略支援部隊信息工程大學(xué)地理空間學(xué)院，河南 鄭州450001)

1 引言

裝備采購，指軍隊選擇購買軍事裝備的有關(guān)活動。它是裝備建設(shè)的重要內(nèi)容，是裝備從提出需求到形成作戰(zhàn)能力之前的整個生成過程中的最后一個環(huán)節(jié)。這項工作的成敗，直接關(guān)系到裝備購置費能否發(fā)揮其應(yīng)有的效益，關(guān)系到部隊裝備的質(zhì)量，在軍隊現(xiàn)代化建設(shè)中占有重要的地位[1]。許多裝備采購決策問題都具有多目標(biāo)、多約束、規(guī)模較大、結(jié)構(gòu)復(fù)雜等特點，傳統(tǒng)的依賴決策者閱歷、知識和偏好的經(jīng)驗型決策已經(jīng)不能滿足裝備采購的需要，必須分析采購決策的特點，利用信息手段、智能算法構(gòu)建決策模型，對信息繁雜、內(nèi)容豐富、目標(biāo)多元的裝備采購決策問題作出精確判斷和科學(xué)定量，運用智能優(yōu)化算法對裝備采購決策問題進(jìn)行求解，實現(xiàn)裝備采購保障的優(yōu)化決策。

目前，在裝備采購決策方面，國內(nèi)外學(xué)者有一定的研究，主要可以分為以下幾類：一是線性權(quán)重法，它的思想是按照一個選擇準(zhǔn)則配備一個權(quán)重，各項選擇準(zhǔn)則的得分與相應(yīng)權(quán)重的乘積的和是該供應(yīng)商定量結(jié)果，最后，對各供應(yīng)商定量選擇結(jié)果進(jìn)行比較得出最佳供應(yīng)商。常見的線性權(quán)重法有德爾菲法、熵值法、分類比較法、蒙特卡洛法等。比如文獻(xiàn)[2]、[3]都運用了德爾菲法對裝備采購決策進(jìn)行了分析研究，文獻(xiàn)[4]Gregory 運用分類比較法給出供應(yīng)商每個準(zhǔn)則的基本判斷，然后計算供應(yīng)商的總積分；文獻(xiàn)[5]、[6]采用的蒙特卡洛法,建立了多屬性決策模型,并給出了求解方法。此方法局限性在于只能解決單目標(biāo)決策問題，對于多目標(biāo)決策想應(yīng)用此方法必須先轉(zhuǎn)化為單目標(biāo)決策問題，而上述研究并沒有給出多目標(biāo)決策如何轉(zhuǎn)化成單目標(biāo)決策的方法。二是綜合成本法，主要內(nèi)容是對符合條件要求的供應(yīng)商的采購報價進(jìn)行比較，價格低的供應(yīng)商為最佳供應(yīng)商。比如Timmerman[7]通過計算各分項占總成本的百分比，來確定最終供應(yīng)商；Roodhooft 和Konings[8]則提出了ABC成本法，通過明確采購的主要矛盾，分清重點與一般，有區(qū)別地計算直接成本和間接成本，最終對比總成本來確定供應(yīng)商。而在現(xiàn)實裝備采購中并不僅僅追求低成本，決策屬性中裝備安全性、可靠性以及裝備運達(dá)的及時性等要素同樣相當(dāng)重要，所以成本法對于裝備采購決策并不完全適應(yīng)。三是數(shù)學(xué)規(guī)劃法，包括線性規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃，混合規(guī)劃等，其局限性在于對問題性質(zhì)有著一些特殊要求，大大限制了方法的應(yīng)用范圍，而且決策變量局限于一個連續(xù)的空間內(nèi)，當(dāng)出現(xiàn)非凸集時不一定能求得最優(yōu)解。如文獻(xiàn)[9]提出了模糊隨機動態(tài)規(guī)劃研究模型，利用隨機數(shù)模擬方法進(jìn)行求解；文獻(xiàn)[10]針對多屬性多階段決策問題，運用極大熵原理建立多目標(biāo)優(yōu)化模型，利用拉格朗日乘子法進(jìn)行求解；文獻(xiàn)[11]利用臨界值策略給出了凸情形下該類問題的一種解法。

裝備采購決策核心就是供應(yīng)商評選，這是一個多準(zhǔn)則決策問題。文獻(xiàn)[12]采用模糊分析法對醫(yī)療設(shè)備供應(yīng)商進(jìn)行排序，使其與理想解相似。文獻(xiàn)[13]建立了一個猶豫模糊集模型用于選擇供應(yīng)商。文獻(xiàn)[14]利用三角模糊信息對供應(yīng)商績效進(jìn)行了評價。文獻(xiàn)[15]采用改進(jìn)的直覺模糊優(yōu)次排序方法解決了供應(yīng)商選擇問題。文獻(xiàn)[16]采用一種綜合的多準(zhǔn)則決策方法對綠色供應(yīng)商進(jìn)行評價。文獻(xiàn)[17]分析了供應(yīng)商選擇的失敗風(fēng)險、數(shù)量和業(yè)務(wù)量折扣。文獻(xiàn)[18]提出了一種新的具有兩級準(zhǔn)則的混合MCDM方法來尋找最優(yōu)供應(yīng)商。文獻(xiàn)[19]提出了一種結(jié)合AHP和TOPSIS的混合模型來選擇最合適的供應(yīng)商。文獻(xiàn)[20]提出了不同決策目標(biāo)下受資金約束零售商在采購策略上的差異性。文獻(xiàn)[21]提出了基于商業(yè)信用的供應(yīng)商選擇策略。文獻(xiàn)[22]針對集團(tuán)采購供應(yīng)鏈中信息共享的協(xié)調(diào)作用展開研究，從信息共享角度提出供應(yīng)商選擇的優(yōu)化策略。

本文將裝備采購問題轉(zhuǎn)化為指派問題，構(gòu)建多約束條件下的多目標(biāo)模糊指派模型，該模型能夠很好的彌補上述方法的局限性。近年來，智能算法常被用來解決多目標(biāo)決策優(yōu)化問題，由于遺傳算法具有群體搜索的特性，具備自組織、自適應(yīng)、可擴展和自學(xué)習(xí)性等特點，以目標(biāo)函數(shù)作為搜索信息，不需要詳細(xì)的函數(shù)解析式，所以本文選擇一種改進(jìn)的遺傳算法對該模型進(jìn)行求解，并給出了算例及仿真示例結(jié)果。

2 問題描述及數(shù)學(xué)建模

實際裝備采購活動可以抽象為：從m個裝備供應(yīng)商采購n種裝備(m≥ n)，考慮L個約束條件(比如采購成本不能超過采購預(yù)算；采購任務(wù)有時限要求等)，實現(xiàn)P個目標(biāo)(如價格低廉，可靠性高，安全性好等)的綜合效益最大問題。此類問題其實可以歸為多約束條件下的多目標(biāo)模糊指派問題[23-24]。

(1)

xij=0,1i=1，2，…m;j=1，2，…，n

j=1，2，…，n；k=1，2，…，p

(2)

對于多目標(biāo)優(yōu)化問題，一般采用的方法是將目標(biāo)進(jìn)行整合轉(zhuǎn)化為單目標(biāo)最優(yōu)化問題，具體步驟如下：

(3)

(4)

上式中，E(ckmax)和E(ckmin)表示矩陣E(Ck)中的整體期望值的最大和最小值。從而得到在目標(biāo)k下屬性值對優(yōu)的隸屬矩陣：

(5)

(6)

至此，多目標(biāo)非平衡指派問題數(shù)學(xué)模型就轉(zhuǎn)化為：

i=1，2，…，m；j=1，2，…，n

(7)

j=1,2,…,n

(8)

求解非平衡指派問題的數(shù)學(xué)模型一般將其等價轉(zhuǎn)化為平衡指派問題進(jìn)行處理，也就是添加m-n件虛擬裝備，湊成m件裝備。虛擬裝備是不存在的，其產(chǎn)生的效益值為0，因此其不會改變問題的實質(zhì)。擴展后的合成效益矩陣和約束矩陣分別變?yōu)镼、S，則：

對應(yīng)的模型就變?yōu)椋?/p>

(9)

xij=0,1，i,j=1,2,…m

3 基于遺傳算法的問題求解

3.1 遺傳算法的描述

遺傳算法[25-27]是將問題的解編碼為“染色體”，組成編碼的元素稱為“基因”。在算法迭代過程中，按照“適者生存”的規(guī)律，選取適應(yīng)度高的染色體進(jìn)行復(fù)制，并對它們進(jìn)行雜交和變異的操作，產(chǎn)生出生存能力更強的新染色體群。通過這樣不停反復(fù)的進(jìn)化，直到產(chǎn)生出生命力最強的染色體產(chǎn)生為止，這個生命力最強的染色體就是問題的最優(yōu)解。

遺傳算法執(zhí)行的基本流程如下：

Step1：編碼。

Step2：種群初始化。

Step3：適應(yīng)度計算。一般將目標(biāo)函數(shù)值作為個體的適應(yīng)度函數(shù)。

Step4：選擇。計算種群中每個個體的適應(yīng)度，選取其中適應(yīng)度較高的一些個體作為種群。

Step5：交叉。在種群個體之間進(jìn)行交叉操作，得到新一代種群。

Step6：變異。在新群體中選取少量個體進(jìn)行變異操作。

Step7：判斷是否滿足終止條件，滿足則輸出最優(yōu)解，否則跳到執(zhí)行Step3。

圖1 算法基本流程圖

3.2 遺傳算法設(shè)計

遺傳算法本身也有一些缺陷，主要表現(xiàn)為快要接近最優(yōu)解時在最優(yōu)解附近左右擺動，收斂較慢；容易得到結(jié)果是局部最優(yōu)解而不是全局最優(yōu)解。結(jié)合實際問題，本文對基本遺傳算法進(jìn)行了優(yōu)化改進(jìn)，

詳細(xì)步驟如下：

第一步：編碼。這里通過符號對基因進(jìn)行編碼，染色體串長度為需采購的裝備套數(shù)m,每個基因就代表一個目標(biāo)，等位基因是提供裝備的供應(yīng)商，這樣每一個染色體就代表一種分配方案。例如，某染色體串為“423615”表示共需采購6套裝備，第1套裝備從供貨商4采購，第2套裝備從供貨商2采購，依次類推其余目標(biāo)。

第二步：種群的初始化。首先確定種群規(guī)模和最大遺傳代數(shù)，而后采取適當(dāng)?shù)姆椒ù_定符合要求的初始種群。

第三步：適應(yīng)度值計算。針對裝備采購的遺傳算法模型，適應(yīng)度值為每個基因個體矩陣與效益矩陣q、s中相對應(yīng)單元乘積的最大值，其中基因個體矩陣中基因值為行標(biāo)、基因位為列標(biāo)。

第四步：選擇。每次一個代內(nèi)求得的最優(yōu)解，可以直接進(jìn)入下一代的群體中，其余個體按照“輪盤賭”方法進(jìn)行選擇，并參加交叉與變異。個體的選擇概率Pi為：

(10)

式中，fi表示適應(yīng)度,i=1，2，…，n。

第七步：按照終止條件判斷輸出結(jié)果，如果滿足終止條件則輸出最優(yōu)解，否則跳到第三步。

4 仿真驗證

4.1 示例仿真

按照演習(xí)任務(wù)需要，急需采購三種裝備，其中A裝備83套，B裝備31套，C裝備52套；從裝備采購信息平臺里選出5家優(yōu)秀供應(yīng)商參與此次競標(biāo)采購，各公司關(guān)于三種裝備單套報價如表1；同時，根據(jù)各供應(yīng)商競標(biāo)文件的陳述，綜合考慮供應(yīng)商規(guī)模、資質(zhì)、業(yè)界地位以及產(chǎn)品市場占有率等各方面因素，由專家組以模糊數(shù)的形式給出從各供應(yīng)商采購裝備的時間、質(zhì)量、性能如表2、3、4所示。要求此次采購任務(wù)48小時內(nèi)完成，采購金額不能超過500萬，力求最佳質(zhì)量和性能，假定價格、時間、質(zhì)量和性能等權(quán)重。

表1 供應(yīng)商對各裝備的報價(單位：萬元/套)

表2 供應(yīng)商送達(dá)裝備的耗時(單位：小時)

表3 供應(yīng)商提供裝備的質(zhì)量(百分?jǐn)?shù)表示)

表4 供應(yīng)商提供裝備的性能(百分?jǐn)?shù)表示)

設(shè)定種群規(guī)模為50，最大遺傳代數(shù)為50，用MATLAB2016進(jìn)行求解，得出目標(biāo)從第五代開始收斂于1.007，最優(yōu)解為34251，即從供貨商3采購A裝備，從供貨商4采購B裝備，從供貨商2采購C裝備，其余2個供應(yīng)商為虛擬任務(wù)，無現(xiàn)實意義。仿真結(jié)果見圖2。

圖2 仿真結(jié)果圖Fig.2 The initial distribution map

由仿真結(jié)果可以看出，僅用了5次迭代，耗時0.237秒，就可以得出函數(shù)最優(yōu)解，證明遺傳算法在上述裝備采購問題中應(yīng)用效果較好，具備收斂速度快和較好的全局搜索能力，驗證了該算法的有效性和實用性，能夠滿足決策的實時性要求，可以為裝備采購決策提供依據(jù)。

4.2 算法對比實驗

匈牙利算法是求解指派問題的一種經(jīng)典算法。本實驗針對上述示例，逐步增加供應(yīng)商數(shù)量(m)和采購裝備種類(n)，分別運用遺傳算法和匈牙利算法進(jìn)行求解，并作出對比。

實驗中包含20個示例，實驗環(huán)境為一臺3.20 GHz AMD Ryzen 5 1600 Six-core Processor處理器、16GB內(nèi)存的計算機，MATLAB2016軟件。算法實驗結(jié)果如表5。從表中可以看到，遺傳算法找到最優(yōu)解的效率總是優(yōu)于匈牙利算法，而且隨著供應(yīng)商數(shù)量和采購裝備種類的不斷增加，匈牙利算法所需的時間呈指數(shù)增長，而遺傳算法的求解時間遠(yuǎn)遠(yuǎn)小于匈牙利算法，這充分證明了遺傳算法的優(yōu)越性。因此，針對本文所提問題及模型，遺傳算法的求解效率要遠(yuǎn)遠(yuǎn)優(yōu)于匈牙利算法。

表5 指派問題實驗結(jié)果

5 結(jié)語

本文根據(jù)裝備采購問題，構(gòu)建了多約束條件下的多目標(biāo)模糊指派模型。同時,詳細(xì)闡述了數(shù)學(xué)建模過程，并設(shè)計出遺傳算法對該模型進(jìn)行求解。最后通過案例驗證和算法對比實驗，證明該算法收斂速度快，容易得出最優(yōu)解，在實際問題中應(yīng)用效果較好，對裝備采購決策優(yōu)化具有較高實用價值，同時該模型對構(gòu)建與求解其它指派問題，也有一定的參考價值。