基于狼群算法求解多项式方程的根

杨楠+郭德龙

【摘 要】针对在工程和科学计算中经常遇到多项式方程求解根的问题，传统的方法有二分法、牛顿法等，但它们收敛速度慢，效率低。对于上述缺点，本文提出狼群算法求解多项式方程根的问题，利用狼群算法的计算鲁棒性和全局收敛性多次迭代寻找方程的最优解。与其他的算法相比，有相对更好的稳定性和全局寻优能力。最后通过数值仿真实验，结果表明该算法能有效的求出多项式方程的根，并且精度高，收敛速度快。

【关键词】多项式方程的根；二分法；狼群算法；最优解

【Abstract】For often encountered in engineering and scientific computing polynomial equation root of the problem， traditional methods have a dichotomy， Newtons method and so on. However，they are not the best way to engineering because the convergence is slow and low inefficient. As for these shortcomings， this paper had been proposed Wolves Algorithm to make out polynomial equation roots of the problem. It use the advantages of Wolves Algorithm computational robustness and global convergence of multiple iterations of the equation to find the optimal solution. Compared with other algorithms， there was relatively better stability and global optimization. Finally， a numerical simulation results show that the algorithm can effectively find the roots of a polynomial equation. Whats more， it can work accurately and quickly.

【Key words】Polynomial equation roots； Dichotomy； Wolves Algorithm； Optimality solution

0 引言

求解多项式方程的历史可以说成是一部代数学史，人们很早就开始探索高次方程的数值求解法的问题。随着计算机的不断发展，求解多项式方程的方法研究也有了飞速的发展，传统求解多项式方程根的方法有牛顿法、二分法等以上方法，但也受到一些条件限制如对初始值的选取是否恰当。针对以上的问题，现提出一种模拟狼群分工协作式捕猎行为的群体智能算法——狼群算法求解多项式方程根，该算法具有较好的计算鲁棒性和全局搜索能力，并通过数值仿真实验的结果优于其他迭代法所求结果，是一种求解多项式方程根的数值解的方法。

1 狼群算法

1.1 狼群算法[1]简介

在自然界中，众所周知狼是群居动物，每匹狼都在狼群中扮演者重要的角色，狼的成功是狼与狼之间的默契配合，它们总能依靠团体的力量去完成每一件事。因此许多狼研究者对于狼的捕食行为提出了一种仿生智能优化算法——狼群算法（Wolf algorithm，简称WA）。2011年，华北电力大学的鄢小虎和柳长安等学者提出了将狼群算法应用在移动机器人路径规划上，主要过程如下：

1）游猎过程：狼个体釆用爬山法搜索当前所在位置附近的局部最优值；

2）围攻过程：狼个体利用群体中最优狼个体的信息搜索全局最优值；

3）食物的分配过程：按“优胜劣汰”的分食原则，最壮的狼更容易得到食物，而最弱小的狼只能被饿死。新狼代替死狼，狼群得到更新，使狼群多样化。

这些步骤如图1[2]所示。

1.2 狼群算法的原理[2]

以迭代的方式不断地寻找最优值，狼群的位置及优化问题的解。狼群通过初始化狼群、竞争领导者狼、向领导者狼移动、包围猎物以及分配食物五个步骤来实现求解最优化问题。

1.2.5 分配食物

根据狼群的事物分配的原则，精壮的狼将优先获取食物，而接着在分配给较为弱小的狼。这样分配食物可能会导致最为弱小的狼会饿死。但是能确保精壮的狼能够继续生存下去，使得种群有着更好的适应能力。据优胜劣汰原则，移除最差的m匹狼，然后随机生成m匹狼。这样种群不易陷入局部最优，且使得种群具有多样性。

1.3 狼群算法的步骤

Step1. 初始化。狼群中有n个狼，最差的有m个狼，首领狼有q匹，搜索h个方向得到最大的搜索次数是max dh，搜索步长和移动步长分别为stepa和stepb，ra和ra分别为围攻步长的最大值最小值，max t是最大迭代次数。初始化每匹狼的位置用公式（1）；

Step2.选最优的q匹狼通过搜索来竞争首领狼，第i匹竞争狼通过式（2）不断向前搜索到最优的位置；

