基于種群活躍與混沌變螺旋策略變色龍群算法及應(yīng)用*

王 義張達(dá)敏*張琳娜趙沛雯

(1.貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽(yáng) 550025；2.貴州大學(xué)機(jī)械工程學(xué)院，貴州 貴陽(yáng) 550025)

隨著信息社會(huì)的進(jìn)一步發(fā)展，各類科學(xué)計(jì)算和應(yīng)用問(wèn)題的計(jì)算規(guī)模不斷增長(zhǎng)，傳統(tǒng)數(shù)值優(yōu)化計(jì)算方法的缺陷逐漸暴露，難以在較短時(shí)間內(nèi)滿足各類優(yōu)化求解需求[1]。針對(duì)各類問(wèn)題的求解，現(xiàn)已有大量研究者展開(kāi)深度研究，如基于啟發(fā)式算法、博弈論以及梯度下降機(jī)制的算法。元啟發(fā)算法為啟發(fā)式算法的分支，是基于社會(huì)群體仿生學(xué)的智能算法，因算法時(shí)間復(fù)雜度低、求解高效和機(jī)制靈活等優(yōu)點(diǎn)得到多學(xué)科研究者的關(guān)注。仿生學(xué)的主要算法有基于生物進(jìn)化啟發(fā)而提出的遺傳算法(Genetic Algorithm，GA)[2]、基于自然界中鳥類覓食行為的粒子群算法(Particle Swarm Algorithm，PSO)[3]、基于樽海鞘鏈的領(lǐng)導(dǎo)者和追隨者共同覓食的樽海鞘群算法(Salps Swarm Algorithm，SSA)[4]以及受狼群的領(lǐng)導(dǎo)、狩獵行為啟發(fā)的灰狼優(yōu)化算法(Grey Wolf Optimizer，GWO)[5]等等。基于社會(huì)群體智能算法的提出，為各類復(fù)雜問(wèn)題、大規(guī)模優(yōu)化問(wèn)題和NP難題的求解提供了新思路。

2021年Malik等[6]在沙漠中觀測(cè)變色龍群體尋食過(guò)程，受啟發(fā)提出變色龍群算法(Chameleon Swarm Algorithm，CSA)。變色龍是一種獨(dú)特、高度專業(yè)化的進(jìn)化分支，物種廣泛，因其改變顏色易融入周圍環(huán)境。變色龍有著極好的視力，其眼睛能進(jìn)行360°獨(dú)立旋轉(zhuǎn)；捕食過(guò)程中憑借粘著的舌頭追逐食物形成小吸盤，能以2 590 m/s的速度進(jìn)行捕捉?；綜SA中，尋食主要分三個(gè)階段:獵物搜索、變色龍眼睛轉(zhuǎn)動(dòng)發(fā)現(xiàn)獵物和跟蹤攻擊。而CSA算法與其他生物行為算法的主要不同點(diǎn)的是，變色龍的眼睛能進(jìn)行360°旋轉(zhuǎn)，發(fā)現(xiàn)獵物的概率增加，并能使用高速發(fā)射的粘性舌頭捕捉獵物，獵物捕捉效率非常高，從而求解效果較好。

CSA算法與其他仿生形式的元啟發(fā)算法一樣，因算法自身特點(diǎn)容易存在陷入局部最優(yōu)、收斂速度慢等缺點(diǎn)。對(duì)此，國(guó)內(nèi)外學(xué)者也對(duì)群體智能算法的自身缺點(diǎn)展開(kāi)深入研究。如Qais M H等[7]在樽海鞘群算法的領(lǐng)導(dǎo)者位置更新方式上引入平方指數(shù)，進(jìn)而提高算法的收斂速度和精度；陳忠云等[8]對(duì)樽海鞘群算法進(jìn)行改進(jìn)，將樽海鞘鏈看成三個(gè)子群，對(duì)子群引入鏈前參數(shù)性能影響分析、鏈中共生時(shí)變策略和鏈尾非均勻高斯變異策略，使該算法的精度和穩(wěn)定性得以較好改善，全局搜索和開(kāi)發(fā)能力之間得到平衡。茍平章等[9]對(duì)螢火蟲算法進(jìn)行改進(jìn)，并將改進(jìn)螢火蟲算法應(yīng)用到傳感網(wǎng)絡(luò)的覆蓋優(yōu)化，實(shí)驗(yàn)表明覆蓋率得以更好提升；龍文等[10]針對(duì)灰狼優(yōu)化算法的缺陷，提出個(gè)體記憶功能指引策略更新位置，以對(duì)歷史最優(yōu)解進(jìn)行保存的思想淘汰其他適應(yīng)度較低的解，提高算法收斂速度；孫麗君等[11]針對(duì)灰狼算法全局收斂精度低的缺陷，首次使用鞅論方法證明收斂性能低下的原因，引入有效改進(jìn)策略提高算法全局收斂性能，進(jìn)行收斂性分析。

