基于模糊邻域差分进化算法求解非线性方程组

陈馨 韦慧

摘  要：讨论模糊邻域概率函数选择策略对算法寻根率和成功率的影响.实验结果表明，凸函数类型的概率选择函数较适用于求解多根和搜索空间较广问题，定值概率选择函数较适合于求解含有大量线性方程的问题.选用适当概率选择函数可以提高模糊邻域差分进化算法寻根率和成功率.

关键词：差分进化算法；非线性方程组；模糊邻域；概率选择函数

[   中图分类号    ]O241.7 [    文献标志码   ]  A

Solving Nonlinear Equation Systems via Fuzzy Neighborhood

Differential Evolution Algorithm

CHEN Xin， WEI Hui

（School of Mathematics and Big Data， Anhui University of Science and Technology， Huainan 232001， China）

Abstract：The influence of fuzzy neighborhood probability selection strategies on algorithm root ratio and success rate is discussed.The experimental results show that convex functions are suitable for solving problems with multiple roots and wide search space problems， fixed-value probability selection functions are suitable for solving problems containing large number of linear equations. Choosing an appropriate probability selection function can improve the root ratio and success rate of the fuzzy neighborhood-based differential evolution with orientation algorithm （FNODE）.

Key words：differential evolution； nonlinear equation systems； fuzzy neighborhood；

probability selection function

在科學、物理、工程等领域中的很多问题会涉及到非线性方程组（nonlinear equation systems，NESs）求解.随着计算机技术的发展，智能优化算法也日趋成熟，近年来被广泛应用于非线性方程组的求解[1-2]，如蚁群算法、布谷鸟算法、粒子群算法等.

Storn和Price[3]在1997年提出的差分进化算法（differential evolution，DE）是一种高效的启发式并行搜索技术， 具有收敛快、控制参数少且设置简单等优点，已经应用在电力系统[4]、神经网络[5]中.DE算法优化参数的选择要兼顾探索能力与开发能力，不当的参数选择策略往往容易造成种群个体早熟收敛、搜索停滞等问题.针对这个问题，Qu[6]等提出了一种基于邻域小生境技术的差分进化算法（NCDE），将原始种群划分为多个子种群，从而扩大种群搜索范围和保持种群多样性.Gong[7]等引入加法排斥技术调整目标函数，将加法排斥技术与差分算法相结合，从而提高了算法在单次运行时的搜索能力.许[8]等采用一种新的变异策略和边界处理方法来提高搜索解的多样性，提出了多模态多目标差分进化算法.He[9]等提出基于模糊邻域的定向差分进化算法（FNODE），根据模糊规则和个体分布选择合适的个体以形成邻域，并将邻域个体迁移的方向信息融合到变异中，从而提高了算法的开发和探索能力.本文讨论模糊邻域技术中邻域内概率选择函数对算法求解非线性方程组的寻根率和成功率的影响，并给出适当的概率函数选择策略.

1 实验环境

算法参数设置：NP=100，F=0.5，CR=0.9，m=11，如果方程组的维数[n≤5]，则[ε=10-6]，否则[ε=10-4].每种方法独立运行20次，最后结果取平均值.实验环境：M1处理器macOS操作系统，8 GB，Matlab 2018 a.

2 概率选择函数与评价指标

对不同的非线性方程组进行研究和讨论，选择文献[7]中的7个测试函数.这些测试函数具有多根、高维、搜索空间大等特点，用于验证算法在一次运行中定位多个根的能力.为了验证算法的性能，根据文献[10]中两个常用的评价指标寻根率（root ratio，RR）和成功率（success rate，SR）来判断.在实验部分采用如下三种不同类型的5个概率选择函数：

类型I-线性函数：（P1） [P=1-‖xj-xi‖d，if‖xj-xi‖≤d0，           otherwise]   .

类型II-非线性函数：（P2） [P=1-‖xj-xi‖d2，if‖xj-xi‖≤d0，                otherwise]   .

（P3） [P=12+12cosπd‖xj-xi‖，if‖xj-xi‖≤d0，                             otherwise]   .

（P4） [P=xj-xid-12，if‖xj-xi‖≤d0，                            otherwise]   .

类型III-均匀分布函数：（P5） [P=12，   if‖xj-xi‖≤d0，    otherwise]   .

其中，[d]为模糊邻域内个体与中心个体的最大距离，通过距离[d]计算个体[xj] 被选中在中心个体[xi]最終邻域的概率[P].

3 概率选择函数对比分析

