北京邮电大学理学院，北京

收稿日期：2023年7月4日；录用日期：2023年8月14日；发布日期：2023年8月22日

摘要

针对使用经典优化方法较难以进行求解的多元非线性方程组问题，首先我们使用群智能优化算法来对其进行求解，其次，在进行问题转化的过程中，提出了一种全新的目标函数构造模型——指数模型来实现对问题的转换；经过验证，相较于传统模型，指数模型有效的增强了算法在求解单目标优化问题上的全局搜索能力；此外，我们采用了带有档案集的差分进化算法，以解决在求解非线性方程组问题的过程中根的留存问题，同时采用随机指数的方式以增强算法的多样性，在所选的六个非线性方程组测试集上，指数模型在相关指标上对比原模型均表现出优势或绝对优势，其中在四个非线性方程组上表现为绝对优势，实验结果表明，所提出的模型能有效搜索到非线性方程组系统的多个根，并与传统的转换模型相比，所提出的指数模型在找根率(root ratio)和成功率(success rate)上更具优越性。

关键词

非线性方程组系统，群智能优化，差分进化算法，指数模型

A Nonlinear Equations Problem Solving Algorithm Based on Exponential Model

Rui Ji

College of Science, Beijing University of Posts and Telecommunications, Beijing

Received: Jul. 4^th, 2023; accepted: Aug. 14^th, 2023; published: Aug. 22^nd, 2023

ABSTRACT

For the problem of multivariate nonlinear equations, which is difficult to be solved by using classical optimization methods, firstly, we use swarm intelligent optimization algorithm to solve it. Secondly, in the process of problem transformation, a new objective function construction-exponential model is proposed to realize the transformation of the problem. It has been verified that compared with the traditional model, the exponential model effectively enhances the global search ability of the algorithm in solving the single objective optimization problem. In addition, we adopted a differential evolution algorithm with file set to solve the problem of root retention in the process of solving nonlinear equations, and adopted a random exponential method to enhance the diversity of algorithms. On the six selected test sets of nonlinear equations, the exponential model showed advantages or absolute advantages compared with the original model in relevant indicators. The experimental results show that the proposed model can effectively search multiple roots of the nonlinear equations system, and compared with the traditional transformation model, the proposed exponential model has more advantages in terms of root ratio and success rate.

Keywords:Nonlinear Equations System, Swarm Intelligence Optimization, Differential Evolution Algorithm, Exponential Model

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

方程求根问题是一个具有悠久历史的重要问题。随着时代的进步和科学技术的不断发展，我们在科学研究和工程实践中遇到的数学问题越来越复杂，方程求根问题更多的开始以方程组、非线性方程组的形式出现，传统数学方法比如牛顿法、拟牛顿法、单纯形法等，十分依赖初值的选取；另外，对于某些导数不存在或是导数难求的方程，传统的数学方法例如牛顿法、改良牛顿法等存在一定的局限性，随着问题复杂度的上升，在非线性方程组系统(nonlinear equations system, NES)上传统的优化算法已经很难高效的求解问题，近年来群智能算法的出现逐渐解决了这一问题，如遗传算法(GAs)、粒子群优化算法(PSO)、差分进化算法(DE)、协方差矩阵自适应进化策略(CMA-ES)。近年来，在非线性方程组上使用群智能算法受到越来越多的关注。在不失一般性的前提下，非线性方程组的公式如下：

$f\left(x\right)={\left(f_1\left(x\right),\cdots ,f_n\left(x\right)\right)}^{\text{T}}=0$ (1)

其中n是方程组中方程的个数， $x={\left(x_1,\cdots ,x_m\right)}^{\text{T}}$ 是一个m维的决策变量。 $x\in S$ ，S是一个搜索区间，每一个变量的边界通常表示如下：

$x_j^L\le x_j\le x_j^U,$ (2)

