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

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

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

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)志碼：A

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

0引言

方程組的求解是數(shù)值代數(shù)的基本問題之一，許多自然生活和工程科學(xué)的計(jì)算問題最后都可歸結(jié)為求解方程組；因此，對(duì)方程組的解法的研究具有重要的意義。方程組可以分為線性方程組和非線性方程組。傳統(tǒng)求解方程組的數(shù)值解法分為直接法和迭代法。如果考慮時(shí)間約束條件，在實(shí)時(shí)系統(tǒng)中現(xiàn)存的數(shù)值解法都可能無法對(duì)方程組進(jìn)行精確求解。為此利用進(jìn)化算法使用計(jì)算機(jī)模擬大自然的進(jìn)化過程，可以求解許多傳統(tǒng)數(shù)值計(jì)算方法難以解決的復(fù)雜問題。由于求方程組的解歸結(jié)為一個(gè)最優(yōu)化問題，當(dāng)方程組有多個(gè)解時(shí)，它的適應(yīng)值函數(shù)就是具有多個(gè)最優(yōu)解的多峰函數(shù)。求具有多個(gè)解的方程組問題就可以轉(zhuǎn)換為對(duì)多峰函數(shù)尋優(yōu)的問題。

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

1PSO算法及帶慣性權(quán)重的PSO算法

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

2QPSO算法

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

在QPSO算法中，粒子的狀態(tài)只需用位置向量來描述，并且算法中只有一個(gè)收縮擴(kuò)張系數(shù)β，對(duì)這個(gè)參數(shù)的選擇和控制是非常重要的，它關(guān)系到整個(gè)算法的收斂性能。 

3方程組的適應(yīng)值函數(shù)

為了求方程組，通?？梢詫⑶蠼獾倪m應(yīng)值函數(shù)定義為

4物種形成原理算法

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

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

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

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

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

(2)計(jì)算所有粒子的適應(yīng)值;

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

(4)對(duì)當(dāng)前所有粒子確定子群種子;

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

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

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

SPSO算法可以表示為：

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

(2)計(jì)算所有粒子的適應(yīng)值;

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

(4)對(duì)當(dāng)前所有粒子確定子群種子;

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

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

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

對(duì)這兩個(gè)算法說明如下：

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

(2)運(yùn)行結(jié)束后得到的種子數(shù)組就是要求解的峰值點(diǎn)值。如果全局最優(yōu)值只有一個(gè)，那么第一個(gè)種子就是全局最優(yōu)點(diǎn)值。

6實(shí)驗(yàn)結(jié)果

表2給出了對(duì)每個(gè)系統(tǒng)分別使用gbest、lbest、SPSO和SQPSO進(jìn)行求解的結(jié)果。從表2可以看出，當(dāng)方程組有多個(gè)解時(shí)，gbest模式PSO算法或lbest模式PSO算法都無法找到所有解，本文提出的算法SPSO和SQPSO對(duì)于所有的測(cè)試方程組都能找到所有解。用這兩種算法求得的解所得到的適應(yīng)值都十分接近零，所有的實(shí)驗(yàn)結(jié)果都收斂于一個(gè)很接近零的解。表3給出了使用各種方法所得解的平均誤差?？梢钥闯鯯PSO和SQPSO比使用gbest和pbest的PSO算法具有更好的精度值。由表4可知，SQPSO算法優(yōu)化在訓(xùn)練集上的平均誤差小于SPSO算法優(yōu)化的狀態(tài)估計(jì)。

7結(jié)束語

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

參考文獻(xiàn)：

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

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”