改进粒子群优化算法的绝对值方程求解
曾京京
【摘 要】为了提高绝对值方程问题的求解精度,提出改进粒子群优化算法的绝对值方程求解方法.首先在粒子群的飞行过程中,对粒子位置进行评价,然后根据评价结果对粒子位置进行更新操作,保证粒子群向全局最优解搜索,最后应用于绝对值方程求解.结果表明,改进后的方法可以避免求解时易出现的早熟现象和难以获得局部最优解问题,能获得更高精度的绝对值方程解,而且迭代次数较少.%In order to improve the accuracy of absolute value equation,a method for solving the absolute value equation based on improved particle swarm optimization algorithm is proposed.Firstly,in the flight process of particle swarm,the position of particle is evaluated,and secondly the particle position is updated according to evaluation results to ensure particle swarm search to the global optimal solution, finally it is applied to absolute value equations.The results show that the improved method can avoid the premature phenomenon and easy to obtaining the local optimal solution,can obtain higher accuracy solution of absolute value equation,and the number of iterations are less.
【期刊名称】《内蒙古师范大学学报（自然科学汉文版）》 【年(卷),期】2017(046)001 【总页数】4页(P10-12,16)
【关键词】绝对值方程;粒子群优化算法;求解精度;迭代次数;位置更新
【作 者】曾京京
【作者单位】武汉华夏理工学院 信息工程学院,武汉 430223 【正文语种】中 文 【中图分类】O221
绝对值方程(Absolute Value Equation,AVE)与二次规划、双矩阵对策直接相关,其目标函数含有绝对值,求解过程是一个典型的非光滑优化问题,属于NP-hard难题[1].文献 [2] 将绝对值方程转换为一个凹优化进行求解,文献 [2] 采用牛顿法对其进行求解,但是它们主要针对绝对值方程存在唯一解进行求解,即事先设定一个初始点,所以无法求出绝对值方程的所有解.随着智能优化算法的不断发展,人们提出了遗传算法、微分进化算法、和声搜索算法、粒子群算法的绝对值方程求解方法[4-5],这些算法搜索能力强,具有并行运算能力,取得了不错的研究成果.其中,粒子群算法需要设置的参数少,能适应各种非线性函数,在绝对值方程中的应用更为广泛,但在实际应用中,传统粒子群算法易出现早熟现象,难以获得局部最优解[6].为了提高绝对值方程求解问题的求解精度,本文提出改进粒子群优化(improved particle swarm optimization,IPSO)算法的绝对值方程求解方法.首先在粒子群的飞行过程中,对粒子位置进行评价,然后根据评价结果对粒子位置进行更新操作,保证粒子群向全局最优解搜索,最后应用于绝对值方程求解.改进后的算法避免了传统粒子群算法在绝对值方程问题求解时存在的问题,可以获得更高精度的绝对值方程解,而且迭代次数较少,加快了绝对值方程求解的速度. 设A∈Rn×n; x,b∈Rn,绝对值方程定义为 b.
Mangasarian[2]的研究结果表,绝对值方程和广义线性互补问题等是等价的,并且存
在唯一非负解.传统算法对绝对值方程的目标函数解析条件有,同时求解速度慢,难以获得高精度的解,为此把绝对值方程问题转化为 min f(x),
x*=arg min f(x)即为绝对值方程的解. 2.1 标准粒子群优化算法
粒子群优化算法(PSO)是受鸟类觅食行为的启发发展起来的人工智能算法,通过不断改变粒子的速度和位置来搜索问题的最优解.粒子被看做觅食的鸟,而且粒子质量的优劣与实际问题中的目标函数相关,通常将实际问题中的目标函数作为粒子群的适应度函数,每一个粒子的适应度值与群体极值(Gbest)和个体极值(Pbest)进行比较,根据比较结果改变粒子飞行的速度与位置.设问题空间为M维,共有n个初始粒子,即X1,X2,…,Xn,第i个粒子的位置为Xi=(xi1,xi2,…,xiM)T (i=1,2,…,n),第i个粒子的Pbest、Gbest和速度分别为:
Pi=(pi1,pi2,…,piM)T,Pg=(pg1,pg2,…,pgM)T,Vi=(vi1,vi2,…,viM)T.在第k代,第i个粒子的速度和位置的更新方式为 ω()+c2r2(), i=1,2,…,n,
其中: ω表示惯性权值; c1,c2为加速因子; r1,r2为 [0,1]内的随机数. 2.2 标准粒子群优化算法的改进
在标准粒子群优化算法的工作过程中,粒子的速度和位置更新与参数ω,c1,c2密切相关,通常固定不变,主要依靠人为经验进行设置,无法进行动态调整,导致搜索效率低,难以找到问题的全局最优解.为此,本文将参数ω,c1,c2设置成变化的量,随着迭代次数的变化不断发生改变,不断自适应调整粒子搜索能力和速率,加快粒子的全局搜索效率,从而提高找到问题全局最优解的概率.ω与粒子个体适应度、迭代次数之间的变化关系为 ω,
其中: ωmin和ωmax分别为ω惯性权值的最小值和最大值; f,favg,fmin分别为个体适应度值、粒子群适应度的均值和粒子群适应度的最小值; kmax为最大迭代次数.c1和c2与迭代次数之间的变化关系为 .5,.5.
Step 1: 初始化粒子群,设置kmax,r1,r2的值,得到第i个粒子的初始速度和位置分别为Vi和Xi.
Step 2: 根据绝对值方程的目标函数估计粒子适应度值,并确定Pbest和Gbest的值.
Step 3: 根据(4)式和(5)式计算参数ω,c1,c2的值,并根据(3)式对粒子的速度和位置进行更新.
Step 4: 重新根据绝对值方程的目标函数估计粒子适应度值,并与Pbest和Gbest进行比较,同时对Pbest和Gbest进行更新操作.
Step 5: 判断迭代次数是否达到kmax条件,若满足该条件,则终止搜索,否则转Step 3继续搜索.
Step 6: 根据Gbest对应的位置得到绝对值方程的最优解.
为了测试改进粒子群优化(IPSO)算法对绝对值方程求解的有效性,采用Matlab 2012a编写程序进行仿真测试.为了便于分析IPSO的性能,选择标准粒子群优化算法(PSO)、遗传算法(GA)和声搜索算法(HS)进行对比实验,均运行10次,取
kmax=20 000.设计两个算例,其中=b中A的奇异值大于1,对绝对值方程有唯一解.当前种群数量为20时,所有算法对绝对值方程求解10次的适应度函数的最优值、均值、最差值和运行时间见表1,同时给出所有算法的适应度函数均值的收敛曲线和最优适应度值的盒图,如图1和图2所示.对表1和图1、图2的测试结果进行分析可以发现,IPSO算法的结果明显优于对比算法,IPSO算法的全局搜索能力更强,同时IPSO算法的运行时间更少,加快了绝对值方程求解的速度,可以满足大规模绝对
值方程的求解要求.
综上所述,结合绝对值方程问题的NP-hard特点,针对传统粒子群优化算法存在的缺陷,设计了基于改进粒子群优化算法的绝对值方程求解方法,并采用测试实验验证了改进粒子群优化算法的有效性和优越性.测试果表明,改进粒子群优化算法具有更好的搜索能力,改善了绝对值方程的求解效率,为求解大规模绝对值方程问题提供了一种有效的方法.
【相关文献】
[1] 雍龙泉,张社民,张建科,等. 绝对值方程研究进展 [J]. 陕西理工学院学报:自然科学版,2012,28(1):17-23.
[2] Mangasarian O L. Knapsack feasibility as an absolute value equation solvable by successive linear programming [J]. Optimization Letters,2009,3(2):161-170. [3] 雍龙泉,拓守恒. 基于凝聚函数的拟牛顿算法求解绝对值方程 [J]. 系统科学与数学,2012,32(11):1427-1436.
[4] Iqbal J,Iqbal A,Arif M. Levenberg-marquardt method for solving systems of absolute value equations [J]. Journal of Computational & Applied Mathematics,2015,282(9):134-138.
[5] 雍龙泉,刘三阳,拓守恒,等. 改进的和声搜素算法求绝对值方程 [J]. 黑龙江大学自然科学学报,2013,6(3):322.
[6] 封京梅. 基于惯性权重指数递减的粒子群优化算法求解绝对值方程 [J]. 吉林大学学报:理学版,2016,54(6):1265-1269.
