具有記憶功能的海鷗優化算法求解方程組

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

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

0 引 言

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

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

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

1 問題描述

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

(1)

方程組可以轉化Ax=b，進一步轉化：Ax-b=0，令f(x)=Ax-b，則構造目標函數如下

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

(2)

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

(3)

所以，為了計算出適應度值，把線性方程組和非線性方程組的求解問題統一轉換為目標函數的最小值思想，即目標函數就是適應度函數。目標函數統一如下所示

(4)

2 改進的海鷗優化算法

2.1 引入記憶功能

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

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

(5)

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

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

if 記憶個體的適應度值>上一代個體的適應度

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

else

記憶個體的位置保持不變

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

2.2 MSOA算法的求解步驟

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

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

步驟2計算當前海鷗種群每個個體的適應度值，計算出當前海鷗種群的全局最優位置和設置個體最優位置；

步驟3迭代尋優，更新海鷗的位置；

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

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

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

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

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

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

步驟10是否滿足條件，若滿足，結束循環，否則，繼續迭代尋優；

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

步驟12結束程序。

3 實驗結果與分析

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

3.1 標準測試函數的測試

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

表1 標準測試函數的相關參數

圖1 函數f1的迭代曲線

圖2 函數f2的迭代曲線

圖3 函數f3的迭代曲線

圖4 函數f4的迭代曲線

表2 SOA、PSO、MSOA算法的實驗結果

圖5 函數f5的迭代曲線

圖6 函數f6的迭代曲線

圖7 函數f7的迭代曲線

圖8 函數f8的迭代曲線

圖9 函數f9的迭代曲線

圖10 函數f10的迭代曲線

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

3.2 線性方程組的測試

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

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

3.3 非線性方程組的測試

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

表3 線性方程組的實驗結果

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

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

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

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

測試方程組(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)的實驗結果

續(表6)

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

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

4 結束語

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