$j=1,\cdots ,m$ ， $x_j^L$ 是 $x_j$ 的下界， $x_j^U$ 是 $x_j$ 的上界，每一个方程组的根 $x^{*}\in S$ 都要满足 $\forall i\in \left\{1,n\right\},f_i\left(x^{*}\right)=0$ 。

我们可以通过转换技术将非线性方程组系统转换为一种优化问题，再即选择或设计一个优化算法去处理将非线性方程组系统转化后的优化问题。

2. 背景

2.1. 非线性方程组

非线性方程，就是因变量与自变量之间的关系不是线性的关系。由于很多问题都可以通过各种手段抽象转化拟成一个方程或方程组，然后可以利用许多数学方法去进行求解，如微分方程、线性规划等，而现实中的很多实际问题转化成方程后往往是非线性的，并且由于问题复杂度的原因往往以方程组的形式出现，因此对非线性方程组求解的研究具有重要意义。

2.2. 相关工作

1) 单目标转换技术(SOT)

单目标转换技术 [1] [2] [3] 是目前利用群智能算法求解非线性方程组问题最为常用的方法之一，其思想是通过将一个非线性方程组转化为一个单目标优化问题，进而可以各种单目标优化算法对问题进行求解，通常采用的转化方式如下：

$\min F\left(x\right)=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}{f}_i^2\left(x\right)$ (3)

或者

$\min F\left(x\right)=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}\left|f_i\left(x\right)\right|$ (4)

采用平方和或者绝对值和的形式对非线性方程组问题进行转化，两种方式的最优解分别对应于原非线性方程组的根。

2) 基于排斥的变换技术(RBT)

基于排斥的变换方法 [4] 结合了单目标优化技术和斥力技术，它的基本思想是：如果一个根 $x^r$ 被发现并保存在一个档案中，一个斥力区域将围绕它产生一个预定义的斥力半径。然后，对处于排斥区域的任何个体的适应度值进行修改，并驱动算法寻找其他有希望的区域。

通过RBT，将非线性方程组转化为优化问题的一般形式为：

$\min R\left(x\right)=F\left(x\right)\odot P\left(x\right)$ (5)

其中 $P\left(x\right)$ 为斥力函数， $F\left(x\right)$ 为单目标转换技术中转化后的函数。

3) 约束单目标变换(CSOT)

约束单目标变换(CSOT) [5] 是在单目标转换技术的基础之上，将方程组的每一个方程作为约束条件，以使得转换后的问题能够应用各种处理约束优化问题的算法，其主要形式如下：

$\min F\left(x\right)=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}{f}_i^2\left(x\right)$ (5)

约束条件： $f_i\left(x\right)\ge 0,i=1,\cdots ,n$ 。

或者

$\min F\left(x\right)=\underset{i=1}{\overset{1n}{{\displaystyle \sum }}}\left|f_i\left(x\right)\right|$ (6)

约束条件： $f_i\left(x\right)=0,i=1,\cdots ,n$ 。

与单目标转换技术类似，约束单目标变换同样需要额外的多样性保存技术，以便在求解的过程中定位非线性方程组不同的根。

4) 非线性规划变换(NLPT)

应用非线性规划变换(NLPT) [6] 技术，可以将非线性方程组问题的求解转化为求解一个非线性规划问题，在相关研究中 [7] ，原本的非线性方程组问题可以通过添加额外的参数 $\epsilon \in R^n$ 转化为如下形式：

$\min {\Vert {\epsilon }_i-{\epsilon }_i^{*}\Vert }_{\infty }$ (7)

约束条件：

$\{\begin{array}{c}\left|f_i\left(x\right)\right|-{\epsilon }_i\le 0;\\ {\epsilon }_i\ge 0,\end{array}$ (8)

其中 $i=1,\cdots ,n$ ， ${\epsilon }_{}^{*}\in R^n$ 是期望的系统精度。因此，使用此种方法求解非线性方程组问题等价于求解 ${\epsilon }_{}^{*}=0$ 的非线性规划问题。

5) 多目标变换(MOT)

