融合混沌對立和分組學(xué)習(xí)的海洋捕食者算法

馬 馳，曾國輝，黃 勃，劉 瑾

上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201600

隨著人工智能技術(shù)的發(fā)展，優(yōu)化求解問題越來越復(fù)雜，導(dǎo)致了相當(dāng)大的計算成本。傳統(tǒng)的牛頓法、梯度下降法等局部搜索方法效率低下，容易陷入局部最優(yōu)，已不能滿足實際需求[1-2]。元啟發(fā)式群智能優(yōu)化算法的核心思想主要源于動物行為或者物理現(xiàn)象，其核心環(huán)節(jié)是探索和開發(fā)，探索用于在解空間中尋找新的解，以獲得全局最優(yōu)值并避免陷入局部收斂。該算法根據(jù)全局最優(yōu)值進行局部搜索，得到最優(yōu)解，其簡單易行，對初始值不敏感，運行時間短，近年來得到了廣泛重視[3-4]。群智能算法能夠有效解決人工智能領(lǐng)域中許多復(fù)雜且具有挑戰(zhàn)性的優(yōu)化問題，主要應(yīng)用于組合優(yōu)化、特征選擇、圖像處理、生產(chǎn)制造與調(diào)度[5]等領(lǐng)域。近年來提出的元啟發(fā)式算法包括粒子群算法（particle swarm optimization，PSO）、灰狼優(yōu)化算法（gray wolf optimization，GWO）、飛蛾撲火算法（moth flame optimization，MFO）、鯨魚優(yōu)化算法（whale optimization algorithm，WOA）、蝴蝶優(yōu)化算法（butterfly optimization algorithm，BOA）、海洋捕食者算法（marine predator algorithm，MPA）、多元宇宙優(yōu)化算法（multi-verse optimizer，MVO）、原子搜索算法（atom search optimization，ASO）等。

MPA算法是2020年由Faramarzi等提出的模擬海洋捕獵行為的元啟發(fā)式算法，該算法的靈感來自于海洋捕食者和獵物的運動方式。其尋優(yōu)過程分為三個階段，捕食者和獵物在這三個階段中按照萊維運動或者布朗運動進行位置更新[6]。同時，獵物在被捕食的同時也充當(dāng)捕食者身份，使得算法更具有動態(tài)特性。且MPA算法獨有的海洋記憶存儲階段與海洋漩渦影響階段，可以進一步提高更新后的種群質(zhì)量，相對粒子群、差分進化等經(jīng)典算法以及上述多數(shù)算法，具有更快的收斂速度和收斂精度。

雖然基本MPA算法在優(yōu)化問題方面具有顯著的優(yōu)勢，但是仍然存在著群智能算法容易陷入局部最優(yōu)、收斂速度較慢的問題，仍需進行改進以提高其優(yōu)化性能。Elaziz等人提出了一種混合MPA和MFO的MPAMFO算法[7]，用MFO代替了MPA的局部搜索方法，提高了MPA的開發(fā)能力，但是收斂速度仍有待提高。Abdel等人提出了一種改進的MPA（improved marine predator algorithm，IMPA）[8]。該算法引入了基于排序的多樣性減少策略，以最佳個體位置直接替換適應(yīng)度持續(xù)不良的搜索個體的位置，提高了MPA的性能并加快了收斂，但是種群多樣性的減少，可能進一步增加陷入局部最優(yōu)的風(fēng)險，使算法的可靠性降低。Fan等人提出了基于新的位置更新規(guī)則、慣性權(quán)重系數(shù)和非線性步長控制參數(shù)策略的改進MPA（modified MPA，MMPA）[9]。MMPA表現(xiàn)出優(yōu)越的性能，在精度、收斂速度和穩(wěn)定性方面得到了有效的提升，但是改進的位置更新規(guī)則在捕食者和獵物的每個運動階段均需按照概率分成兩段，分段匹配正余弦函數(shù)，規(guī)則過于繁瑣。Elaziz等人提出了一種增強型MPA（enhanced marine predator algorithm，MPA）[10]，將差分進化算子（DE）引入MPA算法中，利用差分進化算子加強MPA的探索階段，以便于高效地發(fā)現(xiàn)搜索空間，降低陷入局部最優(yōu)的概率，算法結(jié)構(gòu)簡單，但是通過文中實驗測試對比可知，該EMPA算法對尋優(yōu)精度的提升十分有限。

為了更好地提升MPA算法尋優(yōu)精度和收斂速度，本文將混沌對立初始化與分組維度學(xué)習(xí)策略結(jié)合，同時引入t分布變異算子，提出了一種多策略改進的MPA算法（improved MPA for multi-strategy，MSIMPA），使算法同時獲得了尋優(yōu)精度和收斂速度上的顯著提升。

