具有記憶功能的海鷗優(yōu)化算法求解方程組

許 樂，莫愿斌,2+，盧彥越

(1.廣西民族大學(xué) 人工智能學(xué)院，廣西 南寧 530006；2.廣西民族大學(xué) 廣西混雜計算與集成電路設(shè)計 分析重點實驗室，廣西 南寧 530006；3.廣西民族大學(xué) 化學(xué)化工學(xué)院，廣西 南寧 530006)

0 引 言

目前，求解方程組的智能優(yōu)化算法有環(huán)拓撲混合群體智能算法[1]、粒子群優(yōu)化算法[2]、正余弦算法[3]、錐模型信賴域算法[4]以及布谷鳥算法[5,6]等，這些算法解決了很多科學(xué)、社會、工程等領(lǐng)域的復(fù)雜問題。

其中，海鷗優(yōu)化算法(SOA)[7,8]是Dhiman G博士等提出的一種智能優(yōu)化算法，通過模擬海鷗的生活習(xí)性(遷徙行為和攻擊行為)而建立的數(shù)學(xué)模型，和其它智能優(yōu)化算法進行比較，SOA算法的基本原理易懂，易于實現(xiàn)，具有全局搜索和局部搜索的能力等特點。但是，SOA算法也存在容易陷入局部最優(yōu)、過早收斂以及求解精確度低的缺點，因此，許多學(xué)者進行了一系列的研究和改進。例如：文獻[9]將改進的海鷗優(yōu)化算法用于PEM燃料電池實驗建模，提高了算法的性能。文獻[10]將海鷗優(yōu)化算法應(yīng)用在四川盆地渝西區(qū)塊H井區(qū)頁巖氣儲層最優(yōu)化測井解釋中。

為解決基本的海鷗優(yōu)化算法(SOA)存在的缺點，提出一種具有記憶功能的海鷗優(yōu)化算法(MSOA)。該算法考慮到了海鷗具有記憶功能，即海鷗的前期搜索經(jīng)驗對后期搜索提供了一系列的支持。通過引入記憶功能來提高算法的求解能力和精確度，避免算法陷入局部最優(yōu)。文中通過引入標(biāo)準(zhǔn)測試函數(shù)對MSOA算法進行性能的測試，同時引入了方程組進行仿真實驗，通過算法之間的對比表明該算法在解的數(shù)量和質(zhì)量上都具有優(yōu)勢，進一步驗證了MSOA算法的尋優(yōu)能力。

1 問題描述

(1)線性方程組是各個方程關(guān)于未知量均為一次的方程組，其一般形式如下

(1)

方程組可以轉(zhuǎn)化Ax=b，進一步轉(zhuǎn)化：Ax-b=0，令f(x)=Ax-b，則構(gòu)造目標(biāo)函數(shù)如下

F(x)=f12(x)+f22(x)+…+fn2(x)

(2)

(2)設(shè)非線性方程組[11,12]如下

(3)

所以，為了計算出適應(yīng)度值，把線性方程組和非線性方程組的求解問題統(tǒng)一轉(zhuǎn)換為目標(biāo)函數(shù)的最小值思想，即目標(biāo)函數(shù)就是適應(yīng)度函數(shù)。目標(biāo)函數(shù)統(tǒng)一如下所示

(4)

2 改進的海鷗優(yōu)化算法

2.1 引入記憶功能

海鷗優(yōu)化算法的介紹以及相關(guān)定理請參考引言里面的文獻，文中MSOA算法是在SOA算法海鷗群體進行攻擊行為基礎(chǔ)上改進的，引入兩個隨機因子以及兩個學(xué)習(xí)因子；同時在種群更新中，加入了海鷗種群的最佳位置和個體的歷史最優(yōu)值。一方面，MSOA算法使得海鷗向個體歷史最優(yōu)位置的學(xué)習(xí)；另一方面，它又增強了向群體最佳位置的學(xué)習(xí)，從而避免了種群陷入局部最優(yōu)解區(qū)域，增強了種群的尋優(yōu)性能。記憶功能的公式如下所示

