一種改進的和聲搜索算法求解非線性互補問題

雍龍泉, 熊文濤

(1. 陜西理工大學 數(shù)學與計算機科學學院, 陜西 漢中 723000;2. 湖北工程學院 數(shù)學與統(tǒng)計學院, 湖北 孝感 432000)

互補問題的理論研究和數(shù)值算法是最優(yōu)化理論研究領域中一個重要的課題，它為數(shù)學規(guī)劃提供了一個統(tǒng)一的研究框架，已成為數(shù)學規(guī)劃的一個重要分枝[1-8]。近十年新的理論成果和新的求解方法層出不窮[9-16]，對稱錐互補問題[17]、張量互補問題[18-21]、互補約束優(yōu)化[22]等成為目前的研究熱點。

光滑牛頓法是解決互補問題最常用的方法之一，它利用NCP函數(shù)，可以將互補問題轉(zhuǎn)化為等價的光滑方程組并加以求解，其關鍵問題就是NCP函數(shù)的構(gòu)造[23-29]。此外，針對多個解的互補問題，傳統(tǒng)算法無法同時找到多個解(如何找到盡可能多的解，該方面的研究較少)，因此針對求解具有多個解的互補問題還存在一定的困難。

本文提出一種求解互補問題的新方法，具體做法是利用NCP函數(shù)把互補問題轉(zhuǎn)化為一個非線性方程組，采用智能優(yōu)化算法求解與之等價的無約束優(yōu)化問題并獲得原問題的解(對多個解的互補問題，由于智能優(yōu)化算法是多點尋優(yōu)，因此就可能找到多個解)。該方法對函數(shù)F(x)的單調(diào)性無要求。

1 互補問題轉(zhuǎn)化為無約束優(yōu)化

互補問題就是求一個向量x=(x1,x2,…,xn)T∈Rn，使得

x≥0,F(x)≥0,xTF(x)≥0,

(1)

其中F:Rn→Rn，F(xiàn)(x)=(f1(x),f2(x),…,fn(x))T,fi(x):Rn→R,i=1,2,…,n。

如果F(x)=Mx+q，其中M∈Rn×n，q∈Rn,則稱為線性互補。

定義1 函數(shù)φ:R2→R被稱為NCP函數(shù)，如果對任意(a,b)T∈R2，有

φ(a,b)=0?a≥0,b≥0,ab=0。

結(jié)合NCP函數(shù)的性質(zhì)，互補問題(1)可等價地轉(zhuǎn)化為方程組

(2)

再通過求解如下優(yōu)化問題

(3)

得到非線性方程組(2)的近似解，即互補問題(1)的近似解。

若無約束優(yōu)化問題(3)收斂到零，則原問題可解；若無約束優(yōu)化問題(3)無法收斂到零，則原問題可能無解。下面利用改進的和聲搜索算法求解問題(3)。

2 改進的和聲搜索算法

和聲搜索(Harmony Search,HS)算法模擬了音樂創(chuàng)作中的過程，在該過程中，演奏者憑借自己的記憶，反復調(diào)整樂隊中各樂器的音調(diào)，最終達到一個美妙的和聲狀態(tài)[30-31]。經(jīng)典和聲搜索算法步驟如圖1所示。和聲搜索算法也存在早熟現(xiàn)象，為了維持種群的多樣性并加快收斂速度，給出一種結(jié)合位置更新和小概率變異策略的全局和聲搜索(NGHS)算法，如圖2所示。其中Xbest與Xworst分別表示當前和聲記憶庫HM中最好的和聲與最差的和聲。NGHS算法的特點：初期所有的種群較為分散，于是Xs較大，有利于做全局搜索；后期種群都在向近似解聚集，從而Xs變小，這有利于算法做局部搜索。變異概率pm既保持種群多樣性，又能保證算法收斂。NGHS算法能夠較好地求解一些復雜優(yōu)化問題[32-34]，下面采用NGHS算法求解無約束優(yōu)化問題(3)。

圖1 HS算法流程圖 圖2 NGHS算法流程圖

算法說明：XL與XU分別表示搜索空間的下界與上界。HS與NGHS算法的主要區(qū)別有兩點：①新的和聲Xnew產(chǎn)生方式不同；②種群更新策略不同，HS采用的是精英更新模式，而NGHS直接用Xnew替換掉Xworst(不論Xnew是否優(yōu)于Xworst)。

3 數(shù)值實驗

本節(jié)給出3個互補問題的數(shù)值實驗驗證。

利用定義1中的NCP函數(shù)將其轉(zhuǎn)化為無約束優(yōu)化問題，采用NGHS算法求解，算法程序用MATLABR2009a編寫，在32位的Windows XP系統(tǒng)下運行。為了便于研究NGHS算法的搜索性能，同時給出HS、HSCH[35]、HSWB[36]的求解結(jié)果，算法參數(shù)選?。篐MS=10，HMCR=0.85，PAR=0.35，最大迭代次數(shù)Tmax=50 000，搜索空間為[-5,5]n；在NGHS中選取pm=0.005；4種算法各運行10次。

算例1 考慮非線性互補問題,其中

該非線性互補問題的唯一解為x*=(0,3,1,0,0)T。表1給出了4種算法運行10次的結(jié)果(運行時間取10次的平均值)。圖3是4種算法運行10次的收斂曲線和最優(yōu)目標值的分布盒圖,圖4給出了NGHS算法運行10次后得到的結(jié)果。從圖4中可以看出：每一列表示每次NGHS運行結(jié)束后最好適應值對應的和聲。

表1 算例1的計算結(jié)果比較

(a) 收斂曲線 (b) 最優(yōu)目標值分布盒圖圖3 算例1的平均適應值收斂曲線和最優(yōu)目標值分布盒圖

圖4 NGHS算法運行10次后得到的結(jié)果(每次都收斂到唯一解)

算例2考慮非線性互補問題,其中

該問題的4個解為x*=(2,1,0)T,x*=(3,0,0)T,x*=(1,0,2)T,x*=(1.2,0.2,1.6)T。表2給出了4種算法運行10次的結(jié)果。圖5給出了收斂曲線和最優(yōu)目標值的分布盒圖,圖6給出了NGHS算法運行10次后得到的結(jié)果。

表2 算例2的計算結(jié)果比較

(a) 收斂曲線 (b) 最優(yōu)目標值分布盒圖圖5 算例2的平均適應值收斂曲線和最優(yōu)目標值分布盒圖

圖6 NGHS算法運行10次后得到的結(jié)果(4個解都找到了)

算例3考慮非線性互補問題,其中

該問題有無窮多個解x*=(λ,0,0,0)T,λ∈[0,3]。表3給出了4種算法運行10次的結(jié)果。圖7給出了NGHS算法運行10次后得到的結(jié)果。

表3 算例3的計算結(jié)果比較

圖7 NGHS算法運行10次后得到的結(jié)果(找到了6個解)

計算結(jié)果表明：對于唯一解的互補問題，都收斂到唯一解；對于具有多個解的互補問題，能夠找到盡可能多的解；如需得到較高精度的數(shù)值解，通過增加迭代次數(shù)可以實現(xiàn)。