前人的工作對(duì)智能算法的缺陷已有深入研究，不同程度地提升了算法的收斂能力。本文對(duì)CSA缺陷進(jìn)行改進(jìn)，進(jìn)一步提升CSA尋優(yōu)能力和求解無(wú)源時(shí)差定位(TDOA)問(wèn)題的求解效率。對(duì)此，做了以下工作以提升CSA的搜索性能:①在初始化階段引入偶對(duì)稱無(wú)限折疊偽隨機(jī)數(shù)初始化種群，使空間位置分布更均勻，提高種群多樣性；②在眼睛轉(zhuǎn)動(dòng)發(fā)現(xiàn)食物階段，利用WOA(Whale Optimization Algorithm)[12]變螺旋搜索指引，提升算法搜索能力；③在變螺旋指引機(jī)制上，引入動(dòng)態(tài)自適應(yīng)慣性權(quán)重，使算法繼承上一位置信息按照動(dòng)態(tài)慣性權(quán)重表達(dá)式更新，平衡慣性部分和社會(huì)部分的比重；④迭代后期，利用黎曼流形學(xué)習(xí)策略提升算法后期的活躍性，增強(qiáng)全局搜索到最優(yōu)位置的概率。⑤將改進(jìn)的ICSA算法應(yīng)用到TDOA問(wèn)題，進(jìn)行優(yōu)化特性對(duì)比，設(shè)計(jì)兩組實(shí)驗(yàn)，從收斂曲線和Monte-Carlo仿真實(shí)驗(yàn)，驗(yàn)證在TDOA的求解效率。

1 變色龍群算法

1.1 獵物搜索

變色龍類似于自然界的其他生物，在漫游的獵物搜尋中不斷改變自身位置，通過(guò)先前位置和社會(huì)經(jīng)驗(yàn)的指引跟蹤從而發(fā)現(xiàn)獵物。變色龍?jiān)谝捠尺^(guò)程中的運(yùn)動(dòng)行為可以通過(guò)位置更新策略進(jìn)行數(shù)學(xué)描述，表示如下:

式中:為變色龍i在j維空間中，第t次迭代的位置，P p為感知獵物的概率。p1、p2為用于控制算法開(kāi)發(fā)能力的正系數(shù)，為變色龍i在j維空間經(jīng)t次迭代的最佳位置，r1，r2，r3，r分別為(0，1)之間的隨機(jī)數(shù)。sgn(rand-0.5)代表旋轉(zhuǎn)，表征變色龍的旋轉(zhuǎn)方向，取值為＋1或-1。若r≥Pp，變色龍可以根據(jù)在搜索空間中觀察到的獵物來(lái)改變自己的位置；同理，當(dāng)r＜P p變色龍?jiān)趯ふ耀C物時(shí)，會(huì)在不同方向和區(qū)域隨機(jī)探索搜索空間，這使它們有很大可能感知到附近的目標(biāo)獵物。參數(shù)μ為由t控制的搜索能力參數(shù)，其表達(dá)式為:

原始文獻(xiàn)[6]對(duì)算法進(jìn)行參數(shù)敏感性分析，證實(shí)當(dāng)k＝3.5時(shí)具有較好的搜索性能。T為最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)。

1.2 眼睛轉(zhuǎn)動(dòng)發(fā)現(xiàn)獵物

變色龍相較于其他生物最好的優(yōu)勢(shì)是能通過(guò)眼睛獨(dú)立360°旋轉(zhuǎn)發(fā)現(xiàn)獵物的具體位置，這一過(guò)程可描述為:①找到變色龍的位置重心；②確定獵物位置的旋轉(zhuǎn)矩陣；③根據(jù)重心更新變色龍的位置；④變色龍回到原來(lái)的位置?？杀硎緸?

式(3)中:ˉx i t為t次迭代的重心位置，是經(jīng)變換后的變色龍位置。m是θ和V z1，z2變換的旋轉(zhuǎn)矩陣，表征變色龍眼睛的旋轉(zhuǎn)。式(4)中z1，z2是d維搜索空間的兩個(gè)正交向量，V z1，z2表示經(jīng)z1，z2相互正交后的向量。式(6)中θ表示變色龍的隨機(jī)旋轉(zhuǎn)角度。r為(0，1)隨機(jī)數(shù)，控制旋轉(zhuǎn)角度從0到π幅度使它隨機(jī)旋轉(zhuǎn)。

1.3 獵物捕捉

變色龍捕食主要通過(guò)彈射粘著的舌頭來(lái)捕捉獵物，一旦舌頭接觸到獵物，就會(huì)快速把舌頭粘在獵物身上形成小吸盤。這一過(guò)程的速度更新與粒子群算法(PSO)[3]類似，表達(dá)式為:

表示經(jīng)t＋1迭代后更新的速度。是第t次迭代的速度。第t次迭代的位置。是全局最優(yōu)位置，為局部最優(yōu)位置，r1和r2為(0，1)之間的隨機(jī)數(shù)，c1和c2為和的控制因子。

表 示 當(dāng) 前 的 速 度，為 上 一 次 迭 代 的 速度為當(dāng)前的變色龍位置。a表示加速度，根據(jù)運(yùn)動(dòng)學(xué)中推導(dǎo)出加速度a的表達(dá)式如下:

t為當(dāng)前迭代次數(shù)，加速度隨t變化而非線性變化。

2 自適應(yīng)螺旋指引與黎曼流形變色龍群算法

2.1 偶對(duì)稱無(wú)限折疊序列初始化