Pm(t)=ds(t)×x×y×z+Pbs(t)+(Pg(t)-Ps(t))×r1×w1+(Pbs(t)-Ps(t))×r2×w2

(5)

式中：隨機因子r1和r2設(shè)置為0和1之間的隨機數(shù)，從而增強海鷗飛行過程中的隨機性，學(xué)習(xí)因子w1、w2的值設(shè)置為0.9，從而保證算法能夠更好收斂，增強了海鷗向個體學(xué)習(xí)以及群體學(xué)習(xí)的能力，Pg(t)表示海鷗個體的歷史最優(yōu)位置，Pm(t)為記憶個體，Ps(t)為上一代個體。

為了增強算法的求解能力，需要將迭代出來的海鷗位置，即記憶個體與上一代個體位置的適應(yīng)度進行比較，選出最優(yōu)的位置。判斷如下所示：

if 記憶個體的適應(yīng)度值>上一代個體的適應(yīng)度

上一代個體位置替換記憶個體位置

else

記憶個體的位置保持不變

MSOA算法不但更新當(dāng)前群體的全局最優(yōu)值，而且更新了每個海鷗個體的歷史最優(yōu)信息。這樣不僅能夠使海鷗個體跳出局部極值進入解空間的新區(qū)域繼續(xù)進行搜索最優(yōu)解，也還能夠提高算法的收斂精度和收斂速度，避免陷入局部最優(yōu)。

2.2 MSOA算法的求解步驟

具有記憶功能的海鷗優(yōu)化算法的求解過程分為初始化過程、適應(yīng)度計算過程、循環(huán)迭代過程、篩選過程、更新適應(yīng)度值和位置過程、輸出結(jié)果過程6個過程。具有記憶功能的海鷗優(yōu)化算法(MSOA)的求解步驟如下所述：

步驟1種群初始化。設(shè)置種群大小popsize，最大迭代次數(shù)maxiter，線性頻率fc，螺旋形狀的參數(shù)u、v等；

步驟2計算當(dāng)前海鷗種群每個個體的適應(yīng)度值，計算出當(dāng)前海鷗種群的全局最優(yōu)位置和設(shè)置個體最優(yōu)位置；

步驟3迭代尋優(yōu)，更新海鷗的位置；

步驟4計算出海鷗避免碰撞后的新位置；

步驟5計算出海鷗的最佳位置方向；

步驟6計算海鷗靠近最佳位置；

步驟7引入具有記憶功能式(5)結(jié)合攻擊行為的公式計算出海鷗的新位置，從而得到新的一代海鷗個體；

步驟8比較記憶個體和上一代個體的適應(yīng)度值，把最好的個體保存下來；

步驟9更新海鷗的位置和適應(yīng)度值，個體更新和全體更新；

步驟10是否滿足條件，若滿足，結(jié)束循環(huán)，否則，繼續(xù)迭代尋優(yōu)；

步驟11輸出海鷗的最佳位置和適應(yīng)度值、輸出迭代過程；

步驟12結(jié)束程序。

3 實驗結(jié)果與分析

為了測試MSOA算法的尋優(yōu)能力和精確度，首先使用10個標(biāo)準(zhǔn)測試函數(shù)進行測試，測試算法的尋優(yōu)能力；最后，將MSOA算法運用在求方程組的解，其中，方程組包括5個線性方程組和10個非線性方程組。實驗中使用的仿真軟件是MATLAB R2017a，操作系統(tǒng)是windows10，64位，處理器Intel(R) Core(TM) i5-8300H CPU @ 2.30 GHz 2.30 GHz。

3.1 標(biāo)準(zhǔn)測試函數(shù)的測試

