基于改進(jìn)遺傳算法的互補(bǔ)問(wèn)題研究

董立嬌

互補(bǔ)問(wèn)題是數(shù)學(xué)規(guī)劃中的一個(gè)重要分支，互補(bǔ)問(wèn)題的求解對(duì)于實(shí)際問(wèn)題有著重要的現(xiàn)實(shí)意義，但求解互補(bǔ)問(wèn)題需要計(jì)算梯度信息，還需要給定準(zhǔn)確的初始點(diǎn)［1］；并且大多數(shù)互補(bǔ)問(wèn)題的解不唯一，應(yīng)用傳統(tǒng)的數(shù)學(xué)方法求解互補(bǔ)問(wèn)題不能一次性得出解.因此，求解互補(bǔ)問(wèn)題存在一定的困難，但隨著近年來(lái)智能優(yōu)化算法的廣泛應(yīng)用，如遺傳算法、模擬退火算法、人工神經(jīng)網(wǎng)絡(luò)等，將這些智能優(yōu)化算法［2］應(yīng)用到求解互補(bǔ)問(wèn)題中成了廣大學(xué)者關(guān)注的問(wèn)題，本文應(yīng)用改進(jìn)的遺傳算法來(lái)求解互補(bǔ)問(wèn)題，避免了傳統(tǒng)的遺傳算法在求解最優(yōu)解時(shí)易陷于局部最優(yōu)、過(guò)早收斂等問(wèn)題，最后通過(guò)計(jì)算實(shí)例來(lái)驗(yàn)證算法的效率.

1　互補(bǔ)問(wèn)題的光滑化

所謂互補(bǔ)問(wèn)題是指，對(duì)于任意的向量x∈Rn，當(dāng) x≥0,F(x)≥0時(shí)，xTF(x)=0，其中F:Rn→Rn，表示兩個(gè)決策變量之間呈現(xiàn)互補(bǔ)的關(guān)系，當(dāng)F為線性函數(shù)（F(x)=Mx+q(M∈Rn×n,q∈Rn））時(shí)，稱(chēng)為線性互補(bǔ)問(wèn)題，記為L(zhǎng)CP()M,q；反之稱(chēng)為非線性互補(bǔ)問(wèn)題，記為NCP()F.

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

為了求解上述非線性互補(bǔ)問(wèn)題，基于上述式子不可微的特性，傳統(tǒng)的數(shù)學(xué)方法對(duì)初始點(diǎn)的依賴(lài)較高，計(jì)算起來(lái)復(fù)雜困難，因此不能用傳統(tǒng)的牛頓法、內(nèi)點(diǎn)法來(lái)計(jì)算；為了克服非光滑性［3］，可以應(yīng)用罰函數(shù)方法、乘子法等對(duì)其進(jìn)行光滑化［4］.

為求解互補(bǔ)問(wèn)題x≥0,f(x)≥0,xTf(x)=0的解，我們對(duì)其進(jìn)行如下光滑逼近.

其中，μ＞0.

同樣通過(guò)光滑化，可將（1）式光滑化為

其中，ε＞0.

同時(shí)引入凝聚函數(shù)將非線性互補(bǔ)問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化方程組，應(yīng)用凝聚函數(shù).

利用極小值方法，可將上述求解非線性互補(bǔ)問(wèn)題轉(zhuǎn)化為下式.

所以求解非線性互補(bǔ)問(wèn)題可以轉(zhuǎn)化為求解下列光滑方程組問(wèn)題.

用式（8）來(lái)近似代替方程組（6）.

2　基于互補(bǔ)問(wèn)題的改進(jìn)遺傳算法

2.1　標(biāo)準(zhǔn)遺傳算法

遺傳算法是由達(dá)爾文的自然選擇學(xué)說(shuō)和孟德?tīng)柕倪z傳學(xué)說(shuō)而來(lái)，通過(guò)生物界中適者生存、優(yōu)勝劣汰的遺傳機(jī)制演化為計(jì)算機(jī)語(yǔ)言的隨機(jī)優(yōu)化搜索方法，遺傳算法在求解優(yōu)化問(wèn)題時(shí)不需要借助其他影響因素直接對(duì)問(wèn)題進(jìn)行求解，沒(méi)有要求所求函數(shù)是否連續(xù)以及對(duì)函數(shù)進(jìn)行求導(dǎo)分析等；與其他算法相比，遺傳算法適合大量數(shù)據(jù)的全局搜索，在搜索過(guò)程中自動(dòng)產(chǎn)生搜索空間，并適當(dāng)?shù)卣{(diào)整搜索方向，通過(guò)計(jì)算概率對(duì)染色體進(jìn)行選擇、交叉、變異，通過(guò)不同的編碼技術(shù)來(lái)模仿不同環(huán)境中的自然選擇，通過(guò)在搜索過(guò)程中獲取和積累相關(guān)遺傳信息，自適應(yīng)地控制搜索過(guò)程以求得近似最優(yōu)解.

由于遺傳算法在整體搜索過(guò)程中無(wú)需梯度信息和初始點(diǎn)，只需列出所求互補(bǔ)問(wèn)題的目標(biāo)函數(shù)和約束條件，對(duì)互補(bǔ)問(wèn)題進(jìn)行光滑化處理，將互補(bǔ)問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，繼而應(yīng)用遺傳算法求出互補(bǔ)問(wèn)題的最優(yōu)解，應(yīng)用遺傳算法計(jì)算互補(bǔ)問(wèn)題可以提高傳統(tǒng)數(shù)學(xué)方法在計(jì)算互補(bǔ)問(wèn)題時(shí)的效率和穩(wěn)定性.

2.2　改進(jìn)的遺傳算法

遺傳算法作為近年來(lái)研究?jī)?yōu)化問(wèn)題的智能算法，雖然存在著自身的優(yōu)勢(shì)，不過(guò)在計(jì)算優(yōu)化問(wèn)題時(shí)還存在著一些不足：

