陳建榮　陳建華

摘? 要： 提出一種求解絕對(duì)值方程的捕魚算法。算法首先將絕對(duì)值問題轉(zhuǎn)化為一個(gè)最小化問題，然后使用三種搜索模式對(duì)目標(biāo)函數(shù)進(jìn)行尋優(yōu)。數(shù)值實(shí)驗(yàn)結(jié)果表明，與粒子群算法和人群搜索算法以及他們的改進(jìn)算法相比，所提算法不僅獲得了穩(wěn)定的求解結(jié)果，而且在最小值、最大值、平均值和方差等指標(biāo)上均明顯優(yōu)于其他對(duì)比算法。

關(guān)鍵詞： 絕對(duì)值方程; 群智能算法; 捕魚算法; 優(yōu)化

中圖分類號(hào)：TP183? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-8228（2022）02-72-04

Fishing algorithm for solving absolute value equations

Chen Jianrong1， Chen Jianhua2

（1. School of Public Health and Management， Youjiang Medical University for Nationalities， Baise， Guangxi 533000， China;

2. You Jiang District medical security service center）

Abstract： A fishing algorithm for solving absolute value equations is proposed. The algorithm transforms the absolute value problem into a minimization problem， and then optimizes the objective function by using three search modes. Numerical experimental results show that compared with particle swarm optimization algorithm， crowd search algorithm and their improved algorithms， the proposed algorithm not only obtains stable solution results， but also is obviously superior to other comparison algorithms in minimum， maximum， average and variance.

Key words： absolute value equations; swarm intelligence algorithm; fishing algorithm; optimization

0 引言

絕對(duì)值方程等價(jià)于一個(gè)不可微的NP難問題，其最初研究主要來源于區(qū)間線性方程和線性互補(bǔ)問題[1-2]。目前，對(duì)絕對(duì)值方程的研究主要在理論、算法和應(yīng)用幾個(gè)方面，取得了一定成果[3-9]。Rohn[3]和Mangasarian[4]首先對(duì)絕對(duì)值方程進(jìn)行了引領(lǐng)性的研究，并給出了包括解的存在性與數(shù)量的相關(guān)理論。Yu[5]和Chen[6]分別通過改進(jìn)的多元譜梯度算法和無逆動(dòng)力系統(tǒng)對(duì)絕對(duì)值方程來求解。封[7-8]等人則通過使用粒子群和人群搜索算法來獲得絕對(duì)值方程問題的解。雍[9]則提出了一種五階牛頓迭代法求解絕對(duì)值方程。

群智能算法是一種通過模擬自然界中動(dòng)物（或昆蟲等）的群體行為而提出的一類隨機(jī)搜索方法，屬于一種新興的演化計(jì)算技術(shù)，前文提及的粒子群和人群搜索算法都屬于這一類算法。由于群智能算法具有明顯的并行性特征，魯棒性也較好，因而得到了國(guó)內(nèi)外學(xué)者的普遍關(guān)注和研究[10-13]。陳[13]等人通過觀察和模擬漁夫在江面上捕魚的行為習(xí)慣而提出了采用捕魚策略的優(yōu)化算法（Fishing Strategy Optimization Algorithm），即捕魚算法（Fishing Algorithm）。該算法在求解高爐料面?zhèn)鞲衅鞑贾肹14]、TSP問題[15]和約束優(yōu)化[16]等問題中表現(xiàn)出較好的性能。

1 問題描述與轉(zhuǎn)化

本文考慮的絕對(duì)值方程（Absolute Value Equation，AVE）具有如下的形式[3]：

Ax-|x|=b]?⑴

其中，A∈R，x，b∈R，|x|表示對(duì)x中的每一個(gè)分量取絕對(duì)值。其廣義形式是[4]?Ax+B |x|=b。

引理1[1] 如果[A]的所有奇異值均大于1，那么對(duì)于?b∈R，⑴的解存在且惟一;如果A滿足||A||≤1，那么對(duì)于?b∈R，⑴的解存在且惟一。

引理2[1] 如果b<0，且||A||<γ/2，γ=min|b|/max|b|），那么⑴有完全不同的2個(gè)解，且每個(gè)解都沒有零分量，符號(hào)也不同。