算法的參數(shù)設(shè)置：最大迭代次數(shù)都為200，SOA算法的種群大小為200，線性頻率fc為2，兩個螺旋參數(shù)u和v的大小都為1；PSO算法的種群大小為200，學(xué)習(xí)因子為2，慣性因子等于0.8；MSOA算法的種群大小為80，頻率fc為2，兩個螺旋參數(shù)u、v的大小分別為0.001、0.9。在本次實驗中，每個標(biāo)準(zhǔn)測試函數(shù)的維度都設(shè)置為30，每個函數(shù)都分別獨立運行10次，分別統(tǒng)計出SOA算法、PSO算法以及MSOA算法的平均值、最優(yōu)值以及最差值。其中，表1說明了標(biāo)準(zhǔn)測試函數(shù)相關(guān)參數(shù)的設(shè)置，表2給出了3種算法的不同函數(shù)實驗結(jié)果；為了體現(xiàn)算法的尋優(yōu)效果，圖1～圖10給出了每個函數(shù)對應(yīng)的迭代曲線圖。

表1 標(biāo)準(zhǔn)測試函數(shù)的相關(guān)參數(shù)

圖1 函數(shù)f1的迭代曲線

圖2 函數(shù)f2的迭代曲線

圖3 函數(shù)f3的迭代曲線

圖4 函數(shù)f4的迭代曲線

表2 SOA、PSO、MSOA算法的實驗結(jié)果

圖5 函數(shù)f5的迭代曲線

圖6 函數(shù)f6的迭代曲線

圖7 函數(shù)f7的迭代曲線

圖8 函數(shù)f8的迭代曲線

圖9 函數(shù)f9的迭代曲線

圖10 函數(shù)f10的迭代曲線

實驗結(jié)果分析：從表2可以看出，通過MSOA、SOA、PSO算法進行對比，MSOA算法具有更好的尋優(yōu)能力，其值更接近于理論值。對于單峰函數(shù)f1，MSOA的平均求解精度更高，比PSO高了95個數(shù)量級，SOA的平均值沒有找到最優(yōu)值。對于函數(shù)f2，MSOA的平均求解精度比SOA、PSO高了49個數(shù)量級。對于函數(shù)f3，PSO算法沒有找到理想值，SOA的求解精度比PSO高，MSOA算法的值為0，與理論值一樣，說明MSOA求解能力以及精度比PSO、SOA好。對于函數(shù)f4，SOA與PSO在平均值上都沒有找到理想最優(yōu)解，MSOA的求解效果最好，平均求解精度為e-23。對于函數(shù)f5，PSO的平均求解精度比SOA高了1個數(shù)量級，但是MSOA值為0與理想值完全一樣，求解精度更高。對于函數(shù)f6，SOA與PSO的求解精度一樣，能夠找到較為理想的解，但是MSOA的求解精度比兩者高了24個數(shù)量級。對于函數(shù)f7，SOA沒有搜索到理想的值，MSOA的平均求解精度比PSO算法高了24個數(shù)量級。對于函數(shù)f8，SOA與PSO都沒有在最大的迭代次數(shù)內(nèi)找到最優(yōu)值，MSOA算法的平均求解精度最高。對于函數(shù)f9、f10，SOA與PSO都能找到合理的解，但是通過最優(yōu)值、最差值以及平均值進行比較，MSOA算法的效果更好。從圖1～圖10的迭代曲線可以看出，MSOA算法能夠避免陷入局部最優(yōu)解，使得算法求解精度較高，搜索解的能力較好。

3.2 線性方程組的測試

為了測試該算法求解線性方程組的性能，選取了5組線性方程組[13]進行了測試，每個方程獨立運行10次，結(jié)果取平均值，實驗結(jié)果見表3。實驗參數(shù)的設(shè)置：PSO算法的最大迭代次數(shù)為200，種群大小為200，學(xué)習(xí)因子為2，慣性因子等于0.8；人工魚群算法(AFSA)的種群大小為80，最大迭代系數(shù)為200，感知距離visual=1，移動最大步長step=0.01，最多試探次數(shù)try_number=100，擁擠度因子delta=0.618；斑鬣狗優(yōu)化算法(SHO)[14]的種群大小為30，迭代次數(shù)為100；MSOA算法的種群大小為200，最大迭代次數(shù)為100。線性方程組如下所示

其中，方程組(1)的理論值為(1,3,6)；方程組(2)的理論值為(0.3333,0.3333,0)；方程組(3)的理想值為(12,27,6,-13)；方程組(4)的理論值為(1,2,3,4,5)；方程組(5)的理論值為(1,2.5,3,6.5,7)。

