馬 斌， 吳澤忠

(成都信息工程大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，四川 成都 610225)

0 引言

供應(yīng)鏈網(wǎng)絡(luò)是一個復(fù)雜的動態(tài)系統(tǒng)，網(wǎng)絡(luò)中成員的利益經(jīng)常不一致甚至發(fā)生沖突，在各成員利益均能保證的基礎(chǔ)上，探求供應(yīng)鏈網(wǎng)絡(luò)的均衡條件與實現(xiàn)系統(tǒng)總體的利益最大化的問題越來越受到重視。

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

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

但標(biāo)準(zhǔn)的粒子群算法容易陷入局部最優(yōu)，難以適應(yīng)復(fù)雜的非線性優(yōu)化[10]，本文在此基礎(chǔ)上提出一種動態(tài)調(diào)整學(xué)習(xí)因子的粒子群算法，并將其用于供應(yīng)鏈網(wǎng)絡(luò)均衡問題的求解，通過四個數(shù)值算例與標(biāo)準(zhǔn)PSO算法、同步變化學(xué)習(xí)因子的粒子群算法、蜂群算法[11]進行比較，結(jié)果顯示，改進算法求解的精度高、收斂速度快，驗證了改進的粒子群算法在供應(yīng)鏈網(wǎng)絡(luò)均衡問題求解的有效性與優(yōu)越性。

1 確定需求下供應(yīng)鏈網(wǎng)絡(luò)均衡模型

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

圖1 供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)

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

假設(shè)生產(chǎn)成本函數(shù)、交易成本函數(shù)都是可微的。當(dāng)制造商、零售商、需求市場同時達到最優(yōu)時，整個供應(yīng)鏈網(wǎng)絡(luò)是均衡的。均衡狀態(tài)下的變分不等式[1]為:

(1)

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

(2)

(3)

其中

(4)

(5)

(6)

(7)

(8)

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

(9)

(10)

(11)

(12)

最后，我們通過價值函數(shù)[3]

(13)

該NCP問題可等價的轉(zhuǎn)化為如下的無約束優(yōu)化問題：

(14)

其中

(15)

2 動態(tài)調(diào)整學(xué)習(xí)因子的粒子群優(yōu)化算法

2.1 標(biāo)準(zhǔn)粒子群算法

PSO算法作為人工智能算法的一種，其思想同其它智能算法一樣，也是通過迭代更新來找到最優(yōu)解。該算法將每一組解看作粒子，由給定的迭代策略不斷調(diào)整粒子的位置，通過比較適應(yīng)度函數(shù)的大小來判斷其解的優(yōu)劣程度。在迭代開始階段，賦予每個粒子的隨機的位置和速度，在搜索過程中，粒子自行判斷與最優(yōu)解的距離與方向，及時調(diào)整自己的速度和方向，以此尋找到最優(yōu)解。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為學(xué)習(xí)因子，通常取2；r1,r2是介于[0,1]之間的隨機數(shù)；Pg為全局最優(yōu)位置；第i個粒子的位置Xi=(xi1,xi2,…,xin)，速度為Vi=(vi1,vi2,…,vin)，自身的最優(yōu)位置Pi=(Pi1,Pi2,…,Pin)。

2.2 動態(tài)調(diào)整學(xué)習(xí)因子

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

(18)

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

(19)

(20)

2.3 算法步驟

采用改進的粒子群算法求解供應(yīng)鏈網(wǎng)絡(luò)問題步驟如下：

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

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

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

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

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

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

3 求解算例

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

圖2 例1供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)

制造商的生產(chǎn)成本函數(shù)：

制造商和零售商的交易成本函數(shù)：

零售商的管理成本函數(shù)：

需求市場的需求函數(shù)：

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

零售商和消費者的交易成本函數(shù)：

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

參數(shù)設(shè)置與實驗結(jié)果

圖3 蜂群算法、標(biāo)準(zhǔn)粒子群算法與兩種改進粒子群算法收斂圖

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

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

表1 蜂群算法、標(biāo)準(zhǔn)粒子群與兩種改進算法結(jié)果比較

例2該例子的供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)同例1，將f1(q),c11(q11),c12(q12)做如下改動：

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

圖4 蜂群算法、標(biāo)準(zhǔn)粒子群算法與兩種改進粒子群算法收斂圖

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

表2 蜂群算法、標(biāo)準(zhǔn)粒子群與兩種改進算法結(jié)果比較

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

圖5 例3供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)

制造商的生產(chǎn)成本函數(shù)：

制造商和零售商的交易成本函數(shù):

零售商的管理成本函數(shù)：

需求市場的需求函數(shù)：

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

零售商和消費者的交易成本函數(shù)：

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

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

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

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

圖6 蜂群算法、標(biāo)準(zhǔn)粒子群算法與兩種改進粒子群算法收斂圖

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

表3 蜂群算法、標(biāo)準(zhǔn)粒子群與兩種改進算法結(jié)果比較

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

圖7 例4供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)

制造商的生產(chǎn)成本函數(shù)：

制造商和零售商的交易成本函數(shù)：

零售商的管理成本函數(shù)：

需求市場的需求函數(shù):

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

零售商和消費者的交易成本函數(shù)：

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

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

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

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

圖8 蜂群算法、標(biāo)準(zhǔn)粒子群算法與兩種改進粒子群算法收斂圖

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

表4 蜂群算法、標(biāo)準(zhǔn)粒子群與兩種改進算法結(jié)果比較

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

例3與例4的供應(yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)相比例1與例2更復(fù)雜，需要求解17個變量，蜂群算法收斂效果并不理想，在前期就已經(jīng)陷入局部最優(yōu)，收斂精度也不高。標(biāo)準(zhǔn)粒子群優(yōu)化和同步變化學(xué)習(xí)因子的算法相比蜂群算法收斂速度和精度都較好，但是在中期250代左右收斂速度迅速變慢，表示其陷入局部最優(yōu)解，后期的開采能力也較弱。而異步變化學(xué)習(xí)因子收斂速度最快，在中期能夠跳出局部最優(yōu)解繼續(xù)尋找全局最優(yōu)解的位置。

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

4 結(jié)論

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