①編碼形式種類(lèi)繁多，編碼形式不規(guī)范以及編碼表示的不確定性；

②遺傳算法在進(jìn)行優(yōu)化求解時(shí)，應(yīng)用所選編碼形式不能全方位地表示問(wèn)題的約束條件，需要考慮的是對(duì)于所求問(wèn)題的不可行解采用限制閾值的形式，導(dǎo)致算法在求解問(wèn)題時(shí)所消耗時(shí)間過(guò)長(zhǎng)；

③由于遺傳算法在計(jì)算優(yōu)化問(wèn)題時(shí)計(jì)算量大，所以解決問(wèn)題的效率沒(méi)有別的優(yōu)化算法高；

④遺傳算法在求解問(wèn)題時(shí)，對(duì)搜索空間進(jìn)行全局搜索，但是受其他因素影響，極易導(dǎo)致過(guò)早收斂的狀況；

⑤由于優(yōu)化問(wèn)題的可行解有可能不唯一，所以我們?cè)趹?yīng)用遺傳算法來(lái)求解優(yōu)化問(wèn)題近似解時(shí)，對(duì)于解的精度、可信度等因素，還沒(méi)有統(tǒng)一的方法進(jìn)行定量分析.

為了避免上述遺傳算法在求解互補(bǔ)問(wèn)題時(shí)的不足，本文將遺傳算法和粒子群算法相結(jié)合，在搜索空間D上，有n個(gè)可行解X=(X1,X2,…,Xn)，對(duì)于第i個(gè)可行解有位置向量Xi=[xi1,xi2,…,xiD]T（每個(gè)位置都是問(wèn)題的可行解），用Vi=[Vi1,Vi2,…,ViD]T表示個(gè)體的速度向量，通過(guò)計(jì)算所有位置的適應(yīng)度值，選出個(gè)體最優(yōu)值；同理，經(jīng)過(guò)群體優(yōu)化過(guò)程，比較所有個(gè)體最優(yōu)值得出群體中最好的解作為群體極值；在速度更新、位置更新之后，進(jìn)行選擇、交叉、變異，將遺傳算法同粒子群算法相結(jié)合，盡量避免遺傳算法在求解互補(bǔ)問(wèn)題時(shí)陷入局部尋優(yōu)、過(guò)早收斂.

