基于混合算子蛙跳算法求解線性方程組

郭德龍 周錦程

（1.黔南民族師范學院 數(shù)學與統(tǒng)計學院，貴州 都勻 558000）（2.黔南民族師范學院 復雜系統(tǒng)與計算智能重點實驗，貴州 都勻 558000）

0 引言

生產(chǎn)和實踐中，求解線性方程組的問題是普遍存在的，例如潛艇、航空等方面很多問題的求解都可以轉(zhuǎn)化成求解線性方程組的問題。 求解線性方程組的傳統(tǒng)方法在遇到大型的線性方程組時難以駕馭，實用性不強；牛頓迭代法可以得到不錯的計算結(jié)果，但依然存在一定的局限性，迭代時初值的選取要求十分嚴格，選取的初值欠好，可能會導致不收斂；其次，每一次迭代都要計算，計算量很大，

給應(yīng)用帶來很大的阻礙。 混合蛙跳算法 （SFLA）是Eusuff 和Lansey 在2003 年第一次提出的，是一種嶄新的智能優(yōu)化算法，它結(jié)合了PSO 和模因算法兩者的所長，算法的參數(shù)較少、收斂的速度和計算速度較快、優(yōu)良的全局搜索能力、便于實現(xiàn)等特點[1]。 當前，SFLA 廣泛的應(yīng)用在貼片機貼裝順序優(yōu)化問題、 數(shù)值優(yōu)化和組合優(yōu)化、 函數(shù)優(yōu)化控制器參數(shù)調(diào)整和聚類問題等很多的規(guī)模中[2]。 所以本文在基于SFLA 的基礎(chǔ)上來求線性方程組的解，不改變原算法的子群內(nèi)部搜索策略，將線性方程組轉(zhuǎn)化成優(yōu)化問題， 然后利用蛙跳算法求該優(yōu)化問題從而求出線性方程組的解。

1 問題描述

線性方程組的一般形式如下：

其中未知量列X=（x1，x2，L L xn）T，常數(shù)列b=（b1,b2,L L,bm）T，系數(shù)矩陣A=（aij）mn，求（1）的解。

1.1 問題轉(zhuǎn)化

由（1）變形可得：

將（2）式化為：

由（3）式中的方程組轉(zhuǎn)化為如下函數(shù)形式：

（1）、（4）可轉(zhuǎn)為如下優(yōu)化問題：

每一個未知數(shù)的解對應(yīng)每一只青蛙，搜羅最好的青蛙過程就是在搜索最好的解的行程，然青蛙的好壞由優(yōu)化模型的適應(yīng)度函數(shù)決定。 構(gòu)造的適應(yīng)度函數(shù)如下:

所以求線性方程組（1）的解就轉(zhuǎn)變成求函數(shù)Y 的最小值優(yōu)化問題。

2 混合蛙跳算法

2.1 算法原理

SFLA 的執(zhí)行過程就是模仿一群青蛙在有限空間的一塊區(qū)域內(nèi)覓食的過程，算法的性能良好。 青蛙跳躍覓食過程中，經(jīng)過分組和重新排列，使青蛙之間進行信息交換，然后相互學習，搜羅出區(qū)域內(nèi)食物最好的地方，并通過跳躍將自己的位置更新到食物較多的位置。 如下：

一、在一片水池中，每一個青蛙種群都是隨機生成的，其中的青蛙無論是從構(gòu)造上還是行為習慣上都是相同的，一只青蛙就是一個解。 一群青蛙通過自身的組織能力，將相同個數(shù)的青蛙進行組團搜羅，形成的每一個小團體即為子種群。

二、子群中的青蛙在更新到最好位置時，它們之間會進行信息交流，從而找到食物源最豐富的地方即問題的最優(yōu)解。 青蛙種群中各個子種群的最優(yōu)解又進行混合交流搜羅出最好的解。

三、SFLA 的局部搜索和混合交流是算法的核心，它們的結(jié)合使算法擁有了良好的搜羅能力，這也是其他群體智能優(yōu)化算法的不足之一。 充分利用這優(yōu)勢向著池塘最優(yōu)的方向進行搜索，直到找到最優(yōu)解為止。

2.2 SFLA 的基本流程圖

圖1

3 SFLA 求解線性方程組

步驟1 種群初始化。 確定方程組中的未知數(shù)x 的個數(shù)為N 個； 第i 個未知數(shù)x 在D 維空間中對應(yīng)的坐標是xi=（xi1,xi2,xi3,,L L,xiD）；

