基于遗传算法与模式搜索的混合算法求解绝对值方程

封京梅, 卢　楠

(1.陕西广播电视大学 工程管理系, 陕西 西安　710119; 2.西安电子科技大学 数学与统计学院， 陕西 西安　710126)



基于遗传算法与模式搜索的混合算法求解绝对值方程

封京梅1, 卢楠2

(1.陕西广播电视大学 工程管理系, 陕西 西安710119; 2.西安电子科技大学 数学与统计学院， 陕西 西安710126)

摘要：绝对值方程Ax-|x|=b是一类不可微的NP-hard问题.在假设A的奇异值>1的条件下，给出一种新的求解绝对值方程的混合算法：遗传算法和模式搜索法相结合的一种方法.该混合算法充分发挥了遗传算法较强的全局搜索能力和模式搜索法较强的局部搜索能力的优点，有效避开了遗传算法容易陷入早熟收敛，模式搜索法对初始点要求高的缺点，数值实验结果表明了该算法的可行性和有效性.

关键词：绝对值方程； 遗传算法； 模式搜索法

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]给出了求解绝对值方程的非内部连续化算法；文献[5,6]基于极大熵光滑化处理方法，给出了(1)式的极大熵自适应微粒群混合算法、极大熵牛顿算法;文献[7,8]给出了智能算法中的差分进化-单纯形混合算法、交叉熵蝙蝠算法进行求解，相比较传统的优化算法，效果很好.

本文在假设A的奇异值>1的条件下，将求解Ax-|x|=b转化为求解无约束优化问题，然后给出一种求解Ax-|x|=b的新方法：遗传算法与模式搜索的混合算法(GPS)，此混合算法在多个领域都有应用[9,10].

1问题转化

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

本文总是假设矩阵A的奇异值>1，则(1)式等价于如下无约束优化问题：

(2)

显然，(2)式的解x*=arg minf(x)是(1)式的近似解，问题(2)是一个不可微的优化问题，传统的优化算法需要梯度信息因而失效，下面我们引入GPS混合算法.

2遗传算法与模式搜索的混合算法

2.1遗传算法[11]

遗传算法(genetic algorithm,GA)是一种启发式算法，其基本原理是模拟生物界的“物竞天择、适者生存”的进化法则.首先将问题的可行解表示成遗传空间的染色体，初始化种群，计算每个个体的适应度值，对优良个体进行选择、交叉、变异等操作，产生新的种群，如此不停进化，最终找到最适应环境的染色体，解码，找到原问题的最优解.

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)

本混合算法的主要思想是先利用遗传算法进行全局搜索，连续进化10代得到新种群后，再利用模式搜索法进行一次局部寻优，两种算法不停的交替使用，直至满足终止条件，算法步骤如下：

Step1设置遗传算法参数，种群规模P,进化代数M，交叉概率Pc,变异概率Pm，模式搜索法参数，初始步长δ，加速因子α，缩减率β；

Step2利用GA初始化种群；

Step3计算个体的适应度值，进行选择、交叉、变异等操作；

Step4连续进化10代，判断是否满足终止条件，如果|x(k+1)-x(k)|≤ε,输出最佳染色体，如果否转到step5；

Step5以当前所得种群为初始种群，进行一次模式搜索寻优，如果初始步长δ≤ε，则停止迭代，得到最优点xk；否则转到step3.

3数值试验

为了测试GPS混合算法对求解Ax-|x|=b的有效性，先测试如下算例：

算例1考虑如下AVE，其中

这里A的奇异值>1，该AVE问题存在唯一解x=(-1,1)′.构造目标函数

通过转化将求解绝对值方程问题转化为求解无约束优化问题，下面给出混合算法的相关参数设置.

混合算法选择参数如下：群体规模p=50,进化代数maxgen=30,交叉概率pc=0.6，变异概率pm=0.1.

首先调用基本遗传算法，发现基本遗传算法容易出现如图1、图2所示的情况，由图1可知GA算法容易陷入局部最优，无法跳出，而图2显示GA算法进化30代后只得到了算例1的近似解(-0.994 4,1.002 9)′，局部搜索能力较差.

图1　GA算法(1)

图2　GA算法(2)

在同样的参数设置下，我们使用GPS混合算法求解算例1，混合算法优化过程中各代平均函数值和最优个体函数值变化如图3、图4所示，图3用遗传算法连续进化9代，发现只能达到问题的次优解(-1.001 7,1.002 8)′，图6用遗传算法连续进化10代后，使用1次模式搜索法寻优即可达到问题的最优解(-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的最优解.能否找到求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] 封京梅.求解一类绝对值方程组的非内部连续化算法[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] 袁麟博，章卫国，李广文.一种基于遗传算法-模式搜索法的无人机路径规划[J].弹箭与制导学报，2009,29(6):279-282.

[10] 周念清，陈剑桥，江思珉.基于遗传算法的模式搜索法求解地下水管理模型[J].勘察科学技术，2011,18(1):18-24.

[11] 梁艳春，吴春国，时小虎，等.群智能优化算法理论与应用[M].北京：科技出版社,2009.

[12] 刘洪霞，周永权.一种基于模式搜索算子的人工萤火虫优化算法[J].小型微型计算机系统，2011,32(10)：2 130-2 133.

[13] 吴兴远.模式搜索法在最优化问题中的应用[J].软件导报，2009,8(8):122-123.

[14] 陈宝林.最优化理论与算法[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-),女，河北石家庄人，讲师，在读博士研究生，研究方向：最优化理论与算法

基金项目：国家自然科学基金项目(11301409)

收稿日期:*2014-12-15