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

李偵璦　韋慧

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

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

中圖分類號：O24；TP183? 文獻(xiàn)標(biāo)識碼：A? 文章編號：1673-260X（2023）03-0024-05

1 引言

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

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

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

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

2 預(yù)備知識

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

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

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

2.2 Tent混沌映射

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

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

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

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

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

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

首先，隨機(jī)生成一個分布在[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下對算法進(jìn)行仿真實驗。

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

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

（1）尋根率（root ratio， RR）：RR=，利用此指標(biāo)來評價多次運(yùn)行中找到NESs根的概率。

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

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

3.2 不同算法的比較分析

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

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

（2）NCDE：在NCDE中，提出了一種鄰域突變策略，并將其與擁擠小生境差分進(jìn)化算法相結(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ù)自動匹配到適當(dāng)?shù)闹?，從而提高解決不同NESs的搜索能力，利用鄰域突變和擁擠選擇來保持種群的多樣性。

在實驗中對RADE算法的參數(shù)設(shè)置為NP=100，Hm=200，其余4種算法的參數(shù)設(shè)置均為NP=100，F(xiàn)=0.5，CR=0.5，m=10。每個測試問題獨(dú)立運(yùn)行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，進(jìn)一步說明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)的尋根率和成功率。此外，當(dāng)m取7，8，9，11和12時的結(jié)果差距不大。從表5中的Friedman檢驗的結(jié)果可以明顯看出，當(dāng)模糊邊界參數(shù)m=10時，Tent_FNODE算法可以獲得最佳排名，并且參數(shù)在集合{7，8，9，10}中可以獲得較好的性能。通過表6中Wilcoxon檢驗的結(jié)果可以看出，p-value都大于0.05，說明參數(shù)設(shè)置為10與其他設(shè)置值比較相差不大，進(jìn)一步說明參數(shù)m對Tent_FNODE算法的性能的影響不大。

4 結(jié)論

本文基于He等人提出的FNODE算法，將Tent混沌機(jī)制引入該算法中求解非線性方程組問題。將非線性方程組轉(zhuǎn)換為單目標(biāo)最小值優(yōu)化問題，通過Tent混沌映射初始化種群，生成在搜索空間中分布均勻的初始種群，從而增強(qiáng)種群的多樣性，提高算法的尋優(yōu)速率。主要將基于Tent混沌映射的FNODE算法與原FNODE算法、NCDE、NSDE和RADE算法進(jìn)行比較。選擇了30個具有不同特征的非線性方程組作為測試函數(shù)，進(jìn)行了獨(dú)立運(yùn)行50次的實驗，以尋根率和成功率作為評價指標(biāo)對這5個算法進(jìn)行比較。通過實驗結(jié)果表明，基于Tent混沌初始化的FNODE算法能夠有效提高算法的尋根率與成功率，并且比其他4個算法更具優(yōu)越性。最后，驗證了Tent_FNODE算法中鄰域邊界參數(shù)m對算法性能的影響，實驗結(jié)果表明參數(shù)m對算法的影響不大。

——————————

參考文獻(xiàn)：

〔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ìn)差分進(jìn)化算法[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ù)值解研究。

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