1 海洋捕食者算法

海洋捕食者算法（MPA）是一種模擬海洋獵物和捕食者在自然界中生物行為的元啟發(fā)式算法。獵物位置初始化在解決空間上均勻分布，適應(yīng)度最佳的作為頂級捕食者用于構(gòu)造精英矩陣，矩陣定義為：其中，每一行均為頂級捕食者的位置向量，n是種群數(shù)量，d是個體維度值。捕食者和獵物均被認為是搜索個體，因為每一個個體在捕食的時候，也同樣面臨著被捕食的可能。在每次迭代結(jié)束時，如果頂級捕食者被更好的捕食者取代，精英將被更新。

另一個是獵物矩陣，捕食者基于這個矩陣更新它們的位置。因此，初始化創(chuàng)建了最初的獵物，其中最合適的一個獵物（捕食者）構(gòu)建了精英。獵物矩陣如式（2）所示。

MPA通過三個階段模擬海洋捕食者及其獵物的生活，總結(jié)如下：

階段1獵物比捕食者移動得快或在高速比時(v≥10)。這個階段發(fā)生于迭代初期。捕食者的最佳策略是根本不移動，該階段數(shù)學(xué)模型表述如下：

其中，RB表示布朗運動隨機向量，P是等于0.5的常數(shù)，R表示[0，1]之間的隨機均勻分布值。Iter表示當(dāng)前迭代次數(shù)，MaxIter描述最大迭代數(shù)，RB與獵物的點乘模擬了獵物的運動。

階段2獵物和捕食者以相接近的速度或單位速度比移動(v=1)。該策略發(fā)生在迭代中期，種群被分為兩部分，一部分被指定用于探索，另一部分用于開發(fā)。這時，捕食者做布朗運動，獵物做萊維運動。該階段數(shù)學(xué)模型表述如下：

其中，RL表示萊維運動隨機向量，CF表示控制捕食者移動步長的自適應(yīng)參數(shù)。

階段3捕食者比獵物移動得快或在低速比時(v=0.1)。該階段發(fā)生在迭代時期，該階段主要與局部高開發(fā)能力相關(guān)，此時捕食者的最佳策略為萊維運動，該階段數(shù)學(xué)模型表述如下：

其中，RL與精英矩陣的點乘模擬了捕食者的萊維運動，并通過增加精英的步長，將捕食者的運動模擬為獵物位置的更新。

除了上述階段之外，渦流的形成和魚類聚集裝置（fish aggregating devices，F(xiàn)ADs）對捕食者也有影響，該階段數(shù)學(xué)模型表述如下：

其中，pf=0.2表示優(yōu)化過程中受FADs影響的概率，U是通過在[0，1]中生成一個隨機向量來構(gòu)造的，表示包含0和1的二進制向量數(shù)組。如果數(shù)組小于0.2，則將數(shù)組更改為0，如果大于0.2，則更改為1。r是[0，1]中的均勻隨機數(shù)，r1和r2下標表示獵物矩陣的隨機索引。MPA算法具有海洋記憶功能，其本質(zhì)類似于貪婪策略，在算法迭代開始和位置更新結(jié)束都需要進行適應(yīng)度對比，將更好的解替換先前的解。

2 改進海洋捕食者算法MSIMPA

2.1 加入混沌對立學(xué)習(xí)策略

2.1.1 Tent混沌映射

混沌映射是一種非線性理論，具有非線性、普適性、遍歷性和隨機性的特點，可以按自身的特性在一定范圍內(nèi)不重復(fù)地遍歷所有狀態(tài)，在智能算法優(yōu)化中能幫助生成新的解，增加種群多樣性，因而被廣泛應(yīng)用[11]。Tent映射迭代速度快，混沌序列在[0，1]之間均勻分布，其表達式如下：

其中，λt是第t次迭代時產(chǎn)生的混沌數(shù)，T是最大迭代次數(shù)，α是介于[0，1]的常數(shù)，本文選取α=0.7。

圖1為Tent映射迭代500次，劃分20個區(qū)間時的序列分布直方圖。由圖1可以看出，Tent映射在0～1之間均勻分布。

2.1.2 對立學(xué)習(xí)

在解決問題的時候，考慮到無效解決方案的對立側(cè)可能存在更好的解決方案，Tizhoosh提出了對立學(xué)習(xí)策略（opposition-based learning，OBL）[12]。近年來OBL已經(jīng)有效地應(yīng)用于各種群智能算法中。在群智能算法初始化種群的過程中，隨機生成的部分個體往往會分布在遠離最優(yōu)解的無效區(qū)域和邊緣區(qū)域，進而降低了種群的搜索效率。采用OBL策略，在種群初始化中引入一個隨機解及其對立解要比引入兩個獨立的隨機解更能提高初始種群的質(zhì)量。假設(shè)某個d維個體位置為：

