求解互補問題的改進粒子群算法研究

劉 銘，董立嬌，王秀玉

(長春工業大學數學與統計學院，吉林 長春 130012)

互補問題在經濟、二次規劃、建筑等領域深受廣大學者關注.求解互補問題的方法有許多，例如光滑牛頓法、非光滑牛頓法、內點法等.但普通求解互補問題的數學方法對初始點的要求很高，并且依賴梯度信息，從而導致很難求出互補問題的解.這就需要研究人員結合其他方法進行轉化，以提高求解互補問題的效率.

隨著計算機技術的發展，出現了許多計算優化問題的智能算法.其中應用較廣的是粒子群算法(PSO)、遺傳算法、人工神經網絡等.智能算法在求解互補問題中的應用比較少，應用智能算法計算互補問題可以規避傳統求解互補問題過程中對初始點選取和梯度信息依賴的問題.本文通過改進標準粒子群算法中的慣性權重以及引入收縮因子，結合凝聚函數[1]提出了一種準確率高、收斂速度快的求解互補問題的智能優化算法.

1 互補問題的模型研究

通常情況下，互補問題指：對任意x∈Rn，F：Rn→Rn，有

x≥0，

(1)

F(x)≥0，

(2)

xTF(x)=0.

(3)

當F(x)為線性函數，即F(x)=Mx+q(M為n×n矩陣，q為常向量)時，稱為線性互補問題(LCP)；當F(x)為非線性函數時，稱為非線性互補問題(NCP).

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

常見的NCP函數有：

(4)

(5)

求解非線性互補問題等價于求解如下優化問題的極小值[2]：

(6)

(7)

所以求解NCP可以轉化為求解下列非光滑方程組問題：

[g(x1，F1(x))，g(x2，F2(x))，…，g(xn，Fn(x))]T=0，i=1，2，…，n.

(8)

這是一個較難的不可微優化問題，經典的光滑牛頓法對初始值的依賴性較高，因此用其計算起來比較困難.為克服非光滑性，產生了多種對NCP函數進行光滑化的方法.

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

(9)

其中μ>0.

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

(10)

其中ε>0.

本文借助于凝聚函數將非線性互補問題轉化為無約束優化方程組，應用凝聚函數[6]

(11)

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

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

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

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

(12)

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

綜上，將求解互補問題轉化成了求解非線性光滑方程組的解，取μ的單調遞減函數并趨于0，通過凝聚函數給出了一種求解(6)式的方法.下面應用改進的粒子群算法給出更適合求解互補問題的優化算法.

2 基于互補問題的改進粒子群算法研究

2.1 標準粒子群算法

將粒子群算法應用到求解互補問題中.算法中的每一個粒子都代表互補問題中的一個解，粒子在迭代過程中計算自身適應度值，并在尋優過程中會動態調整自身的速度和位移，通過比較個體極值和群體極值，尋找最優個體位置.[9]個體極值表示群體中個體所經歷的所有位置的最優值，群體極值指群體中所有粒子中的最優值.通過循環迭代，搜索到互補問題的最優解.

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

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

(13)

(14)

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

圖1 PSO算法流程圖

2.2 改進的粒子群算法

2.2.1 線性遞減慣性權重的粒子群算法(W-PSO)

在標準的速度更新公式中引入線性遞減慣性權重[11]，慣性權重w可以影響粒子的局部尋優能力和全局尋優能力，這里選擇線性遞減慣性權重為

(15)

其中：k為當前迭代次數；wk為當前迭代慣性權重；wmax和wmin分別為最大慣性權重和最小慣性權重；kmax為最大迭代次數.因此，根據(15)式速度迭代公式變為

(16)

綜上所述，粒子群算法在求解非線性互補問題的極值方面應用廣泛.在約束范圍內，通過調節粒子群算法中的參數[12-13]來計算種群中每個粒子的適應度值，并通過不斷的迭代比較個體適應度值和全局適應度值，最終得到相應的最優解.應用粒子群算法可以求解很多復雜的互補問題，避免求不出可行解的情況發生.通過改進的粒子群算法，提高了求解非線性互補問題的準確性.

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

為提高算法的收斂速度，在對標準PSO算法速度更新公式引入線性遞減權重的前提下，在(16)式基礎上引入收縮因子[14-15]：

(17)

(18)

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

(19)

在標準的粒子群算法下，通過改進慣性權重和引入收縮因子，使算法不再陷于局部尋優，提高算法尋優的準確率和收斂速度.

3 實例分析

為了檢驗本文所改進的粒子群算法在求解互補問題中的性能，選擇了在許多互補問題論文中所列舉的例子.通過應用標準粒子群算法、改進慣性權重的粒子群算法以及在改進慣性權重的基礎上在速度更新處引入收縮因子來提高粒子群計算效率.

為解決以下互補問題，選取種群規模為1 000，最大進化代數為500，權重由wmax=0.9線性遞減到wmin=0.4，設置容許誤差為e<0.01.

例1求解非線性互補問題中的Kojima-Shindo問題[8]：

首先應用傳統PSO算法進行計算.設置參數p=1 000 000，c1=c2=1.494 45，w=1.隨機產生初始點對上述實例進行20次重復計算，選擇出在容許誤差e<0.01范圍內符合條件的最優解，結果有12次搜索到最優解；其次，在標準PSO算法的基礎上調整w的值，使w呈線性遞減變換，同樣進行20次重復計算，得到的結果顯示搜索的準確率明顯提高：20次計算在容許誤差范圍內都能搜到使互補問題接近于0的最優解，并且搜索速度比標準PSO算法的速度更快.為進一步提高計算的收斂速度，在改進慣性權重的PSO算法中引入收縮因子，結果顯示收斂精度遠遠超過標準PSO算法.三種算法的驗證結果分析見表1，收斂速度見圖2.

表1 三種算法20次驗證結果分析

圖圖2三種算法收斂結果

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

此線性互補問題的解為xT=(0.5，0，0.5，0，0.5)，應用上例所用的方法得到的結果如表2所示.

表2 三種算法20次驗證結果分析

由例1—2，可見在傳統PSO算法的基礎上，線性改進慣性權重不僅增加了算法的準確性，而且在速度更新處添加收縮因子后，在保證準確率的基礎上提高了算法的收斂速度.這避免粒子在尋優過程中過早收斂，保證了粒子的活躍性，同時也避免了在搜索過程中粒子都是向全局最優靠近的同一性.在解決互補問題時不用考慮初始點和導數信息的情況下，更好更快的得出問題的結果.

4 結束語

通過改進標準粒子群算法中的慣性權重并且引入收縮因子，并結合凝聚函數來求解互補問題，不但提高了算法的準確率和收斂速度，而且本文粒子群算法在計算互補問題時不依靠初始點的選取和梯度信息，不僅給求解互補問題提出了新的方法，同樣也擴展了智能算法在互補問題求解方面的應用范圍.實驗結果表明，改進的粒子群算法準確率高、穩定性好、收斂速度快，是求解互補問題的一種有效算法.