求解絕對值方程的改進捕魚算法

陳建榮，陳建華

（1.右江民族醫學院公共衛生與管理學院，百色 533000；2.右江區醫療保障服務中心，百色 533000）

0 引言

關于絕對值方程（absolute value equations，AVEs）的研究主要來源于兩個方面［1-3］，一是區間線性方程，二是線性互補問題。自Rohn［4］和Mangasarian［5］在絕對值方程相關理論方面做出了開創性的研究工作后，眾多學者對絕對值方程開展了較為廣泛的研究，并取得了較為豐富的成果［6-10］。張曉敏［6］使用神經網絡算法對絕對值方程進行求解。封京梅等人［8］提出了基于單純性法進行局部優化的人群搜索算法求解絕對值方程。雍龍泉［9］則提出一種五階牛頓迭代法來獲得絕對值方程的解。Dong 等人［10］提出一種求解絕對值方程的新的SOR-like方法。

群智能算法［11］作為演化計算技術的一類，是一種能夠解決大多數全局優化問題的有效方法，且因其具有潛在的并行性和分布式特征而得到了廣泛的研究和應用［12-13］。采用捕魚策略的優化算法，即捕魚算法（fishing algorithm），是陳建榮等人［14］通過觀察和模擬漁夫在江面上捕魚的行為習慣而提出的一種群智能算法，該算法被應用于函數尋優和求解約束優化等問題，并表現出較好的性能［14-16］。

1 問題與轉化

一般而言，絕對值方程問題的形式如下［4］：

2 捕魚算法簡介［14］

算法的基本假設包括七方面：一是水中魚的分布及密度保持不變；二是漁夫在撒網前無法提前知曉水中魚的分布情況；三是漁夫會朝魚密度大的方向前進；四是漁夫會停留在魚密度大的位置撒網捕魚；五是漁夫通過使用網眼更小的漁網將魚一網打盡；六是如果當前位置沒有魚或者魚很少，那么漁夫會移動到別的位置撒網捕魚；七是漁夫之間避免相互碰撞。

捕魚算法包括三種基本的搜索方法，即移動搜索、收縮搜索和隨機搜索。算法開始時，首先對漁夫群體進行初始化，然后各個漁夫根據自身當前的狀態來選擇不同的搜索方法進行狀態更新，最后在全體漁夫的共同努力下找到魚密度最高的位置（即問題的最優解）。

3 改進捕魚算法

3.1 算法參數

改進捕魚算法在運行前，需要設置的算法參數包括如下六個：最大迭代次數?、群體規模θ、步長τ、收縮系數σ、撒網次數m和閾值ω。此外，為了記錄每一次迭代中找到的最優值Z（x*）和對應的最優解x*，算法設置有公告板。

3.2 漁夫個體及目標函數

用n維向量xj=（xj,1,…,xj,k,…,xj,n）T來表示漁夫群體中的第j個個體所處的位置。此外，由（2）得到目標函數為

其中，U=Ax- |x|-b。于是，第j個漁夫所處位置對應的目標函數值為Z（x）j。

3.3 撒網方法與改進

根據分析可知，捕魚算法的撒網點集中數據點的數量是3n，也就是說，每一個漁夫的撒網點集的規模會隨著所求解問題的維數而呈現指數級增長。例如，對于二維的問題，漁夫撒網點的個數是32=9；而當問題的維數變成五維的時候，漁夫撒網點的個數就是35=243；當維數是十維的時候，對應撒網點的個數是310=59049。注意，在撒網點集中的數據點都是向量（一維問題時為標量），因此，對于十維的問題，在算法每一次迭代過程中，至少需要存儲59049個十維向量。

此外，由于在每次產生撒網點集之后，需要計算出所有撒網點對應的目標函數值，漁夫才能根據這些結果來選擇自己下一步的搜索行為（即選擇何種搜索方法）。以上述的十維問題為例，漁夫的撒網點數是59049，那么需要計算這59049個點對應的目標函數的值，也就是需要計算59049 次函數的值。按照漁夫規模θ= 100 計算，每一次迭代就需要計算5904900 次目標函數值。倘若目標函數值的計算相對復雜，則需要消耗大量的運算資源，從而使算法效率大大降低。

為了降低計算機系統內存的使用和減少目標函數的計算次數，受到文獻［15］的啟發，本文對捕魚算法的撒網方法進行改進。具體而言，在改進捕魚算法中，第j個漁夫的撒網點集由下式給出：