步驟2 把xi代入函數(shù)中，看它是否是使函數(shù)F（X）=或是使方程最接近于0 的解，即求出了函數(shù)的適應(yīng)度fitness=F（X）；

步驟4 子種群的劃分。 將N 按一定規(guī)則分成M個子種群 ｛Y1,Y2,Y3,L LYM｝，每一個子種群有S個解，其中N=M*S[3]。 分組規(guī)則如下：

第一個解分入Y1， 第二個解分入Y2， 第三個解分入Y3，直到第S 個解分入YM，然后再將第S+1 個解分入Y1，將第S+2 個解分入Y2，一直輪回分派直到所有的解N 都分派完為止。 分派完成后，找出各個子種群中適應(yīng)度最好的解xa=（xa1,xa2,xa3,L L,xaD），適應(yīng)度最差的解xb=（xb1,xb2,xb3,L L,xbD），種群中適應(yīng)度最好的解為xw=（xw1,xw2,xw3,L L,xwD）[1]。

步驟5 子種群的局部搜索。 每次搜羅中，對子種群中最差的青蛙進行位置更新，按如下公式進行：

其中rand 是（0，1）間隨機生成的數(shù)，Di是解的移動步長，Dmax表示青蛙最大移動的步長；按（7）式和（8）式進行每一次的局部搜索， 且對各個子種群的最差解xb進行位置更新這一操作。 按（7）式中計算出最差的解xb更新后的得到解xb'，若f（xb'）比f（xb)好，則就用xb'替代xb，若沒有改進則用xw來代替xb。 再利用公式（7）（8）重新計算更新后的解，如果更新后的解比xb'更好，則用xb'替代最差的解xb，若仍然沒有改進，則從搜索中從新隨機產(chǎn)生一個新的解來替換原來的xw，子種群中最差的解的位置就得到了改變，各個子種群都重復上述搜索，一直到規(guī)定的最大局部搜索的次數(shù)為止[2]。

步驟6 子種群混合。 將求出的全部解混在一起，又重新劃分子種群，再實施局部搜索，直到循環(huán)滿足終止條件。

4 實驗仿真結(jié)果與分析

4.1 仿真結(jié)果

實驗環(huán)境Lenovo-PC 機Intel （R）Core （TM）i5-5257U CPU、2.70GHz、Window8、RAM:4GB 和MATLAB R2014a 中進行。為了測試該算法求解線性方程組的性能，任意選取了6 個線性方程組進行測試。 參數(shù)設(shè)置：組內(nèi)迭代數(shù)Ne=25，最大步長smax=100，種群分組數(shù)m=50，每組青蛙數(shù)n=35，種群總進化代數(shù)MAXGEN=100， 優(yōu)化問題維數(shù)d=25。

表1 線性方程組的求解結(jié)果

圖2 第一個線性方程組的優(yōu)化過程

圖3 第二個線性方程組的優(yōu)化過程

表2 線性方程組的求解結(jié)果

圖4 第三個線性方程組的優(yōu)化過程

圖5 第四個線性方程組的優(yōu)化過程

表3 線性方程組的求解結(jié)果

圖6 第一個線性方程組的優(yōu)化過程

圖7 第二個線性方程組的優(yōu)化過程

4.2 結(jié)果分析

從圖2-圖7 中，可看出SFLA 求解線性方程組的解是可行的，且每次都能在較短時間內(nèi)尋找到最優(yōu)解。 從圖中可看到SFLA 在求解精度上與傳統(tǒng)方法相比提高了很多，收斂速度方面上的效果也比傳統(tǒng)方法還要好， 跟牛頓迭代法相比，SFLA 的求解效果都較好； 也可以看到SFLA 對求解線性方程組的解也便于實現(xiàn)。

5 結(jié)束語

SFLA 算法的性能良好， 種群中的青蛙是有智能行為的， 在解決各類優(yōu)化問題方面得以成功的應(yīng)用。 基于這些優(yōu)點， 將原線性方程組化成解優(yōu)化函數(shù)問題，再利用SFLA 算法來求函數(shù)的優(yōu)化問題， 間接求得方程組的解。 SFLA 算法不用考慮初值的選取，且參數(shù)算法少，搜索能力強，無論是簡單函數(shù)還是復雜函數(shù)，都便于實現(xiàn)。 6 個例子仿真實驗結(jié)果顯示，該算法求解線性方程組的解比牛頓迭代法好，提高了解的收斂速度,同時也得到比傳統(tǒng)方法還要好的求解精度。