一種新的基于鄰域結構的骨干正余弦算法

趙永奇，鄒 鋒，陳得寶

(淮北師范大學物理與電子信息學院，安徽淮北235000)

目前，智能優化算法在越來越多的領域得到應用，并取得了一系列的豐碩成果。研究人員常用的傳統智能優化算法包括遺傳算法(GA)[1]、粒子群算法(PSO)[2]、螢火蟲算法(GSO)[3]等。隨著需要優化的問題越來越復雜，在求解這些問題的過程中，傳統優化算法暴露出很多自身的缺陷。因此，研究人員開始結合其他算法或者學習策略，通過其他算法或策略的優勢來彌補原始算法的不足，從而提高算法的性能。

澳大利亞格里菲斯大學的MIRJALILI[4]在2016年提出一種新型的智能優化算法——標準的正余弦算法(sin cosin algorithm，SCA)。該算法利用隨機參數和自適應參數很好地平衡算法的探索階段和開發階段。SCA的參數較少，位置更新方程簡單，易于實現，收斂速度快，但也存在著計算精度低，后期收斂速度慢等缺點。對此，陳聰[5]引進量子進化的相關理論，利用量子位對個體進行編碼，個體對最優解的搜索通過量子旋轉門來完成，通過量子門實現個體的變異，從而提高算法的性能。HATHIRAM NENAVATH[6]通過正余弦算法和教學優化算法相結合的方式，前期利用正余弦算法實現全局探索，后期利用教學優化算法實現局部搜索，有效地實現全局搜索和局部搜索的平衡。

針對正余弦算法計算精度低，容易陷入局部最優解，后期收斂速度慢等問題，本文提出一種基于鄰域結構的骨干正余弦算法(bare bone sine cosine algorithm based on neighborhood structure，BBNSCA)。首先，建立環形鄰域模型[7]，確定每個個體的鄰域。然后，利用全局最優解和鄰域最優解通過高斯采樣[8]產生新的個體，保證種群的多樣性。最后，引入線性遞減的隨機權重系數，提高隨迭代次數的增加而增加高斯采樣的權重，避免算法陷入局部最優解。

1 正余弦算法

在求解優化問題時，SCA的主要思想是，首先在目標空間中隨機產生m個個體的位置，并用Xi=(Xi1,Xi2…,Xi dim)T表示第i(i=1,2,…,m)個個體的位置，其中dim為個體的維度，第t代個體經過最好的位置表示為Pdim，其位置更新方程為：

(1)

(2)

其中，a為常數，一般取2，t為當前迭代次數，T為最大迭代次數。

在SCA中，參數r1具有平衡算法探索和開發的能力。當r1>1時，下一代個體出現的位置在當前解和目標解之外(探索階段)；當r1<1時，下一代個體出現的位置在當前解和目標解之間(開發階段)。參數r2決定個體下一代移動的步長。當r3>1時，表明增強當前最優解的作用；當r3<1時，表明減弱當前最優解的作用。參數r4<0.5時，算法按照正弦方式迭代，反之則按照余弦方式迭代。

2 基于鄰域結構的骨干正余弦算法

隨著對智能優化領域的深入研究，研究人員發現單一優化算法并不能在處理任何優化問題時都能表現出優異的性能。斯坦福大學的WOLPERT和MACREADY[9]在此基礎上提出了著名的無免費午餐定理(No-Free-Lunch定理)。No-Free-Lunch定理指出，通過與其他策略相融合的方式，可以利用其他學習策略的優勢來彌補本算法的劣勢，以此來提高本算法的優化性能。由此，本文提出了一種基于鄰域結構的骨干正余弦算法。

圖1 環形鄰域

2.1 環形鄰域結構

鄰域結構決定著鄰域中的個體如何分配以及個體之間如何相互溝通信息，根據模擬不同的群體行為關系的結構，可以分為環形、星型、金字塔形和馮依曼型[10-12]。環形鄰域是一種常見的鄰域結構，如圖1所示，在環形鄰域中，每個個體只與其附近的兩個個體交流信息，從而有效地保證種群的多樣性，采用環形鄰域結構也是為了維持種群多樣性的一種有效方式。引入鄰域結構的最重要一步是確定每個個體的鄰域范圍。例如，對于個體i，其鄰域的個體為個體i+1和個體i-1，個體之間的信息交流被局限于這個鄰域之中。這種環形鄰域結構能保證算法對目標空間的不同區域進行充分搜索，從而提高種群的探索能力，而不至于陷入過早收斂的情形，這些鄰域結構的優點在實際應用中得到了證明。除此之外，這種環形鄰域結構僅與個體的下標有關，可以有效地對目標空間進行搜索。其環形鄰域結構數學模型為：

