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

楊楠+郭德龍

【摘 要】針對在工程和科學(xué)計算中經(jīng)常遇到多項式方程求解根的問題，傳統(tǒng)的方法有二分法、牛頓法等，但它們收斂速度慢，效率低。對于上述缺點，本文提出狼群算法求解多項式方程根的問題，利用狼群算法的計算魯棒性和全局收斂性多次迭代尋找方程的最優(yōu)解。與其他的算法相比，有相對更好的穩(wěn)定性和全局尋優(yōu)能力。最后通過數(shù)值仿真實驗，結(jié)果表明該算法能有效的求出多項式方程的根，并且精度高，收斂速度快。

【關(guān)鍵詞】多項式方程的根；二分法；狼群算法；最優(yōu)解

【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 引言

求解多項式方程的歷史可以說成是一部代數(shù)學(xué)史，人們很早就開始探索高次方程的數(shù)值求解法的問題。隨著計算機的不斷發(fā)展，求解多項式方程的方法研究也有了飛速的發(fā)展，傳統(tǒng)求解多項式方程根的方法有牛頓法、二分法等以上方法，但也受到一些條件限制如對初始值的選取是否恰當。針對以上的問題，現(xiàn)提出一種模擬狼群分工協(xié)作式捕獵行為的群體智能算法——狼群算法求解多項式方程根，該算法具有較好的計算魯棒性和全局搜索能力，并通過數(shù)值仿真實驗的結(jié)果優(yōu)于其他迭代法所求結(jié)果，是一種求解多項式方程根的數(shù)值解的方法。

1 狼群算法

1.1 狼群算法[1]簡介

在自然界中，眾所周知狼是群居動物，每匹狼都在狼群中扮演者重要的角色，狼的成功是狼與狼之間的默契配合，它們總能依靠團體的力量去完成每一件事。因此許多狼研究者對于狼的捕食行為提出了一種仿生智能優(yōu)化算法——狼群算法（Wolf algorithm，簡稱WA）。2011年，華北電力大學(xué)的鄢小虎和柳長安等學(xué)者提出了將狼群算法應(yīng)用在移動機器人路徑規(guī)劃上，主要過程如下：

1）游獵過程：狼個體釆用爬山法搜索當前所在位置附近的局部最優(yōu)值；

2）圍攻過程：狼個體利用群體中最優(yōu)狼個體的信息搜索全局最優(yōu)值；

3）食物的分配過程：按“優(yōu)勝劣汰”的分食原則，最壯的狼更容易得到食物，而最弱小的狼只能被餓死。新狼代替死狼，狼群得到更新，使狼群多樣化。

這些步驟如圖1[2]所示。

1.2 狼群算法的原理[2]

以迭代的方式不斷地尋找最優(yōu)值，狼群的位置及優(yōu)化問題的解。狼群通過初始化狼群、競爭領(lǐng)導(dǎo)者狼、向領(lǐng)導(dǎo)者狼移動、包圍獵物以及分配食物五個步驟來實現(xiàn)求解最優(yōu)化問題。

1.2.5 分配食物

根據(jù)狼群的事物分配的原則，精壯的狼將優(yōu)先獲取食物，而接著在分配給較為弱小的狼。這樣分配食物可能會導(dǎo)致最為弱小的狼會餓死。但是能確保精壯的狼能夠繼續(xù)生存下去，使得種群有著更好的適應(yīng)能力。據(jù)優(yōu)勝劣汰原則，移除最差的m匹狼，然后隨機生成m匹狼。這樣種群不易陷入局部最優(yōu)，且使得種群具有多樣性。

1.3 狼群算法的步驟

Step1. 初始化。狼群中有n個狼，最差的有m個狼，首領(lǐng)狼有q匹，搜索h個方向得到最大的搜索次數(shù)是max dh，搜索步長和移動步長分別為stepa和stepb，ra和ra分別為圍攻步長的最大值最小值，max t是最大迭代次數(shù)。初始化每匹狼的位置用公式（1）；

Step2.選最優(yōu)的q匹狼通過搜索來競爭首領(lǐng)狼，第i匹競爭狼通過式（2）不斷向前搜索到最優(yōu)的位置；

Step3.眾多的競爭狼中選出最厲害的狼作為領(lǐng)導(dǎo)者，剩下的狼向著領(lǐng)導(dǎo)者靠近移動，位置按（3）式更新；