設(shè)其個體位置的下界和上界分別為lb、ub，則其對立側(cè)位置可以表示為：

但是，在目標函數(shù)上下界限對稱的時候，由式（16）可看出，所生成的反向解為原來解的完全鏡像（取負），對部分具有偶函數(shù)特性的函數(shù)，完全鏡像解與原解目標值一致，不適合將兩個種群做適應(yīng)度排序，無法有效獲得高質(zhì)量種群。

2.1.3 混沌對立策略

本文將Tent混沌映射與OBL相結(jié)合，提出了一種新的TOBL（Tent and opposition-based learning）機制。TOBL的數(shù)學(xué)模型如下：

其中，為第i個獵物對立位置的第j維分量。

TOBL策略相當(dāng)于以目標函數(shù)上下界限的和為中心，利用Tent的均勻變化，來動態(tài)壓縮原初始種群的分布范圍，并在壓縮的同時盡量讓種群均勻。

圖2為不同策略下30個個體在[-20,20]的二維平面初始化分布圖，由圖2（a）、（b）可以看出，兩種方式的初始化分布呈現(xiàn)完全的中心對稱，這種鏡像現(xiàn)象會制約對立解的有效性。圖2（c）的TOBL初始化分布雖然不如圖2（a）中的個體分布均勻，但是兩種方式的初始化分布差異很大，更適合將兩者合并，然后按照適應(yīng)度將個體排序，擇優(yōu)選取與原來相同數(shù)量的個體，作為新的初始化種群，進而提高初始化種群的質(zhì)量。

假設(shè)海洋捕食者（獵物）種群數(shù)量為n，該策略的具體步驟為：首先通過隨機分布生成n個位置，再通過TOBL生成n個混沌對立位置，這些對立位置很有可能更加接近于目標獵物，最后將這2n個位置按照適應(yīng)度排序，取適應(yīng)度最佳的前n個獵物位置，作為初始化種群。

2.2 加入自適應(yīng)t分布

t分布又稱為學(xué)生分布[13]，它的分布函數(shù)曲線形狀與其自由度n密切相關(guān)。

圖3為自由度為5的t分布、標準正態(tài)分布和標準柯西分布的函數(shù)分布圖像對比。由圖3可知，t分布大致介于標準正態(tài)分布和標準柯西分布之間，其自由度n越小，曲線的雙尾就翹得越高，中間峰值越小，整體越加平滑。當(dāng)n=1時，t分布變?yōu)闃藴士挛鞣植?。反之，自由度n越大，中間峰值越大，整體越加陡峭。當(dāng)n趨于無窮時，t分布變?yōu)闃藴收龖B(tài)分布。

基本MPA中，獵物更新完位置以后，需要檢測和更新頂級捕食者的位置，并進行一次海洋記憶存儲，接下來再考慮FADs的影響，對獵物的位置做進一步更新。

為了保證此次記憶存儲更加有效，引入自適應(yīng)t分布算子，在模擬FADs的影響之前，對獵物的位置進行變異，如果變異后的位置更佳，則代替原來的位置。數(shù)學(xué)模型如下：

其中，Xi′為第i個獵物變異后的位置，t(Iter)為以當(dāng)前迭代次數(shù)為自由度的t分布。在迭代初期，迭代次數(shù)較少，t分布近似于柯西分布，分布得更加平滑。此時，t分布算子在大概率上取到較大值，位置變異所采取的步長較大，算法具有良好的全局探索能力，與MPA第一階段的全局搜索特性形成正反饋；在迭代中期，一半的捕食者用于全局探索，另一半的捕食者用于局部開發(fā)，而此時t分布介于柯西分布和正態(tài)分布之間，t分布算子在大概率上取值相對折中，同時兼顧了MPA第二階段的全局搜索和局部開發(fā)，使捕食者更容易返回到獵物豐富的地區(qū)并成功覓食，進而對算法性能形成正反饋；在迭代后期，t分布近似于標準正態(tài)分布，分布得更加集中，t分布算子在大概率上取較小值，致變異所采取的步長較小，兼顧了MPA第三階段的局部開發(fā)特性。

2.3 加入分組維度學(xué)習(xí)策略

