求解非線性方程組的量子行為粒子群算法

摘要：介紹了利用量子行為粒子群算法解決非線性方程組的問題。求方程組的解歸結為一個最優化問題，當方程組有多個解時，它的適應值函數就是具有多個最優解的多峰函數。為此，引進一種物種形成原理算法，該算法根據群體微粒的相似度并行地分成子群體。每個子群體是圍繞一個群體種子而建立的。對每個子群體進行QPSO最優搜索，從而保證方程組中每個可能的解都能被搜索到，具有良好的局部尋優特性。對幾個重要的測試函數進行仿真實驗，結果證明了所用算法可以保證找到方程組所有的解，并且具有很好的精確度。

關鍵詞：粒子群算法； 量子行為粒子群算法； 非線性方程組； 物種形成原理

中圖分類號：TP301文獻標志碼：A

文章編號：1001－3695(2007)05－0080－03

0引言

方程組的求解是數值代數的基本問題之一，許多自然生活和工程科學的計算問題最后都可歸結為求解方程組；因此，對方程組的解法的研究具有重要的意義。方程組可以分為線性方程組和非線性方程組。傳統求解方程組的數值解法分為直接法和迭代法。如果考慮時間約束條件，在實時系統中現存的數值解法都可能無法對方程組進行精確求解。為此利用進化算法使用計算機模擬大自然的進化過程，可以求解許多傳統數值計算方法難以解決的復雜問題。由于求方程組的解歸結為一個最優化問題，當方程組有多個解時，它的適應值函數就是具有多個最優解的多峰函數。求具有多個解的方程組問題就可以轉換為對多峰函數尋優的問題。

粒子群(Particle Swarm Optimization，PSO)算法和量子行為粒子群（Quantum－behaved Particle Swarm Optimization， QPSO）算法都屬于進化算法，它們都具有群體智能、迭代過程相對簡單和收斂速度較快等優點。其中QPSO是全局收斂的而PSO卻不能保證收斂到全局最優解[1]。本文在QPSO算法的基礎上引進物種形成原理算法（Speciation Algorithm），提出了改進的基于物種形成的QPSO算法，即SQPSO（Species－based QPSO）算法。在算法中將粒子群動態并行劃分為不同的子群。這種物種形成原理算法與Li J.等人研究的利用遺傳算法實現多峰優化問題[2]相似。它將粒子群系統中的粒子根據相似度進行劃分，并將每個子群中擁有局部最優值的粒子作為該子群的種子，而種子的局部最優值被設為該子群的全局最優值。這樣就使得每個子群中的粒子都收斂于該子群的局部最優值，而不是全部收斂于粒子系統中的一個全局最優值。因此這樣就可以并行地產生子群，從而有效地進行多峰尋優。

1PSO算法及帶慣性權重的PSO算法

PSO算法最早是在1995年由美國社會心理學家James Kennedy和電氣工程師Russell Eberhart共同提出的[3]，源于對鳥群捕食的行為研究。PSO中，每個優化問題的解都是搜索空間中的一只鳥，稱之為粒子。所有的粒子都有一個由被優化的函數決定的適應值(Fitness Value)，每個粒子還有一個速度決定它們飛翔的方向和距離。粒子們就追隨當前的最優粒子在解空間中搜索。PSO初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己。第一個就是粒子本身所找到的最優解。這個解叫做個體極值pbest；另一個極值是整個種群目前找到的最優解，這個極值是全局極值gbest。另外也可以不用整個種群而只是用其中一部分最好粒子的鄰居，那么在所有鄰居中的極值就是局部極值lbest[4，5]。在找到這兩個最優值時， 粒子根據如下的公式來更新自己的速度和新的位置。

2QPSO算法

PSO是基于種群的進化搜索技術，但是所有基本的和改進的PSO算法不能保證算法的全局收斂[1]，因為PSO的進化方程式使所有粒子在一個有限的樣本空間中搜索。根據粒子群的基本收斂性質，受量子物理基本理論的啟發，本文提出了一種新的能保證全局收斂的粒子群算法——QPSO算法[7，8]是對整個PSO算法進化搜索策略的改變，并且進化方程中不需要速度向量，進化方程的形式更簡單、參數更少且更容易控制。QPSO算法在搜索能力上優于所有已開發的PSO算法。

在QPSO算法中，粒子的狀態只需用位置向量來描述，并且算法中只有一個收縮擴張系數β，對這個參數的選擇和控制是非常重要的，它關系到整個算法的收斂性能。 

3方程組的適應值函數

為了求方程組，通常可以將求解的適應值函數定義為

4物種形成原理算法

