基于遺傳算法與模式搜索的混合算法求解絕對值方程

封京梅, 盧　楠

(1.陜西廣播電視大學(xué) 工程管理系, 陜西 西安　710119; 2.西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院， 陜西 西安　710126)

?

基于遺傳算法與模式搜索的混合算法求解絕對值方程

封京梅1, 盧楠2

(1.陜西廣播電視大學(xué) 工程管理系, 陜西 西安710119; 2.西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院， 陜西 西安710126)

摘要：絕對值方程Ax-|x|=b是一類不可微的NP-hard問題.在假設(shè)A的奇異值>1的條件下，給出一種新的求解絕對值方程的混合算法：遺傳算法和模式搜索法相結(jié)合的一種方法.該混合算法充分發(fā)揮了遺傳算法較強的全局搜索能力和模式搜索法較強的局部搜索能力的優(yōu)點，有效避開了遺傳算法容易陷入早熟收斂，模式搜索法對初始點要求高的缺點，數(shù)值實驗結(jié)果表明了該算法的可行性和有效性.

關(guān)鍵詞：絕對值方程； 遺傳算法； 模式搜索法

0引言

考慮如下形式的絕對值方程(absolute value equations, AVE)：

Ax-|x|=b

(1)

其中A∈Rn×n,x,b∈Rn,|x|表示對x的各個分量取絕對值.

首先Mangasarian在文獻[1]中給出了(1)式有唯一解、非負(fù)解、2n個解及無解的充分條件，之后許多學(xué)者在(1)式存在唯一解的前提下對其算法進行了深入的研究；文獻[2,3]在無任何假設(shè)條件下把AVE用半光滑牛頓算法轉(zhuǎn)換為二階錐互補問題，利用二階錐互補問題的研究結(jié)果，給出了AVE解的凸性；文獻[4]給出了求解絕對值方程的非內(nèi)部連續(xù)化算法；文獻[5,6]基于極大熵光滑化處理方法，給出了(1)式的極大熵自適應(yīng)微粒群混合算法、極大熵牛頓算法;文獻[7,8]給出了智能算法中的差分進化-單純形混合算法、交叉熵蝙蝠算法進行求解，相比較傳統(tǒng)的優(yōu)化算法，效果很好.

本文在假設(shè)A的奇異值>1的條件下，將求解Ax-|x|=b轉(zhuǎn)化為求解無約束優(yōu)化問題，然后給出一種求解Ax-|x|=b的新方法：遺傳算法與模式搜索的混合算法(GPS)，此混合算法在多個領(lǐng)域都有應(yīng)用[9,10].

1問題轉(zhuǎn)化

引理1[1]對任意的b∈Rn，若A的奇異值>1，則AVE存在唯一解.

本文總是假設(shè)矩陣A的奇異值>1，則(1)式等價于如下無約束優(yōu)化問題：

(2)

顯然，(2)式的解x*=arg minf(x)是(1)式的近似解，問題(2)是一個不可微的優(yōu)化問題，傳統(tǒng)的優(yōu)化算法需要梯度信息因而失效，下面我們引入GPS混合算法.

2遺傳算法與模式搜索的混合算法

2.1遺傳算法[11]

遺傳算法(genetic algorithm,GA)是一種啟發(fā)式算法，其基本原理是模擬生物界的“物競天擇、適者生存”的進化法則.首先將問題的可行解表示成遺傳空間的染色體，初始化種群，計算每個個體的適應(yīng)度值，對優(yōu)良個體進行選擇、交叉、變異等操作，產(chǎn)生新的種群，如此不停進化，最終找到最適應(yīng)環(huán)境的染色體，解碼，找到原問題的最優(yōu)解.

2.2模式搜索法(PS)[12-14]

1961年，Hooks和Jeeves提出了模式搜索法(pattern search,PS)，PS的基本思想，從幾何意義上講，是尋找具有較小函數(shù)值的“山谷”，試圖用迭代產(chǎn)生的序列沿“山谷”走向逼近極小點.PS計算步驟如下：

(1)給定初始點x(1)∈Rn，n個坐標(biāo)e1,e2,…,en，初始步長δ，加速因子α≥1，縮減率β∈(0,1)，允許誤差ε>0,置y(1)=x(1),k=1,j=1.