實驗結(jié)果分析：從表3可以看出，對于方程組(1)，利用傳統(tǒng)方法(牛頓法)能夠求出理想值，PSO、AFSA以及SHO算法的值接近理論值，SOA的值與理論值有一定的差距，通過比較，MSOA的求解精度更好；對于方程組(2)，5種方法都能找到理論值、精確度較高，但是SOA存在求解精度偏低；對于方程組(3)，AFSA、SOA在最大迭代次數(shù)內(nèi)沒有找到理想解，MSOA的平均精度比PSO、SHO高；對于方程組(4)，傳統(tǒng)方法、PSO、AFSA以及SHO的解接近理論值，但MSOA的效果更好；對于方程組(5)，牛頓法、AFSA、SOA算法偏離理想值，PSO和SHO的值接近理想值，但是MSOA更具有優(yōu)勢，說明傳統(tǒng)方法已經(jīng)不適合大型計算?？偟膩碚f，MSOA算法的尋優(yōu)能力和求解精度都比其它算法的效果好。

3.3 非線性方程組的測試

為了測試MSOA算法在求非線性方程組的性能，文中引入了文獻[15,16]中的非線性方程組進行了仿真實驗，MSOA、SOA、PSO、SHO的種群大小為500，最大迭代次數(shù)為1000，其它參數(shù)和線性方程組測試一致。其中方程組(1)～方程組(6)分別運行10次取平均值，方程組(7)～方程組(10)分別運行50次取平均值。實驗結(jié)果見表4～表6，圖11給出了方程組(10)的進化曲線，非線性方程組如下

表3 線性方程組的實驗結(jié)果

表4 非線性方程組(1)～方程組(6)的實驗結(jié)果

實驗結(jié)果分析：從表4可知，對于方程組(1)，文獻[12]和文獻[17]能夠找出方程組的全部解且其值接近于理論值，SOA算法只能找出兩個解且求解精度不高，SHO算法找出了3個解，但是求解精度不高，而MSOA算法更具有優(yōu)勢；對于方程組(2)、方程組(3)，MSOA算法的求解精度都要高于其它算法；對于方程組(4)，ABFA算法的值接近于理論值，文獻[18]的求解精度較高，SOA算法沒有找到值，SHO算法的求解精度一般，但是MSOA的求解精度較高一點；對于方程組(5)，BOA算法沒有找到較好的解，而IBOA算法的求解能力比BOA算法要高，CGSO算法的求解精度較好，SOA和SHO算法與理論值有一定的差距，而MSOA算法在求解精度更好；對于方程組(6)，BOA和IBOA算法相比，IBOA算法更具有優(yōu)勢，CGSO、SOA、SHO算法的值接近于理論值，而MSOA算法的精確值為0和1，求解精度優(yōu)于參考文獻中的算法。所以，MSOA算法具有較好的求解能力。

測試方程組(7)～方程(9)，其中，方程組(7)有4個近似解，分別為(0.8165,1.547)，(-0.8165,-1.547)，(-0.8165,1.547)，(0.8165,-1.547)。方程組(8)也有4個近似解，解分別為(-1.563 53,0.277 63)，(-0.789 71,1.088 30)，(1.563 53,0.277 63)，(0.789 71,1.088 30)。方程組(9)有10個近似解，分別為(-1.810 89,-0.349 09)，(-1.810 89,0.349 09)，(-1.502 22,-0.409 08)，(-1.502 22,0.409 08)，(-1.791 30,0.301 93)，(-1.791 30,-0.301 93)，(-0.947 27,0.785 02)，(-0.947 27,-0.785 02)，(-0.213 06,1.256 85)，(-0.213 06,-1.256 85)。