(3)

對鄰域結構中的個體進行評價，計算其適應度值，確定鄰域中最優個體B，其表達式為：

(4)

2.2 骨干優化思想

研究人員從粒子群優化算法的理論研究中證明，每個粒子的極限收斂于個體最優位置與全局最優位置的加權平均，基于這一理論，研究人員提出了基于高斯采樣學習的骨干優化方法。受此思想啟發，本文將高斯采樣學習引入正余弦算法中，以提高正余弦算法的優化性能。

(5)

2.3 新提出的迭代學習方法

SCA的位置更新方程是利用數學模型的震蕩性尋找最優解，前期具有較強的探索能力。但是，在開發階段，個體一旦陷入局部最優解，就很難擺脫束縛，從而導致算法的多樣性降低，尋優精度不高。而高斯采樣學習可以提高種群的多樣性，避免算法過早收斂。新算法的主要思想是前期利用SCA優秀的探索能力，探尋更廣泛的目標區域，在算法后期為了防止陷入局部最優解，利用權重因子調節高斯采樣在算法中的比重，使算法具有跳出局部最優解的能力。新算法的迭代方程為：

(6)

(7)

其中，t是當前迭代次數，T是最大迭代次數。

線性遞減的權重因子K的作用是隨著迭代次數的增加，降低正余弦算法的權重，提高高斯采樣學習的權重，更好地平衡算法的探索和開發階段。權重因子K使新算法在前期繼承SCA較強的搜索能力，同時也使新算法具備在后期利用高斯采樣學習跳出局部最優解的能力。

2.4 算法步驟

根據標準正余弦算法的優化框架，提出的基于鄰域結構的骨干正余弦算法的步驟具體如下：

步驟一：設置種群規模m，空間維度D，最大評價次數E，下界Xmin，上界Xmax。

步驟二：初始化種群的位置和環形鄰域，并對種群進行評價確定全局最優解。

步驟三：根據式(1)生成Y，根據式(5)生成Z。

步驟四：據式(6)生成新個體，對個體進行評價。

步驟五：判斷新解是否優于當前解，優于當前解即保留，反之，則舍棄。

步驟六：若當前評價次數小于最大迭代次數，則返回步驟三，否則迭代結束。

3 仿真實驗分析

為了驗證改進的正余弦算法的可行性和有效性，本實驗將采用18個有代表性的測試基準函數，將基于鄰域結構的骨干正余弦算法與采用相同策略改進的算法(例如BBExp[14]、BBPSO[15]、BBTLBO[16]、BBDE[17])進行比較分析，然后再將新算法與jDE[18]、SaDE[19]、PSOwFIPS[20]、SCA進行仿真比較。

3.1 參數設置

本文所用的18個函數如表1所示。F1(x)～F4(x)是單峰函數，F5(x)～F10(x)為多峰函數，F11(x)～F18(x)分別是F3(x)～F10(x)的旋轉函數。本文中所有的實驗環境均為：Windows 10操作系統，主頻為3.2 GHz，RAM為8 GB，開發工具為MATLAB R2015b。所有算法的種群大小m都為40，分別在維度D=30和D=50的情況下進行仿真實驗，以函數值為算法的適應度值，最大函數評價次數(5 000*D)作為算法的終止準則。

其他算法的參數均來自參考文獻，相關參數如下所示：

jDE[21]：縮放因子F=0.5，交叉概率Pcr=0.9；

SaDE[22]：縮放因子F滿足F～N(0.5，0.3)，初始交叉概率Pcr0=0.5，交叉概率Pcr滿足Pcr～N(Pcrm，0.1)，學習代數L=50；

PSO-wFIPS[20]：慣性權重w=0.729 8.

表1 18個基準測試函數

3.2 結果分析

為了驗證新算法與采用相同策略改進的算法(例如BBExp、BBPSO、BBTLBO、BBDE)之間的優劣，分別對30維函數進行實驗，每種算法獨立運行10次，記錄各個算法對應各個函數所得到的最優解(best)、平均值(mean)、標準差(Std)進行統計分析，實驗結果如表2所示。由于部分基準函數的收斂曲線比較相似，圖2中僅給出有代表性的收斂曲線。在下面敘述中，用F1～F18代表F1(x)～F18(x)。

表2 30維函數測試結果

續表

注：帶*數據表示最好結果。

