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

楊楠+郭德龍

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

【關鍵詞】多項式方程的根；二分法；狼群算法；最優解

【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.

[責任編輯：楊玉潔]