为了分析不同概率选择函数下算法的性能，对每个测试函数进行独立20次实验，表1和表2为5种不同概率选择函数下算法的寻根率和成功率.FNODE-1～FNODE-5分别表示（P1）-（P5）概率选择函数的FNODE算法.

根据实验结果，可得到如下结论：

（1）对于较多包含线性方程的高维优化问题，如F19，采用P5概率函数即取定值时算法的寻根率和成功率最好，采用P2和P3增大靠近中心个体的概率值可有效提升寻根率和成功率；对于不包含线性方程的高维优化问题F01，P5的效果不佳，选用其他4个动态变化的概率选择函数结果良好.

（2）对于具有较大搜索空间的优化问题F04和F23，采用P4效果较好，此概率选择公式在接近中心个体的附近概率值下降速度快，使得个体之间概率值对比明显.其次是P1，P3和P2，而P5固定的概率显然不适用于求解这个问题.

（3）对于多根问题F04，F12，F13，F17和F23，采用P4和P1效果较好，P2，P3的结果相当，P5最不理想.

综合上述分析，P4的计算效果比较稳定.

表3和表4分别给出了Wilcoxon和Friedman检验的统计结果.在Wilcoxon检验中将FNODE-4与采用其他概率选择公式的算法结果相比，可以看出R+的值比R-值好，说明FNODE-4在RR和SR值的结果较优.FNODE-4的结果明显优于FNODE-5，因为p-value小于0.05.在Friedman检验中FNODE-4获得了最好的RR和SR排名，FNODE-1和FNODE-3比FNODE-4稍差，分别排名第二、第三.FNODE-2排名第四，而FNODE-5排名最低.进一步说明选用不同概率选择公式可以使得算法获得更好的结果.

4 结论

本文主要利用He等提出的模糊邻域定向差分进化算法求解非线性方程组，将非线性方程组求解问题转换为单目标最小值优化问题，讨论生成个体模糊邻域时不同概率选择函数对算法的影响.针对多根、高维、大搜索空间等问题，讨论5个不同概率选择函数情形下算法的寻根率和成功率，并进行Wilcoxon和Friedman检验.对于包含较多线性方程的高维优化问题，选用定值概率选择函数可以获取更优的效果；对于多根或具有较大搜索空间的优化问题，选用凸函数类型的非线性概率选择公式可以获取更优的效果.对于本文中不同类型的优化问题，使用P4的计算效果更加稳定.未来将致力于研究设计混合多种技术的算法求解非线性方程组，如排斥技术、聚类技术、多目标技术等，以进一步优化算法性能，提高寻根率和成功率.

参考文献

[1]王剑， 王冰， 葛孟珂. 基于反向学习的人工蜂群算法 [J]. 牡丹江师范学院学报： 自然科学版， 2022 （01）： 23-30.

[2]张小萍. 求解0-1背包问题的佳点集乌鸦优化算法 [J]. 牡丹江师范学院学报： 自然科学版， 2021 （04）： 1-6.

[3]STORN R， PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of global optimization， 1997， 11（4）： 341-359.

[4]吴桂芳， 崔勇， 刘宏， 等. 基于差分进化算法的三维电场传感器解耦标定方法 [J]. 电工技术学报， 2021， 36（19）： 3993-4001.

[5]钟桂凤， 庞雄文， 孙道宗. 基于差分进化的卷积神经网络的文本分类研究 [J]. 南京师大学报： 自然科学版， 2022， 45（01）： 136-141.

[6]QU B-Y， SUGANTHAN P N， LIANG J-J. Differential evolution with neighborhood mutation for multimodal optimization [J]. IEEE transactions on evolutionary computation， 2012， 16（5）： 601-614.

[7]GONG W， WANG Y， CAI Z， et al. Finding multiple roots of nonlinear equation systems via a repulsion-based adaptive differential evolution [J]. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2018， 50（4）： 1499-1513.

[8]许伟伟， 梁静， 岳彩通， 等.多模态多目标差分进化算法求解非线性方程组 [J]. 计算机应用研究， 2019， 36（5）： 1305-1310.

[9]HE W， GONG W， WANG L， et al.  Fuzzy neighborhood-based differential evolution with orientation for nonlinear equation systems [J]. Knowledge-Based Systems， 2019， 182： 104796.

[10]GAO W， LI G， ZHANG Q， et al. Solving nonlinear equation systems by a two-phase evolutionary algorithm [J]. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2019， 51（9）： 5652-5663.

编辑：琳莉