基于改進的粒子群算法求解供應鏈網絡均衡問題

馬 斌， 吳澤忠

(成都信息工程大學 應用數學學院，四川 成都 610225)

0 引言

供應鏈網絡是一個復雜的動態系統，網絡中成員的利益經常不一致甚至發生沖突，在各成員利益均能保證的基礎上，探求供應鏈網絡的均衡條件與實現系統總體的利益最大化的問題越來越受到重視。

Nagurney等人在2002年提出了供應鏈網絡均衡模型[1]，研究了由制造商、零售商與需求市場組成的單商品流供應鏈網絡均衡問題，提出可以將模型轉變為變分不等式，通過修正投影法進行求解；Dong等人認為確定的需求不符合現實情況，于是在Nagurney研究的基礎上，構建出更符合實際情況的隨機需求供應鏈均衡模型[2]，該模型仍然通過投影算法得到最優解；由于修正投影法中步長與李氏常數的確定往往依賴經驗，不同的參數值會對結果產生較大影響，而在求解非線性優化問題方面，擬牛頓法一直是最有效方法之一，Meng Q[3]與Zhang LP[4]分別用擬牛頓法與光滑牛頓法求解Nagurney提出的基礎模型并將結果在精度與耗時兩個方面做了對比。修正投影法與擬牛頓法在求解該問題時都存在各自的優勢與缺陷，當供應鏈節點增多，網絡結構相對復雜時，計算量會明顯的上升，模型的求解速度也會變慢。本文作者也曾提出利用蜂群算法求解供應鏈網絡[5]，相比傳統方法較為簡單，但其求解精度并不高。

心理學家Kenndy和電氣工程師Eberhart通過模擬自然界鳥群、魚群等生物相互合作，隨機搜索找到食物的機制提出了粒子群優化算法[6]。由于其結構簡單、需要調節的參數少，容易實現等優勢受到研究者的廣泛關注，并將其應用到了許多實際問題中。如Ramadan RM等人將改進的粒子群算法應用于人臉識別系統中[7]；原文林等人[8]將協同進化的粒子群算法用于求解比較復雜的高維梯級水庫短期發電優化調度問題；韓毅等人[9]將其用于求解無能力約束生產批量計劃問題中等。

但標準的粒子群算法容易陷入局部最優，難以適應復雜的非線性優化[10]，本文在此基礎上提出一種動態調整學習因子的粒子群算法，并將其用于供應鏈網絡均衡問題的求解，通過四個數值算例與標準PSO算法、同步變化學習因子的粒子群算法、蜂群算法[11]進行比較，結果顯示，改進算法求解的精度高、收斂速度快，驗證了改進的粒子群算法在供應鏈網絡均衡問題求解的有效性與優越性。

1 確定需求下供應鏈網絡均衡模型

該模型由頂層的m個制造商，中間層n個零售商以及底層的o個消費者組成。i,j,k分別代表每一層中具體的制造商、零售商以及消費者。

圖1 供應鏈網絡結構

制造商i向零售商j之間的產品發貨量為qij，零售商j與消費者k之間的產品發貨量為qjk，qij組成m×n維發貨量矩陣Q1，qjk組成n×o維發貨矩陣Q2。Cij表示制造商i與零售商j的交易成本(包含產品的運輸成本)，每個制造商i面對一個生產成本函數，其依賴于整個向量的生產量，表示為fi。確定需求是指在需求市場k處消費者對商品的需求可以用dk(ρ3)表示，其中ρ3k表示在需求市場k處產品的價格，而ρ3表示需求市場價格的o維列向量。

假設生產成本函數、交易成本函數都是可微的。當制造商、零售商、需求市場同時達到最優時，整個供應鏈網絡是均衡的。均衡狀態下的變分不等式[1]為:

(1)

將其等價的改寫為NCP問題，即尋找一個列向量

(2)

(3)

其中

(4)

(5)

(6)

(7)

(8)

i=1,…,m;j=1,…,n

(9)

(10)

(11)

(12)

最后，我們通過價值函數[3]

(13)

該NCP問題可等價的轉化為如下的無約束優化問題：

(14)

其中

(15)

2 動態調整學習因子的粒子群優化算法

2.1 標準粒子群算法

PSO算法作為人工智能算法的一種，其思想同其它智能算法一樣，也是通過迭代更新來找到最優解。該算法將每一組解看作粒子，由給定的迭代策略不斷調整粒子的位置，通過比較適應度函數的大小來判斷其解的優劣程度。在迭代開始階段，賦予每個粒子的隨機的位置和速度，在搜索過程中，粒子自行判斷與最優解的距離與方向，及時調整自己的速度和方向，以此尋找到最優解。PSO算法更新速度、位置的公式如下:

