基于模糊鄰域差分進化算法求解非線性方程組

陳馨 韋慧

摘 ?要：討論模糊鄰域概率函數選擇策略對算法尋根率和成功率的影響.實驗結果表明，凸函數類型的概率選擇函數較適用于求解多根和搜索空間較廣問題，定值概率選擇函數較適合于求解含有大量線性方程的問題.選用適當概率選擇函數可以提高模糊鄰域差分進化算法尋根率和成功率.

關鍵詞：差分進化算法；非線性方程組；模糊鄰域；概率選擇函數

[ ? 中圖分類號 ? ?]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.

編輯：琳莉