(2)如果f(y(j)+δej)

(3)如果f(y(j)-δej)

(4)如果j

(5)如果f(y(n+1))

(6)置x(k+1)=y(n+1),令y(1)=x(k+1)+α(x(k+1)-x(k))置k:k+1,j=1轉(zhuǎn)步驟(2).

(7)如果δ≤ε，則停止迭代，得點x(k)；否則，置δ:=βδ,y(1)=x(k),x(k+1)=x(k)，置k:k+1,j=1,轉(zhuǎn)步驟(2).

2.3基于模式搜索的遺傳算法(GPS)

本混合算法的主要思想是先利用遺傳算法進行全局搜索，連續(xù)進化10代得到新種群后，再利用模式搜索法進行一次局部尋優(yōu)，兩種算法不停的交替使用，直至滿足終止條件，算法步驟如下：

Step1設(shè)置遺傳算法參數(shù)，種群規(guī)模P,進化代數(shù)M，交叉概率Pc,變異概率Pm，模式搜索法參數(shù)，初始步長δ，加速因子α，縮減率β；

Step2利用GA初始化種群；

Step3計算個體的適應(yīng)度值，進行選擇、交叉、變異等操作；

Step4連續(xù)進化10代，判斷是否滿足終止條件，如果|x(k+1)-x(k)|≤ε,輸出最佳染色體，如果否轉(zhuǎn)到step5；

Step5以當(dāng)前所得種群為初始種群，進行一次模式搜索尋優(yōu)，如果初始步長δ≤ε，則停止迭代，得到最優(yōu)點xk；否則轉(zhuǎn)到step3.

3數(shù)值試驗

為了測試GPS混合算法對求解Ax-|x|=b的有效性，先測試如下算例：

算例1考慮如下AVE，其中

這里A的奇異值>1，該AVE問題存在唯一解x=(-1,1)′.構(gòu)造目標(biāo)函數(shù)

通過轉(zhuǎn)化將求解絕對值方程問題轉(zhuǎn)化為求解無約束優(yōu)化問題，下面給出混合算法的相關(guān)參數(shù)設(shè)置.

混合算法選擇參數(shù)如下：群體規(guī)模p=50,進化代數(shù)maxgen=30,交叉概率pc=0.6，變異概率pm=0.1.

首先調(diào)用基本遺傳算法，發(fā)現(xiàn)基本遺傳算法容易出現(xiàn)如圖1、圖2所示的情況，由圖1可知GA算法容易陷入局部最優(yōu)，無法跳出，而圖2顯示GA算法進化30代后只得到了算例1的近似解(-0.994 4,1.002 9)′，局部搜索能力較差.

圖1　GA算法(1)

圖2　GA算法(2)

在同樣的參數(shù)設(shè)置下，我們使用GPS混合算法求解算例1，混合算法優(yōu)化過程中各代平均函數(shù)值和最優(yōu)個體函數(shù)值變化如圖3、圖4所示，圖3用遺傳算法連續(xù)進化9代，發(fā)現(xiàn)只能達到問題的次優(yōu)解(-1.001 7,1.002 8)′，圖6用遺傳算法連續(xù)進化10代后，使用1次模式搜索法尋優(yōu)即可達到問題的最優(yōu)解(-1.000 0,1.000 0)′.實驗結(jié)果顯示GPS混合算法求解AVE非常有效.

圖3　GPS算法(1)

圖4　GPS算法(2)

為了測試GPS混合算法求解Ax-|x|=b的有效性，求解如下隨機生成的算例，矩陣A(奇異值>1)和向量b有如下MATLAB[15]R2010a程序生成：

rand ('state',0);

R=rand (n, n);

b=100*rand (n,1);

A=R'* R+ n*eye(n);

給定矩陣的階數(shù)n,調(diào)用本文算法，可以快速得到AVE的解.

4 結(jié)論

考慮到絕對值方程Ax-|x|=b是一類不可微的NP-hard問題，本文設(shè)計了一種基于模式搜索的遺傳算法(GPS)，GPS混合算法充分利用遺傳算法極強的全局搜索能力和模式搜索法極好的局部搜索能力，同時有效避開了遺傳算法容易陷入局部收斂，模式搜索法對初始點要求高的缺點，數(shù)值試驗表明該GPS混合算法僅需較少的進化代數(shù)，可求AVE的最優(yōu)解.能否找到求AVE的更好算法，是筆者以后研究的重點.