Step3.众多的竞争狼中选出最厉害的狼作为领导者，剩下的狼向着领导者靠近移动，位置按（3）式更新；

Step4.首领狼搜索到猎物。其他狼包围猎物，通过式（4）对其位置进行更新，并对更新后的位置依照公式（5）进行越界处理；

Step5.对狼群的更新是按照狼群分配食物的原则，除掉最差的m匹狼，同时 m匹狼通过（1）随机产生。

Step6.一次迭代结束，进行下一次迭代，判断是否满足结束的条件，满足条件退出循环，记录结果；不满足条件，转到step2。

1.4 狼群算法的流程图[4]

2 狼群算法求解多项式方程的步骤

Step1.初始化狼群，包括各初始化仿真参数，狼群的个数N_num、最大的迭代次数Max_iter，探狼比例因α，最大游走次数T_max，距离判定因子w，步长因子S等等；

Step2.初始化头狼，通过迭代计数剔除最次狼个数，同时初始化出除头狼外的最佳人工狼为探狼，并执行游走行为，直到某只探狼比头狼感知猎物的气味浓度大或者达到最大游走次数。

Step3.狼个体的游猎过程，旨在寻找多项式方程的局部最优值，是求解多项式方程根的算法的中间力量。根据侦查出的气味浓度，更新头狼及其位置，并发起召唤行为，实现了多项式方程根的多样性，避免算法陷入局部极值。

Step4.统计狼群信息选出探狼和猛狼，如果猛狼离猎物更近，置为头狼，然后发起召唤，执行围攻行为，不断更新头狼，并记录当前位置；

Step5.判断算法是否合理，如果达到优化精度要求或者最大迭代次数T_max，说明算法合理，则输出头狼的位置，即为多项式方程的最优根，同时结束迭代，否则转向步骤4；

Step6.采用多次迭代的方式降低狼群算法求解多项式方程根的随机性，通过人为设定循环次数来终止算法，从而得出多项式方程的最优解。

3 仿真实验

仿真实验在以下硬件环境中进行：CPU：Intel（R） Core（TM）i5-2520M CPU @ 2.50GHz2.50 GHz 内存：4.00GB 操作系统：Windows8 系统类型：64位程序 执行软件：matlab R2010a。

以下二个例子都是在固定的参数条件下进行运算，其中狼群个数 N_num=30，1b=-4，ub=3，x=1b：0.05：ub；未知量个数dim=1；仿真参数 Alpha=4，Beta=6，w=1000，S=2000，h=20，T_max=20。

例1 求解多项式方程[5] x2-3=0在区间x∈[0，4]的一个根。

例2 求解多项式方程[6]：x3-x-1=0在区间[1.0，1.5]内的一个实根。

4 结束语

根据狼群算法的捕食原理，将其与求解多项式方程根相结合，提出了一种基于狼群算法求解多项式方程根的算法。利用狼群为了生存，不断在头狼的带领下搜寻、围捕猎物的过程，一步步的接近多项式方程的最优值，从而最终找到全局的最优解。通过仿真实验，与其他多种算法的比较，证明了同等条件下狼群算法对于数值问题的求解，是一种收敛更快速，结果更精确的有效方法。

【参考文献】

[1]王传伟.基于狼群算法的三维传感器优化布置研究[J].大连理工大学，2014（6）：13-17.

[2]Seyedali Mirjalili，Seyed Mohammad Mirjalili，Andrew Lewis. Grey Wolf Optimizer[J]. School of Information and Communication Technology， Griffith University， Nathan， Brisbane， QLD 4111.

[3]周强.狼群算法与萤火虫群优化算法及其应用研究[D].广西民族大学，2014， 44：4-7

[4]周强，周永权.一种基于领导者策略的狼群搜索算法[J].广西民族大学，信息科学与工程学院，2013，9（30）：2630-2632.

[5]李瑞芳.非线性方程求解的不动点算法及其研究[D].长沙学院：本科学位论文，2012，2（24）：6-10.

[6]李庆扬，王能超，易大义.数值分析[M].北京：清华大学出版社，2008.

[责任编辑：杨玉洁]