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

李偵璦　韋慧

摘 要：針對非線性方程組多根問題，準確定位多根的位置十分關(guān)鍵。為了增強種群多樣性，提高基于模糊鄰域定向差分進化算法的尋根率，利用Tent混沌映射初始化種群。為了說明改進算法的效率和尋根率，選取了30個非線性方程組進行測試，并與原模糊鄰域定向差分算法、基于鄰域的擁擠差分算法、基于鄰域的物種形成差分算法和基于排斥的自適應(yīng)差分算法進行比較。實驗結(jié)果表明，加入Tent混沌映射的模糊鄰域定向差分進化算法在尋根率和成功率上更具有優(yōu)越性。

關(guān)鍵詞：非線性方程組；Tent混沌；差分進化；模糊鄰域

中圖分類號：O24；TP183? 文獻標識碼：A? 文章編號：1673-260X（2023）03-0024-05

1 引言

非線性方程組（NESs）的求解問題目前廣泛應(yīng)用于數(shù)學、科學和工程等領(lǐng)域[1，2]。傳統(tǒng)優(yōu)化算法有牛頓法、梯度下降法等，但這些方法存在著一定的局限性，并且在一次運行中只能定位到一個根。而智能優(yōu)化算法作為一種基于群體的優(yōu)化算法，具有較高的適應(yīng)性和有效性。智能優(yōu)化算法能夠有效解決傳統(tǒng)算法難以解決的復(fù)雜問題，并且被廣泛的應(yīng)用于非線性方程組的求解。常見的智能優(yōu)化算法有：遺傳算法[3]、布谷鳥算法[4]、粒子群算法[5]、差分進化算法（DE）[6]等。

利用智能優(yōu)化算法求解非線性方程組，首先要將方程組轉(zhuǎn)換為優(yōu)化問題，然后用智能優(yōu)化算法對該優(yōu)化問題進行求解。轉(zhuǎn)換方式包括：將非線性方程組轉(zhuǎn)換為單目標優(yōu)化問題，或多目標優(yōu)化問題。Qu等人[7]將鄰域技術(shù)分別與擁擠技術(shù)（NCDE）和物種形成技術(shù)（NSDE）相結(jié)合來提高算法性能。Gao等人[8]介紹了一種基于K-means聚類的選擇策略，通過聚類技術(shù)來解決多目標優(yōu)化問題。對于單目標優(yōu)化問題，Gong等人[9]提出一種基于排斥技術(shù)的自適應(yīng)差分進化算法（RADE）來求解非線性方程組，并通過鄰域突變和擁擠選擇保持種群多樣性進一步提高算法的搜索能力。Liao等人[10]提出一種基于動態(tài)排斥技術(shù)的進化算法，通過動態(tài)排斥技術(shù)控制排斥半徑，從而解決了排斥性半徑的最優(yōu)參數(shù)設(shè)置的難題。He等人[11]提出基于模糊鄰域的定向差分進化算法（FNODE）。在FNODE算法中，改進的模糊鄰域技術(shù)自適應(yīng)的選擇合適的個體形成鄰域，將鄰域中個體遷移的方向信息整合到突變策略中，推動后代個體向更好的地方遷移，提高了算法的探索和開發(fā)能力。

在FNODE算法中，通過均勻分布隨機生成初始種群化。為了進一步提高種群多樣性，利用Tent混沌映射初始化種群，充分利用混沌映射隨機性、遍歷性和規(guī)律性的特點來增強初始種群的多樣性，提高算法的尋優(yōu)速率和全局搜索能力。

將基于Tent混沌映射的FNODE算法，與FNODE、NCDE、NSDE和RADE這4個優(yōu)化算法來求解非線性方程組，在尋根率和成功率兩個方面對這5個算法進行對比。最后又討論了鄰域參數(shù)對基于Tent混沌映射的FNODE算法的影響。

2 預(yù)備知識

2.1 問題提出及轉(zhuǎn)化

一般的，非線性方程組（NESs）由m個方程組成，其中至少包含一個非線性方程。決策向量x=（x1，x2，…xn）T∈S是n維的，S是決策向量的搜索空間，NESs的表達式為，

