求解绝对值方程的捕鱼算法

陈建荣　陈建华

摘  要： 提出一种求解绝对值方程的捕鱼算法。算法首先将绝对值问题转化为一个最小化问题，然后使用三种搜索模式对目标函数进行寻优。数值实验结果表明，与粒子群算法和人群搜索算法以及他们的改进算法相比，所提算法不仅获得了稳定的求解结果，而且在最小值、最大值、平均值和方差等指标上均明显优于其他对比算法。

关键词： 绝对值方程; 群智能算法; 捕鱼算法; 优化

中图分类号：TP183          文献标识码：A 文章编号：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 引言

绝对值方程等价于一个不可微的NP难问题，其最初研究主要来源于区间线性方程和线性互补问题[1-2]。目前，对绝对值方程的研究主要在理论、算法和应用几个方面，取得了一定成果[3-9]。Rohn[3]和Mangasarian[4]首先对绝对值方程进行了引领性的研究，并给出了包括解的存在性与数量的相关理论。Yu[5]和Chen[6]分别通过改进的多元谱梯度算法和无逆动力系统对绝对值方程来求解。封[7-8]等人则通过使用粒子群和人群搜索算法来获得绝对值方程问题的解。雍[9]则提出了一种五阶牛顿迭代法求解绝对值方程。

群智能算法是一種通过模拟自然界中动物（或昆虫等）的群体行为而提出的一类随机搜索方法，属于一种新兴的演化计算技术，前文提及的粒子群和人群搜索算法都属于这一类算法。由于群智能算法具有明显的并行性特征，鲁棒性也较好，因而得到了国内外学者的普遍关注和研究[10-13]。陈[13]等人通过观察和模拟渔夫在江面上捕鱼的行为习惯而提出了采用捕鱼策略的优化算法（Fishing Strategy Optimization Algorithm），即捕鱼算法（Fishing Algorithm）。该算法在求解高炉料面传感器布置[14]、TSP问题[15]和约束优化[16]等问题中表现出较好的性能。

1 问题描述与转化

本文考虑的绝对值方程（Absolute Value Equation，AVE）具有如下的形式[3]：

Ax-|x|=b] ⑴

其中，A∈R，x，b∈R，|x|表示对x中的每一个分量取绝对值。其广义形式是[4] Ax+B |x|=b。

引理1[1] 如果[A]的所有奇异值均大于1，那么对于∀b∈R，⑴的解存在且惟一;如果A满足||A||≤1，那么对于∀b∈R，⑴的解存在且惟一。

引理2[1] 如果b<0，且||A||<γ/2，γ=min|b|/max|b|），那么⑴有完全不同的2个解，且每个解都没有零分量，符号也不同。

为求得绝对值方程⑴的解，首先将其转化为如下的最小化问题[7]：

2 捕鱼算法简介[13]

作为一种群智能优化算法，捕鱼算法的基本假设包括如下七个方面：①渔夫的行为对水中鱼的密度无影响;②渔夫不知道水中鱼的分布情况;③渔夫往鱼密度大的方向前进以便能捕到更多的鱼;④渔夫会停留在鱼的密度比四周高的位置捕鱼;⑤渔夫使用网眼更小的渔网以便将鱼一网打尽;⑥若当前位置没有鱼或者鱼比较少，那么渔夫会尝试到其他地方捕鱼;⑦渔夫之间避免碰撞。

算法主要通过移动搜索、收缩搜索和随机搜索三种搜索模式对渔夫的行为习惯进行模拟。在开始时，首先在定义域范围内对渔夫个体的位置等参数进行初始化;然后各渔夫根据自己所处的状态来选择不同的搜索模式进行搜索和状态更新;最后，在渔夫们的共同努力下找到问题的最优解。

3 求解绝对值方程的捕鱼算法

3.1 基本参数

算法设置有公告板，用于记录迭代过程中渔夫找到的最优值[F（xB）]及对应的最优解[xB]。此外，需要设置的参数还包括最大迭代次数[φ]、渔夫规模m、步长[λ]、收缩系数[δ]和阈值[ε]。

