基于Tent混沌初始化差分算法求解非线性方程组

李侦瑷　韦慧

摘 要：针对非线性方程组多根问题，准确定位多根的位置十分关键。为了增强种群多样性，提高基于模糊邻域定向差分进化算法的寻根率，利用Tent混沌映射初始化种群。为了说明改进算法的效率和寻根率，选取了30个非线性方程组进行测试，并与原模糊邻域定向差分算法、基于邻域的拥挤差分算法、基于邻域的物种形成差分算法和基于排斥的自适应差分算法进行比较。实验结果表明，加入Tent混沌映射的模糊邻域定向差分进化算法在寻根率和成功率上更具有优越性。

关键词：非线性方程组；Tent混沌；差分进化；模糊邻域

中图分类号：O24；TP183  文献标识码：A  文章编号：1673-260X（2023）03-0024-05

1 引言

非线性方程组（NESs）的求解问题目前广泛应用于数学、科学和工程等领域[1，2]。传统优化算法有牛顿法、梯度下降法等，但这些方法存在着一定的局限性，并且在一次运行中只能定位到一个根。而智能优化算法作为一种基于群体的优化算法，具有较高的适应性和有效性。智能优化算法能够有效解决传统算法难以解决的复杂问题，并且被广泛的应用于非线性方程组的求解。常见的智能优化算法有：遗传算法[3]、布谷鸟算法[4]、粒子群算法[5]、差分进化算法（DE）[6]等。

利用智能优化算法求解非线性方程组，首先要将方程组转换为优化问题，然后用智能优化算法对该优化问题进行求解。转换方式包括：将非线性方程组转换为单目标优化问题，或多目标优化问题。Qu等人[7]将邻域技术分别与拥挤技术（NCDE）和物种形成技术（NSDE）相结合来提高算法性能。Gao等人[8]介绍了一种基于K-means聚类的选择策略，通过聚类技术来解决多目标优化问题。对于单目标优化问题，Gong等人[9]提出一种基于排斥技术的自适应差分进化算法（RADE）来求解非线性方程组，并通过邻域突变和拥挤选择保持种群多样性进一步提高算法的搜索能力。Liao等人[10]提出一种基于动态排斥技术的进化算法，通过动态排斥技术控制排斥半径，从而解决了排斥性半径的最优参数设置的难题。He等人[11]提出基于模糊邻域的定向差分进化算法（FNODE）。在FNODE算法中，改进的模糊邻域技术自适应的选择合适的个体形成邻域，将邻域中个体迁移的方向信息整合到突变策略中，推动后代个体向更好的地方迁移，提高了算法的探索和开发能力。

在FNODE算法中，通过均匀分布随机生成初始种群化。为了进一步提高种群多样性，利用Tent混沌映射初始化种群，充分利用混沌映射随机性、遍历性和规律性的特点来增强初始种群的多样性，提高算法的寻优速率和全局搜索能力。

将基于Tent混沌映射的FNODE算法，与FNODE、NCDE、NSDE和RADE这4个优化算法来求解非线性方程组，在寻根率和成功率两个方面对这5个算法进行对比。最后又讨论了邻域参数对基于Tent混沌映射的FNODE算法的影响。

2 预备知识

2.1 问题提出及转化

一般的，非线性方程组（NESs）由m个方程组成，其中至少包含一个非线性方程。决策向量x=（x1，x2，…xn）T∈S是n维的，S是决策向量的搜索空间，NESs的表达式为，

利用优化算法求解NESs，要将NESs转换为单目标最小化问题，即

2.2 Tent混沌映射

在混沌机制中，Tent混沌映射[12，13]具有较高的随机性和遍历性，在[0，1]区间能够生成分布均匀的序列。Tent混沌映射的结构简单，并且便利性好。

利用Tent混沌映射初始化种群，首先通过映射方程在[0，1]区间内生成一个混沌序列，映射方程为

其中，Zij为混沌序列，i=1，2，…，NP代表种群规模，j=1，2，…，D表示种群变量的维数。接着将混沌序列中的点通过下式载波到各个分量的搜索空间中。

其中，[mini，maxi]是Xij的搜索区间。

2.3 基于Tent混沌初始化的FNODE算法

基于Tent混沌初始化的FNODE算法，利用Tent混沌映射生成初始种群。充分利用混沌映射随机性与遍历性的特点，在搜索空间内生成分布均匀的初始种群，以提高种群的多样性和算法的寻优速率。关于FNODE算法见参考文献[11]，下面简单介绍通过Tent混沌生成初始种群步骤。

