求解絕對值方程的改進(jìn)捕魚算法

陳建榮，陳建華

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

0 引言

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

群智能算法［11］作為演化計(jì)算技術(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)前無法提前知曉水中魚的分布情況；三是漁夫會朝魚密度大的方向前進(jìn)；四是漁夫會停留在魚密度大的位置撒網(wǎng)捕魚；五是漁夫通過使用網(wǎng)眼更小的漁網(wǎng)將魚一網(wǎng)打盡；六是如果當(dāng)前位置沒有魚或者魚很少，那么漁夫會移動到別的位置撒網(wǎng)捕魚；七是漁夫之間避免相互碰撞。

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

3 改進(jìn)捕魚算法

3.1 算法參數(shù)

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

3.2 漁夫個(gè)體及目標(biāo)函數(shù)

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

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

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

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

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

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

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

3.4 程序流程

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

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

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

（1）對θ個(gè)漁夫進(jìn)行隨機(jī)初始化；

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

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

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

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

3）若wj≥ω，則對第j個(gè)漁夫進(jìn)行重新隨機(jī)初始化。

4 數(shù)值實(shí)驗(yàn)與對比分析

4.1 實(shí)驗(yàn)環(huán)境與說明

數(shù)值實(shí)驗(yàn)部分所使用的臺式計(jì)算機(jī)硬件配置為：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ù)值實(shí)驗(yàn)分為兩部分，第一部分是捕魚算法與改進(jìn)捕魚算法求解絕對值方程的結(jié)果對比，第二部分是改進(jìn)捕魚算法與其他群智能算法的對比。為簡單起見，下文中以改進(jìn)算法指代改進(jìn)捕魚算法。

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

4.2 結(jié)果與分析

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

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

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

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

從表2—表5中的數(shù)據(jù)可以看出，對于求解不同維數(shù)的絕對值方程問題，從最小值、最大值、平均值和方差這四個(gè)指標(biāo)上看，與粒子群算法、改進(jìn)粒子群算法、人群搜索算法及其改進(jìn)算法相比，本文給出的改進(jìn)算法的求解精度都是最高的，而且算法的穩(wěn)定性均比其他對比算法要好。此外，從運(yùn)行時(shí)間上看，本文給出的改進(jìn)算法的運(yù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)方法的改進(jìn)，進(jìn)而給出了一種求解絕對值方程的改進(jìn)捕魚算法。改進(jìn)算法在求解絕對值方程問題時(shí)，不僅能獲得更快的收斂速度，而且在計(jì)算機(jī)內(nèi)存消耗和運(yùn)行耗時(shí)上均比原算法要好。此外，與粒子群算法和人群搜索算法相比，改進(jìn)算法擁有更好的穩(wěn)定性和求解精度。未來的研究將針對表達(dá)形式更為復(fù)雜的高維絕對值問題的求解展開，并在此基礎(chǔ)上分析和討論改進(jìn)算法的性能特點(diǎn)，以期進(jìn)一步擴(kuò)展改進(jìn)算法的應(yīng)用范圍。