陳建榮，陳建華

（1.右江民族醫(yī)學(xué)院公共衛(wèi)生與管理學(xué)院，百色 533000；2.右江區(qū)醫(yī)療保障服務(wù)中心，百色 533000）

0 引言

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

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

1 問題與轉(zhuǎn)化

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

2 捕魚算法簡介［14］

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

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

3 改進捕魚算法

3.1 算法參數(shù)

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

3.2 漁夫個體及目標函數(shù)

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

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

3.3 撒網(wǎng)方法與改進

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

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

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

其中，j= 1,2,…,θ，rand返回一個在區(qū)間（0，1）內(nèi)均勻分布的隨機數(shù)。

3.4 程序流程

現(xiàn)將改進捕魚算法的流程簡單描述如下。

輸入：最大迭代次數(shù)?、群體規(guī)模θ、步長τ、收縮系數(shù)σ、撒網(wǎng)次數(shù)m和閾值ω。

輸出：最優(yōu)值Z（x*）和最優(yōu)解x*。

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

（2） 如果當前迭代次數(shù)已達到最大迭代次數(shù)?，算法停止并輸出結(jié)果，否則轉(zhuǎn)（3）；

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

（4） 根據(jù)式（4）產(chǎn)生θ個漁夫的撒網(wǎng)點集，并用式（3）計算出點集中所有的點對應(yīng)的目標函數(shù)值；

（5） 根據(jù)下述三條規(guī)則依次對θ個漁夫進行狀態(tài)更新，并轉(zhuǎn)（2）。

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

4 數(shù)值實驗與對比分析

4.1 實驗環(huán)境與說明

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

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

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

4.2 結(jié)果與分析

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

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

表1 捕魚算法與改進算法結(jié)果對比

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

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

表2 不同算法求解例1的結(jié)果對比

表3 不同算法求解例2的結(jié)果對比

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

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

5 結(jié)語

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