一種新的基于鄰域結(jié)構(gòu)的骨干正余弦算法

趙永奇，鄒 鋒，陳得寶

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

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

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

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

1 正余弦算法

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

(1)

(2)

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

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

2 基于鄰域結(jié)構(gòu)的骨干正余弦算法

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

圖1 環(huán)形鄰域

2.1 環(huán)形鄰域結(jié)構(gòu)

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

(3)

對鄰域結(jié)構(gòu)中的個(gè)體進(jìn)行評價(jià)，計(jì)算其適應(yīng)度值，確定鄰域中最優(yōu)個(gè)體B，其表達(dá)式為：

(4)

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

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

(5)

2.3 新提出的迭代學(xué)習(xí)方法

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

(6)

(7)

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

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

2.4 算法步驟

根據(jù)標(biāo)準(zhǔn)正余弦算法的優(yōu)化框架，提出的基于鄰域結(jié)構(gòu)的骨干正余弦算法的步驟具體如下：

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

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

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

步驟四：據(jù)式(6)生成新個(gè)體，對個(gè)體進(jìn)行評價(jià)。

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

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

3 仿真實(shí)驗(yàn)分析

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

3.1 參數(shù)設(shè)置

本文所用的18個(gè)函數(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)的旋轉(zhuǎn)函數(shù)。本文中所有的實(shí)驗(yàn)環(huán)境均為：Windows 10操作系統(tǒng)，主頻為3.2 GHz，RAM為8 GB，開發(fā)工具為MATLAB R2015b。所有算法的種群大小m都為40，分別在維度D=30和D=50的情況下進(jìn)行仿真實(shí)驗(yàn)，以函數(shù)值為算法的適應(yīng)度值，最大函數(shù)評價(jià)次數(shù)(5 000*D)作為算法的終止準(zhǔn)則。

其他算法的參數(shù)均來自參考文獻(xiàn)，相關(guān)參數(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)，學(xué)習(xí)代數(shù)L=50；

PSO-wFIPS[20]：慣性權(quán)重w=0.729 8.

表1 18個(gè)基準(zhǔn)測試函數(shù)

3.2 結(jié)果分析

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

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

續(xù)表

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

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

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

對于表2中的實(shí)驗(yàn)結(jié)果以及圖2中的收斂曲線，本文將從最優(yōu)解、平均值、標(biāo)準(zhǔn)差這3個(gè)性能指標(biāo)進(jìn)行分析：(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，新算法的平均值達(dá)到理論上的最優(yōu)值，由此可知新算法的求解精度優(yōu)于其他算法；(3)對標(biāo)準(zhǔn)差分析可知，對于函數(shù)F1、F3、F5～F9、F11、F13～F17，新算法的標(biāo)準(zhǔn)差優(yōu)于其他4種算法，這說明新算法的魯棒性優(yōu)于其他4種算法，性能比較穩(wěn)定，能夠很快地收斂到最優(yōu)解。

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

函數(shù)性能指標(biāo)測試結(jié)果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ù)表示最好結(jié)果。

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

4 結(jié)語

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