首先，随机生成一个分布在[0，1]区间内的n维的初始向量Z（0）。利用映射方程公式（3）将初始向量通过迭代生成一个大小为NP的混沌序列Zij。接着通过公式（4）将混沌序列中的各个分量载波到对应变量的搜索空间，即生成一个初始种群P，其中包含NP个个体：

3 实验及结果分析

本文基于Intel（R） Core（TM） i5-8250U CPU @ 1.60GHz 1.80 GHz，8GB内存，Windows 10操作系统和软件MATLAB R2018b下对算法进行仿真实验。

3.1 测试函数与评价指标

从文献[14]中选择了30个不同特征的非线性方程组作为测试函数，对这5个算法进行实验。通过两个常用的评价指标来比较不同算法的性能[15，16]。

（1）尋根率（root ratio， RR）：RR=，利用此指标来评价多次运行中找到NESs根的概率。

（2）成功率（success rate， SR）：SR=，在所有运行中成功运行的概率。

其中，Nr是独立运行的次数，NOSi表示第i次运行中找到根的个数，NOS为方程组真实的根的个数，Nrs是成功运行的次数。

3.2 不同算法的比较分析

基于Tent映射初始化的FNODE算法与如下4个优化算法进行对比：

（1）FNODE：在FNODE中，将改进的模糊邻域和邻域方向结合在一起，对算法的开发与勘探的平衡有很好的影响，提高了算法的搜索效率。通过与FNODE方法的比较，评价Tent混沌映射的效果。

（2）NCDE：在NCDE中，提出了一种邻域突变策略，并将其与拥挤小生境差分进化算法相结合用于解决多模态优化问题。

（3）NSDE：与（2）中NCDE算法相同，在NSDE中，利用的是物种形成小生境技术。与NCDE和NSDE相比，基于Tent映射的FNODE算法采用了拥挤选择技术和相似的邻域突变。

（4）RADE：在RADE中，DE算法采用自适应参数控制技术以控制参数自动匹配到适当的值，从而提高解决不同NESs的搜索能力，利用邻域突变和拥挤选择来保持种群的多样性。

在实验中对RADE算法的参数设置为NP=100，Hm=200，其余4种算法的参数设置均为NP=100，F=0.5，CR=0.5，m=10。每个测试问题独立运行50次。表1是5种算法在求解30个非线性方程组时所获得的寻根率（RR）和成功率（SR）。

根据实验结果，5个算法针对不同类型的测试函数可归纳得到如下结论：

（1） 在30个测试函数中，包含线性方程的高维NESs问题，即F19，Tent_FNODE算法能够获取最好的寻根率和成功率，与原始FNODE算法相比，有效提高了寻根率和成功率。对于不包含线新方程的高维NESs问题，即F01，Tent_FNODE方法的寻根率和成功率最优，NSDE算法的效果不佳。

（2） 对于多根问题，如F02、F03、F12、F17和F23，从表中可以明显看出Tent_FNODE算法的效最佳，而NSDE算法的结果最不理想。

由表中数据可以明显看出，Tent_FNODE方法能够获得最优的平均RR值和SR值，NSDE的效果相比之下较差。综上分析，Tent_FNODE算法能够有效提高算法的求根效率，在求解NESs问题上比其他4种算法的性能更具优势。

此外，表2和表3分别是Friedman和Wilcoxon检验的结果。从表2中可以看出，Tent_FNODE算法获得了最佳的RR和SR排名，而NSDE算法获得了最低排名。在Wilcoxon秩和检验中，将Tent_FNODE方法与其他4种算法相比。可以明显看出Tent_FNODE的结果优于其他4种方法，因为p-value小于0.05。并且R+值总是大于R-值，说明Tent_FNODE算法获得了更好的RR和SR值。Tent_FNODE的显著性优势从小到大排序依次是FNODE、NCDE、RADE和NSDE，进一步说明Tent_FNODE方法在搜索NESs根时的性能明显优于其他4种算法。

3.3 Tent_FNODE中不同参数设置的影响

在Tent_FNODE算法中形成模糊邻域时，引入了邻域边界m参数。在算法比较实验中，对邻域边界参数的设置为m=10。对于邻域边界m，通过对它赋以不同的值：7，8，9，10，11和12，讨论了关于该参数的设置对算法性能的影响。在Tent_FNODE中的所有其他参数设置都不变。关于不同m值的平均寻根率和平均成功率结果如表4所示，表5和表6分别是对于不同参数设置的Friedman和Wilcoxon检验的结果。