方程組具有多個解時，適應值函數就是具有多個最優值的多峰函數。為了實現對多峰函數尋優，引進一種物種形成原理算法。這個算法將粒子群系統中相似的微粒并行地劃分成子群體，一個子群就是一類具有相似特點的粒子集合。每個子群體中的粒子都圍繞在本群體中具有最優適應值的粒子周圍，該粒子稱為種子（Seed）。利用兩個微粒間的歐氏距離來判斷它們之間的相似程度，距離越遠，則兩個微粒間的相似度越低。

采用Li J.等人介紹的方法[2]確定一個子群種子的算法。每次迭代都使用這種算法后，就可以為不同的子群確立各自的種子，然后分別將種子的局部最優值設為該子群的全局最優值。確定種子的算法流程如下：

5SQPSO和Species－based PSO(SPSO)算法

一旦確定好每個子群的種子后，在每個子群中，種子的最優值就是同一子群中其他粒子的全局最優值，這樣SQPSO算法可以表示為：

(1)初始化種群的每個粒子的位置向量;

(2)計算所有粒子的適應值;

(3)根據粒子適應值由高到低的順序排列粒子;

(4)對當前所有粒子確定子群種子;

(5)將種子的最優值確定為其所在子群中所有粒子的全局最優值;

(6)根據式（7）、（8）改變粒子的位置;

(7)轉(2），直至條件滿足。

SPSO算法可以表示為：

(1)初始化種群的每個粒子的位置向量;

(2)計算所有粒子的適應值;

(3)根據粒子適應值由高到低的順序排列粒子;

(4)對當前所有粒子確定子群種子;

(5)將種子的最優值確定為其所在子群中所有粒子的全局最優值;

(6)根據式（3）、（4）或（5）改變粒子的位置;

(7)轉（2），直至條件滿足。

對這兩個算法說明如下：

(1)在算法中每一次迭代確定的種子總是那個子群中適應值最好的粒子。

(2)運行結束后得到的種子數組就是要求解的峰值點值。如果全局最優值只有一個，那么第一個種子就是全局最優點值。

6實驗結果

表2給出了對每個系統分別使用gbest、lbest、SPSO和SQPSO進行求解的結果。從表2可以看出，當方程組有多個解時，gbest模式PSO算法或lbest模式PSO算法都無法找到所有解，本文提出的算法SPSO和SQPSO對于所有的測試方程組都能找到所有解。用這兩種算法求得的解所得到的適應值都十分接近零，所有的實驗結果都收斂于一個很接近零的解。表3給出了使用各種方法所得解的平均誤差。可以看出SPSO和SQPSO比使用gbest和pbest的PSO算法具有更好的精度值。由表4可知，SQPSO算法優化在訓練集上的平均誤差小于SPSO算法優化的狀態估計。

7結束語

本文在QPSO算法的基礎上使用物種形成的概念，提出了一種SQPSO算法用來實現求解具有多個解的方程組。并將SQPSO算法和基于PSO算法的SPSO算法以及gbest模式和lbest模式的PSO算法進行了性能比較。通過對一系列廣泛使用的方程組（一個解或多個解）進行仿真實驗，可以證明當方程組具有多個解時，gbest_PSO和lbest_PSO算法不能求得所有解，而SPSO算法和SQPSO算法是有效的，并且具有更高精度值的解。同時從實驗中也證明SQPSO算法的收斂能力優于SPSO算法，其精確度更高。

參考文獻：

［1］BERGH F V.An analysis of particle swarm optimizers[D].[S.l.]:University of Pretoria，2001.

［2］LI J， BALAZS M E， PARKS G T，et al. A species conserving genetic algorithm for multimodal function optimization[J].Evolutionary Computation，2003，10(3):207－234.

［3］KENNEDY J，EBERHART R C.Particle swarm optimization:procee－dings of the IEEE International Joint Conference on Neural Networks[C].[S.l.]:[s.n.]，1995:1942－1948.

［4］KENNEDYJ，WORLDS S，MINDS M J.Effects of neighborhood topo－logy on particle swarm performance:proceedings of the Congress on Evolutionary Computation[C].[S.l.]:[s.n.]，1999:1931－1938.

［5］SUGANTHAN P N.Particle swarm optimizer with neighborhood optimizer:proceedings of the Congress on Evolutionary Computation[C].[S.l.]:[s.n.]，1999:1958－1961.

［6］SHI Y，EBERHART R C.A modified particle swarm:proc.of the IEEE International Conference on Evolutionary Computation[C].[S.l.]:[s.n.]，1998:1945－1950.

［7］SUN Jun， XU Wenbo. A global search strategy of quantum－behaved particle swarm optimization:proceedings of IEEE conference on Cybernetics and Intelligent Systems[C].[S.l.]:[s.n.]，2004:111－116

［8］SUN Jun， FENG Bin， XU Wenbo. Particle swarm optimization with particles having quantum behavior:proceedings of the Congress on Evolutionary Computation[C].[S.l]:[s.n.]，2004:325－331.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”