在算法迭代過程中，有些獵物位置的某些維度實際上可能早已達到了最優(yōu)維度，由于其中個別維度的影響，使得這些獵物位置的適應(yīng)度變差[14]。為了能在海洋里生存下去，位置差的獵物（捕食者）需要向位置好的獵物（捕食者）學(xué)習(xí)捕食本領(lǐng)，基于這個思想，提出了一種分組維度學(xué)習(xí)的策略。將FADs影響后的獵物按照適應(yīng)度排序平均分成兩組，適應(yīng)度好的一組稱為精英組，適應(yīng)度差的一組稱為學(xué)習(xí)組[15]。

2.3.1 學(xué)習(xí)組維度交叉策略

因為精英組的維度各有優(yōu)劣，所以將精英組的位置維度取平均值，學(xué)習(xí)組的每一個獵物都向精英組平均維度進行學(xué)習(xí)。該策略將學(xué)習(xí)組每個獵物的每一維度同精英組平均維度值做差，按照絕對差異大的優(yōu)先交叉原則，取絕對差異大的前H1個對應(yīng)維度逐一交叉，如果交叉后獵物的適應(yīng)度更好，則交叉對應(yīng)維度，反之則不交叉。該策略的數(shù)學(xué)模型為：

其中，XL,i表示學(xué)習(xí)組第i個獵物位置，Xk,crossL,i表示與精英組平均維度值第k維交叉后的第i個獵物位置，ΔXkL,i表示學(xué)習(xí)組第i個獵物第k維和精英組平均維度第k維的絕對差異，XkJAVG表示精英組平均值的第k維。圖4為H1=2時學(xué)習(xí)組維度交叉示意圖。

以圖4學(xué)習(xí)組第2個個體為例，其第1維交叉以后適應(yīng)度更好，交叉成功。第3維交叉后適應(yīng)度變差，故交叉失敗。當(dāng)H1取值越大，所交叉的維度就越多，對學(xué)習(xí)組個體而言，會使得學(xué)習(xí)組的個體大程度上接近精英組平均值，減小了學(xué)習(xí)組個體之間的差異。此時，雖然種群平均適應(yīng)度減小，加快了收斂速度，但是個體差異性的減少會帶來陷入局部最優(yōu)的風(fēng)險，即使收斂精度相比原算法有提升，但仍有一定概率使改進算法尋優(yōu)精度降低。當(dāng)H1取值越小，交叉次數(shù)越少，相比于未交叉之前的個體差異微小。雖然個體多樣性得到保持，但是較少維度的交叉大大減弱了改進算法跳出局部最優(yōu)的能力，同樣有陷入局部最優(yōu)的風(fēng)險。而且交叉過少，個體之間得不到很好的學(xué)習(xí)，會降低收斂速度，因此，H1的選取要折中考慮。經(jīng)過大量仿真測試，選取個體維度一半左右進行交叉效率最高，本文實驗中，選取H1等于個體維度數(shù)的一半。

學(xué)習(xí)組向精英組平均值進行維度學(xué)習(xí)的過程中，質(zhì)量較差的學(xué)習(xí)組個體就不至于跨越太大的步長，以免越過全局最優(yōu)點及其鄰域。因此，學(xué)習(xí)組的平均維度學(xué)習(xí)會大大減少該部分個體向最優(yōu)值迭代的次數(shù)，提升了收斂速度。

2.3.2 精英組維度交叉策略

精英組整體離全局最優(yōu)點相對較近，因此不適合全部維度的擾動變異，這樣會導(dǎo)致精英在最優(yōu)解附近徘徊，影響收斂精度。令精英組的獵物相互之間取長補短，在保留自己優(yōu)勢維度的前提下，向相鄰的獵物進行學(xué)習(xí)。該策略交叉原則和學(xué)習(xí)組獵物交叉原則相同，只是將交叉對象，由精英組平均維度值更換為與該獵物相鄰的前一個獵物。設(shè)精英組每個獵物取絕對差異大的前H2個相鄰對應(yīng)維度逐一交叉，圖5為H2=4時精英組維度交叉示意圖。

以圖5精英組第3個個體為例，其第1、5維和倒數(shù)第2維交叉以后適應(yīng)度更好，交叉成功。第7維交叉后適應(yīng)度變差，故交叉失敗。有關(guān)H2的選取規(guī)則，同理于H1的選取規(guī)則。本文實驗中，選取H2等于個體維度數(shù)的一半。

該策略相當(dāng)于原來質(zhì)量較高的個體，僅朝著所交叉的維度方向步進，仍保留其他優(yōu)勢維度。相比于整個個體的變異，這種策略的擇優(yōu)性更強，可以有效增強算法維度的縱深挖掘性能，提高原算法的收斂精度。

2.4 MSIMPA算法實現(xiàn)步驟

