求解互補(bǔ)問(wèn)題的改進(jìn)粒子群算法研究

劉 銘，董立嬌，王秀玉

(長(zhǎng)春工業(yè)大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，吉林 長(zhǎng)春 130012)

互補(bǔ)問(wèn)題在經(jīng)濟(jì)、二次規(guī)劃、建筑等領(lǐng)域深受廣大學(xué)者關(guān)注.求解互補(bǔ)問(wèn)題的方法有許多，例如光滑牛頓法、非光滑牛頓法、內(nèi)點(diǎn)法等.但普通求解互補(bǔ)問(wèn)題的數(shù)學(xué)方法對(duì)初始點(diǎn)的要求很高，并且依賴(lài)梯度信息，從而導(dǎo)致很難求出互補(bǔ)問(wèn)題的解.這就需要研究人員結(jié)合其他方法進(jìn)行轉(zhuǎn)化，以提高求解互補(bǔ)問(wèn)題的效率.

隨著計(jì)算機(jī)技術(shù)的發(fā)展，出現(xiàn)了許多計(jì)算優(yōu)化問(wèn)題的智能算法.其中應(yīng)用較廣的是粒子群算法(PSO)、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)等.智能算法在求解互補(bǔ)問(wèn)題中的應(yīng)用比較少，應(yīng)用智能算法計(jì)算互補(bǔ)問(wèn)題可以規(guī)避傳統(tǒng)求解互補(bǔ)問(wèn)題過(guò)程中對(duì)初始點(diǎn)選取和梯度信息依賴(lài)的問(wèn)題.本文通過(guò)改進(jìn)標(biāo)準(zhǔn)粒子群算法中的慣性權(quán)重以及引入收縮因子，結(jié)合凝聚函數(shù)[1]提出了一種準(zhǔn)確率高、收斂速度快的求解互補(bǔ)問(wèn)題的智能優(yōu)化算法.

1 互補(bǔ)問(wèn)題的模型研究

通常情況下，互補(bǔ)問(wèn)題指：對(duì)任意x∈Rn，F(xiàn)：Rn→Rn，有

x≥0，

(1)

F(x)≥0，

(2)

xTF(x)=0.

(3)

當(dāng)F(x)為線(xiàn)性函數(shù)，即F(x)=Mx+q(M為n×n矩陣，q為常向量)時(shí)，稱(chēng)為線(xiàn)性互補(bǔ)問(wèn)題(LCP)；當(dāng)F(x)為非線(xiàn)性函數(shù)時(shí)，稱(chēng)為非線(xiàn)性互補(bǔ)問(wèn)題(NCP).

稱(chēng)函數(shù)g(a，b)：R2→R為NCP函數(shù)，如果g(a，b)=0?a≥0，b≥0，ab=0.

常見(jiàn)的NCP函數(shù)有：

(4)

(5)

求解非線(xiàn)性互補(bǔ)問(wèn)題等價(jià)于求解如下優(yōu)化問(wèn)題的極小值[2]：

(6)

(7)

所以求解NCP可以轉(zhuǎn)化為求解下列非光滑方程組問(wèn)題：

[g(x1，F(xiàn)1(x))，g(x2，F(xiàn)2(x))，…，g(xn，F(xiàn)n(x))]T=0，i=1，2，…，n.

(8)

這是一個(gè)較難的不可微優(yōu)化問(wèn)題，經(jīng)典的光滑牛頓法對(duì)初始值的依賴(lài)性較高，因此用其計(jì)算起來(lái)比較困難.為克服非光滑性，產(chǎn)生了多種對(duì)NCP函數(shù)進(jìn)行光滑化的方法.

為了求出互補(bǔ)問(wèn)題[3]在x≥0，f(x)≥0時(shí)xTf(x)=0的解，可以采用極小算子的光滑逼近的形式[4]

(9)

其中μ>0.

同樣通過(guò)光滑化[5]，可將(4)式光滑化為

(10)

其中ε>0.

本文借助于凝聚函數(shù)將非線(xiàn)性互補(bǔ)問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化方程組，應(yīng)用凝聚函數(shù)[6]

(11)

對(duì)max函數(shù)進(jìn)行光滑化，使得對(duì)任意μ，gμ(x，f(x))=-μ*ln{exp(-x/μ)+exp(-f(x)/μ)}.由關(guān)系式[7-8]

-max{-x，-f(x)}-μln2≤-μln{exp(-x/μ)+exp(-f(x)/μ)}≤-max{-x，-f(x)}，

當(dāng)μ→0時(shí)，gμ{x，f(x)}一致收斂于gμ{x，f(x)}，且gμ{x，f(x)}的每一分量有近似光滑函數(shù)

gμ{xi，fi(x)}=-μln{exp(-xi/μ)+exp(-fi(x)/μ)}，i=1，2，…，n.