為求得絕對(duì)值方程⑴的解，首先將其轉(zhuǎn)化為如下的最小化問題[7]：

2 捕魚算法簡(jiǎn)介[13]

作為一種群智能優(yōu)化算法，捕魚算法的基本假設(shè)包括如下七個(gè)方面：①漁夫的行為對(duì)水中魚的密度無影響;②漁夫不知道水中魚的分布情況;③漁夫往魚密度大的方向前進(jìn)以便能捕到更多的魚;④漁夫會(huì)停留在魚的密度比四周高的位置捕魚;⑤漁夫使用網(wǎng)眼更小的漁網(wǎng)以便將魚一網(wǎng)打盡;⑥若當(dāng)前位置沒有魚或者魚比較少，那么漁夫會(huì)嘗試到其他地方捕魚;⑦漁夫之間避免碰撞。

算法主要通過移動(dòng)搜索、收縮搜索和隨機(jī)搜索三種搜索模式對(duì)漁夫的行為習(xí)慣進(jìn)行模擬。在開始時(shí)，首先在定義域范圍內(nèi)對(duì)漁夫個(gè)體的位置等參數(shù)進(jìn)行初始化;然后各漁夫根據(jù)自己所處的狀態(tài)來選擇不同的搜索模式進(jìn)行搜索和狀態(tài)更新;最后，在漁夫們的共同努力下找到問題的最優(yōu)解。

3 求解絕對(duì)值方程的捕魚算法

3.1 基本參數(shù)

算法設(shè)置有公告板，用于記錄迭代過程中漁夫找到的最優(yōu)值[F（xB）]及對(duì)應(yīng)的最優(yōu)解[xB]。此外，需要設(shè)置的參數(shù)還包括最大迭代次數(shù)[φ]、漁夫規(guī)模m、步長(zhǎng)[λ]、收縮系數(shù)[δ]和閾值[ε]。

3.2 漁夫個(gè)體

3.3 目標(biāo)函數(shù)

結(jié)合⑵，得到求解絕對(duì)值方程的捕魚算法的目標(biāo)函數(shù)如下：

⑶ 隨機(jī)搜索

對(duì)第i個(gè)漁夫的位置進(jìn)行隨機(jī)初始化，并還原其步長(zhǎng)和閾值，根據(jù)⑶重新構(gòu)造撒網(wǎng)點(diǎn)集。

3.5 算法流程

算法流程如下。

步驟1：在定義域范圍內(nèi)隨機(jī)初始化m個(gè)漁夫的位置;

步驟2：如果算法迭代次數(shù)達(dá)到[φ]，則程序停止并將公告板記錄值輸出;

步驟3：根據(jù)漁夫的狀態(tài)選擇執(zhí)行相應(yīng)的搜索模式;

步驟4：如果找到更優(yōu)值則更新公告板，否則轉(zhuǎn)步驟2。

4 數(shù)值實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)環(huán)境及參數(shù)

實(shí)驗(yàn)使用的計(jì)算機(jī)軟硬件配置：Intel（R） Core（TM） i7-4790K CPU @ 4.00GHz（睿頻4.8GHz），32GB雙通道DDR3 2400MHz內(nèi)存，64位Windows 10專業(yè)版操作系統(tǒng)，MATLAB版本為R2020a。

為消除算法參數(shù)、初始值等因素對(duì)本文算法的影響，在數(shù)值實(shí)驗(yàn)中采取如下方法：①每次運(yùn)行時(shí)，使用MATLAB中的隨機(jī)函數(shù)對(duì)漁夫位置進(jìn)行初始化;②對(duì)于每一個(gè)算例，本文算法均獨(dú)立運(yùn)行20次;③對(duì)于所有的算例，將本文算法的參數(shù)統(tǒng)一設(shè)置為：漁夫規(guī)模[m=50]、最大迭代次數(shù)[φ=100]、步長(zhǎng)[λ=0.6]、收縮系數(shù)[δ=0.5]和閾值[ε=10]。

4.2 實(shí)驗(yàn)算例及結(jié)果

數(shù)值實(shí)驗(yàn)中使用的四個(gè)算例[7-8]如下。