步驟1由式（14）～（17）對獵物的位置進行混沌對立初始化，并設(shè)置種群規(guī)模、最大迭代次數(shù)、FADs等相關(guān)參數(shù)。

步驟2計算每個獵物適應(yīng)度值，并將適應(yīng)度值進行比較、替換，由最佳獵物構(gòu)成頂級捕食者矩陣，并進行海洋記憶存儲。

步驟3由式（3）～（11）更新獵物位置和移動步長。

步驟4由式（18）的t分布變異算子進行位置擾動更新，并保留最佳位置。

步驟5重新計算每個獵物適應(yīng)度值，并將適應(yīng)度值進行比較、替換，由最佳獵物構(gòu)成頂級捕食者矩陣，并進行海洋記憶存儲。

步驟6考慮FADs和漩渦的影響，由式（12）進一步更新位置，并保留最佳位置。

步驟7將更新后的種群按照適應(yīng)度優(yōu)劣均分成學(xué)習(xí)組和精英組，由式（19）～（20）進行維度交叉，交叉后適應(yīng)度變好則交叉對應(yīng)維度，反之則不交叉。

步驟8判斷算法是否滿足迭代條件，若滿足，則算法終止，否則轉(zhuǎn)至步驟2。

2.5 MSIMPA復(fù)雜度分析

算法的復(fù)雜度主要取決于算法語句的重復(fù)執(zhí)行次數(shù)，MPA中循環(huán)次數(shù)主要受最大迭代次數(shù)T、種群規(guī)模N和個體維度D的影響[16]。根據(jù)上節(jié)步驟分析MISMAP：步驟1混沌對立初始化種群數(shù)量翻倍，增加O(N×D)運算量，但復(fù)雜度仍為O(N×D)；步驟2和步驟5搜尋頂級捕食者以及海洋記憶存儲的復(fù)雜度為O(N×T)；步驟3位置更新復(fù)雜度為O(N×D×T)；步驟4對每個個體位置擾動，復(fù)雜度為O(N×T)；步驟6對整體位置統(tǒng)一增加一個步長，復(fù)雜度為O(T)；步驟7對每個個體的一半維度進行維度學(xué)習(xí)，復(fù)雜度為O(N×D×T)。綜上，略去低次項，原算法復(fù)雜度為O(N×D×T)，MSIMPA復(fù)雜度增加體現(xiàn)在步驟1、步驟4和步驟7，運算量雖然稍有增加，但是總體復(fù)雜度不變，不影響算法執(zhí)行效率。

2.6 MSIMPA收斂性分析

原始海洋捕食者算法按照迭代次數(shù)分為三個尋優(yōu)階段。階段2為階段1和階段3的整合，其局部開發(fā)遵循階段1的收斂性，全局搜索階段遵循階段3的收斂性，故無需對其單獨分析。文獻[17]中，算法的提出者已經(jīng)詳細證明了階段1和階段3的收斂性，下面僅給出結(jié)論。在階段1，原算法收斂性取決于φ1：

由上式可知，當(dāng)φ1＜1時，MPA在階段1收斂，否則發(fā)散。而階段1原本就是用來全局搜索，因此它按概率發(fā)散也無關(guān)緊要。

在階段3，MPA收斂，且收斂于頂級捕食者構(gòu)成的精英矩陣E，即全局最優(yōu)位置：

綜上，MPA在整個迭代過程中，最終是呈現(xiàn)出收斂的。在MSIMPA中，主要加入了三個策略。其中，混沌對立策略僅參與一次初始化種群，不參與算法的迭代過程，不對算法收斂性造成影響，無需單獨分析。自適應(yīng)t分布以及分組學(xué)習(xí)，本質(zhì)上都是引入隨機變異，來對原來的種群進行擾動，然后遵循貪心策略保留精英。

根據(jù)數(shù)列基本定理，有：

定理1單調(diào)不升且存在下界的數(shù)列{}fn必收斂于其極限inf{fn}，即inf{fn}。

文獻[17]對混合優(yōu)化算法的全局收斂性進行了詳細的分析，證明得出如下定理：

定理2如果某種算法同時具備以下兩個條件，則該算法最優(yōu)序列依概率1全局收斂。

條件1在迭代最優(yōu)解時，采用貪心策略保留精英，即：

其中，fBestk為比較k次后的最優(yōu)適應(yīng)度，X為第k+1次迭代后用來與fBestk比較的解。

條件2從任意一個非全局最優(yōu)點X′轉(zhuǎn)移到與之對應(yīng)的水平集L(Xr)={X|f(X)＜f(Xr),X∈S}的概率不為0，S表示整個搜索空間。

假設(shè)MSIMPA的目標函數(shù)f為求極小值，隨機采樣序列為，采樣點最優(yōu)序列為，全局最優(yōu)點為fBest。