CSA初始化中由于沒(méi)有任何先驗(yàn)的搜索方式和信息協(xié)作交流，初始位置為隨機(jī)生成，種群的多樣性較差?；煦绯跏蓟夹g(shù)是一種簡(jiǎn)單確定性系統(tǒng)產(chǎn)生的偽隨機(jī)數(shù)，具備良好的遍歷性、規(guī)律性[13]，可以將初始種群均勻分布在可行解空間，與隨機(jī)初始化相比更具備更好優(yōu)勢(shì)。常用的映射主要有Tent映射[14]、高斯映射[15]、Logistic映射[16]等，但這類映射在有限區(qū)間內(nèi)的折疊有限，相空間結(jié)構(gòu)較為簡(jiǎn)單，使映射的隨機(jī)性和遍歷性不強(qiáng)。由此，提出一種偶對(duì)稱的無(wú)限折疊混沌映射[17]初始化種群。偶對(duì)稱無(wú)限折疊思想:將可行解區(qū)域通過(guò)對(duì)稱關(guān)系，無(wú)限迭代，在有限區(qū)間內(nèi)無(wú)限折疊映射，因此相空間結(jié)構(gòu)趨近于白噪聲模型。因此在[0，1]之間的混沌序列通過(guò)逆映射轉(zhuǎn)化到變色龍個(gè)體的搜索空間，使初始種群在可行空間范圍內(nèi)更好地遍歷，其數(shù)學(xué)模型為:

式中:為第i個(gè)變色龍個(gè)體的第j維空間產(chǎn)生的混沌序列；α∈[1，∞]，β∈(0，1)為混沌參數(shù)；i＝1，2，…，N代表種群規(guī)模大小，j＝1，2，…，d為變量空間維度，為映射序號(hào)。mod(·，β)為模β的函數(shù)。圖1為種群大小為40的群體分布圖，圖1(a)為隨機(jī)初始化種群，圖1(b)為偽隨機(jī)數(shù)初始化種群，取α＝1，β＝1。

圖1 兩種初始化種群分布圖

由圖1可看出，利用偶對(duì)稱無(wú)限折疊映射產(chǎn)生的偽隨機(jī)數(shù)雖然隨機(jī)性不強(qiáng)，但不會(huì)產(chǎn)生非常接近、重疊等現(xiàn)象，空間遍歷和分布均勻性得以提高，算法初始階段多樣性更好。將產(chǎn)生偽隨機(jī)數(shù)逆映射到種群個(gè)體的空間得到初始位置變量，其位置表達(dá)式如下:

式中:lbi和ubi分別表示種群區(qū)域的上邊界和下邊界。

2.2 自適應(yīng)螺旋式位置指引機(jī)制

由式(3)可看出，變色龍的位置更新需要借助中心位置和當(dāng)前位置，并根據(jù)旋轉(zhuǎn)矩陣改變搜索方向、四周搜尋向中心位置靠近，達(dá)到增強(qiáng)種群多樣性的效果，增加變色龍的全局搜索能力；這一過(guò)程雖然具備指引作用，但比較盲目、隨機(jī)性較強(qiáng)。前期，個(gè)體位置離中心位置較遠(yuǎn)，導(dǎo)致算法搜索處于盲目，指引機(jī)制失效。因此，這一過(guò)程難以具備理想搜索效果。借鑒鯨魚優(yōu)化算法[12]的螺旋式搜索指引，改善全局搜索能力。鯨魚優(yōu)化的螺旋指引策略位置更新機(jī)制為:

式中:為經(jīng)螺旋式指引更新后的位置，x為第t次迭代中心位置，b為決定螺旋形狀的常數(shù)，取b＝1。l、r為[-1，1]間的隨機(jī)數(shù)，D′為中心位置與實(shí)際位置的隨機(jī)距離，隨算法的迭代漸漸減小。

將螺旋式指引策略引入到變色龍眼睛轉(zhuǎn)動(dòng)過(guò)程中，算法在搜索過(guò)程中對(duì)中心位置的依賴較大，算法的全局搜索和開(kāi)發(fā)能力難以平衡[18]。因此引入自適應(yīng)動(dòng)態(tài)慣性權(quán)重對(duì)螺旋式指引策略搜索進(jìn)行自適應(yīng)調(diào)整，使前期具備較好得全局搜索能力，后期具有較好的局部搜索能力。引入自適應(yīng)動(dòng)態(tài)慣性權(quán)重的位置更新如下:

式(12)中:Tmax為最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)，λ和μ為權(quán)重動(dòng)態(tài)變化因子，為保證動(dòng)態(tài)自適應(yīng)的搜索特征，λ、μ的取值見(jiàn)表1。圖2為自適應(yīng)動(dòng)態(tài)權(quán)重ω隨迭代次數(shù)t的變化圖。

圖2 自適應(yīng)動(dòng)態(tài)權(quán)重曲線

引入自適應(yīng)的螺旋式位置指引策略主要有以下特點(diǎn):①迭代前期，中心位置與實(shí)際位置的距離較遠(yuǎn)，與獵物目標(biāo)位置差異較大，算法仍處于隨機(jī)搜索，易陷入局部最優(yōu)。引入變螺旋式搜索，縮小范圍，通過(guò)引入螺旋式行進(jìn)包圍獵物，降低搜索盲目性，提升收斂能力；②ω的引入是為了在前期搜索中借鑒先驗(yàn)搜索位置的能力，快速定位局部范圍；后期，為了更好地在局部位置自由探索，削減先驗(yàn)位置帶來(lái)的影響，增強(qiáng)群體的信息交流合作能力，找到最優(yōu)解，提升全局搜索性能；

2.3 黎曼流形種群活躍度策略