3.2 渔夫个体

3.3 目标函数

结合⑵，得到求解绝对值方程的捕鱼算法的目标函数如下：

⑶ 随机搜索

对第i个渔夫的位置进行随机初始化，并还原其步长和阈值，根据⑶重新构造撒网点集。

3.5 算法流程

算法流程如下。

步骤1：在定义域范围内随机初始化m个渔夫的位置;

步骤2：如果算法迭代次数达到[φ]，则程序停止并将公告板记录值输出;

步骤3：根据渔夫的状态选择执行相应的搜索模式;

步骤4：如果找到更优值则更新公告板，否则转步骤2。

4 数值实验及分析

4.1 实验环境及参数

实验使用的计算机软硬件配置：Intel（R） Core（TM） i7-4790K CPU @ 4.00GHz（睿频4.8GHz），32GB双通道DDR3 2400MHz内存，64位Windows 10专业版操作系统，MATLAB版本为R2020a。

为消除算法参数、初始值等因素对本文算法的影响，在数值实验中采取如下方法：①每次运行时，使用MATLAB中的随机函数对渔夫位置进行初始化;②对于每一个算例，本文算法均独立运行20次;③对于所有的算例，将本文算法的参数统一设置为：渔夫规模[m=50]、最大迭代次数[φ=100]、步长[λ=0.6]、收缩系数[δ=0.5]和阈值[ε=10]。

4.2 实验算例及结果

数值实验中使用的四个算例[7-8]如下。

不同算法运行结果见表1-表4。由表1-表3中的数据可知，在求解例1-例3时，本文算法在目标函数的最小值、最大值、平均值和方差几个指标上，所得结果均比其他算法要好。由表4中求解例4的对比数据可以看出，除PSPSO算法找到的最小值与本文算法一致（均是0）之外，本文算法在对比指标上均比其他算法要优。

表5中展示的是本文算法求解例1-例4的结果（对比算法未给出相关数据），包括算法求得的解、找到解的平均迭代次数以及平均耗时。从表中数据可以看出，本文算法的收敛速度很快，在100代以内即可找到算例的最优解，且算法的平均耗时均不超过0.4秒。

5 结束语

本文提出一种用于求解绝对值方程的捕鱼算法。数值实验结果表明，该算法具有运行耗时低，收敛速度快，求解精度高等优点。这为实际问题中获得绝对值方程的解提供了一种有效的算法。下一步将尝试对高维的绝对值问题求解，并对算法的性能做更深入的研究与测试，以进一步拓宽其应用范围。

参考文献（References）：

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

[2] 韩继业，修乃华，戚厚铎.非线性互补理论与算法[M].上海：上海科学技术出版社，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] 封京梅，刘三阳.基于模式搜索的粒子群算法求解绝对值方程[J].兰州大学学报（自然科学版），2017，53（5）：701-705

[8] 封京梅，刘三阳.基于单纯形法进行局部优化的人群搜索算法求解绝对值方程[J].吉林大学学报（理学版），2019，57（5）：1075-1080

[9] 雍龙泉.一种五阶牛顿迭代法求解绝对值方程[J].数学的实践与认识，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].计算机时代，2021（5）：68-72

[12] 张健，范晓武.基于改进蚁群算法的高速公路协同救援路径规划[J].计算机时代，2021（3）：1-6

[13] 陈建荣，王勇.采用捕鱼策略的优化方法[J].计算机工程与应用，2009，45（9）：53-56

[14] 苗亮亮，陈先中，侯庆文，等.高炉料面传感器布置的混沌捕鱼策略[J].仪器仪表学报，2014，35（1）：132-139

[15] 陈建荣，陈建华.求解TSP問题的离散捕鱼策略优化算法[J].计算机科学，2017，44（S1）：139-140，160

[16] 陈建荣，陈建华.求解约束优化问题的自适应精英捕鱼算法[J].信息技术，2019，43（4）：91-95