證明MSIMPA不論原算法還是改進后的策略均遵循貪心策略，滿足定理2的條件1。

由定理1可知fkBest有極限，設(shè)nBest=inf{fBestk}≠fBest,則有fBestn＞fBest,且?k∈Z+,fBestk≥fBestn。因為原算法MPA最后收斂于頂級捕食者構(gòu)成的精英矩陣，所以當(dāng)X取值到精英周圍足夠小的鄰域時，必有P{L(X′)}=P{X|f(X)＜f(X′),X∈S}≠0（此處P{}·表示概率），故滿足條件2。

綜上，MSIMPA算法依概率1全局收斂，即P{Best}=1。其收斂速度受t分布隨機取值以及維度交叉有效性的影響，有效性越高收斂越快。

3 函數(shù)測試與數(shù)值分析

3.1 函數(shù)測試

為了檢驗本文提出的MSIMPA算法的有效性，選取了15個測試函數(shù)與MPA、MVO、PSO、MFO、WOA、GWO、ASO這7種算法進行求極小值仿真對比。測試函數(shù)中含有6個多維單峰函數(shù)F1～F6、6個多維多峰函數(shù)F7～F12和3個固定維度多峰函數(shù)，具體函數(shù)信息見表1。所有算法迭代次數(shù)均設(shè)置為500次，種群數(shù)量均為30個。多維測試函數(shù)維度為30、50維，固定維度函數(shù)F13為2維，F(xiàn)14、F15為4維。將8種算法分別獨立運行30次，分別計算30次運行的平均最佳適應(yīng)度值和最佳適應(yīng)度值的方差。優(yōu)先根據(jù)平均適應(yīng)度值（尋優(yōu)精度）對算法性能進行排序，如果平均適應(yīng)度相同，再根據(jù)方差和收斂速度排序。

表1測試函數(shù)Table 1 Test functions

本文繪制出50維時8種算法在5個單峰測試函數(shù)、5個多峰函測試數(shù)和2個固定維度測試函數(shù)下的迭代收斂曲線圖，見圖6。

如圖6所示，在求解F6、F8、F10、F11等函數(shù)時，MSIMPA的初始適應(yīng)度更佳，表明混沌對立初始化可以有效提高初始種群質(zhì)量。在求解多維函數(shù)F1、F2、F4、F7、F8和F10時都達到最優(yōu)，精度顯著提升。其中F11具有多個局部最優(yōu)峰值，且波谷內(nèi)較為平緩，大多數(shù)算法很難找到其全局最小值，MPA算法雖然相對于其他幾種算法有略微優(yōu)勢，但是尋優(yōu)精度不夠，可見原算法考慮FADs的位置擾動并不能滿足需求。而MSIMPA在迭代開始階段，t分布變異含有全局搜索成分，收斂曲線迅速下降，迭代到90次左右時，結(jié)合和分組維度學(xué)習(xí)的作用，迭代曲線迅速收斂。由F8可知，MPA和WOA雖然也達到理論最小值，但是收斂速度明顯不如MSIMPA。F14～F15是固定維度函數(shù)，最優(yōu)值非0，MSIMPA和MPA平均適應(yīng)度均為最佳，但收斂速度上MSIMPA更快。同樣，在F9上也能進一步明顯體現(xiàn)出MSIMPA尋優(yōu)精度高、收斂速度快的優(yōu)勢。

3.2 數(shù)據(jù)分析

表2為30維時F1～F12的最終測試結(jié)果，表3為50維時F1～F12和固定維度時F13～F15的最終測試結(jié)果。通過表2和表3數(shù)據(jù)分析可知，無論是30維還是50維的情況下，MSIMPA算法的方差和平均適應(yīng)度指標相較其他算法具有明顯優(yōu)勢。

表2 30維函數(shù)測試數(shù)據(jù)Table 2 Test data of 30 dimensional functions

表3 50維及固定維度函數(shù)測試數(shù)據(jù)Table 3 Test data of 50 dimensional functions

表3 （續(xù)）

維度由30維提升到50維時，其余7種算法整體尋優(yōu)性能均相對變差，而對于MSIMPA算法，維度變高以后，分組維度學(xué)習(xí)范圍也按比例變寬，在較大程度上可以減弱高維帶來的影響，在F1～F5、F7～F8和F10上依然可以達到理論極小值0，尋優(yōu)精度遠高于MPA。雖然在少數(shù)幾個函數(shù)上，升高到50維時的MSIMPA尋優(yōu)精度也有所降低，但仍然要優(yōu)于其他對比算法。標準差體現(xiàn)出算法在求解中的穩(wěn)定性，算法GWO、ASO隨著求解維度的增高，標準差明顯增加，說明這兩個算法求解高維度問題時穩(wěn)定性較差。而MISCSA算法標準差相較于MPA、PSO、WOA等都低，說明算法的穩(wěn)定性更好。