在CSA迭代后期，所有變色龍種群會(huì)聚集在局部范圍區(qū)域，導(dǎo)致后期種群相似度極高，種群的活躍度和多樣性缺失，造成易陷入局部最優(yōu)的困境。Lin等[19]在2008年基于高維樣本的本征維度呈黎曼流形分布提出黎曼流量子學(xué)習(xí)策略，即黎曼流形中量子具備強(qiáng)烈的活躍度。在CSA中的獵物捕捉階段，由于變色龍捕捉獵物時(shí)，種群速度總會(huì)在一個(gè)可行范圍，導(dǎo)致算法不能完全收斂到全局范圍的最優(yōu)解，且種群相似度高和多樣性缺失，利用黎曼流形學(xué)習(xí)在這一階段中提升種群活躍度，以更高概率收斂到全局最優(yōu)。利用黎曼流形進(jìn)行位置更新方式如下:

式中:為經(jīng)黎曼流形學(xué)習(xí)變換后的位置，u和r為(0，1)區(qū)間的均勻隨機(jī)數(shù)，符號(hào)函數(shù)sign(·)用于控制算法的搜索方向。ν為收-縮膨脹系數(shù)，為變色龍t次迭代在第j維空間上的位置中心，X(t)為全局最優(yōu)和局部最優(yōu)相互作用調(diào)節(jié)的位置。ν、和X(t)的表達(dá)式分別如下:

式(15)中:r為隨機(jī)數(shù)，g t為t次迭代的全局最優(yōu)位置，p t i為局部最優(yōu)位置。式(16)中，收縮膨脹系數(shù)與t和最大迭代次數(shù)Tmax有關(guān)，用于控制活躍度提升的程度，在后期t增大，活躍程度提高。式(17)中N為種群大小，用于計(jì)算每維空間的中心位置。

2.4 算法流程圖及時(shí)間復(fù)雜度分析

2.4.1 ICSA算法流程圖

結(jié)合CSA算法，引入三種策略對(duì)算法進(jìn)行改進(jìn)，ICSA執(zhí)行流程如圖3所示。

圖3 融合改進(jìn)變色龍群算法流程框圖

2.4.2 算法時(shí)間復(fù)雜度分析

時(shí)間復(fù)雜度是衡量算法的主要關(guān)鍵性能之一，能體現(xiàn)算法的運(yùn)算效率，時(shí)間復(fù)雜度分析具有關(guān)鍵意義。設(shè)變色龍群體大小為N，維度空間為D，目標(biāo)計(jì)算量為T(D)。在初始化階段，ICSA算法引用無(wú)限折疊映射初始化種群，設(shè)初始參數(shù)時(shí)間為t0，產(chǎn)生混沌序列的時(shí)間為t1，對(duì)適應(yīng)度進(jìn)行排序，找到當(dāng)前最優(yōu)位置的時(shí)間為t2，適應(yīng)度計(jì)算時(shí)間為f(D)，則初始化階段為:

獵物搜索階段:更新式(2)、式(8)和式(19)的時(shí)間為t3，生成位置的時(shí)間為t4，自適應(yīng)權(quán)重和螺旋策略所需時(shí)間為t5，則這一階段計(jì)算為:

眼睛轉(zhuǎn)動(dòng)階段:設(shè)方向旋轉(zhuǎn)階段的時(shí)間為t6，變螺旋搜索生成新位置的時(shí)間為t7，那眼睛轉(zhuǎn)動(dòng)過(guò)程的時(shí)間復(fù)雜度為:

獵物捕捉階段:設(shè)速度位置更新式的時(shí)間為t8，位置更新式(7)為t9，再結(jié)合黎曼流形量子學(xué)習(xí)策略位置更新式為t5。這一階段的時(shí)間復(fù)雜度為:

最后，更新適應(yīng)度值為f(D)，邊界處理和更新當(dāng)次迭代最優(yōu)位置的計(jì)算時(shí)間為t10，那最后更新所需的間為:

結(jié)合最大迭代次數(shù)Tmax，整個(gè)算法所需計(jì)算時(shí)間復(fù)雜度可寫為:與CSA相比，雖然增加了少量的時(shí)間開(kāi)銷，但性能得到了優(yōu)化。

3 實(shí)驗(yàn)仿真與結(jié)果分析

為驗(yàn)證提出算法和不同策略的有效性，將融合改進(jìn)的變色龍群算法記為ICSA；引入偶對(duì)稱無(wú)限折疊映射初始化策略的變色龍群算法記為CCSA、引入自適應(yīng)變螺旋指引的變色龍群算法記為ASCSA、引入黎曼流形量子學(xué)習(xí)策略的變色龍群算法記為L(zhǎng)ICSA。此外，引入近年提出的研究較為深入的樽海鞘群算法(SSA)[4]、鯨魚優(yōu)化算法(WOA)[12]和灰狼優(yōu)化算法(GWO)[5]進(jìn)行比較分析，突出算法有效性對(duì)比。

3.1 實(shí)驗(yàn)參數(shù)設(shè)置與檢驗(yàn)函數(shù)

設(shè)實(shí)驗(yàn)最大迭代次數(shù)為1 000，群體規(guī)模大小為40，維度空間為D＝30。算法參數(shù)設(shè)置見(jiàn)表1。

表1 不同算法的主要參數(shù)