(12)

(12)式即為方程組(6)的近似.

綜上，將求解互補(bǔ)問(wèn)題轉(zhuǎn)化成了求解非線(xiàn)性光滑方程組的解，取μ的單調(diào)遞減函數(shù)并趨于0，通過(guò)凝聚函數(shù)給出了一種求解(6)式的方法.下面應(yīng)用改進(jìn)的粒子群算法給出更適合求解互補(bǔ)問(wèn)題的優(yōu)化算法.

2 基于互補(bǔ)問(wèn)題的改進(jìn)粒子群算法研究

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

將粒子群算法應(yīng)用到求解互補(bǔ)問(wèn)題中.算法中的每一個(gè)粒子都代表互補(bǔ)問(wèn)題中的一個(gè)解，粒子在迭代過(guò)程中計(jì)算自身適應(yīng)度值，并在尋優(yōu)過(guò)程中會(huì)動(dòng)態(tài)調(diào)整自身的速度和位移，通過(guò)比較個(gè)體極值和群體極值，尋找最優(yōu)個(gè)體位置.[9]個(gè)體極值表示群體中個(gè)體所經(jīng)歷的所有位置的最優(yōu)值，群體極值指群體中所有粒子中的最優(yōu)值.通過(guò)循環(huán)迭代，搜索到互補(bǔ)問(wèn)題的最優(yōu)解.

設(shè)搜索空間為D維，其中有n個(gè)粒子組成的種群X=(X1，X2，…，Xn)，其中第i個(gè)粒子的位置用一個(gè)D維的向量Xi=[Xi1，Xi2，…，XiD]T表示.通過(guò)計(jì)算并比較粒子在各個(gè)位置上的適應(yīng)度值，可得出個(gè)體極值；在群體優(yōu)化過(guò)程中，所有粒子經(jīng)過(guò)的最優(yōu)極值為群體極值.第i個(gè)粒子的速度用一個(gè)D維的向量表示為Vi=[Vi1，Vi2，…，ViD]T.

在每一次迭代過(guò)程中，粒子通過(guò)個(gè)體極值和全局極值更新自己的速度和位置[10]，更新公式如下：

(13)

(14)

其中：c1，c2∈[0，1]為加速因子，通常c1，c2取常數(shù)時(shí)可以得到較好的最優(yōu)解；w為慣性權(quán)重，通常取常數(shù)d=1，2，…，D；i=1，2，…，n；Vid為粒子速度；Xid為粒子位置；r1，r2∈[0，1]為隨機(jī)數(shù).為防止粒子在搜索過(guò)程中出現(xiàn)冗余，通常將粒子速度和位置限定在一定區(qū)域[-Xmax，Xmax]，[-Vmax，Vmax].具體PSO算法流程見(jiàn)圖1.

圖1 PSO算法流程圖

2.2 改進(jìn)的粒子群算法

2.2.1 線(xiàn)性遞減慣性權(quán)重的粒子群算法(W-PSO)

在標(biāo)準(zhǔn)的速度更新公式中引入線(xiàn)性遞減慣性權(quán)重[11]，慣性權(quán)重w可以影響粒子的局部尋優(yōu)能力和全局尋優(yōu)能力，這里選擇線(xiàn)性遞減慣性權(quán)重為

(15)

其中：k為當(dāng)前迭代次數(shù)；wk為當(dāng)前迭代慣性權(quán)重；wmax和wmin分別為最大慣性權(quán)重和最小慣性權(quán)重；kmax為最大迭代次數(shù).因此，根據(jù)(15)式速度迭代公式變?yōu)?/p>

(16)

綜上所述，粒子群算法在求解非線(xiàn)性互補(bǔ)問(wèn)題的極值方面應(yīng)用廣泛.在約束范圍內(nèi)，通過(guò)調(diào)節(jié)粒子群算法中的參數(shù)[12-13]來(lái)計(jì)算種群中每個(gè)粒子的適應(yīng)度值，并通過(guò)不斷的迭代比較個(gè)體適應(yīng)度值和全局適應(yīng)度值，最終得到相應(yīng)的最優(yōu)解.應(yīng)用粒子群算法可以求解很多復(fù)雜的互補(bǔ)問(wèn)題，避免求不出可行解的情況發(fā)生.通過(guò)改進(jìn)的粒子群算法，提高了求解非線(xiàn)性互補(bǔ)問(wèn)題的準(zhǔn)確性.

2.2.2 引入收縮因子的粒子群算法(W-CPSO)

為提高算法的收斂速度，在對(duì)標(biāo)準(zhǔn)PSO算法速度更新公式引入線(xiàn)性遞減權(quán)重的前提下，在(16)式基礎(chǔ)上引入收縮因子[14-15]：

(17)

(18)

φ=c1+c2，φ>4，xi=xi+vi.

(19)