Vi(t+1)=ωVi(t)+c1r1(Pi-Xi(t))+

c2t2(Pg-Xi(t))

(16)

Xi(t+1)=Xi(t)+Vi(t+1)

(17)

其中i=1,2,…,n；ω是慣性因子；c1c2為學習因子，通常取2；r1,r2是介于[0,1]之間的隨機數；Pg為全局最優位置；第i個粒子的位置Xi=(xi1,xi2,…,xin)，速度為Vi=(vi1,vi2,…,vin)，自身的最優位置Pi=(Pi1,Pi2,…,Pin)。

2.2 動態調整學習因子

在粒子的搜索過程中，每個粒子在每一次位置更新后，都將通過評價函數來判斷當前解的優劣程度，及時調整當前的位置與速度，以便找到最優解。自身的信息與群體的信息可以通過兩個學習因子來控制，而兩個隨機數增強了群體的多樣性。若學習因子缺少變化，容易導致粒子陷入局部最優。Suganthan[12]提出將c1、c2進行相同速率的改變，其采用的方式為同速率線性遞減，即

(18)

該方法不斷的同步改變學習因子取值來改善優化的結果。而本文考慮到認知部分和社會部分對算法的不同影響，即(16)式的第二部分與第三部分在不同時期對算法的影響應該是不同的，隨著迭代次數的增加，粒子的全局搜索能力應該增強，局部探索能力適度減弱，這樣改動使算法初期具有較強的開采能力，后期不至于陷入局部最優解，平衡了算法的局部開采與全局尋優能力。綜上所述，c1,c2分別采用線性遞減與線性遞增策略，改進如下:

(19)

(20)

2.3 算法步驟

采用改進的粒子群算法求解供應鏈網絡問題步驟如下：

Step1賦予粒子群初始的隨機位置和速度；

Step2將(15)式作為該算法的適應度函數，計算每個粒子適應度值Ψ1；

Step3將每個粒子的當前的適應值與其所經歷的最好位置的適應度值Ψpbest作比較，若當前的值更好，進行替換，并記錄最好位置pbest；

Step4將每個粒子的適應值與所有粒子經歷的最好位置Ψgbest作比較，若當前的值更好，則用該粒子的適應值替換全局最優值，記錄全局最好位置gbest；

Step5按照式(19)、(20)對c1、c2進行線性調整，通過式(16)、式(17)更新粒子的速度和位置；

Step6判斷是否滿足結束條件，如若最優解精度不夠或者沒有達到Kmax，則返回第二步。

3 求解算例

例1該例子由2個制造商，2個零售商，2個消費者組成，如圖所示：

圖2 例1供應鏈網絡結構

制造商的生產成本函數：

制造商和零售商的交易成本函數：

零售商的管理成本函數：

需求市場的需求函數：

d1(ρ3)=-2ρ31-1.5ρ32+1000d2(ρ3)=-2ρ32-1.5ρ31+1000

零售商和消費者的交易成本函數：

c11(Q2)=q11+5,c12(Q2)=q12+5c21(Q2)=q21+5,c22(Q2)=q22+5

參數設置與實驗結果

圖3 蜂群算法、標準粒子群算法與兩種改進粒子群算法收斂圖

在四種智能算法中，群體規模為200，粒子搜索空間范圍為[0,400]，迭代次數為500次。蜂群算法Limit設置為50次，標準PSO算法中取定c1=c2=2，兩種改進算法中c1,c2的取值范圍為[0.8,2]，算法實驗50次取均值。在Matlab2010a上進行實驗，學習因子異步變化的粒子群算法在第367次迭代后取得最優值，蜂群算法，標準粒子群算法與兩種改進算法的函數值Ψ1與迭代次數關系如圖3所示。

四種算法取得的最小值與具體結果如表1所示。

表1 蜂群算法、標準粒子群與兩種改進算法結果比較

例2該例子的供應鏈網絡結構同例1，將f1(q),c11(q11),c12(q12)做如下改動：

智能算法參數設置同例1，學習因子異步變化的粒子群算法在第453次迭代后取得最小值,四種算法的函數值Ψ1與迭代次數關系如圖4所示。

圖4 蜂群算法、標準粒子群算法與兩種改進粒子群算法收斂圖

四種算法取得的最小值與具體結果如表2所示。

表2 蜂群算法、標準粒子群與兩種改進算法結果比較

例3該算例由2個制造商，3個零售商，2個消費者組成，如圖所示：

圖5 例3供應鏈網絡結構

制造商的生產成本函數：

制造商和零售商的交易成本函數:

零售商的管理成本函數：

需求市場的需求函數：