為驗(yàn)證ICSA的有效性，選用CEC測(cè)試函數(shù)[20]的經(jīng)典集函數(shù)進(jìn)行優(yōu)化驗(yàn)證，CEC測(cè)試函數(shù)集較經(jīng)典測(cè)試函數(shù)集更為復(fù)雜，有效性對(duì)比驗(yàn)證更強(qiáng)，CEC測(cè)試函數(shù)集基本信息見(jiàn)表2。

表2 CEC測(cè)試函數(shù)基本信息

續(xù)表2 CEC測(cè)試函數(shù)基本信息

3.2 結(jié)果與分析討論

表3從不同算法最優(yōu)值、平均值、標(biāo)準(zhǔn)差、求解成功率和耗時(shí)等視野驗(yàn)證ICSA的尋優(yōu)能力、收斂精度和運(yùn)行時(shí)間。由于IEEE會(huì)議集中最新函數(shù)的復(fù)雜特征，優(yōu)化對(duì)比較好，算法尋優(yōu)精度差異大，算法精度和尋優(yōu)能力對(duì)比更突出。從表3中CSA和SSA算法對(duì)比可看出，大部分函數(shù)都處于正指數(shù)量級(jí)，尋優(yōu)效果差。從最優(yōu)值上看，ICSA有4個(gè)函數(shù)的最優(yōu)值不如其他算法的最優(yōu)值。但最優(yōu)值反映的是獨(dú)立運(yùn)行30次取最優(yōu)情況，具有一定偶然性，不能直接判斷ICSA在該函數(shù)測(cè)試上整體不如其他算法；如F5函數(shù)和F10函數(shù)最優(yōu)值不是ICSA，但該函數(shù)的均值最好的是ICSA，總體而言優(yōu)于其他算法。對(duì)比CSA、SSA、WOA、GWO以及ICSA，ICSA總體具有較好的優(yōu)勢(shì)，原因之一由于算法都是原始算法，沒(méi)有添加其他指引策略，憑借原始的慣性部分和社會(huì)部分對(duì)目標(biāo)進(jìn)行搜索。對(duì)比這5個(gè)算法的均值，ICSA體現(xiàn)出顯著性優(yōu)勢(shì)，其次與它性能相對(duì)的是WOA。對(duì)于未改進(jìn)的算法無(wú)論從均值和最優(yōu)值看都處于正指數(shù)量級(jí)，效果不佳。綜上描述，無(wú)論從均值、平均值和標(biāo)準(zhǔn)差上看，ICSA都與其他算法擁有顯著優(yōu)勢(shì)，驗(yàn)證了ICSA算法與其他算法比較的優(yōu)越性能。

標(biāo)準(zhǔn)差主要衡量測(cè)試算法結(jié)果的偏離程度，是衡量算法穩(wěn)定性的主要指標(biāo)之一。同樣從表3中可看出，ICSA的標(biāo)準(zhǔn)差不遜于其他對(duì)比算法。從時(shí)間耗時(shí)上看，CSA及它引入改進(jìn)策略的算法，運(yùn)行時(shí)間相對(duì)略高。與其他算法相比，CSA具有三個(gè)階段，且在眼睛轉(zhuǎn)動(dòng)過(guò)程中需要進(jìn)行方向變換，獵階段操作過(guò)程較為復(fù)雜，運(yùn)行的時(shí)間較多，經(jīng)時(shí)間復(fù)雜度分析，CSA在運(yùn)行時(shí)間上增加也是正常的。同時(shí)也可看出，CSA與引入策略的算法運(yùn)行時(shí)間相當(dāng)，時(shí)間誤差可接受，說(shuō)明引入的策略也并沒(méi)有帶來(lái)過(guò)多的時(shí)間消耗。

上述比較是基于CSA、SSA、WOA、GWO以及ICSA的比較，并未具體分析三種策略帶來(lái)的影響，為驗(yàn)證不同引入策略的有效性，在表3中記錄了消融實(shí)驗(yàn):CCSA、ASCSA和LICSA。從消融實(shí)驗(yàn)結(jié)果也可看出，引入的三種策略較CSA的收斂精度和尋優(yōu)能力都有不同程度的提高，證實(shí)引入不同策略到CSA中的有效性，其搜索效果優(yōu)于CCSA、ASCSA和LICSA。綜上，從不同角度來(lái)看，ICSA經(jīng)分析具備良好搜索能力和可靠精度，算法對(duì)比有效性強(qiáng)。

表3 不同算法在IEEE CEC函數(shù)集上有效性對(duì)比

續(xù)表3 不同算法在IEEE CEC函數(shù)集上有效性對(duì)比

3.3 收斂曲線分析

衡量算法的收斂快慢，可直觀利用收斂曲線圖展現(xiàn)。圖4繪制6個(gè)IEEE CEC函數(shù)維度為30的曲線收斂圖，結(jié)果如圖4所示，從圖中可清晰看出ICSA、CSA、ASCSA、LICSA、CCSA、SSA、WOA以及GWO算法的迭代收斂趨勢(shì)。由圖4可知，ICSA的收斂速度較快、收斂精度高。另外，從收斂曲線上看，CSA、SSA、GWO收斂精度相比ICA、GWO和LICSA等算法較低；圖中也可看出曲線在0～1 000次迭代趨勢(shì)，CSA、SSA以及GWO在F1、F2、F5、F7、F9這5個(gè)測(cè)試集上趨于平緩，一方面能直觀看出收斂精度較低；另一方面，可知算法從開(kāi)始到迭代結(jié)束都出現(xiàn)停滯，即陷入局部最優(yōu)。由此可直觀說(shuō)明ICSA具備較快收斂速度，精度得到有效提升。