Step4.首領(lǐng)狼搜索到獵物。其他狼包圍獵物，通過式（4）對其位置進行更新，并對更新后的位置依照公式（5）進行越界處理；

Step5.對狼群的更新是按照狼群分配食物的原則，除掉最差的m匹狼，同時 m匹狼通過（1）隨機產(chǎn)生。

Step6.一次迭代結(jié)束，進行下一次迭代，判斷是否滿足結(jié)束的條件，滿足條件退出循環(huán)，記錄結(jié)果；不滿足條件，轉(zhuǎn)到step2。

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

2 狼群算法求解多項式方程的步驟

Step1.初始化狼群，包括各初始化仿真參數(shù)，狼群的個數(shù)N_num、最大的迭代次數(shù)Max_iter，探狼比例因α，最大游走次數(shù)T_max，距離判定因子w，步長因子S等等；

Step2.初始化頭狼，通過迭代計數(shù)剔除最次狼個數(shù)，同時初始化出除頭狼外的最佳人工狼為探狼，并執(zhí)行游走行為，直到某只探狼比頭狼感知獵物的氣味濃度大或者達到最大游走次數(shù)。

Step3.狼個體的游獵過程，旨在尋找多項式方程的局部最優(yōu)值，是求解多項式方程根的算法的中間力量。根據(jù)偵查出的氣味濃度，更新頭狼及其位置，并發(fā)起召喚行為，實現(xiàn)了多項式方程根的多樣性，避免算法陷入局部極值。

Step4.統(tǒng)計狼群信息選出探狼和猛狼，如果猛狼離獵物更近，置為頭狼，然后發(fā)起召喚，執(zhí)行圍攻行為，不斷更新頭狼，并記錄當前位置；

Step5.判斷算法是否合理，如果達到優(yōu)化精度要求或者最大迭代次數(shù)T_max，說明算法合理，則輸出頭狼的位置，即為多項式方程的最優(yōu)根，同時結(jié)束迭代，否則轉(zhuǎn)向步驟4；

Step6.采用多次迭代的方式降低狼群算法求解多項式方程根的隨機性，通過人為設(shè)定循環(huán)次數(shù)來終止算法，從而得出多項式方程的最優(yōu)解。

3 仿真實驗

仿真實驗在以下硬件環(huán)境中進行：CPU：Intel（R） Core（TM）i5-2520M CPU @ 2.50GHz2.50 GHz 內(nèi)存：4.00GB 操作系統(tǒng)：Windows8 系統(tǒng)類型：64位程序 執(zhí)行軟件：matlab R2010a。

以下二個例子都是在固定的參數(shù)條件下進行運算，其中狼群個數(shù) N_num=30，1b=-4，ub=3，x=1b：0.05：ub；未知量個數(shù)dim=1；仿真參數(shù) Alpha=4，Beta=6，w=1000，S=2000，h=20，T_max=20。

例1 求解多項式方程[5] x2-3=0在區(qū)間x∈[0，4]的一個根。

例2 求解多項式方程[6]：x3-x-1=0在區(qū)間[1.0，1.5]內(nèi)的一個實根。

4 結(jié)束語

根據(jù)狼群算法的捕食原理，將其與求解多項式方程根相結(jié)合，提出了一種基于狼群算法求解多項式方程根的算法。利用狼群為了生存，不斷在頭狼的帶領(lǐng)下搜尋、圍捕獵物的過程，一步步的接近多項式方程的最優(yōu)值，從而最終找到全局的最優(yōu)解。通過仿真實驗，與其他多種算法的比較，證明了同等條件下狼群算法對于數(shù)值問題的求解，是一種收斂更快速，結(jié)果更精確的有效方法。

【參考文獻】

[1]王傳偉.基于狼群算法的三維傳感器優(yōu)化布置研究[J].大連理工大學(xué)，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]周強.狼群算法與螢火蟲群優(yōu)化算法及其應(yīng)用研究[D].廣西民族大學(xué)，2014， 44：4-7

[4]周強，周永權(quán).一種基于領(lǐng)導(dǎo)者策略的狼群搜索算法[J].廣西民族大學(xué)，信息科學(xué)與工程學(xué)院，2013，9（30）：2630-2632.

[5]李瑞芳.非線性方程求解的不動點算法及其研究[D].長沙學(xué)院：本科學(xué)位論文，2012，2（24）：6-10.

[6]李慶揚，王能超，易大義.數(shù)值分析[M].北京：清華大學(xué)出版社，2008.

[責(zé)任編輯：楊玉潔]