柯西變異的駱駝算法優(yōu)化與應用

任春慧，劉 升，張偉康，張微微

上海工程技術大學 管理學院，上海201620

生活已成為開發(fā)許多優(yōu)化算法的啟示源，這些優(yōu)化算法可分為確定性算法和隨機算法[1]。確定性算法是具有可預測行為的算法，如果給定特定輸入，它們將始終產生相同的輸出。隨機算法可以分為啟發(fā)式算法和元啟發(fā)式算法，它們之間的差別很小。啟發(fā)式算法在可接受的時間內解決問題，但不能保證可以找到最佳解決方案，這意味著沒有這樣的最優(yōu)性。雖然元啟發(fā)式算法意味著“超越”或“更高層次”，但它們通常比簡單啟發(fā)式方法表現更好。另外，所有元啟發(fā)式算法都使用了隨機化和局部搜索之間的某種權衡。

在過去的幾十年中，元啟發(fā)式算法吸引了越來越多研究學者的關注，現在仍然是一個活躍領域。后來提出了幾種算法，例如粒子群算法[2]、蟻群優(yōu)化算法[3]、細菌覓食優(yōu)化算法[4]、花授粉算法[5]、磷蝦群算法[6]、烏鴉搜索算法[7]等。如今，有許多實際的優(yōu)化問題需要解決，任務是針對大多數的問題而不是所有問題設計更好的算法。

Ibrahim和Ali在2016年提出的駱駝算法[8]是一種元啟發(fā)式優(yōu)化技術，它模仿了駱駝在沙漠中覓食過程中的行進行為，可以描述為它們向著食物源位置的合作運動，接收、感知和分析空氣中的氣味以確定食物源或配對伴侶的潛在方向。由于有多循環(huán)嵌套和多個參數選擇，該算法具有復雜的結構，這會對執(zhí)行效率和內存大小產生負面影響。本文介紹改進的駱駝行進行為算法（MCA），顯著提高了其計算速度和收斂性，同時簡化了算法結構。為了檢驗其性能，進行仿真研究，將改進的算法與CA、PSO和CSA算法進行了比較，并在工程應用中進行測試抗干擾智能天線優(yōu)化，結果表明MCA能有效處理實際工程問題。

1 駱駝優(yōu)化算法

1.1 駱駝行進行為

駱駝可以在高溫和缺水的情況下，適應長時間的生存。在夏季，它平均8~10天涉水一次，并通過脫水減去多達30%的重量。具體而言，當平均溫度約為30℃~35℃時，駱駝在沒有水的情況下可以生存10~15天，但當溫度高于46℃時，則需要較短時間的飲水。

在駱駝穿越沙漠到達某個目的地的過程中，它們遵循有組織的先天性行為來尋找食物。駱駝散布在某個地區(qū)，尋找食物，一旦某個駱駝到達一個綠洲，它就會與駱駝群其他成員進行某種信號交流，指引其他駱駝來到綠洲處。只要駱駝群中任意個體能看到信號源駱駝的位置，它們就可以改變方向，尋找通往綠洲的道路。由于沙漠中沙丘的存在，并非所有駱駝都可以看到食物供應的地點，未看到的駱駝繼續(xù)隨機運動尋找下一個綠洲。在此行進期間，另一頭駱駝可能會找到更好的食物供應位置，因此它會與其他駱駝再次進行信號交流，更改它們前往該新位置的路線，這個過程一直持續(xù)到駱駝到達一定的綠洲為止。

從上述系統(tǒng)行為中，啟發(fā)了駱駝算法。駱駝行為[9]的概述可以歸納為以下幾點：

（1）駱駝以集群的形式行進。

（2）駱駝散開去尋找綠洲。

（3）到達區(qū)域的駱駝與其他駱駝進行信號交流，來指引前進方向。

（4）沙丘可能會阻止某些駱駝看到綠洲區(qū)域，這些駱駝會繼續(xù)隨機運動。

（5）在此行進過程中，另一只駱駝可能到達更好的綠洲，然后重復更新過程。

值得一提的是，駱駝群在過去的整個行進過程中會一直尋找最佳位置。換句話說，駱駝群是根據全局最佳位置而不是局部最佳位置來更新其行進路徑。

1.2 駱駝優(yōu)化算法

假設有N只駱駝穿越D維環(huán)境。駱駝i在時間迭代(iter)時的位置可以表示：

其中，i=1,2,…,N；iter=1,2,…,itermax。

開始時(iter=0)，駱駝在沙漠中散布開來，隨機尋找綠洲，如下式所示：

其中，d=1,2,…,D；Rand表示一個均勻分布在0和1之間的隨機數；xmin表示駱駝位置的最小限制（優(yōu)化變量），xmax駱駝位置的最大限制（優(yōu)化變量）。

