求解非线性方程组的自适应细菌觅食算法

张晓明

（长春建筑学院 基础教学部，吉林 长春 130607）

： 针对传统的数值算法求解非线性方程组时对方程组要求高和初始值敏感等缺点，提出了一种自适应细菌觅食算法。该算法改变了传统算法的固定趋化步长，进行自适应调整，加快算法的收敛速度，具有更好的全局搜索能力，改变了固定迁移概率，避免了在进化后期精英解丢失的问题。将自适应细菌觅食算法应用到求解非线性方程组中，结果表明，与其他算法相比，该算法能够有效避免陷入局部最优，能更好地寻求最优解。

：细菌觅食算法；非线性方程组；自适应

传统的求解非线性方程组的方法主要有牛顿法、迭代法等，但这些方法对初始点的选取要求很精确，且要求方程组连续、可导等。近年来随着智能算法的兴起，其在求解非线性方程组问题上得到了很好的应用。2002年，PASSINO K M根据生物体大肠杆菌的觅食行为，提出了细菌觅食算法［12］(Bacterial Foraging Algorithm, BFA)。本文利用BFA很强的全局搜索能力和并行计算能力对非线性方程组进行求解，仿真实验表明了算法的有效性。

1问题描述

设非线性方程组形式如下：

f1(x1,x2,…,xn)=A1

f2(x1,x2,…,xn)=A2

…

fn(x1,x2,…,xn)=An （1）

非线胜方程组由n个方程组成，有n个未知变量，其中fi(x1,x2,…,xn)=Ai(i=1,2,…,n)为非线性方程，BFA对非线性方程组求解时，取目标函数的方式如下：

易证，当目标函数值等于零时的解为最优解。

2细菌觅食算法

细菌觅食算法是随机搜索的群智能优化算法，其模拟细菌觅食行为的数学模型在优化计算时，主要由4个步骤完成：趋向、聚集、复制、迁移。

2.1趋向性操作

大肠杆菌主要是依据自身鞭毛的旋转方向进行觅食。相应的数学模型解释为通过计算出的适应度值进行比较，决定细菌是继续前进还是寻找随机方向移动，当尝试次数达到最大限制数时选择下一个细菌进行趋向性的操作。

在BFA模型中，细菌的趋向性操作的数学表达式为：

其中，θi(j,k,l)表示细菌i在第j次趋向第k次复制第l次迁移操作之后所在的位置，C(i)为趋向步长长度，Δ(i)Δ(i)TΔ(i)为移动的一个随机前进方向。

2.2聚集性操作

聚集操作体现为引力和斥力，引力表示细菌会快速地聚集在一起围绕最优食物觅食。斥力表示细菌独立寻找食物的特性。公式为：

其中，dattractant是引力深度，wattractant是引力宽度，hrepellent是斥力高度，wrepellent是斥力宽度，θim为细菌i的第 m个分量。通常取dattractant=hrepellent，趋向性操作的适应度值表示为：

J(i,j+1,k,l)=J(i,j,k,l)+Jcc(θi(j+1,k,l),

P(j+1,k,l))（5）

即通过此引力和斥力操作影响适应度值的大小。

2.3复制性操作

在BFA模型中， Jihealth是细菌i的能量函数，其大小决定细菌觅食能力的强弱。将细菌觅食后的能量函数值进行大小排序，淘汰掉S2个能量值较小的细菌，将剩余的S2个细菌进行复制操作，新生成的复制细菌体与原细菌具有完全相同的觅食能力。

2.4迁移性操作

当局部区域的温度升高或者食物被消耗掉，必然导致细菌被迫迁移到新的区域去寻找食物，即为迁移操作。细菌按照一定的概率进行迁移，新种群的随机特性可能具有不同的觅食能力，这种随机特性能使群体跳出局部极值而更好地寻找全局最优解。

3自适应细菌觅食算法（ABFA）

3.1自适应趋向步长

在BFA进行趋向操作时，固定的步长对算法寻优有很大的影响，太大易忽略局部最优点，太小易陷入局部最优且用时较长。李珺等人［3］提出自适应调节步长，利用群体内细菌的最大最小距离构建步长调整方式，考虑因素缺少。综合算法各个参数进行耦合，提出自适应变步长的调整方式如下：