實驗結(jié)果分析：從表5可知，對于方程組(7)、方程組(8)，MSOA算法能夠找出方程的全部解，通過與提供的近似解相比，發(fā)現(xiàn)MSOA算法的解接近于近似解，精確度較高，尋優(yōu)的能力較好，MMODE算法[16]也能找出4個最優(yōu)解，搜索到的全部解還沒有完全接近于理論解，但是該算法的最大迭代次數(shù)為50 000，運行時間較長，所以在時間方面MSOA算法更具有優(yōu)勢；對于方程組(9)，MMODE算法[16]找出了方程組的全部解，且搜索到的解與真實值比較接近，IBA算法[21]也能找出方程組的全部解且求解的成功率達到了100%，而MSOA算法能夠找出10個最優(yōu)解，接近于理論解，通過MMODE、IBA、MSOA算法的結(jié)果進行對比，改進算法具有一定的優(yōu)勢。

表5 非線性方程組(7)～方程組(9)的實驗結(jié)果

測試方程組(10)，其中，對于方程組(10)，方程組有16個解，分別如下所示：(0.1644,-0.9864,-0.9471,-0.321,-0.9982,-0.0594,0.411,0.9116)、(0.1644,-0.9864,-0.9471,-0.321,-0.9982,0.0594,0.411,-0.9116)、(0.1644,-0.9864,-0.9471,-0.321,0.9982,-0.0594,0.411,0.9116)、(0.1644,-0.9864,-0.9471,-0.321,0.9982,0.0594,0.411,-0.9116)、(0.1644,-0.9864,0.7185,-0.6956,-0.998,-0.0638,-0.5278,0.8494)、(0.1644,-0.9864,0.7185,-0.6956,-0.998,0.0638,-0.5278,-0.8494)、(0.1644,-0.9864,0.7185,-0.6956,0.998,-0.0638,-0.5278,0.8494)、(0.1644,-0.9864,0.7185,-0.6956,0.998,0.0638,-0.5278,-0.8494)、(0.6716,0.741,-0.6516,-0.7586,-0.9625,-0.2711,-0.4376,0.8992)、(0.6716,0.741,-0.6516,-0.7586,-0.9625,0.2711,-0.4376,-0.8992)、(0.6716,0.741,-0.6516,-0.7586,0.9625,-0.2711,-0.4376,0.8992)、(0.6716,0.741,-0.6516,-0.7586,0.9625,0.2711,-0.4376,-0.8992)、(0.6716,0.741,0.9519,-0.3064,-0.9638,-0.2666,0.4046,0.9145)、(0.6716,0.741,0.9519,-0.3064,-0.9638,0.2666,0.4046,-0.9145)、(0.6716,0.741,0.9519,-0.3064,0.9638,0.2666,0.4046,-0.9145)、(0.6716,0.741,0.9519,-0.3064,0.9638,-0.2666,0.4046,0.9145)。

表6 非線性方程組(10)的實驗結(jié)果

續(xù)(表6)

實驗結(jié)果分析：從表6可知，對于含有16個解的方程組(10)，MSOA算法找出了方程組的全部解且求解精度較高，而MMODE算法[16]求解該問題時，16個解還不能很好地搜索到，IBA算法[21]在最大迭代次數(shù)為5000時，搜索到了15個近似解且成功率為93.75%。從方程組的進化曲線圖可以看出，MSOA算法在求解該問題時能夠在較短的時間內(nèi)收斂。通過比較，進一步說明改進算法的尋優(yōu)能力較好。

圖11 方程組(10)的進化曲線

4 結(jié)束語

分析了基本的海鷗優(yōu)化算法(SOA)存在容易陷入局部最優(yōu)的問題，提出了一種具有記憶功能的海鷗優(yōu)化算法(MSOA)。在算法測試方面，首先引入了10個標(biāo)準(zhǔn)測試函數(shù)進行測試，通過PSO算法以及SOA算法的對比，結(jié)果說明MSOA算法具有良好的尋優(yōu)能力；其次，MSOA算法對5個線性方程組進行求解，通過與傳統(tǒng)方法、其它智能算法進行比較，MSOA算法的平均求解精度、最優(yōu)值等都要優(yōu)于其它方法；最后，引入了10個非線性方程組進行測試，MSOA算法分別與文獻中的方法以及其它新算法進行仿真對比，結(jié)果表明該算法在求解的數(shù)量以及精確度上都具有一定的優(yōu)勢，進一步說明MSOA算法的尋優(yōu)能力較好。