參考文獻

[1] Mangasarian O L,Meyer R R.Absolute value equations[J].Linear Algebra and Its Application,2006,419(5):359-367.

[2] Hu Shenglong,Huang Zhenghai.A note on absolute value equations[J].Optimization Letters,2009,4(3):417-424.

[3] Hu Shenglong,Huang Zhenghai,Zhang Qiong.A generalized newton method for absolute value equation associated with second order cones[J].Computational Optimaization and Applications,2011,235:1 490-1 501.

[4] 封京梅.求解一類絕對值方程組的非內(nèi)部連續(xù)化算法[J],陜西科技大學(xué)學(xué)報(自然科學(xué)版),2011,29(2):165-169.

[5] 雍龍泉，孫培民，高凱.極大熵自適應(yīng)微粒群混合算法求解絕對值方程[J].計算機應(yīng)用研究，2011,28(7)：2 479-2 481．

[6] 鄧永坤,王海軍,張萍.基于極大熵牛頓法求解絕對值方程[J].計算機應(yīng)用研究，2012,29(12):4 546-4 548．

[7] 雍龍泉.基于差分進化-單純形混合算法求解絕對值方程[J].計算機應(yīng)用研究，2011,28(9):3 327-3 329．

[8] 李國成,肖慶憲.絕對值方程的交叉熵蝙蝠算法求解[J].計算機應(yīng)用研究，2014,31(10):2 965-2 968．

[9] 袁麟博，章衛(wèi)國，李廣文.一種基于遺傳算法-模式搜索法的無人機路徑規(guī)劃[J].彈箭與制導(dǎo)學(xué)報，2009,29(6):279-282.

[10] 周念清，陳劍橋，江思珉.基于遺傳算法的模式搜索法求解地下水管理模型[J].勘察科學(xué)技術(shù)，2011,18(1):18-24.

[11] 梁艷春，吳春國，時小虎，等.群智能優(yōu)化算法理論與應(yīng)用[M].北京：科技出版社,2009.

[12] 劉洪霞，周永權(quán).一種基于模式搜索算子的人工螢火蟲優(yōu)化算法[J].小型微型計算機系統(tǒng)，2011,32(10)：2 130-2 133.

[13] 吳興遠(yuǎn).模式搜索法在最優(yōu)化問題中的應(yīng)用[J].軟件導(dǎo)報，2009,8(8):122-123.

[14] 陳寶林.最優(yōu)化理論與算法[M].2版.北京:清華大學(xué)出版社,2005:332-343.

[15] 史峰,王輝,胡斐,等.MATLAB智能算法30個案例分析[M].北京：北京航空航天大學(xué)出版社,2011.

Pattern search method for solving absolute value equation

based on genetic algorithm

FENG Jing-mei1, LU Nan2

(1.Department of Engineering Management, Shaanxi Radio & TV University, Xi′an 710119, China; 2.School of Mathematics and Statistics， Xidian University, Xi′an 710126, China)

Abstract:Absolute value equations Ax-|x|=b is a non-differentiable NP-hard problem in its general form.A new hybrid algorithm for solving absolute value equations is proposed under the condition that all singular values of A exceed one,genetic algorithm and pattern search hybrid algorithm.The hybrid algorithm had sufficiently displayed the characteristics of genetic algorithm′s group searching and pattern search method′s local strong searching.Effectively avoid the genetic algorithm is easy to fall into premature convergence and pattern search method is require accurate of the initial point .Numerical results show that the feasibility and effectiveness of the hybrid algorithm.

Key words:absolute value equations; genetic algorithm; pattern search method

中圖分類號：O24

文獻標(biāo)志碼：A

文章編號：1000-5811(2015)02-0173-04

作者簡介:封京梅(1983-),女，河北石家莊人，講師，在讀博士研究生，研究方向：最優(yōu)化理論與算法

基金項目：國家自然科學(xué)基金項目(11301409)

收稿日期:*2014-12-15