因此，每個駱駝的位置都要經過一定的適應度來確定最佳位置。環(huán)境溫度直接影響駱駝的行進，并顯著影響駱駝的耐力E。由于不同的駱駝向稀疏位置移動，它們遇到的溫度不同，導致每個駱駝的耐力水平也不同。駱駝i在迭代時間iter時的溫度T是最小溫度范圍Tmin和最大溫度Tmax之間的波動如下：

溫度對駱駝耐力E的影響：

從等式（4）可以清楚地看出，駱駝的承受力與溫度成反比，且耐力越高，駱駝步距越寬。

沙丘可能會擋住某些駱駝的視線，使它們無法更新通往某只駱駝發(fā)現綠洲的路線。因此，有兩種方案可以更新每個駱駝的位置。

當駱駝的能見度v大于特定的能見度閾值時，更新函數如下式：

當駱駝的能見度v小于能見度閾值時，會發(fā)生更新過程的第二種情況，在此情況下，駱駝會根據等式（2）隨機更新其位置。新位置也會根據指定的適應度函數的影響，確定當前的最佳位置。如果當前位置優(yōu)于過去的位置，則新的位置是全局最佳位置，否則過去的位置仍然是全局最佳位置。應該注意的重要一點是，駱駝能見度在每次迭代中都是0到1之間的隨機數，因為它取決于沙丘存在的隨機位置。更新過程一直持續(xù)到達到最大迭代次數或達到適應度函數中的某個閾值為止。

駱駝算法[10]如下所示：

輸入：目標函數f(x)，駱駝位置限制xmin和xmax，設置溫度范圍Tmin和Tmax，設置駱駝群的規(guī)模N，設置可見性閾值v，最大迭代次數Maxiter

1.初始化：根據等式（2）初始化每個駱駝的位置，對位置進行適應度調整；確定當前的最佳位置；為每個駱駝隨機分配能見度v。

2 駱駝優(yōu)化算法的改進

2.1 柯西變異策略

柯西分布是概率論中常見的連續(xù)型分布之一，其密度函數表達式可定義為：

表示為C(α,β)，其中α和β是兩個參數。特別地，當α=1，β=0時，可得標準的柯西分布的密度函數：

高斯分布和柯西分布的比較如圖1所示，從圖中可以看出柯西分布圖形是對稱的且兩翼較為平坦、寬大，在原點附近有一個較低的極值，且水平下降比高斯分布下降慢，柯西分布在水平方向上越接近水平軸，變得越緩慢，因此柯西分布可以看作是無限的，因此，從概率上講，Cauchy分布具有更寬的分布范圍，它允許較大的變異，因此采用柯西變異產生的子代距離父代較遠的概率高于高斯變異，從而易于跳出局部最小點。以這種方式可以產生更多樣化的個體和涵蓋更多的主要空間。與此相反，高斯變異能夠以其最接近的空間完成準確鄰近的探索[11]。

圖1 柯西（Cauchy）分布和高斯（Gaussian）分布比較Fig.1 Comparison of Cauchy distribution and Gaussian distribution

針對駱駝算法易陷入局部最優(yōu)的特點，利用柯西變異來增加目標的多樣性，提高算法的全局搜索能力，增加搜索空間。

由于柯西分布函數的峰值較低，該特點能夠縮短變異后的駱駝個體在鄰域周圍搜索的時間。因此在求得當前最優(yōu)解后，使用公式（7）所示的更新公式對當前全局最優(yōu)解進行變異處理。

2.2 改進的駱駝算法

柯西分布函數從峰值向兩側下降相對平緩，駱駝個體受局部的極值點約束力在進行柯西變異后下降，并且柯西分布函數的峰值相對較小，駱駝個體在變異后會使用相對較少的時間來搜索相鄰區(qū)間，把更多的時間放在搜尋全局最優(yōu)值上，使得改進的駱駝算法在尋找全局的最優(yōu)值方面具備很好的調節(jié)能力。用柯西變異進行隨機擾動有利于增加種群的多樣性從而避免算法陷入局部最優(yōu)，提高全局搜索最優(yōu)值的能力。柯西分布的特征使其能夠產生與原點相距較遠的隨機數，這意味著經過柯西變異后的駱駝個體具備了能夠迅速逃離局部極值的能力。

通過融合柯西變異函數對駱駝行進分布進行優(yōu)化處理后，使得CA算法具有更好的局部尋優(yōu)能力，改進后的CA算法流程圖如圖2所示。

圖2 改進后的算法流程圖Fig.2 Improved algorithm flow chart

3 函數測試與結果分析

3.1 仿真實驗環(huán)境