在进化计算(EC)群体中，进化多目标优化(EMO)是非常活跃的 [8] [9] 。EMO的主要目的是找到一组具有良好收敛性和覆盖率的非支配解，即得到的非支配解接近分布良好的真Pareto前沿。定位非线性方程组的多根类似于求解EMO的非支配解。利用多目标转换技术，可以将一个NES问题转化为一个多目标优化问题(MOP)。

2.3. 群智能优化算法

群智能算法是一类仿生计算方法，灵感来源于群体生物(如鸟群、蚁群等)在协作中展现出的智能行为。这些算法通过模拟自然界中的群体行为和交互方式，将个体之间的合作与竞争相结合，从而实现优化问题的求解。典型的群智能算法包括粒子群优化算法(Particle Swarm Optimization, PSO)、蚁群算法(Ant Colony Optimization, ACO)、差分进化算法(Differential Evolution, DE)等。

2.4. 差分进化算法

差分进化算法 [10] 的基本思想：随机生产一组初始个体，每个个体代表一个初始解，新个体的产生借助指定的变异、交叉等方式生成。每个新个体与原父个体进行比较，如果优于原父个体，则选择新个体作为子代，反之原父个体作为子代。这种替换的优势在于子代个体总是优于父代个体，种群通过不断地进化直至收敛到全局最优个体或是满足指定结束条件。

3. 基于指数模型的求解算法

3.1. 模型思路

基于指数模型的思想，为解决转换成单目标优化问题的非线性方程组问题，本文提出了新的求解模型，其基本思想是：将现有的两种单目标转换技术进行结合，通过指数模型构建目标函数如下：

$\min F\left(x\right)=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}\left|f_i^m\left(x\right)\right|$ (9)

其中m即可以为预先设定的超参数，也可以根据所选取的算法来进行针对性的调整，通过控制m的值来对模型进行调整和优化。当m取1或2的时候，分别对应原始的两种求解非线性方程组问题的单目标转换技术。

$\min F\left(x\right)=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}\left|f_i\left(x\right)\right|$ (10)

和

$\min F\left(x\right)=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}{f}_i^2\left(x\right)$ (11)

3.2. 参数设置

在指数模型指数的设置上，在每次算法进行迭代计算的过程当中，m随机从(2, 5, 10)三个数当中选取一个数作为本次迭代的指数数值，经过数值模拟实验验证，采用这种方法可以使得在迭代过程中增强算法的全局搜索能力，从而提高算法在对应非线性方程组问题求解上的效果。

3.3. 衡量指标

为了衡量算法的性能和其对于非线性方程组问题的求解效率，我们采用文献 [11] 中的两个性能指标：寻根率(root ratio, RR)和成功率(success rate, SR)来判断。

RR的计算公式如下：

$\text{RR}=\frac{{\displaystyle {\sum }_{i=1}^{N_r}{\text{NOR}}_i}}{\text{NOR}\cdot N_r}$ (12)

其中， $N_r$ 是算法独立运行的总次数， ${\text{NOR}}_i$ 为当前第i次独立运行找到根的个数，NOR为当前NES已知根的个数。

SR的计算公式如下：

$\text{SR}=\frac{N_{sr}}{N_r}$ (13)

其中 $N_{sr}$ 为成功找到NES所有根的次数。

4. 数值实验

本次数值实验部分，我们使用Windows 10操作系统。用MATLAB语言编写了本文提出的基于指数模型的新算法程序，算法基于MATLAB2021b版本环境运行。

4.1. 选用的测试数据

为验证模型的有效性，本文采用了从低维到高维的六组非线性方程组对文中所提出的模型和算法的效果进行测试，分别是三个2元非线性方程组，一个3元非线性方程组、一个4元非线性方程组、一个5元非线性方程组。

4.2. 测试算法

