摘要:多阶段多模型的微粒群优化算法是一种改进的微粒群优化算法,具有较强的全局搜索能力。将非线性方程或非线性方程组的求解问题转化为函数优化问题,应用多阶段多模型的微粒群优化算法求解非线性方程组的解。计算中不需要使用目标函数的导数信息和初始点的信息,数值实验结果表明了该算法的有效性和可行性。
关键词:微粒群优化算法;多阶段;多模型;非线性方程组;函数优化
0引言
在科学技术及生产实践中,许多问题的求解最终往往是转化成求解非线性方程或非线性方程组。非线性方程或非线性方程组的求解是数值计算领域中较困难的问题,传统的解法如牛顿迭代法的收敛性和性能特征在很大程度上依赖于初始点的选择,对于许多复杂的非线性方程组,要选择一个较好的初始点是一件非常困难的事情。
微粒群优化算法[2、3](Particle Swarm Optimization,PSO)是由美国社会心理学家James Kennedy和电气工程师Russell Eberhart根据鸟群觅食行为模拟,于1995年共同提出的一种新的演化计算技术。该新的优化算法具有许多特点如:实现容易、收敛性强、性能良好等。
多阶段多模型的微粒群优化算法[4](MM-PSO)是一种改进的微粒群优化算法,将微粒群分多个阶段利用多种进化模型迭代进化,该改进算法具有比标准微粒群优化算法更容易找到全局最优解的优点。
本文利用多阶段多模型的微粒群优化算法求解非线性方程组,首先将求解非线性方程或非线性方程组的问题转化为函数的优化问题,然后利用转化过来的优化函数当作PSO算法的适应度函数进行优化求解,方程的求解不依赖于初始点和目标函数的导数信息。实验结果表明,应用多阶段多模型的微粒群优化算法对转化过来的函数进行优化求解,求解的结果是非线性方程或非线性方程组的有效解。
1多阶段多模型的微粒群优化算法
微粒群优化算法基于群体与适应度的优化算法,是通过对鸟群觅食行为的模拟得来。首先系统初始化微粒为一组随机解,所有微粒有位置和速度两个特征,微粒的适应度值是由其位置决定的,通过迭代来改变其速度与位置求出问题的解。其数学表述为:由N个微粒组成的群体,在D维的目标搜索空间中,第i(i=1,2,…,N)个微粒在第t代的位置坐标可表成向量xit=(xi1,xi2,…,xid, …,xiD)T,速度可表示为:vit=(vit1,vti2,…,vtid,…,vtiD)T,个体最优位置pBest可表示为:pit=(pti1,pti2,…,ptid,…,ptiD)T,种群的全局最优gBest可表示为:pgt=(ptg1,ptg2,…,ptgd,…,ptgD)T。
对于第i个微粒的第d维在第t+1代根据如下公式迭代更新:
其中,vtid—当前的速度,
—粒子i在第t次迭代后的新速度,
ω—惯性权重,
c1,c2—加速(学习)因子,
r1,r2—0到1之间均匀分布的随机数,
xtid—粒子i当前的位置,
—粒子i第t次迭代后的新位置。
加速因子c1,c2是调整微粒的自身经验与社会经验在其速度中所起作用的权重。如果c2=0,则微粒没有群体共享信息,只有自身经验,微粒个体之间没有交互,每个微粒仅受自己的飞行经验的影响,不受其它微粒的影响。它的特点是:微粒在目标空间里大范围搜索,不容易陷入局部最优点。此模型称之为Cognition Only模型[5],其迭代公式为:
算法迭代的终止条件一般根据具体问题选为最大迭代次数或者微粒搜索到的最优位置满足预先设定的最小适应阈值。
在应用微粒群优化算法求解普通问题时比较简单,容易求得满意的解。但是人们发现在实际应用过程中,PSO算法对于复杂优化问题求解时容易陷入局部极值[5]。针对微粒群优化算法求解复杂问题时易出现“早熟”收敛的现象,文献【4】提出了一种多阶段多模型的改进微粒群优化算法。考虑到寻优过程中不同阶段的开发与探测能力需求的差异,算法将寻优过程分成三个阶段,不同阶段采用不同的模型。
第一阶段利用标准微粒群优化算法发现局部极值的邻域,第二阶段利用Cognition Only模型快速找到局部极值点,以提高寻优效率,第三阶段,利用新的模型跳出局部极值点,以便寻找全局最优点。
其中第三阶段新的模型设计原理是为保证模型和标准PSO算法的结构形式一致并考虑微粒群算法的统计规律性,定义一个减速因子(与加速因子c1,c2对应)和一个0到1之间均匀分布的随机数(与r1,r2对应)。
模型迭代公式为:
其中ω,c1,c2,r1,r2与式(1),(2)定义相同,
c3—减速因子,
r3—0~1之间均匀分布的随机数。
2求解非线性方程组的MM-PSO算法
2.1非线性方程组的描述与转化
非线性方程或非线性方程组的求解问题是一个比较古老的数学问题,其数学模型一般可表示为:
f (X)=0(8)
在式(8)中,一般X被认为是在实数范围内待求解的n个未知量,可转换表示为f(x)=[f1(x), f2(x),…,fm(x)]T变量X的m维向量函数。将此方程写成分量的形式表示,即:
因此,原非线性方程或非线性方程组的求解问题,可等价于求解函数:
的优化问题。(10)
应用多阶段多模型的微粒群优化算法对非线性方程或非线性方程组的求解,可令转化过来的函数
作为微粒群优化算法的适应度函数。
2.2求解非线性方程及方程组的流程
步骤1初始化设置微粒群微粒的个数、最大迭代次数、惯性权重,加速因子、减速因子、标准PSO迭代阈值σ、模型迭代次数ε、各粒子初始位置和初始速度等。
步骤2将要求解的非线性方程或非线性方程组转化成要优化的函数。
步骤3评价各微粒的初始适应值、保存初始最好位置及初始最优适应值。
步骤4根据式(1)计算各微粒新的速度,根据式(2)计算各微粒新的位置、并对各微粒新的速度和位置进行限幅处理。
步骤5更新各微粒的个体历史最好适应值和个体历史最好位置;更新全局历史最好适应值和全局历史最好位置。
步骤6比较前后两次全局历史最好适应值的差,如果该差值大于我们事先设定标准PSO迭代阈值σ,返回步骤4,否则进入步骤7。
步骤7采用Cognition Only模型对粒子的速度和位置进行进化,并更新各微粒的个体历史最好适应值和个体历史最好位置;更新全局历史最好适应值和全局历史最好位置,按照设定的参数重复步骤7ε次后,转入步骤8。
步骤8采用式(5)与式(6)对粒子的速度和位置进行进化,并更新各微粒的个体历史最好适应值和个体历史最好位置;更新全局历史最好适应值和全局历史最好位置,按照设定的参数重复步骤8ε次后,转入步骤9。
步骤9若满足停止条件(迭代次数超过最大允许迭代次数),搜索停止,输出全局历史最好位置和全局历史最好适应值;否则,返回步骤7继续搜索。
3实验结果
将多阶段多模型的微粒群优化算法应用于非线性方程或非线性方程组的求解。多阶段多模型的微粒群优化算法的参数按文献【4】的设置为:ω取值从0.9线性衰变至0.4,加速因子c1,c2为2,减速因子c3为2,最大迭代次数为2000,微粒的数量为60,第三阶段模型的迭代次数ε为25。最小适应度阈值设为
多阶段多模型的微粒群优化算法是一种随机搜索算法,为了验证算法的有效性,对于每个算例都应用MM-PSO算法独立运行50次,将这50次运行的最终结果统计如表1所示:
应用多阶段多模型的微粒群优化算法求解以上三个算例每次都收敛,运算速度快,算法编程实现简单,并且每次都求得满意精度的解。
4结束语
多阶段多模型的微粒群优化算法是一种改进的微粒群优化算法,该改进算法具有更好的全局搜索寻优性能,本文应用多阶段多模型的微粒群优化算法对非线性方程及非线性方程组进行了求解。
对于非线性方程或非线性方程组的求解,传统数值方法一般都要应用到初始点信息和目标函数的导数信息,而一个好的初始点的选择是一件困难的事情。本文将非线性方程及非线性方程组的求解问题转化为函数优化问题,应用多阶段多模型的微粒群优化算法进行求解。该方法不需要初始点的信息和目标函数的导数信息,不易陷入局部解。测试实验的结果表明:该方法有效、求解精度高、算法实现简单。
参考文献:
[1] 李庆扬,莫孜中,祁力群.非线性方程组的数值解法[M].北京:科学出版社,1999.
[2] Kennedy J,Eberhart R. Particle Swarm Optimization[C].IEEE Int"1 Conf. on Neural Networks. Perth, Australia, IEEE Service Center Piscataway NJ, 1995. 1942~1948.
[3] Eberhart R, Kennedy J.A New Optimizer Using Particle Swarm Theory[C]. Proc. of the 6th International Symposium on Micro Machine and Human Science, Nagoya, Japan: IEEE Service Center Piscataway NJ, 1995. 39~43.
[4] 赵嘉,孙辉.多阶段多模型的改进微粒群优化算法[J].计算机工程与应用,2010,
[5] Eberhart R. Shi Y, Particle Swarm Optimization: Developments, applications and resources[C]. Proceedings of the IEEE congress on Evolutionary Computation (CEC2001), Seoul, Korea, 2001.81~84.
[6] 孙志忠,袁慰平,闻震初.数值分析[M].南京:东南大学出版社,2002.
[7] 臧明磊,杨士俊.用遗传算法解一元非线性方程[J].济宁师专学报,1998,19(6):
[8] 林成森.数值分析[M].北京:科学出版社,2006.
项目资助:南昌工程学院青年基金科技项目(2010KJ
018)。