本仿真測試環(huán)境為操作系統(tǒng)Windows10，CPU為Intel?Core?i5-5200U，主頻2.7 GHz，內存為8 GB，仿真軟件為Matlab2019a。

3.2 測試函數

為了驗證MCA算法的性能，選擇三個單峰和三個多峰基準函數進行仿真測試實驗。表1列出了選定的六個基準測試函數，F1(x)到F3(x)為單峰基準函數，F4(x)到F6(x)為多峰基準函數，這些基準測試函數的最小值等于零。

表1 基準測試函數Table 1 Benchmark function

3.3 實驗的初始參數設置

本文將MCA與原始CA，烏鴉搜索算法（CSA）和粒子群優(yōu)化算法（PSO）進行比較[12]。在以下條件下測試算法：初始種群規(guī)模N統(tǒng)一設為50，最大迭代次數為500次。對于MCA和CA，可見性閾值v=0.1，位置限制xmin=-32,xmax=32，溫度范圍Tmin=30℃和Tmax=60℃；對于CSA：飛行長度fl=2，感知概率AP=0.1；對于PSO：慣性系數w=0.9,wdamp=0.4，學習因子c1=1.5,c2=2。

3.4 實驗結果與分析

與原始CA相比，MCA的主要優(yōu)勢在于其執(zhí)行速度高，內存小，大幅度減少了運行的時間，提高了執(zhí)行效率。MCA僅需要一個駱駝的全局最佳位置向量，該駱駝是[1×Dim]矩陣。除了顯著減少內存大小外，該算法還減少了一個循環(huán)，與CSA相比，MCA的執(zhí)行速度得到了提高。

為了驗證MCA在執(zhí)行速度方面優(yōu)于CA、CSA和PSO，對算法運行時間進行了測量。表2列出了針對30次運行和單次運行的每個測試函數執(zhí)行每種算法所需的時間。圖3顯示了30次運行的執(zhí)行時間，圖4顯示了單次運行的平均時間。從表2以及圖3和圖4中可以看出，MCA比CSA、CA和PSO運行速度更快。因此，MCA非常適合在線優(yōu)化系統(tǒng)，該系統(tǒng)需要較小的內存大小并快速響應其參數的突然變化。

圖4 單次運行的執(zhí)行時間Fig.4 Execution time of single run

表2 測試函數實驗運行時間Table 2 Test function experiment running time

圖3 30次運行的執(zhí)行時間Fig.3 Execution time of 30 runs

從精度至關重要的離線優(yōu)化的角度出發(fā)，對每個測試函數進行30次運行，獲得平均值、標準偏差和測試函數最佳值的中值。還根據以下公式計算每種算法的成功率（SR）：

其中成功運行次數表示達到以下條件的運行次數：

表3 展示了MCA、CSA、PSO、CA這四種算法獨立運行30次后所得到的最優(yōu)值、均值、標準差、中位數和成功率的結果。

根據表3，可以清楚地看出對于所選測試函數，MCA的尋優(yōu)能力最強明顯優(yōu)于CSA、PSO和CA。對于函數F1、F5、F6，MCA可以直接搜索到最優(yōu)值0，尋優(yōu)效果可以達到100%；對于函數F2、F3、F4，MCA尋優(yōu)效果良好，且接近PSO，具有PSO相當的性能，且對于多峰函數MCA表現出比PSO更好的成功率。

表3 測試函數實驗結果Table 3 Experimental results of test function

為了直觀地展示MCA的尋優(yōu)性能，作出了關于測試函數的迭代收斂曲線圖，如圖5所示。

圖5 測試函數收斂曲線圖Fig.5 Convergence curve of the test function

3.5 高維系統(tǒng)中的性能比較

沒有一種算法可以精確有效地執(zhí)行所有優(yōu)化問題，因此，MCA的缺點出現在高維優(yōu)化系統(tǒng)中。對于高維（維度d=200），與多模式優(yōu)化系統(tǒng)的PSO相比，MCA性能下降，CSA的失效性最為明顯，如表4所示。從實驗結果來看，MCA在高維函數求解中仍具有較好的尋優(yōu)穩(wěn)定性。對于多峰函數，四種算法執(zhí)行效果都不好，函數會形成大量局部極值區(qū)域，易陷入局部最優(yōu)且不易跳出，在高維測試函數下求解難度較大，在測試函數維數大于200維時，就屬于大規(guī)模函數優(yōu)化問題。隨著搜索空間維數的增加，問題的復雜度以及指數級數的增長，從而出現“維數災難”問題，根據無萬能算法理論，沒有任何一個算法適合解決所有問題，所以這個結果是可以接受的。盡管局部最佳使算法復雜化并減慢了速度，但仍顯著提高了算法的精度。針對此點，可以得出MCA在低維離線優(yōu)化和高維單峰離線優(yōu)化過程中是有效的。