為了多方面驗證新算法的性能，將新算法與jDE、SaDE、PSOwFIPS、SCA在50維度的情況下對18個基準函數運行10遍，進行仿真實驗，記錄各個算法對應各個函數所得到的最優解、平均值、標準差并進行統計分析，結果如表3所示。圖3為具有代表性的函數平均適應度值變化圖。

分析表3中記錄的實驗數據和圖3的平均適應度值變化圖，可得到以下結論：對函數F1、F3、F6～F9、F11、F13～F17，從最優解、平均值、標準差這3個性能指標方面分析可以得到新算法的性能優于其他4種算法。從函數F2、F4、F5、F10、F12、F18的實驗結果可知，新算法的性能與jDE和SaDE相當，但依然優于PSOwFIPS和SCA。由此可得，新算法的平均性能優于jDE、SaDE、PSOwFIPS、SCA，且相較于基本SCA算法的求解精度和收斂速度都有較大程度的提高。

對于表2中的實驗結果以及圖2中的收斂曲線，本文將從最優解、平均值、標準差這3個性能指標進行分析：(1)從最優解分析可知，對于函數F1、F3、F6～F17，新算法的最優解優于其他4種算法，且對于函數F1、F3、F6～F9、F11～F12、F14～F17，新算法的最優解得到了理論上的最優值；(2)從平均值可以分析，對于函數F1、F3、F6～F9、F11、F13～F17，新算法的平均值優于其他4種算法，且對于函數F1、F3、F6～F9、F14～F17，新算法的平均值達到理論上的最優值，由此可知新算法的求解精度優于其他算法；(3)對標準差分析可知，對于函數F1、F3、F5～F9、F11、F13～F17，新算法的標準差優于其他4種算法，這說明新算法的魯棒性優于其他4種算法，性能比較穩定，能夠很快地收斂到最優解。

圖2 30維部分函數平均適應度值變化圖

函數性能指標測試結果jDESaDEPSOwFIPSSCABBNSCAF1best3.81E-89 8.12E-85 6.39E-07 3.17E-08 0.00E+00*mean1.45E-85 2.50E-78 1.20E-06 2.58E+04 0.00E+00*std4.48E-85 5.48E-78 3.79E-07 34 958.49 0.00E+00*F2best7.48E-02*2.25E-01 1.82E+03 1.41E+05 1.43E+01 mean2.70E-01*4.30E-01 2.47E+03 2.33E+05 2.65E+01 std0.136 01*0.193 690 289.841 3 77 987.26 12.474 45 F3best1.74E-90 1.36E-88 1.87E-07 6.64E-07 0.00E+00*mean5.64E-86 2.54E-77 3.38E-07 3.13E+02 0.00E+00*std1.24E-85 7.93E-77 1.50E-07 2 309.106 0.00E+00*F4best3.68E-05*4.81E-05 5.90E+00 1.65E+03 1.68E-03 mean1.87E-04*3.76E-04 1.03E+01 2.91E+04 8.66E-03 std0.000 22 0.000 311*2.620 800 654 406.0 0.006 404 F5best19.675 5*39.494 73 44.635 27 1 375.998 39.584 78 mean21.543 0*42.545 78 45.108 67 1.39E+04 39.901 59 std1.412 26 1.800 157 0.253 649 4 548.549 0.231 145*F6best7.11E-15 3.55E-15 1.45E-04 1.03E-06 0.00E+00*mean9.24E-15 6.04E-15 1.87E-04 1.06E+01 0.00E+00*std3.43E-15 1.72E-15 2.79E-05 10.976 86 0.00E+00*

續表

注：帶*數據表示最好結果。

圖3 50維部分函數平均適應度值變化圖

4 結語

綜上所述，本文提出了一種基于鄰域結構的骨干正余弦算法，既保留了SCA的全局搜索能力，又利用高斯采樣學習增強了算法的多樣性，通過線性遞減的權重因子較好地調節了高斯采樣學習對整個算法的影響，能夠較好地平衡算法的探索和開發階段，避免了算法陷入局部最優解，并利用貪婪選擇機制加速算法的收斂速度。通過對18個基準函數的實驗結果表明，新算法在求解單峰函數和大部分多峰函數時，在收斂速度、穩定性和求解精度這三方面都有優異的表現。新算法在處理個別復雜函數時，其收斂速度和求解精度不是最好的，但也不是最差的，這也側面驗證了“無免費午餐定理”。總的來說，對標準SCA算法改進的基于鄰域結構的骨干正余弦算法是有效的。