趙永奇，鄒 鋒，陳得寶

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

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

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

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

1 正余弦算法

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

(1)

(2)

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

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

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

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

圖1 環(huán)形鄰域

2.1 環(huán)形鄰域結構

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

(3)

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

(4)

2.2 骨干優(yōu)化思想

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

(5)

2.3 新提出的迭代學習方法

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

(6)

(7)

其中，t是當前迭代次數(shù)，T是最大迭代次數(shù)。

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

2.4 算法步驟

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

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

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

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

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

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

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

3 仿真實驗分析

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

3.1 參數(shù)設置

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

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

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)，學習代數(shù)L=50；

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

表1 18個基準測試函數(shù)

3.2 結果分析

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

表2 30維函數(shù)測試結果

續(xù)表

注：帶*數(shù)據(jù)表示最好結果。

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

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

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

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

函數(shù)性能指標測試結果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*

續(xù)表

注：帶*數(shù)據(jù)表示最好結果。

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

4 結語

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