不同算法運(yùn)行結(jié)果見表1-表4。由表1-表3中的數(shù)據(jù)可知，在求解例1-例3時(shí)，本文算法在目標(biāo)函數(shù)的最小值、最大值、平均值和方差幾個(gè)指標(biāo)上，所得結(jié)果均比其他算法要好。由表4中求解例4的對(duì)比數(shù)據(jù)可以看出，除PSPSO算法找到的最小值與本文算法一致（均是0）之外，本文算法在對(duì)比指標(biāo)上均比其他算法要優(yōu)。

表5中展示的是本文算法求解例1-例4的結(jié)果（對(duì)比算法未給出相關(guān)數(shù)據(jù)），包括算法求得的解、找到解的平均迭代次數(shù)以及平均耗時(shí)。從表中數(shù)據(jù)可以看出，本文算法的收斂速度很快，在100代以內(nèi)即可找到算例的最優(yōu)解，且算法的平均耗時(shí)均不超過0.4秒。

5 結(jié)束語

本文提出一種用于求解絕對(duì)值方程的捕魚算法。數(shù)值實(shí)驗(yàn)結(jié)果表明，該算法具有運(yùn)行耗時(shí)低，收斂速度快，求解精度高等優(yōu)點(diǎn)。這為實(shí)際問題中獲得絕對(duì)值方程的解提供了一種有效的算法。下一步將嘗試對(duì)高維的絕對(duì)值問題求解，并對(duì)算法的性能做更深入的研究與測(cè)試，以進(jìn)一步拓寬其應(yīng)用范圍。

參考文獻(xiàn)（References）：

[1] Rohn J. Systems of linear interval equtions[J].LinearAlgebra and its Applications，1989，126：39-78

[2] 韓繼業(yè)，修乃華，戚厚鐸.非線性互補(bǔ)理論與算法[M].上海：上?？茖W(xué)技術(shù)出版社，2006

[3] Rohn J. A theorem of the alternatives for the equation Ax+B|x|=b[J]. Linear and Multilinear Algebra，2004，52（6）：421-426

[4] Mangasarian O L， Meyer R R. Absolute value equations[J].Linear Algebra and its Applications，2006，419：359-367

[5] Yu Z S， Li L， Yuan Y. A modified multivariate spectral?gradient algorithm for solving absolute value equations[J].Applied Mathematics Letters，2021，121：107461

[6] Chen C R， Yang Y， Yu D M， Han D R. An inverse-free?dynamical system for solving the absolute value equations[J]. Applied Numerical Mathematics，2021，168：170-181

[7] 封京梅，劉三陽.基于模式搜索的粒子群算法求解絕對(duì)值方程[J].蘭州大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，53（5）：701-705

[8] 封京梅，劉三陽.基于單純形法進(jìn)行局部?jī)?yōu)化的人群搜索算法求解絕對(duì)值方程[J].吉林大學(xué)學(xué)報(bào)（理學(xué)版），2019，57（5）：1075-1080

[9] 雍龍泉.一種五階牛頓迭代法求解絕對(duì)值方程[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2021，51（7）：261-267

[10] Ntakolia C; Iakovidis D K. A swarm intelligence graph-based pathfinding algorithm （SIGPA） for multi-objective route planning[J]. Computers & Operations Research，2021，133：105358

[11] 陳曉全.基于改進(jìn)粒子群算法的解耦控制研究與仿真[J].計(jì)算機(jī)時(shí)代，2021（5）：68-72

[12] 張健，范曉武.基于改進(jìn)蟻群算法的高速公路協(xié)同救援路徑規(guī)劃[J].計(jì)算機(jī)時(shí)代，2021（3）：1-6

[13] 陳建榮，王勇.采用捕魚策略的優(yōu)化方法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（9）：53-56

[14] 苗亮亮，陳先中，侯慶文，等.高爐料面?zhèn)鞲衅鞑贾玫幕煦绮遏~策略[J].儀器儀表學(xué)報(bào)，2014，35（1）：132-139

[15] 陳建榮，陳建華.求解TSP問題的離散捕魚策略優(yōu)化算法[J].計(jì)算機(jī)科學(xué)，2017，44（S1）：139-140，160

[16] 陳建榮，陳建華.求解約束優(yōu)化問題的自適應(yīng)精英捕魚算法[J].信息技術(shù)，2019，43（4）：91-95