圖4 部分函數(shù)收斂趨勢(shì)圖

3.4 Friedman統(tǒng)計(jì)檢驗(yàn)分析

僅從平均收斂曲線和直觀數(shù)據(jù)對(duì)ICSA進(jìn)行分析較主觀；因此，該小節(jié)對(duì)算法進(jìn)行統(tǒng)計(jì)定性分析，從統(tǒng)計(jì)學(xué)角度判斷算法的優(yōu)劣，判定效果更客觀、更容易接受。為定性分析各算法優(yōu)劣，利用Friedman檢驗(yàn)[6]對(duì)算法進(jìn)行統(tǒng)計(jì)檢驗(yàn)。在分析前，需先對(duì)算法進(jìn)行平均排名，突出算法整體性能，平均排名表達(dá)式為:

式中:K為測(cè)試函數(shù)個(gè)數(shù)；為算法j在第k個(gè)測(cè)試函數(shù)上的性能排名，參與排名算法個(gè)數(shù)為8。通過(guò)平均排名對(duì)比，整體判斷算法的穩(wěn)健性能。Friedman算法的平均排名見(jiàn)表4。

表4 不同算法的平均排名

從表4可看出，ICSA算法排名最好，其次是ASCSA。另外，算法的目標(biāo)是為了得到更好的搜索能力，換言之算法的穩(wěn)定性只是對(duì)搜索穩(wěn)定性的判斷，但更看重算法的搜索潛力。為對(duì)算法的搜索潛力進(jìn)行判斷，對(duì)30次獨(dú)立實(shí)驗(yàn)做后續(xù)統(tǒng)計(jì)分析，使算法的優(yōu)劣特征得到定性判斷。此實(shí)驗(yàn)的算法個(gè)數(shù)為8，其自由度為7，12個(gè)測(cè)試函數(shù)共同計(jì)算的卡方值為:36.395；根據(jù)自由度、卡方值和p值的關(guān)系，計(jì)算出p值為6.105 2E-06。同時(shí)，根據(jù)卡方檢驗(yàn)，查表可知，自由度為7、顯著水平設(shè)定為α＝5%下的臨界卡方值為:14.067。實(shí)際計(jì)算卡方值遠(yuǎn)大于臨界卡方值，由此判斷不同算法間存在顯著性組間差異，使Holm測(cè)試定性判斷具有統(tǒng)計(jì)意義。Holm檢驗(yàn)是驗(yàn)證組間差異的有效工具，設(shè)Holm檢驗(yàn)中排名最好的算法為控制算法，由表5結(jié)果取ICSA。因此，算法組間差異的檢驗(yàn)如表5所示。

表5 不同算法的Holm檢驗(yàn)結(jié)果

由表5可看出，在ICSA vs ASCSA和LICSA判決結(jié)果為接受，即α/i值＜p值，此統(tǒng)計(jì)結(jié)果表明ICSA與ASCSA和LICSA的組間差異不明顯，不能拒絕假設(shè)，性能接近ICSA但又劣于ICSA，可說(shuō)明兩種策略改進(jìn)的有效性更好。同樣可看出，其他5個(gè)算法均為拒絕，由此說(shuō)明ICSA要顯著性優(yōu)于“拒絕”的算法。由表4和表5的統(tǒng)計(jì)分析，可看出每個(gè)算法的綜合排名，同時(shí)也能得出排名間的組間差異分布情況。由統(tǒng)計(jì)結(jié)果得出，最優(yōu)算法為ICSA，其次是ASCSA，最差為SSA。鑒于所提出的偽隨機(jī)數(shù)初始化種群，存在組間差異，解釋如下:由于偽隨機(jī)數(shù)僅對(duì)算法初始化起作用，只是在初始化階段能保證算法具有先驗(yàn)優(yōu)勢(shì)，但隨著迭代進(jìn)行，搜索機(jī)制在于算法本身。除初始化以外，算法進(jìn)行迭代后收斂能力如同CSA，因此算法存在組間差異是正常的。

3.5 在CEC2021競(jìng)賽集函數(shù)上對(duì)比分析

上述實(shí)驗(yàn)的收斂性分析和結(jié)果對(duì)比是從算法搜索有效性角度進(jìn)行優(yōu)化驗(yàn)證，對(duì)更復(fù)雜組合函數(shù)的優(yōu)化問(wèn)題未充分對(duì)比。為驗(yàn)證對(duì)于復(fù)雜函數(shù)的性能，該部分設(shè)計(jì)CEC2021競(jìng)賽集進(jìn)行函數(shù)對(duì)比驗(yàn)證。CEC2021為遺傳及進(jìn)化計(jì)算會(huì)議最新測(cè)試集，包括基本函數(shù)、旋轉(zhuǎn)函數(shù)和轉(zhuǎn)換函數(shù)，分別表示為(Basic，Shift和Rotation)，其函數(shù)特征為單模態(tài)(UN)、多模態(tài)(MN)、混合函數(shù)(HF)和復(fù)合函數(shù)(CF)。設(shè)實(shí)驗(yàn)最大迭代次數(shù)為2 0000，維度為20，獨(dú)立運(yùn)行30次。函數(shù)信息如表6所示。