d1(ρ3)=-2ρ31-1.5ρ32+1000d2(ρ3)=-2ρ32-1.5ρ31+1000

零售商和消費者的交易成本函數：

c11(Q2)=q11+5,c12(Q2)=q12+5

c21(Q2)=q21+5,c22(Q2)=q22+5

c31(Q2)=q31+5,c32(Q2)=q32+5

四種智能算法種參數設置同例1，學習因子異步變化的粒子群算法在第432次迭代后取得最小值，四種算法所得到的函數值與迭代次數關系如圖6所示。

圖6 蜂群算法、標準粒子群算法與兩種改進粒子群算法收斂圖

四種算法取得的最小值與具體結果如表3所示。

表3 蜂群算法、標準粒子群與兩種改進算法結果比較

例4該算例由3個制造商，2個零售商，3個消費者組成，如圖所示:

圖7 例4供應鏈網絡結構

制造商的生產成本函數：

制造商和零售商的交易成本函數：

零售商的管理成本函數：

需求市場的需求函數:

d1(ρ3)=-2ρ31-1.5ρ32+1000d2(ρ3)=-2ρ32-1.5ρ31+1000d3(ρ3)=-2ρ33-1.5ρ31+1000

零售商和消費者的交易成本函數：

c11(Q2)=q11+5,c12(Q2)=q12+5

c13(Q2)=q13+5,c21(Q2)=q21+5

c22(Q2)=q22+5,c23(Q2)=q23+5

四種智能算法種參數設置同例1，學習因子異步變化的粒子群算法在第355次迭代后取得最小值，四種算法所得到的函數值Ψ1與迭代次數關系如圖8所示。

圖8 蜂群算法、標準粒子群算法與兩種改進粒子群算法收斂圖

四種算法取得的最小值與具體結果如表4所示。

表4 蜂群算法、標準粒子群與兩種改進算法結果比較

結果分析：四個例子分別給出了四種算法在求解最優值時的收斂曲線，其中縱坐標采用以10為底的對數形式。例1與例2需要求解12個變量，四種算法均能收斂。蜂群算法收斂速度最慢，并且最優解的精度也不高。標準粒子群優化算法和同步變化學習因子的算法在前期的收斂速度與精度基本一致，中后期可看出同步變化學習因子算法有較強的開采能力。異步變化學習因子從最開始就表現出較強的搜索與開采能力，最優值曲線下降迅速，能夠在前期準確定位最優解的位置，后期進行深入的挖掘，最終在第367與453次迭代后找到最優解。

例3與例4的供應鏈網絡結構相比例1與例2更復雜，需要求解17個變量，蜂群算法收斂效果并不理想，在前期就已經陷入局部最優，收斂精度也不高。標準粒子群優化和同步變化學習因子的算法相比蜂群算法收斂速度和精度都較好，但是在中期250代左右收斂速度迅速變慢，表示其陷入局部最優解，后期的開采能力也較弱。而異步變化學習因子收斂速度最快，在中期能夠跳出局部最優解繼續尋找全局最優解的位置。

從四個例子可以看出，學習因子異步變化的粒子群算法的最優值曲線呈近似直線的下降，其在解決供應鏈網絡求解問題中的效果尤為突出。其中蜂群算法非常容易“早熟”，在最優解的搜索上停滯不前，結果精度不高，開采能力較差；標準粒子群算法與學習因子同步變化的粒子群算法都能夠搜索到最優解附近，但是不能深入的挖掘出最優解，最終也陷入了局部最優；從四個表中也可以看出，學習因子異步變化的粒子群算法收斂的精度遠高于其他算法，改進的算法在搜索前期能夠在解空間內廣泛的搜索不至于陷入局部最優，而在迭代的后期又能在近似最優解附近深入的探索，種群始終有較強的探索能力，說明改進的粒子群算法有效的平衡了全局搜索與局部搜素的能力。相比Nagurney的修正投影法，兩種算法得到的結果基本一致，但是在求解過程中，改進的智能算法完全不會受到李氏常數、初值條件、或者迭代步長的干擾，是完全隨機的在解空間進行搜索的結果。

4 結論

本文研究了供應鏈網絡均衡問題以及求解方法，首先介紹了確定需求下的供應鏈網絡均衡模型，提出了一種異步線性改變學習因子的粒子群算法，并對該問題進行求解。通過四個實值算例，將該方法與蜂群算法、標準粒子群算法、學習因子同步變化的粒子群算法進行比較，實驗結果表明，改進的算法在求解該問題時有更好的全局和局部搜索能力，在收斂速度和精度有顯著的提高，為求解供應鏈網絡均衡問題提供了一種新的有效的方法。