利用優(yōu)化算法求解NESs，要將NESs轉(zhuǎn)換為單目標最小化問題，即

2.2 Tent混沌映射

在混沌機制中，Tent混沌映射[12，13]具有較高的隨機性和遍歷性，在[0，1]區(qū)間能夠生成分布均勻的序列。Tent混沌映射的結(jié)構(gòu)簡單，并且便利性好。

利用Tent混沌映射初始化種群，首先通過映射方程在[0，1]區(qū)間內(nèi)生成一個混沌序列，映射方程為

其中，Zij為混沌序列，i=1，2，…，NP代表種群規(guī)模，j=1，2，…，D表示種群變量的維數(shù)。接著將混沌序列中的點通過下式載波到各個分量的搜索空間中。

其中，[mini，maxi]是Xij的搜索區(qū)間。

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

基于Tent混沌初始化的FNODE算法，利用Tent混沌映射生成初始種群。充分利用混沌映射隨機性與遍歷性的特點，在搜索空間內(nèi)生成分布均勻的初始種群，以提高種群的多樣性和算法的尋優(yōu)速率。關(guān)于FNODE算法見參考文獻[11]，下面簡單介紹通過Tent混沌生成初始種群步驟。

首先，隨機生成一個分布在[0，1]區(qū)間內(nèi)的n維的初始向量Z（0）。利用映射方程公式（3）將初始向量通過迭代生成一個大小為NP的混沌序列Zij。接著通過公式（4）將混沌序列中的各個分量載波到對應(yīng)變量的搜索空間，即生成一個初始種群P，其中包含NP個個體：

3 實驗及結(jié)果分析

本文基于Intel（R） Core（TM） i5-8250U CPU @ 1.60GHz 1.80 GHz，8GB內(nèi)存，Windows 10操作系統(tǒng)和軟件MATLAB R2018b下對算法進行仿真實驗。

3.1 測試函數(shù)與評價指標

從文獻[14]中選擇了30個不同特征的非線性方程組作為測試函數(shù)，對這5個算法進行實驗。通過兩個常用的評價指標來比較不同算法的性能[15，16]。

（1）尋根率（root ratio， RR）：RR=，利用此指標來評價多次運行中找到NESs根的概率。

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

其中，Nr是獨立運行的次數(shù)，NOSi表示第i次運行中找到根的個數(shù)，NOS為方程組真實的根的個數(shù)，Nrs是成功運行的次數(shù)。

3.2 不同算法的比較分析

基于Tent映射初始化的FNODE算法與如下4個優(yōu)化算法進行對比：

（1）FNODE：在FNODE中，將改進的模糊鄰域和鄰域方向結(jié)合在一起，對算法的開發(fā)與勘探的平衡有很好的影響，提高了算法的搜索效率。通過與FNODE方法的比較，評價Tent混沌映射的效果。

（2）NCDE：在NCDE中，提出了一種鄰域突變策略，并將其與擁擠小生境差分進化算法相結(jié)合用于解決多模態(tài)優(yōu)化問題。

（3）NSDE：與（2）中NCDE算法相同，在NSDE中，利用的是物種形成小生境技術(shù)。與NCDE和NSDE相比，基于Tent映射的FNODE算法采用了擁擠選擇技術(shù)和相似的鄰域突變。

（4）RADE：在RADE中，DE算法采用自適應(yīng)參數(shù)控制技術(shù)以控制參數(shù)自動匹配到適當?shù)闹担瑥亩岣呓鉀Q不同NESs的搜索能力，利用鄰域突變和擁擠選擇來保持種群的多樣性。

在實驗中對RADE算法的參數(shù)設(shè)置為NP=100，Hm=200，其余4種算法的參數(shù)設(shè)置均為NP=100，F(xiàn)=0.5，CR=0.5，m=10。每個測試問題獨立運行50次。表1是5種算法在求解30個非線性方程組時所獲得的尋根率（RR）和成功率（SR）。

根據(jù)實驗結(jié)果，5個算法針對不同類型的測試函數(shù)可歸納得到如下結(jié)論：