表6 CEC2021競(jìng)賽集測(cè)試信息

表7記錄了CEC2021競(jìng)賽集函數(shù)的優(yōu)化對(duì)比結(jié)果。由于測(cè)試集具有復(fù)雜的函數(shù)特征，難以找到最優(yōu)值，只能從平均值和標(biāo)準(zhǔn)差中看出函數(shù)最優(yōu)值的情況分布。

表7 CEC2021函數(shù)優(yōu)化結(jié)果對(duì)比

由表7，對(duì)于平均值，ISSA僅有CEC01函數(shù)的平均值劣于SSA。從標(biāo)準(zhǔn)差上分析，ICSA部分函數(shù)標(biāo)準(zhǔn)差與其他算法相比偏大，但不難從結(jié)果中看出，ICSA的標(biāo)準(zhǔn)差僅次于其他算法中的 一個(gè)，在該函數(shù)中位列第二，由此，從表中數(shù)據(jù)證明算法對(duì)復(fù)雜問(wèn)題有較好性能。從每個(gè)CEC測(cè)試函數(shù)的排名看，僅在CEC01函數(shù)上劣于SSA算法，其他函數(shù)的排名ICSA均為第一；同樣，從表中能看出，除ICSA排名最穩(wěn)定外，其他算法排名相對(duì)不穩(wěn)定，具有幅度變化。由此從直觀上看，ICSA在CEC中也取得良好效果。綜上，ICSA算法在CEC競(jìng)賽測(cè)試集20 000次迭代中依然具有顯著性特征，全方面證實(shí)算法良好的性能和尋優(yōu)能力。

4 ICSA在無(wú)源時(shí)差定位中的應(yīng)用

4.1 無(wú)源時(shí)差定位描述

無(wú)源時(shí)差定位[21](TDOA，Time Difference Of Arrival)是確定點(diǎn)位置的一種定位方法，利用電磁波在兩個(gè)點(diǎn)的到達(dá)時(shí)間差來(lái)判斷目標(biāo)點(diǎn)的位置。為驗(yàn)證ICSA在具體應(yīng)用場(chǎng)景中的尋優(yōu)潛力，將ICSA應(yīng)用到TDOA問(wèn)題來(lái)判斷定位準(zhǔn)確率。三維空間多站時(shí)差定位中包括1個(gè)主站和N個(gè)輔站。多站時(shí)差定位的主站為S0＝[0，0，0]，設(shè)置輔站位置為S j＝[x j，y j，z j]，j＝1，…，N，設(shè)目標(biāo)發(fā)射源位置為E＝[x，y，z]。單位均為km。記目標(biāo)發(fā)射源到達(dá)主站的時(shí)間為:

同理，目標(biāo)發(fā)射源到達(dá)第j個(gè)輔站的時(shí)間記為:

式中:c為電磁波的傳播速度，取值為3×105km/s。由于觀測(cè)站測(cè)量的實(shí)際時(shí)間會(huì)存在時(shí)延測(cè)量誤差(主要由于發(fā)射和接收端的處理時(shí)延)，設(shè)主站到輔站j由系統(tǒng)因素造成的時(shí)延為d0，j，設(shè)d0，j服從N～的高斯分布。

因此，對(duì)于主站與輔站j在觀測(cè)站所測(cè)得的實(shí)際時(shí)間測(cè)量值為:

由于d0，j服從均值為0，方差為σ2t的高斯分布，所以t0，j則服從t0-t j，方差為σ2t的高斯分布。時(shí)差定位模型的目標(biāo)是提升定位精度和目標(biāo)位置的估計(jì)。多個(gè)輔站場(chǎng)景時(shí)，可利用最大似然估計(jì)法求解。設(shè)觀測(cè)站的測(cè)量值相互獨(dú)立，則最大似然函數(shù)可表示為:

目標(biāo)位置的估計(jì)可表示為:

式(21)寫為向量形式可表示為

式中:

由式(23)可見(jiàn)，由于最大似然函數(shù)中其他方程為常數(shù)，求解L只與(Δt-t0＋t1)(Δt-t0＋t1)T有關(guān)。為求解最大L，只需使(Δt-t0＋t1)(Δt-t0＋t1)T最小即可。由此，設(shè)計(jì)求解問(wèn)題的目標(biāo)函數(shù)可表示為:

4.2 TDOA的求解

考慮以Y型的四站部署方式，設(shè)置TDOA輔站的個(gè)數(shù)為3，且所有輔站位于地平面。設(shè)三個(gè)輔站的位置分別為:S1＝[0 20 0]，S2＝[-10，10，0]，S3＝[-10，-10，0]。設(shè)觀測(cè)范圍上邊界ub＝[100 100 50]，下邊界lb＝[-100，100，0]。實(shí)驗(yàn)最大迭代次數(shù)均為500。

實(shí)驗(yàn)1:為比較ICSA算法與其他對(duì)比算法，進(jìn)行收斂特性對(duì)比仿真實(shí)驗(yàn)，目標(biāo)為最大化似然函數(shù)L轉(zhuǎn)化為最小化Fitness。在優(yōu)化對(duì)比特性實(shí)驗(yàn)中，設(shè)目標(biāo)發(fā)射源位置E＝[70，65，25]。繪制不同算法500次迭代收斂曲線，驗(yàn)證ICSA在TDOA中的收斂潛能，結(jié)果如圖5所示。