在30維和50維情況下，各算法排名差異不大，保持在前列的為MSIMPA、MPA、GWO，性能較差的為MVO、MFO。為了更直觀地分析各算法的尋優(yōu)能力，繪制出圖7的排序雷達圖，算法性能曲線越靠近中間，則性能越優(yōu)越。

由圖7可知，忽略MSIMPA算法，MPA算法在F1、F2、F5、F7、F9、F12、F13上分別被不同的算法超越，排名在2～4之間，可見原MPA算法雖然性能較佳，但仍存在一定的不足，而MSIMPA算法在15個測試函數(shù)中性能均為最佳。值得一提的是MVO在F13上表現(xiàn)出色，尋到了理論最優(yōu)值，且收斂速度排在了第2位，方差排在第3位。

3.3 統(tǒng)計檢驗

Derrac等人在文獻[18]中指出，僅依靠平均值和標準差來比較算法的差異不夠嚴謹。獨立運行得到的平均適應(yīng)度值和標準差，仍有一定概率出現(xiàn)較好的數(shù)據(jù)，從而影響算法之間的性能比較。想要對改進算法性能做評估，需要在統(tǒng)計學(xué)層面上來判斷不同算法整體指標的顯著性區(qū)別。因此，將8種算法分別在15個測試函數(shù)上獨立測試30次的結(jié)果作為樣本，在0.05的顯著性水平下分別對30維和50維以及固定維度函數(shù)的測試結(jié)果進行Wilcoxon統(tǒng)計檢驗，判斷7個對比算法的結(jié)果與MSIMPA的結(jié)果的顯著性區(qū)別。檢驗結(jié)果見表4和表5。

根據(jù)文獻[18]，當(dāng)P＜0.05時可以被認為是拒絕零假設(shè)的有力驗證，說明所對比的兩種算法具有顯著性差異，P＞0.05則說明兩種算法的尋優(yōu)結(jié)果在整體上是相同的。根據(jù)表4和表5中的結(jié)果，因為MPA求解函數(shù)F8、F10以及WOA求解函數(shù)F8，均與MSIMPA同時搜索到全局最小值0，所以該統(tǒng)計檢驗不適用，記為“NaN”。其中，50維情況下，MSIMPA與WOA只有在求解F10時可以認為無明顯差異，求解其余測試函數(shù)時均與其余所有對比算法有顯著區(qū)別。30維情況下，MSIMPA的P全部小于0.05，表明了算法的優(yōu)越性在統(tǒng)計上是顯著的。

表4 30維時Wilcoxon統(tǒng)計檢驗結(jié)果Table 4 Wilcoxon statistical test results in 30 dimensions

表5 50維及固定維度時Wilcoxon統(tǒng)計檢驗結(jié)果Table 5 Wilcoxon statistical test results of 50 dimensions and fixed dimensions

4 MSIMPA優(yōu)化無線傳感器網(wǎng)絡(luò)覆蓋

假設(shè)在邊長分別為L1和L2的矩形無線傳感器WSN檢測范圍內(nèi)，隨機分布N個同構(gòu)傳感器的節(jié)點，假設(shè)節(jié)點Zi的位置坐標為，每個節(jié)點的感知范圍是以該節(jié)點為中心，Rs為半徑的圓形區(qū)域，則將該圓形區(qū)域稱感知圓盤，Rs稱為感知半徑。為了便于建模計算，將感知圓盤離散為m×n個待覆蓋的目標點，目標點Cj的位置坐標為( )xj,yj，則目標點和傳感器節(jié)點的距離定義為：

若存在某個節(jié)點與目標點的距離小于或等于感知半徑Rs，則代表目標點已被傳感網(wǎng)絡(luò)覆蓋。基于0/1模型，將目標點被傳感器節(jié)點Zi感知的概率定義為[19]：

其中，Re為節(jié)點感知誤差；λ為感知衰減系數(shù)。當(dāng)目標點被多個傳感器感知，則目標點的聯(lián)合檢測概率為：

該區(qū)域的覆蓋率為全部節(jié)點所覆蓋的目標點總數(shù)與區(qū)域內(nèi)目標點總數(shù)的比值，定義為：