在進(jìn)行優(yōu)化搜索時(shí)，對(duì)個(gè)體的速度和位置進(jìn)行更新迭代，公式如下.

3　實(shí)例分析

通過(guò)改進(jìn)遺傳算法，將遺傳算法與粒子群算法相結(jié)合，提高算法的收斂速度和效率，選取經(jīng)典互補(bǔ)問(wèn)題的實(shí)例，應(yīng)用Matlab軟件運(yùn)行改進(jìn)的遺傳算法計(jì)算互補(bǔ)問(wèn)題，減少了求解互補(bǔ)問(wèn)題對(duì)初始點(diǎn)選取和對(duì)梯度信息的依賴(lài)，大大提高求解互補(bǔ)問(wèn)題近似解的效率.

應(yīng)用改進(jìn)遺傳算法求解互補(bǔ)問(wèn)題時(shí)，選取初始種群規(guī)模為100，進(jìn)化次數(shù)選為100，個(gè)體的速度范圍為[-1,1]，位置范圍為[-5,5]，交叉概率Pc=0.6，變異概率Pm=0.2，容許誤差e＜0.1.

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

此線性互補(bǔ)問(wèn)題的解為xT=()0.5,0,0.5,0,0.5，分別應(yīng)用遺傳算法和將遺傳算法與粒子群算法相結(jié)合的方法計(jì)算例題，通過(guò)進(jìn)行100次運(yùn)算，運(yùn)算結(jié)果如表1所示.

表1　驗(yàn)證結(jié)果分析

從表1可以看出，在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上引入粒子群算法，將兩種智能優(yōu)化算法相結(jié)合，明顯地提高了算法的準(zhǔn)確率，并且可以看出由于遺傳算法自身的缺陷，在求解互補(bǔ)問(wèn)題時(shí)準(zhǔn)確率不是很高，通過(guò)引入粒子群算法，可以避免遺傳算法在求解問(wèn)題時(shí)過(guò)早收斂和陷入局部尋優(yōu)，同時(shí)，在應(yīng)用改進(jìn)遺傳算法計(jì)算互補(bǔ)問(wèn)題時(shí)不需要了解初始點(diǎn)和梯度的信息，大大縮減了求解互補(bǔ)問(wèn)題的難度.

4　結(jié)論

本文借助極大熵函數(shù)法對(duì)互補(bǔ)問(wèn)題進(jìn)行光滑化，將互補(bǔ)問(wèn)題轉(zhuǎn)化為無(wú)約束的優(yōu)化問(wèn)題，并通過(guò)改進(jìn)遺傳算法，將遺傳算法和粒子群算法相結(jié)合來(lái)求解互補(bǔ)問(wèn)題.此方法不僅深化了遺傳算法在互補(bǔ)問(wèn)題方面的應(yīng)用，同時(shí)也擴(kuò)展了智能優(yōu)化算法在互補(bǔ)問(wèn)題方向的領(lǐng)域.實(shí)驗(yàn)結(jié)果表明，改進(jìn)的遺傳算法準(zhǔn)確率高、解的穩(wěn)定性好，是求解互補(bǔ)問(wèn)題的一種有效算法.

參考文獻(xiàn)：

［1］楊泰山，姜興武，王秀玉.線性互補(bǔ)問(wèn)題解的存在性［J］.吉林大學(xué)學(xué)報(bào)，2013，51（6）：1063-1067.

［2］匡芳君.群智能混合優(yōu)化算法及其應(yīng)用研究［D］.南京：南京理工大學(xué)，2014.

［3］孫菊賀，紀(jì)東辰，王琪.求解非線性互補(bǔ)問(wèn)題的一類(lèi)光滑牛頓算法［J］.沈陽(yáng)航空航天大學(xué)學(xué)報(bào)，2016，33（5）：74-81.

［4］Huang Z H，Gu W Z.A Smoothing-Type Algorithm for Solving Linear Complementarity Problems with Strong Convergence Properties［J］.Applied Mathematics&Optimi?zation，2008，57（1）：17-29.