圖5 不同算法的迭代收斂曲線圖

由圖5可清晰看出，在前50次迭代中，和CSA相比，ICSA具備較快的收斂下降能力，說(shuō)明無(wú)限折疊混沌映射初始化為后期搜索提供良好先天基礎(chǔ)；隨著迭代持續(xù)進(jìn)行，ICSA依然具有穩(wěn)定搜索性能，且與CSA相比不會(huì)陷入局部最優(yōu)。在迭代后期，CSA因陷入局部最優(yōu)收斂值變化緩慢，收斂性能低下；而ICSA算法卻因后期有黎曼流形量子活躍特性，增加跳出局部最優(yōu)的概率，從而直觀證明算法后期的收斂潛能。在進(jìn)行500次迭代后，ICSA最優(yōu)收斂值為0.994，CSA為3.266，其次是GWO為3.452，最差是WOA，為10.562。目標(biāo)函數(shù)最小，最大似然函數(shù)越大，從而證實(shí)ICSA的良好收斂能力。同時(shí)從對(duì)比曲線也可看出，CSA對(duì)求解TDOA問(wèn)題具備良好潛力。

實(shí)驗(yàn)2:為觀測(cè)目標(biāo)發(fā)射場(chǎng)在不同位置的定位準(zhǔn)確度，使得TDOA在觀測(cè)空間內(nèi)更有意義，此部分主要考慮不同目標(biāo)發(fā)射源的定位精確度。實(shí)驗(yàn)中選取不同近場(chǎng)和遠(yuǎn)場(chǎng)發(fā)射點(diǎn)，獨(dú)立進(jìn)行30次Monte-Carlo實(shí)驗(yàn)仿真對(duì)比，并計(jì)算定位精度，得出定位準(zhǔn)確率。若目標(biāo)發(fā)射場(chǎng)的位置與觀測(cè)站實(shí)際測(cè)得的位置誤差在0.02 km以下時(shí)判定為定位精確，否則定位不精確。表8為不同目標(biāo)發(fā)射源觀測(cè)定位準(zhǔn)確率，并與其他算法對(duì)比。

表8 不同目標(biāo)發(fā)射場(chǎng)的定位準(zhǔn)確度對(duì)比 單位:%

由表8的定位準(zhǔn)確率結(jié)果可知，ICSA在同一位置的觀測(cè)定位準(zhǔn)確率要高于其他算法，其次是CSA。同樣從表8中看出，CSA算法對(duì)于TDOA的求解擁有良好的尋優(yōu)潛力，但主要缺陷是后期易陷入局部最優(yōu)。而ICSA算法克服了CSA的缺陷，在后期依然持續(xù)搜索。在近場(chǎng)區(qū)域內(nèi)，除WOA算法外，其余算法的定位效果均比較理想。隨著距離的變遠(yuǎn)，算法的定位效果差異開(kāi)始出現(xiàn)。如GWO在[30-20 20]位置上精度達(dá)不到100%，隨著距離持續(xù)增加，其他算法的準(zhǔn)確率都出現(xiàn)下降趨勢(shì)。在進(jìn)入遠(yuǎn)場(chǎng)區(qū)域[80 60 30]的目標(biāo)點(diǎn)時(shí)，5個(gè)算法的準(zhǔn)確率都達(dá)不到100%，但是比較而言，最好的準(zhǔn)確率為ICSA，其次是CSA。進(jìn)一步說(shuō)明CSA算法在TDOA與其他經(jīng)典算法相比具有較好潛能。在觀測(cè)邊緣區(qū)域時(shí)(最遠(yuǎn)點(diǎn))，ICSA的準(zhǔn)確率為98.4%，依然保持著較好的定位準(zhǔn)確率。

5 總結(jié)

本文針對(duì)變色龍群算法(CSA)的主要缺陷—求解精度低、收斂速度慢、穩(wěn)定性不強(qiáng)等缺陷進(jìn)行改進(jìn)，引入三種有效策略:①初始化階段引入無(wú)限折疊的偶對(duì)稱混沌映射，使群體較好地均勻遍歷在目標(biāo)搜索空間，增強(qiáng)群體的多樣性；②變色龍眼睛轉(zhuǎn)動(dòng)發(fā)現(xiàn)食物這一過(guò)程搜索范圍較大，導(dǎo)致搜索趨于盲目，根據(jù)WOA的變螺旋搜索指引機(jī)制，有效縮小搜索空間；③算法迭代后期因種群相似度高陷入局部最優(yōu)，利用黎曼流形量子學(xué)習(xí)的高活躍度特性使種群跳出局部最優(yōu)，有效提升收斂精度。最后，利用IEEE CEC函數(shù)集對(duì)不同策略的有效性進(jìn)行驗(yàn)證，并繪制收斂曲線圖分析搜索特征。實(shí)驗(yàn)表明在未增加時(shí)間復(fù)雜度下有效提升算法搜索性能。以無(wú)源時(shí)差定位為應(yīng)用場(chǎng)景，將ICSA應(yīng)用到TDOA中分析最優(yōu)化時(shí)差定位問(wèn)題和觀測(cè)不同目標(biāo)點(diǎn)的定位準(zhǔn)確率，實(shí)驗(yàn)表明ICSA具有良好的應(yīng)用潛力。