在本次实验中，由于传统的差分进化算法通常在一次运行中仅能同时定位记录优化问题的一个解(在非线性方程组问题上即只能记录方程组的一个根)，由于非线性方程组问题通常具有多个根，因此我们选用改进后的差分进化算法来求解利用指数模型方法和单目标转换技术转化后的非线性方程组问题，改进后的差分进化算法与原差分进化算法的区别主要在于增加了外部存档集这种额外的多样性保存技术，以储存算法在运行过程当中找到的非线性方程组的根，同时引入初始化策略，在找到该根的位置并记录在外部存档集之后，对根所在的位置进行初始化，以使得算法能够继续寻找该非线性方程组问题其他的根，以增强算法的多样性，并最终实现对该利用指数模型方法和单目标转换技术转化后的非线性方程组问题的求解。

4.3. 实验参数

1) 候选根精度： $\theta ={10}^{-6}$ (因为方程组的维数 $n\le 5$ )；

2) 距离半径(保证两候选根不要靠得太近，即是不同的根)： $\delta ={10}^{-3}$ ；

3) 外部存档容纳最大个体数 ${\max }_{sa}=\text{NP}$ ，对所有问题，算法独立运行30次( $N_r=30$ )。

4.4. 数值结果

图1. 不同指数在各个方程组上的SR (成功率)

图2. 不同指数在各个方程组上的RR (找根率)

4.5. 结果对比和分析

本文采用了基于指数模型的全新转换技术，来将一个非线性方程组问题转化为一个带有指数目标函数的单目标优化问题，在使用相同的单目标优化算法的情况下(带有档案集的改进的差分进化算法)，算法基于这两种不同的模型分别在SR和RR两个衡量指标上的对比结果见图1和图2，从实验结果中可以看出，新模型在六个非线性方程组的均表现出优势或绝对优势，其中SR值(见图1)在4个非线性方程组上数值最高，RR值(见图2)也在其中4个非线性方程组上数值最高(二者有交叉和不重合的部分)，即指数模型在我们所选用的非线性方程组测试集的6个方程组上，在超过一半的方程组上是绝对优于原模型的，说明新模型结合非线性方程组单目标转换技术在利用单目标群智能算法求解转化非线性方程组问题上具有一定优势。

4.6. 模型分析

本文在将非线性方程组问题转换为单目标优化问题这一过程中，采用全新的指数模型来构建单目标优化函数，取代了传统转换技术中采用平方和和绝对值和的两种模型，新的指数模型不仅能够完全包含传统方法中的模型，更是通过引入指数这一变量的方式增强算法在求解问题时的全局搜索能力，但指数模型对算法在求解问题时的收敛能力提升有限，同时在面对非线性方程组的根分布较为密集、解空间较小的情况下对算法求解问题的性能提升较弱，如何更好的平衡算法在求解问题时的全局搜索能力和局部收敛能力、对于部分复杂非线性方程组如何更好的求解是接下来需要继续研究和探讨的问题。

5. 结论

本文为求解非线性方程组问题，在使用单目标转换技术的基础之上提出了一种新的转换模型，即一种基于指数模型的转换格式，我们通过分析非线性方程组问题及利用单目标转换技术后问题的结构，发现可以引入指数模型来在原本所使用的单目标群智能优化算法的基础上来增强算法的效果，并且当取特定指数的时候，指数模型与原单目标转换技术等价，因此，指数模型不仅能够完全的覆盖原有的转换模型，更因为引入了指数这一变量使得模型的拓展性更强。此外，与单目标转换技术不同，本文引入随机指数模型来增强算法的多样性。数值实验标明，我们的新模型在求解非线性方程组问题的成功率和找根率等性能上具有一定的优势。

文章引用

纪 瑞. 一种基于指数模型的非线性方程组问题求解算法
A Nonlinear Equations Problem Solving Algorithm Based on Exponential Model[J]. 运筹与模糊学, 2023, 13(04): 4081-4087. https://doi.org/10.12677/ORF.2023.134408

参考文献