其中，j= 1,2,…,θ，rand返回一個在區間（0，1）內均勻分布的隨機數。

3.4 程序流程

現將改進捕魚算法的流程簡單描述如下。

輸入：最大迭代次數?、群體規模θ、步長τ、收縮系數σ、撒網次數m和閾值ω。

輸出：最優值Z（x*）和最優解x*。

（1）對θ個漁夫進行隨機初始化；

（2） 如果當前迭代次數已達到最大迭代次數?，算法停止并輸出結果，否則轉（3）；

（3）根據式（3）分別計算出θ個漁夫各自的目標函數值Z（x）j，j=1,2,…,θ；

（4） 根據式（4）產生θ個漁夫的撒網點集，并用式（3）計算出點集中所有的點對應的目標函數值；

（5） 根據下述三條規則依次對θ個漁夫進行狀態更新，并轉（2）。

3）若wj≥ω，則對第j個漁夫進行重新隨機初始化。

4 數值實驗與對比分析

4.1 實驗環境與說明

數值實驗部分所使用的臺式計算機硬件配置為：Inte（lR）Core（TM）i7-4790K CPU@4.00 GHz（睿頻4.8 GHz），32 GB 雙通道DDR3 2400 MHz 內存；軟件環境為：64 位Windows 10 專業版操作系統，MATLAB版本R2020a。

數值實驗分為兩部分，第一部分是捕魚算法與改進捕魚算法求解絕對值方程的結果對比，第二部分是改進捕魚算法與其他群智能算法的對比。為簡單起見，下文中以改進算法指代改進捕魚算法。

此外，為了能更好地檢驗算法的性能，在數值實驗中采取以下的方法：①在每一次算法開始運行時，均使用MATLAB 中的隨機函數對漁夫位置進行隨機初始化。②對于每一個算例，算法均獨立運行20次，并記錄和統計出最后結果。

4.2 結果與分析

（1）捕魚算法與改進算法性能對比。這里將捕魚算法和改進算法的參數統一設置為：最大迭代次數?= 800、群體規模θ= 10、步長τ= 0.8、收縮系數σ= 0.8、撒網次數m=27（僅改進算法有此參數）和閾值ω= 10。

兩種算法的運行結果如表1 所示。從表中可以看出，在求解維數較低的問題時，如例1 和例2，兩種算法的求解效果和精度都很好。但當問題的維數達到十維的時候，如例3（n=10）和例4（n=10），改進算法在最小值、最大值、平均值和方差這四個指標上均比捕魚算法效果要好。從運行時間上看，改進算法的耗時明顯比捕魚算法要低得多，這說明改進之后算法的計算量有較大幅度的下降，求解問題的速度提高了。值得注意的是，當n=20 時，如例3（n=20）和例4（n=20），因捕魚算法所需內存容量遠大于32 GB 的系統內存而無法運行，所以表1 中未能給出相應的計算結果。然而，改進算法對于求解n=20的問題毫無壓力，不僅獲得了較高的求解精度，且其運行耗時和低維問題相比并沒有顯著提高，這說明本文對捕魚算法的改進是有效的。

表1 捕魚算法與改進算法結果對比

（2）改進算法與其他群智能算法求解結果對比。不同算法運行結果如表2—表5 所示（“—”表示原文未給出數據）。

從表2—表5中的數據可以看出，對于求解不同維數的絕對值方程問題，從最小值、最大值、平均值和方差這四個指標上看，與粒子群算法、改進粒子群算法、人群搜索算法及其改進算法相比，本文給出的改進算法的求解精度都是最高的，而且算法的穩定性均比其他對比算法要好。此外，從運行時間上看，本文給出的改進算法的運行速度很快，大概只需要0.4 秒即可求得問題的最優解。

表2 不同算法求解例1的結果對比

表3 不同算法求解例2的結果對比

表4 不同算法求解例3（n=20）的結果對比

表5 不同算法求解例4（n=20）的結果對比

5 結語

本文在分析捕魚算法不足的基礎上，通過對漁夫撒網方法的改進，進而給出了一種求解絕對值方程的改進捕魚算法。改進算法在求解絕對值方程問題時，不僅能獲得更快的收斂速度，而且在計算機內存消耗和運行耗時上均比原算法要好。此外，與粒子群算法和人群搜索算法相比，改進算法擁有更好的穩定性和求解精度。未來的研究將針對表達形式更為復雜的高維絕對值問題的求解展開，并在此基礎上分析和討論改進算法的性能特點，以期進一步擴展改進算法的應用范圍。