由表4可以看出，m=10提供了最優的寻根率和成功率。此外，当m取7，8，9，11和12时的结果差距不大。从表5中的Friedman检验的结果可以明显看出，当模糊边界参数m=10时，Tent_FNODE算法可以获得最佳排名，并且参数在集合{7，8，9，10}中可以获得较好的性能。通过表6中Wilcoxon检验的结果可以看出，p-value都大于0.05，说明参数设置为10与其他设置值比较相差不大，进一步说明参数m对Tent_FNODE算法的性能的影响不大。

4 结论

本文基于He等人提出的FNODE算法，将Tent混沌机制引入该算法中求解非线性方程组问题。将非线性方程组转换为单目标最小值优化问题，通过Tent混沌映射初始化种群，生成在搜索空间中分布均匀的初始种群，从而增强种群的多样性，提高算法的寻优速率。主要将基于Tent混沌映射的FNODE算法与原FNODE算法、NCDE、NSDE和RADE算法进行比较。选择了30个具有不同特征的非线性方程组作为测试函数，进行了独立运行50次的实验，以寻根率和成功率作为评价指标对这5个算法进行比较。通过实验结果表明，基于Tent混沌初始化的FNODE算法能够有效提高算法的寻根率与成功率，并且比其他4个算法更具优越性。最后，验证了Tent_FNODE算法中邻域边界参数m对算法性能的影响，实验结果表明参数m对算法的影响不大。

——————————

参考文献：

〔1〕Fujita H， Cimr D. Computer aided detection for fibrillations and flutters using deep convolutional neural network [J]. Information Sciences 2019; 486：231-239.

〔2〕Zhao J， Xu Y， Fujita H. An improved non-parallel Universum support vector machine and its safe sample screening rule [J]. Knowledge-Based Systems 2019; 170：79-89.

〔3〕Ghodousian A， Babalhavaeji A. An efficient genetic algorithm for solving nonlinear optimization problems defined with fuzzy relational equations and max-Lukasiewicz composition [J]. Applied Soft Computing 2018; 69：475-492.

〔4〕Zhang X， Wan Q， Fan Y. Applying modified cuckoo search algorithm for solving systems of nonlinear equations [J]. Neural Computing & Applications 2019; 31：553-576.

〔5〕Ibrahim AM， Tawhid MA. A hybridization of cuckoo search and particle swarm optimization for solving nonlinear systems [J]. Evolutionary Intelligence 2019; 12：541-561.

〔6〕Tawhid MA， Ibrahim AM. A hybridization of grey wolf optimizer and differential evolution for solving nonlinear systems [J]. Evolving Systems 2020; 11：65-87.

〔7〕Qu BY， Suganthan PN， Liang JJ. Differential evolution with neighborhood mutation for multimodal optimization [J]. IEEE Transactions on Evolutionary Computation 2012; 16：601-614.

〔8〕Gao W， Luo Y， Xu J， Zhu S. Evolutionary algorithm with multiobjective optimization technique for solving nonlinear equation systems [J]. Information Sciences 2020; 541：345-361.

〔9〕Gong W， Yong W， Cai Z， Wang L. Finding multiple roots of nonlinear equation systems via a repulsion-Based adaptive differential evolution [J]. IEEE Transactions on Systems， Man， and Cybernetics： Systems 2020; 50：1499-1513.

〔10〕Liao Z， Gong W， Yan X et al. Solving nonlinear equations system with dynamic repulsion-based evolutionary algorithms [J]. IEEE Transactions on Systems， Man， and Cybernetics： Systems 2020; 50：1590-1601.

〔11〕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.

〔12〕Jiandong L， Ming Z， Bo L et al. Design of three-dimensional dynamic integer tent map and its image encryption algorithm [J]. Multimedia Tools and Applications 2021; 80：19219-19236.

〔13〕Nezhad SYD， Safdarian N， Zadeh SAH. New method for fingerprint images encryption using DNA sequence and chaotic tent map [J]. Optik 2020; 224.

〔14〕Liao Z， Gong W， Wang L et al. A decomposition-based differential evolution with reinitialization for nonlinear equations systems [J]. Knowledge-Based Systems 2020; 191：105312.

〔15〕王開，龚文引.求解非线性方程组系统的改进差分进化算法[J].控制与决策，2020，35（03）：8-13.

〔16〕Zhang X-T， Xu B， Zhang W et al. Dynamic neighborhood-based particle swarm optimization for multimodal problems [J]. Mathematical Problems in Engineering 2020; 2020.

收稿日期：2022-11-14

通讯作者：韦慧（1986-），女，广西河池人，副教授，博士，主要从事偏微分方程数值解研究。

基金项目：安徽省自然科学基金（2108085MA14）；安徽省博士后基金（2019B318）