在標(biāo)準(zhǔn)的粒子群算法下，通過(guò)改進(jìn)慣性權(quán)重和引入收縮因子，使算法不再陷于局部尋優(yōu)，提高算法尋優(yōu)的準(zhǔn)確率和收斂速度.

3 實(shí)例分析

為了檢驗(yàn)本文所改進(jìn)的粒子群算法在求解互補(bǔ)問(wèn)題中的性能，選擇了在許多互補(bǔ)問(wèn)題論文中所列舉的例子.通過(guò)應(yīng)用標(biāo)準(zhǔn)粒子群算法、改進(jìn)慣性權(quán)重的粒子群算法以及在改進(jìn)慣性權(quán)重的基礎(chǔ)上在速度更新處引入收縮因子來(lái)提高粒子群計(jì)算效率.

為解決以下互補(bǔ)問(wèn)題，選取種群規(guī)模為1 000，最大進(jìn)化代數(shù)為500，權(quán)重由wmax=0.9線(xiàn)性遞減到wmin=0.4，設(shè)置容許誤差為e<0.01.

例1求解非線(xiàn)性互補(bǔ)問(wèn)題中的Kojima-Shindo問(wèn)題[8]：

首先應(yīng)用傳統(tǒng)PSO算法進(jìn)行計(jì)算.設(shè)置參數(shù)p=1 000 000，c1=c2=1.494 45，w=1.隨機(jī)產(chǎn)生初始點(diǎn)對(duì)上述實(shí)例進(jìn)行20次重復(fù)計(jì)算，選擇出在容許誤差e<0.01范圍內(nèi)符合條件的最優(yōu)解，結(jié)果有12次搜索到最優(yōu)解；其次，在標(biāo)準(zhǔn)PSO算法的基礎(chǔ)上調(diào)整w的值，使w呈線(xiàn)性遞減變換，同樣進(jìn)行20次重復(fù)計(jì)算，得到的結(jié)果顯示搜索的準(zhǔn)確率明顯提高：20次計(jì)算在容許誤差范圍內(nèi)都能搜到使互補(bǔ)問(wèn)題接近于0的最優(yōu)解，并且搜索速度比標(biāo)準(zhǔn)PSO算法的速度更快.為進(jìn)一步提高計(jì)算的收斂速度，在改進(jìn)慣性權(quán)重的PSO算法中引入收縮因子，結(jié)果顯示收斂精度遠(yuǎn)遠(yuǎn)超過(guò)標(biāo)準(zhǔn)PSO算法.三種算法的驗(yàn)證結(jié)果分析見(jiàn)表1，收斂速度見(jiàn)圖2.

表1 三種算法20次驗(yàn)證結(jié)果分析

圖圖2三種算法收斂結(jié)果

例2求解線(xiàn)性互補(bǔ)問(wèn)題F(x)=Mx+q，其中矩陣M和向量q由下式給出：

此線(xiàn)性互補(bǔ)問(wèn)題的解為xT=(0.5，0，0.5，0，0.5)，應(yīng)用上例所用的方法得到的結(jié)果如表2所示.

表2 三種算法20次驗(yàn)證結(jié)果分析

由例1—2，可見(jiàn)在傳統(tǒng)PSO算法的基礎(chǔ)上，線(xiàn)性改進(jìn)慣性權(quán)重不僅增加了算法的準(zhǔn)確性，而且在速度更新處添加收縮因子后，在保證準(zhǔn)確率的基礎(chǔ)上提高了算法的收斂速度.這避免粒子在尋優(yōu)過(guò)程中過(guò)早收斂，保證了粒子的活躍性，同時(shí)也避免了在搜索過(guò)程中粒子都是向全局最優(yōu)靠近的同一性.在解決互補(bǔ)問(wèn)題時(shí)不用考慮初始點(diǎn)和導(dǎo)數(shù)信息的情況下，更好更快的得出問(wèn)題的結(jié)果.

4 結(jié)束語(yǔ)

通過(guò)改進(jìn)標(biāo)準(zhǔn)粒子群算法中的慣性權(quán)重并且引入收縮因子，并結(jié)合凝聚函數(shù)來(lái)求解互補(bǔ)問(wèn)題，不但提高了算法的準(zhǔn)確率和收斂速度，而且本文粒子群算法在計(jì)算互補(bǔ)問(wèn)題時(shí)不依靠初始點(diǎn)的選取和梯度信息，不僅給求解互補(bǔ)問(wèn)題提出了新的方法，同樣也擴(kuò)展了智能算法在互補(bǔ)問(wèn)題求解方面的應(yīng)用范圍.實(shí)驗(yàn)結(jié)果表明，改進(jìn)的粒子群算法準(zhǔn)確率高、穩(wěn)定性好、收斂速度快，是求解互補(bǔ)問(wèn)題的一種有效算法.