其中，V代表灵敏度；Ji为第i个细菌能量值；Jmax为最大能量值；Xmax与Xmin为变量的边界值；t为当前迭代次数；Tmax为最大迭代次数；s为大于 1 的整数，本文s取值范围［4］ 为［1,30］。V按照β非线性递减，迭代开始时离最优解较远，步长较大，当逐渐靠近最优解时，步长取值较小。该方法能较好地平衡全局搜索能力和局部搜索能力，提高了算法的有效性。

3.2自适应驱散概率

在传统BFA算法迁移操作中,细菌迁移概率是固定的，固定的迁移概率会引起优秀的细菌群体发生迁移，即丢失精英解，因此迁移操作导致解的退化，故在此提出自适应迁移概率。

其中：Ji为第i个细菌能量值，Jmax为最大、能量值，Javg为平均能量值，pmax、pmin为最大、最小变异概率。迁移概率按照能量值进行调整，形成良好的解空间状态。

4求解非线性方程组的流程

使细菌觅食算法的主要步骤如下。

（1）初始化参数：种群大小S、空间维数P、趋向性的次数Nc、趋向性最大步数Ns、复制操作次数Nre、迁移操作次数Ned、迁移概率Ped，细菌i的信息用D维向量表示。

（2）形成初始解的细菌群，按照式（5）计算细菌适应度，适应度函数中步长更新按照式（6）进行，存储最优值Jbest。

（3）趋向性循环操作。按照ABFA进行步长的参数调整，并计算相应适应度值。

（4）复制循环操作。按照趋向性操作后计算的适应度值进行从小到大排序，淘汰掉S2个适应度值较小即能量值较差的细菌，将剩余的适应度值较大的细菌进行复制，使其保存优越的性能。

（5）迁移循环操作。在经过趋向性和复制操作后，将细菌按照一定的迁移概率（式（7））进行迁移，分配到寻优的空间中。

（6）循环结束条件判断，输出结果。

5数值计算及分析

为了验证ABFA在求解非线性方程组的能力，本文针对参考文献［5］~［8］中典型的方程组进行求解测试。

例题1

f1(x)=x21+x22+x23－3=0

f2(x)=x21+x22+x1x2+x1+x2－5=0

f3(x)=x1+x2+x3－3=0

其中－1.732≤x1,x2,x3≤1.732，理论解为x*=(1,1,1)T。

例题2

f1(x)=x21－x2+1=0

f2(x)=x1－cos(0.5πx2)=0

其中x∈［－2,2］，理论解为x*=(－12,1.5)T，x*=(0,1)T，x*=(－1,2)T。

例题3

f1(x)=xx21+xx12－5x1x2x3－85=0

f2(x)=x31－xx32－xx23－60=0

f3(x)=xx31+xx13－x2－2=0

其中3≤x1≤5，2≤x2≤4，－1≤x3≤2，理论解为x*=(4,3,1)T。

数值计算环境在MATLAB 2010b操作环境编程运行。设置ABFA的参数：细菌的个数为S=50、Nc=20、Nre=20、Ned=4、Tmax=100、最大和最小变异概率为0.35和0.25，进行50次实验取平均值,实验结果见表1。

结果分析：平均适应度值越趋近于理论值0，表明算法性能更好。例1中ABC、PSO都能取得近似解，但计算的精度不够，ABFA利用其自适应调整参数的特性，跳出局部极值且计算出精确的解。例2中，由于传统PSO算法搜索的缺点，只能搜索到两组解，丢失解（-1,2），ABFA能搜索到第三组解，体现出该算法有更好的搜索性能。例3中，ABC［8］、QPSO［9］算法的搜索精度及成功率没有ABFA具有优势，且ABFA算法平均适应度值的精度优于其他两种算法。ABFA在计算时采用的是3层循环操作，使用MATLAB计算唯一的缺是点以牺牲时间为代价，用PSO及ABC计算的时间不超过10 s，而ABFA计算时间平均在20 s左右。该算法具有较好的全局搜索能力和求解的搜索精度且在求解非线性方程组上具有明显优势。

6结论

本文提出一种自适应的细菌觅食算法，改变传统细菌觅食算法在计算时步长和变异概率选取上的固定性，根据适应度值和计算次数进行自适应调整参数，增强了算法的快速收敛性能，提高了算法在求解全局最优解的能力和搜索精度，是一种较好求解非线性方程组的算法。

参考文献

［1］ PASSINO K M. Biomimicry of bacterial foraging for distributed optimization and control［J］.IEEE Control Systems Magazine,2002,22(3):5267.