（1） 在30個測試函數(shù)中，包含線性方程的高維NESs問題，即F19，Tent_FNODE算法能夠獲取最好的尋根率和成功率，與原始FNODE算法相比，有效提高了尋根率和成功率。對于不包含線新方程的高維NESs問題，即F01，Tent_FNODE方法的尋根率和成功率最優(yōu)，NSDE算法的效果不佳。

（2） 對于多根問題，如F02、F03、F12、F17和F23，從表中可以明顯看出Tent_FNODE算法的效最佳，而NSDE算法的結(jié)果最不理想。

由表中數(shù)據(jù)可以明顯看出，Tent_FNODE方法能夠獲得最優(yōu)的平均RR值和SR值，NSDE的效果相比之下較差。綜上分析，Tent_FNODE算法能夠有效提高算法的求根效率，在求解NESs問題上比其他4種算法的性能更具優(yōu)勢。

此外，表2和表3分別是Friedman和Wilcoxon檢驗的結(jié)果。從表2中可以看出，Tent_FNODE算法獲得了最佳的RR和SR排名，而NSDE算法獲得了最低排名。在Wilcoxon秩和檢驗中，將Tent_FNODE方法與其他4種算法相比。可以明顯看出Tent_FNODE的結(jié)果優(yōu)于其他4種方法，因為p-value小于0.05。并且R+值總是大于R-值，說明Tent_FNODE算法獲得了更好的RR和SR值。Tent_FNODE的顯著性優(yōu)勢從小到大排序依次是FNODE、NCDE、RADE和NSDE，進一步說明Tent_FNODE方法在搜索NESs根時的性能明顯優(yōu)于其他4種算法。

3.3 Tent_FNODE中不同參數(shù)設(shè)置的影響

在Tent_FNODE算法中形成模糊鄰域時，引入了鄰域邊界m參數(shù)。在算法比較實驗中，對鄰域邊界參數(shù)的設(shè)置為m=10。對于鄰域邊界m，通過對它賦以不同的值：7，8，9，10，11和12，討論了關(guān)于該參數(shù)的設(shè)置對算法性能的影響。在Tent_FNODE中的所有其他參數(shù)設(shè)置都不變。關(guān)于不同m值的平均尋根率和平均成功率結(jié)果如表4所示，表5和表6分別是對于不同參數(shù)設(shè)置的Friedman和Wilcoxon檢驗的結(jié)果。

由表4可以看出，m=10提供了最優(yōu)的尋根率和成功率。此外，當m取7，8，9，11和12時的結(jié)果差距不大。從表5中的Friedman檢驗的結(jié)果可以明顯看出，當模糊邊界參數(shù)m=10時，Tent_FNODE算法可以獲得最佳排名，并且參數(shù)在集合{7，8，9，10}中可以獲得較好的性能。通過表6中Wilcoxon檢驗的結(jié)果可以看出，p-value都大于0.05，說明參數(shù)設(shè)置為10與其他設(shè)置值比較相差不大，進一步說明參數(shù)m對Tent_FNODE算法的性能的影響不大。

4 結(jié)論

本文基于He等人提出的FNODE算法，將Tent混沌機制引入該算法中求解非線性方程組問題。將非線性方程組轉(zhuǎn)換為單目標最小值優(yōu)化問題，通過Tent混沌映射初始化種群，生成在搜索空間中分布均勻的初始種群，從而增強種群的多樣性，提高算法的尋優(yōu)速率。主要將基于Tent混沌映射的FNODE算法與原FNODE算法、NCDE、NSDE和RADE算法進行比較。選擇了30個具有不同特征的非線性方程組作為測試函數(shù)，進行了獨立運行50次的實驗，以尋根率和成功率作為評價指標對這5個算法進行比較。通過實驗結(jié)果表明，基于Tent混沌初始化的FNODE算法能夠有效提高算法的尋根率與成功率，并且比其他4個算法更具優(yōu)越性。最后，驗證了Tent_FNODE算法中鄰域邊界參數(shù)m對算法性能的影響，實驗結(jié)果表明參數(shù)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〕王開，龔文引.求解非線性方程組系統(tǒng)的改進差分進化算法[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-），女，廣西河池人，副教授，博士，主要從事偏微分方程數(shù)值解研究。

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