表4 MCA高維函數求解結果Table 4 Solution result of MCA high dimensional function

4 工程優(yōu)化應用

4.1 抗干擾智能天線系統(tǒng)

抗干擾智能天線[13]可用于軍事，這是一個實時系統(tǒng)，它經常不斷地更新其操作參數。圖6說明了M元素智能天線系統(tǒng)的工作原理和參數。所需的傳輸與接收站固定在站點（LOS）線內。其他干擾源沿不同方向分布，以傳輸偽造消息或僅向標記功能干擾原始系統(tǒng)?？垢蓴_智能天線系統(tǒng)嘗試將天線主波束[14]定向到所需的傳輸方向，并在干擾信號的方向上定位零點。實際上，所需信號與干擾之間是否存在任何相關性信號，傳統(tǒng)的波束形成算法無法完美消除干擾信號。在這種情況下，傳統(tǒng)的波束形成算法只能衰減干擾信號。但是，有時會以高于所需信號功率的功率發(fā)送干擾信號，因此在這種情況下衰減將無效[15]。駱駝算法與信號之間的相關性無關，無論其傳輸功率大小如何，都可以完美消除干擾信號。

圖6 M元智能天線系統(tǒng)Fig.6 M-dimensional smart antenna system

4.2 抗干擾智能天線優(yōu)化

考慮到有(k+1)個信號從不同方向照亮M元素智能天線。這些信號由它們的強度S（信號功率的平方根）表示，使得{S0,S1,…,Sk}。假設接收信號S0是從寬邊方向照亮智能天線的所需信號(Φ=90)。所有其他信號均被視為干擾信號。感應到的信號所有元素都可以用矢量符號表示，陣列系統(tǒng)的復數權重矢量表示為。智能天線系統(tǒng)的輸出信號為：

其中，上標H表示復共軛轉置。

由智能天線系統(tǒng)采集的接收信號矢量最初的構造為：

其中，ak是指到達角為Φk的第k個信號的導引向量。

轉向矢量信號可以表示為：

其中，d表示每兩個相鄰元素之間的波長(λ)，而β表示傳播相位常數：

對于天線陣列[16]，只要天線元件是全向的，輻射方向圖就等于陣列系數(AF)。因此，可以從陣列因子方程確定輻射方向圖，如下所示：

其中，a(Φ)代表任意角度(Φ)的一般轉向矢量：

權重向量元素之間的相位角(δ)決定了應朝向所需信號方向定向的天線主波束角Φ0。以下準則確定權重矢量

元素之間的相位角：

所需的信號角度為(Φ0=90°)，因此δ的值等于零。但是，權重向量的大小決定了天線陣列因子的零位。結果，權重向量的大小||w是此類系統(tǒng)的優(yōu)化變量。對于上述系統(tǒng)，適應度函數F為：

數值示例：考慮M=10智能天線系統(tǒng)，其期望信號強度等于S0=1。假設存在一個極端干擾問題，包括三個強度分別為S1=3,S2=2,S3=3。

以下情況表示四個干擾信號的不同到達角度：

Case 1：Φ1=20,Φ2=60,Φ3=120

Case 2：Φ1=30,Φ2=80,Φ3=140

Case 3：Φ1=50,Φ2=100,Φ3=130

表5 為應用MCA后每種情況下的權重向量的優(yōu)化大小。圖7針對每種情況從權重向量得到的陣列因子的歸一化幅度。顯然，無論信號之間的相關性如何，天線系統(tǒng)都可以通過將零點指向其到達角度來完全消除干擾信號。

表5 智能權重向量優(yōu)化幅度Table 5 Intelligent weight vector optimization amplitude

圖7 優(yōu)化的智能天線歸一化陣列因子Fig.7 Optimized normalized array factor for smart antenna

5 結束語

本文提出了一種模仿駱駝行進行為的新型改進CA算法。在全局位置更新后的值引入柯西變異算子，增加了種群多樣性，降低算法陷入局部最優(yōu)的可能性。由于減少了原始算法中使用的設置參數的數量，因此該算法的結構很簡單。使用具有不同變量維度的不同單峰和多峰基準函數測試了修改后的CA，結果表明，MCA具有更好的尋優(yōu)能力和魯棒性。且對于低維變量，修改后的CA的精度與PSO相當。通過優(yōu)化受約束的工程應用，抗干擾智能天線的優(yōu)化來驗證MCA的性能。對于抗干擾智能天線，該算法通過將零點指向其方向來完美消除干擾信號。此外，進一步研究駱駝算法參數值可能會進一步提高其性能和收斂速度，將算法應用到更廣泛的領域。