通過函數(shù)測試對比，MSIMPA和MPA算法的綜合能力領(lǐng)先于其他對比算法，且考慮到本文主要測試MPA算法的改進性能，故本文的WSN覆蓋優(yōu)化只選擇MSIMPA和MPA算法進行對比。具體的實施步驟與第2.4節(jié)算法實施步驟基本相似，將覆蓋區(qū)域邊界長度設(shè)置為第2.4節(jié)算法中的尋優(yōu)邊界，設(shè)種群中的個體維度為2N,則種群中的每個個體位置構(gòu)成N個二維平面坐標，代表N個傳感器節(jié)點。算法邏輯上為搜尋最小值，欲求最大覆蓋率，將式（28）改為：

選取式（29）作為適應(yīng)度函數(shù)，捕食者在搜尋獵物的時候不斷更新自己的位置，并在位置更新以后采用分組維度學(xué)習(xí)的方式對位置維度取長補短，可以較大程度上提升最優(yōu)個體的位置精度。算法迭代結(jié)束后，得到式（29）的最小值，即可反向求出傳感器節(jié)點的最大覆蓋率。實驗參數(shù)設(shè)置如表6。

表6 參數(shù)設(shè)置Table 6 Parameter setting

當(dāng)傳感器節(jié)點為30個時，MSIMPA和MPA的初始化覆蓋情況如圖8，紅點代表節(jié)點，圓圈代表感知圓盤。MPA采用隨機分布初始化，初始覆蓋率為53.92%，而MSIMPA算法采用混沌對立初始化，初始覆蓋率為65.23%，提高了約11個百分點，反映出混沌對立初始化的種群質(zhì)量更高。

算法優(yōu)化后的傳感器區(qū)域覆蓋結(jié)果如圖9所示。圖9（a）、（b）為30個節(jié)點時的覆蓋情況，MPA算法優(yōu)化的覆蓋率為81.15%，MSIMPA算法優(yōu)化的覆蓋率為87.03%。從圖9（a）中可以清楚地看到，MPA優(yōu)化時覆蓋區(qū)域的邊緣和中心部位都有明顯的空缺，各個節(jié)點感知范圍重疊較為密集，圖9（b）中MSIMPA優(yōu)化覆蓋的區(qū)域則更加均勻。圖9（c）、（d）為40個節(jié)點時傳感器區(qū)域的覆蓋情況，此時圖9（c）中MPA優(yōu)化后的覆蓋率為90.61%，原點附近仍有較大盲區(qū)且重疊部分略多，圖9（d）中MSIMPA優(yōu)化后的覆蓋率為96.55%，重疊部分有所改善且無明顯盲區(qū)。

為了使實驗更加準確，算法分別獨立運行30次，平均覆蓋率見表7。通過表7可知，MSIMPA的覆蓋率和初始覆蓋率都高于MPA。

表7 平均覆蓋率Table 7 Average coverage 單位：%

迭代曲線如圖10所示。圖10（a）中30個節(jié)點時，MSIMPA由于初始化質(zhì)量更高，迭代曲線起點高且迅速上升，在120代時趨于穩(wěn)定，MPA迭代曲線還處于上升階段，此時覆蓋率相差最大。在迭代到400代時，MSIMPA優(yōu)化精度略微提高后再次穩(wěn)定，這時處于迭代后期，t分布變異著重于局部開發(fā)，配合個體之間的維度學(xué)習(xí)，使得尋優(yōu)精度進一步提高。40個節(jié)點時，相當(dāng)于個體維度增加，MSIMPA的分組維度學(xué)習(xí)策略依然有效，無論是收斂速度還是覆蓋范圍，均明顯高于MPA算法的優(yōu)化效果。

綜上所述，通過與不同節(jié)點在同等測試條件下的實驗結(jié)果對比，MSIMPA算法實現(xiàn)了更高的平均覆蓋率，節(jié)點分布更加均勻，覆蓋盲區(qū)和感知范圍重疊區(qū)面積更少，驗證了所提出改進策略的有效性。

5 結(jié)束語

為了進一步改進海洋捕食者算法的尋優(yōu)性能，本文提出了MSIMPA算法。首先，在MPA算法中加入了混沌對立初始化，提高了初始種群質(zhì)量。其次，加入了自適應(yīng)t分布變異算子，增加算法逃逸出局部最優(yōu)的能力。最后，對位置更新完畢的種群進行分組維度學(xué)習(xí)，增加算法的收斂速度和精度。將MSIMPA與其他7種算法在15個測試函數(shù)上測試對比，MSIMPA在求解高維單峰和多峰函數(shù)以及固定維度函數(shù)時，求解精度與收斂速度均有明顯優(yōu)勢。并將MSIMPA在WSN覆蓋優(yōu)化問題上與MPA算法進行對比，實驗結(jié)果進一步驗證了所提出改進策略的有效性。