封京梅, 盧　楠

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

?

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

封京梅1, 盧楠2

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

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

關鍵詞：絕對值方程； 遺傳算法； 模式搜索法

0引言

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

Ax-|x|=b

(1)

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

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

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

1問題轉化

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

本文總是假設矩陣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ōu)良個體進行選擇、交叉、變異等操作，產生新的種群，如此不停進化，最終找到最適應環(huán)境的染色體，解碼，找到原問題的最優(yōu)解.

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

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

(1)給定初始點x(1)∈Rn，n個坐標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轉步驟(2).

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

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

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

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

Step2利用GA初始化種群；

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

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

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

3數值試驗

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

算例1考慮如下AVE，其中

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

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

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

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

圖1　GA算法(1)

圖2　GA算法(2)

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

給定矩陣的階數n,調用本文算法，可以快速得到AVE的解.

4 結論

考慮到絕對值方程Ax-|x|=b是一類不可微的NP-hard問題，本文設計了一種基于模式搜索的遺傳算法(GPS)，GPS混合算法充分利用遺傳算法極強的全局搜索能力和模式搜索法極好的局部搜索能力，同時有效避開了遺傳算法容易陷入局部收斂，模式搜索法對初始點要求高的缺點，數值試驗表明該GPS混合算法僅需較少的進化代數，可求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] 封京梅.求解一類絕對值方程組的非內部連續(xù)化算法[J],陜西科技大學學報(自然科學版),2011,29(2):165-169.

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

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

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

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

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

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

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

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

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

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

[15] 史峰,王輝,胡斐,等.MATLAB智能算法30個案例分析[M].北京：北京航空航天大學出版社,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

文獻標志碼：A

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

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

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

收稿日期:*2014-12-15