一种改进的和声搜索算法求解非线性互补问题

雍龙泉, 熊文涛

(1. 陕西理工大学 数学与计算机科学学院, 陕西 汉中 723000;2. 湖北工程学院 数学与统计学院, 湖北 孝感 432000)

互补问题的理论研究和数值算法是最优化理论研究领域中一个重要的课题，它为数学规划提供了一个统一的研究框架，已成为数学规划的一个重要分枝[1-8]。近十年新的理论成果和新的求解方法层出不穷[9-16]，对称锥互补问题[17]、张量互补问题[18-21]、互补约束优化[22]等成为目前的研究热点。

光滑牛顿法是解决互补问题最常用的方法之一，它利用NCP函数，可以将互补问题转化为等价的光滑方程组并加以求解，其关键问题就是NCP函数的构造[23-29]。此外，针对多个解的互补问题，传统算法无法同时找到多个解(如何找到尽可能多的解，该方面的研究较少)，因此针对求解具有多个解的互补问题还存在一定的困难。

本文提出一种求解互补问题的新方法，具体做法是利用NCP函数把互补问题转化为一个非线性方程组，采用智能优化算法求解与之等价的无约束优化问题并获得原问题的解(对多个解的互补问题，由于智能优化算法是多点寻优，因此就可能找到多个解)。该方法对函数F(x)的单调性无要求。

1 互补问题转化为无约束优化

互补问题就是求一个向量x=(x1,x2,…,xn)T∈Rn，使得

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

(1)

其中F:Rn→Rn，F(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 函数φ:R2→R被称为NCP函数，如果对任意(a,b)T∈R2，有

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

结合NCP函数的性质，互补问题(1)可等价地转化为方程组

(2)

再通过求解如下优化问题

(3)

得到非线性方程组(2)的近似解，即互补问题(1)的近似解。

若无约束优化问题(3)收敛到零，则原问题可解；若无约束优化问题(3)无法收敛到零，则原问题可能无解。下面利用改进的和声搜索算法求解问题(3)。

2 改进的和声搜索算法

和声搜索(Harmony Search,HS)算法模拟了音乐创作中的过程，在该过程中，演奏者凭借自己的记忆，反复调整乐队中各乐器的音调，最终达到一个美妙的和声状态[30-31]。经典和声搜索算法步骤如图1所示。和声搜索算法也存在早熟现象，为了维持种群的多样性并加快收敛速度，给出一种结合位置更新和小概率变异策略的全局和声搜索(NGHS)算法，如图2所示。其中Xbest与Xworst分别表示当前和声记忆库HM中最好的和声与最差的和声。NGHS算法的特点：初期所有的种群较为分散，于是Xs较大，有利于做全局搜索；后期种群都在向近似解聚集，从而Xs变小，这有利于算法做局部搜索。变异概率pm既保持种群多样性，又能保证算法收敛。NGHS算法能够较好地求解一些复杂优化问题[32-34]，下面采用NGHS算法求解无约束优化问题(3)。

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

算法说明：XL与XU分别表示搜索空间的下界与上界。HS与NGHS算法的主要区别有两点：①新的和声Xnew产生方式不同；②种群更新策略不同，HS采用的是精英更新模式，而NGHS直接用Xnew替换掉Xworst(不论Xnew是否优于Xworst)。

3 数值实验

本节给出3个互补问题的数值实验验证。

利用定义1中的NCP函数将其转化为无约束优化问题，采用NGHS算法求解，算法程序用MATLABR2009a编写，在32位的Windows XP系统下运行。为了便于研究NGHS算法的搜索性能，同时给出HS、HSCH[35]、HSWB[36]的求解结果，算法参数选取：HMS=10，HMCR=0.85，PAR=0.35，最大迭代次数Tmax=50 000，搜索空间为[-5,5]n；在NGHS中选取pm=0.005；4种算法各运行10次。

算例1 考虑非线性互补问题,其中

该非线性互补问题的唯一解为x*=(0,3,1,0,0)T。表1给出了4种算法运行10次的结果(运行时间取10次的平均值)。图3是4种算法运行10次的收敛曲线和最优目标值的分布盒图,图4给出了NGHS算法运行10次后得到的结果。从图4中可以看出：每一列表示每次NGHS运行结束后最好适应值对应的和声。

表1 算例1的计算结果比较

(a) 收敛曲线 (b) 最优目标值分布盒图图3 算例1的平均适应值收敛曲线和最优目标值分布盒图

图4 NGHS算法运行10次后得到的结果(每次都收敛到唯一解)

算例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次的结果。图5给出了收敛曲线和最优目标值的分布盒图,图6给出了NGHS算法运行10次后得到的结果。

表2 算例2的计算结果比较

(a) 收敛曲线 (b) 最优目标值分布盒图图5 算例2的平均适应值收敛曲线和最优目标值分布盒图

图6 NGHS算法运行10次后得到的结果(4个解都找到了)

算例3考虑非线性互补问题,其中

该问题有无穷多个解x*=(λ,0,0,0)T,λ∈[0,3]。表3给出了4种算法运行10次的结果。图7给出了NGHS算法运行10次后得到的结果。

表3 算例3的计算结果比较

图7 NGHS算法运行10次后得到的结果(找到了6个解)

计算结果表明：对于唯一解的互补问题，都收敛到唯一解；对于具有多个解的互补问题，能够找到尽可能多的解；如需得到较高精度的数值解，通过增加迭代次数可以实现。