自適應(yīng)多策略正余弦算法①

(淮北師范大學(xué)1.物理與電子信息學(xué)院;2. 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 淮北 235000)

0 引 言

智能優(yōu)化算法作為處理各類優(yōu)化問(wèn)題的重要工具，在工程應(yīng)用和科學(xué)研究中都得到了廣泛應(yīng)用。隨著需要優(yōu)化的問(wèn)題越來(lái)越復(fù)雜，僅僅依靠某一種優(yōu)化算法去求解問(wèn)題，往往并不能得到令人滿意的結(jié)果。因此，人們開(kāi)始利用集成的思想，借鑒其他算法的優(yōu)勢(shì)和特點(diǎn)，并加以利用，通過(guò)多種更新策略的優(yōu)勢(shì)來(lái)彌補(bǔ)單一算法在處理優(yōu)化問(wèn)題時(shí)的缺陷。正余弦算法(Sine Cosine Algorithm，SCA)作為一種新型啟發(fā)式智能優(yōu)化算法，一經(jīng)提出便受到眾多研究人員的關(guān)注。雖然正余弦算法結(jié)構(gòu)簡(jiǎn)單易于實(shí)現(xiàn)，但是仍存在著求解精度低，后期收斂速度慢等缺點(diǎn)。于是，Rizk M等人提出了一種改進(jìn)的基于正交并行信息的正余弦全局優(yōu)化算法，Sujoy Das等人利用正余弦算法解決短期熱液調(diào)度問(wèn)題，Diego Oliva等人利用蟻獅算法和正余弦算法相混合的方式改進(jìn)算法的性能來(lái)解決圖像分割問(wèn)題。為改進(jìn)正余弦算法的性能，在算法更新過(guò)程中采用多種策略對(duì)個(gè)體進(jìn)行更新。本文除了正余弦算法外，又提出了三種不同的策略：(1)基于最優(yōu)個(gè)體引導(dǎo)的進(jìn)化策略。(2)基于個(gè)體差異引導(dǎo)的進(jìn)化策略。(3)基于其他個(gè)體知識(shí)學(xué)習(xí)的進(jìn)化策略。

1 正余弦算法

正余弦算法的原理簡(jiǎn)單，易于實(shí)現(xiàn)，其利用自適應(yīng)參數(shù)實(shí)現(xiàn)算法的探索階段和開(kāi)發(fā)階段的平穩(wěn)轉(zhuǎn)換。正余弦算法的更新方程為：

(1)

其中，Xit是第t次更新過(guò)程中i個(gè)體的位置，Pit是第t次迭代中的最優(yōu)個(gè)體在搜索空間第i維度下的位置，r2∈[0,2π]；r3∈[0,2]；r4∈[0,1]。r1為：

(2)

其中，a作為一個(gè)常數(shù)，通常設(shè)置為2，t，T分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)。

參數(shù)r1在算法的更新過(guò)程中，通過(guò)改變數(shù)值大小，以此平衡算法的探索階段和開(kāi)發(fā)階段，當(dāng)r1>1時(shí)，算法的探索能力增強(qiáng)，反之，算法的開(kāi)發(fā)能力增強(qiáng)。參數(shù)r2可以改變算法中個(gè)體在下一代更新中的步長(zhǎng)。參數(shù)r3具有調(diào)節(jié)算法在更新過(guò)程中對(duì)最優(yōu)個(gè)體的依賴程度，當(dāng)r3<1時(shí)，增加對(duì)最優(yōu)個(gè)體的依賴，反之，則減弱。參數(shù)r4的作用則是等概率的切換算法的更新方式。

2 自適應(yīng)多策略正余弦算法

現(xiàn)實(shí)中，優(yōu)化問(wèn)題的種類繁多且復(fù)雜，僅僅依靠某一種優(yōu)化算法來(lái)解決這些優(yōu)化問(wèn)題，結(jié)果往往并不能全部滿足人們的需求。因此，多策略改進(jìn)的方式應(yīng)運(yùn)而生，多種策略的學(xué)習(xí)方式可以很大程度上避免算法陷入某一種算法的劣勢(shì)，從而開(kāi)啟了智能優(yōu)化領(lǐng)域的另一個(gè)新的篇章。

2.1 多策略學(xué)習(xí)

1)正余弦優(yōu)化算法更新策略：正余弦算法雖然局部搜索能力不強(qiáng)、收斂精度低，但是其利用隨機(jī)參數(shù)切換算法的更新模式，確保算法具有一定的探索能力，防止算法在更新過(guò)程中過(guò)早收斂。其位置更新公式如下所示：

(3)

2)基于最優(yōu)個(gè)體引導(dǎo)的進(jìn)化策略：該策略以最優(yōu)個(gè)體的位置引導(dǎo)當(dāng)前個(gè)體位置的更新，其更新公式如下所示：

(4)

其中，rand為(0，1)之間的隨機(jī)數(shù)。

3)基于個(gè)體差異引導(dǎo)的進(jìn)化策略：受教學(xué)優(yōu)化算法(TLBO)[6]的啟發(fā)，通過(guò)其他個(gè)體差異更新當(dāng)前位置信息，能夠有效的提高算法的探索能力，避免算法過(guò)早收斂，其位置更新公式為：

(5)

其中，j≠k。

4)基于其他個(gè)體知識(shí)學(xué)習(xí)的進(jìn)化策略：本策略采用差分進(jìn)化的DE/Rand/1/bin[7]的進(jìn)化方式，其優(yōu)勢(shì)是搜索范圍廣，全局收斂速度較強(qiáng)，不易陷入局部最優(yōu)解。該策略類似于遺傳算法的變異操作，這種進(jìn)化策略能夠提高種群的多樣性，在算法進(jìn)化的過(guò)程中，結(jié)合反向?qū)W習(xí)策略，能夠有效地避免過(guò)早的收斂，其表達(dá)式為：

(6)

其中，j≠k≠l。

5)反向?qū)W習(xí)：反向?qū)W習(xí)機(jī)制(Opposition-based learning，OBL)[8]是Tizhoosh教授于2005年提出的一個(gè)新的概念。反向?qū)W習(xí)的主要思想是在當(dāng)前個(gè)體所在的區(qū)域產(chǎn)生反向個(gè)體，并利用反向解提高智能優(yōu)化算法的搜索能力和效率。目前，反向?qū)W習(xí)策略被廣泛的應(yīng)用于各種算法的改進(jìn)中，如反向?qū)W習(xí)的蟻群算法(OACO)[9]、反向?qū)W習(xí)的粒子群算法(OPSO)[10]、反向?qū)W習(xí)的群搜索優(yōu)化算法(OSGO)[11]等。

(7)

其中，ub，lb分別是上下界，Y是當(dāng)前解，Z是當(dāng)前解的反向解。

圖1 算法流程圖

新算法為保證種群的多樣性，在選擇其中一種策略更新之后，結(jié)合反向解，其更新公式為：

(8)

其中，u為(0,1)之間的隨機(jī)數(shù)。

2.2 多策略選擇機(jī)制

為了衡量各個(gè)策略在整個(gè)算法過(guò)程不同階段的優(yōu)劣，本文將引進(jìn)收斂速度和多樣性兩個(gè)指標(biāo)作為評(píng)價(jià)各個(gè)策略的優(yōu)劣。收斂速度反映算法尋找最優(yōu)解的快慢，多樣性反映算法群體之間的差異。

1)多策略算法的收斂速度：算法的收斂速度是通過(guò)比較當(dāng)前代個(gè)體適應(yīng)度比前一代個(gè)體適應(yīng)度的提高程度，可以通過(guò)公式(9)進(jìn)行計(jì)算。

(9)

其中，oldSi表示前一代個(gè)體的收斂速度，oldFiti表示前一代個(gè)體的適應(yīng)度值，F(xiàn)iti是當(dāng)前代個(gè)體的適應(yīng)度值，為防止個(gè)體更新到最優(yōu)解之后Fiti為0，需要設(shè)置一個(gè)比較小的值，ε=E-500。

2)多策略算法的多樣性：歐氏距離，漢明距離，熵等指標(biāo)通常被用來(lái)作為測(cè)量算法的依據(jù)，為了簡(jiǎn)單直觀分析各個(gè)策略的多樣性，本文采用基于所有個(gè)體的歐氏距離來(lái)衡量各個(gè)策略的多樣性。策略的多樣性的計(jì)算公式：

(10)

3)分?jǐn)?shù)計(jì)算：在算法選擇不同策略更新時(shí)，應(yīng)該考慮這種策略是否有效，需要同時(shí)衡量收斂速度和多樣性這兩個(gè)方面，并為策略進(jìn)行“打分”，其計(jì)算表達(dá)式為：

score(k)=norm(d(i))+norm(S(i))

(11)

其中，1≤k≤4，norm(x)表示x的歸一化值。

4)賭輪選擇：為了避免算法在更新過(guò)程中陷入某一種位置更新策略，本文引進(jìn)了賭輪選擇[12]。賭輪選擇是通過(guò)各個(gè)個(gè)體的選擇概率，計(jì)算其累計(jì)概率。由此可知，各個(gè)策略中被選中的概率和得分情況成正比，其選擇概率P(k)的表達(dá)式為：

(12)

2.3 算法流程

由上述分析可知，改進(jìn)的算法流程圖如圖1所示：

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

為了驗(yàn)證自適應(yīng)多策略行為正余弦算法的性能，本實(shí)驗(yàn)將采用18個(gè)經(jīng)典測(cè)試函數(shù)，在win10系統(tǒng)，RAM為8GB，MATLAB R2015b的環(huán)境下進(jìn)行仿真實(shí)驗(yàn)，將自適應(yīng)多策略正余弦算法與JADE[13]，PSOFDR[14]，BSA[15]，TLBO，SCA等算法進(jìn)行比較分析。

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

本文實(shí)驗(yàn)所需的函數(shù)如表1所示。為了保證合理量化各個(gè)算法的性能，各個(gè)算法在同等條件下進(jìn)行測(cè)試，即設(shè)定全部算法具有相同的種群數(shù)目40，而且當(dāng)算法的評(píng)價(jià)次數(shù)達(dá)到150000次時(shí)，算法停止運(yùn)行。

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

3.2 結(jié)果分析

在表2中記錄AMSCA算法與其他優(yōu)化算法JADE,PSOFDR,BSA,TLBO,SCA在30維情況下且每種算法獨(dú)立運(yùn)行10次的最優(yōu)解(Best)、平均值(Mean)、標(biāo)準(zhǔn)差(Std)，并進(jìn)行分析。其中，表2中粗體為最優(yōu)值。為了直觀方便的比較各個(gè)算法的收斂情況，舍棄部分相似的函數(shù)收斂曲線圖，圖2中給出部分具有代表性的函數(shù)曲線圖。

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

算法F4BestMeanStdF5BestMeanStdF6BestMeanStdJADE1.94E-101.27E-081.46E-086.228557.79731.093.55E-156.04E-151.72E-15PSOFDR1.31E-119.90E-092.14E-088.371.04E+011.657.11E-159.24E-153.43E-15BSA1.8112464.759833.1797720.414920.84740.28833.08E-121.85E-111.74E-11TLBO1.03E-507.696E-481.51E-471.79E+0119.45960.79673.55E-153.55E-150SCA1.480431086.21441.49526.987927.604870.42022.38E-130.000950.0034AMSCA?067.996215.022227.901528.267790.3192000

算法F7BestMeanStdF8BestMeanStdF9BestMeanStdJADE000000000PSOFDR20.894131.83876.81301.61E-014.71E-0100.008860.01132BSA7.59E-060.1520.32221.71E-132.01E-112.26E-11000TLBO010.54664.9902000000SCA7.11E-1513.220224.196911.248727.317911.33700.038020.1202AMSCA000000000

算法F10BestMeanStdF11BestMeanStdF12BestMeanStdJADE0.0003811.844237.45351.90E-583.67E-141.16E-139.98E-114.16E-096.09E-09PSOFDR2055.982945.34531.364.06E-801.74E-453.73E-451.43E-111.35E-083.79E-08BSA0.000380.00080.00131.08E-127.49E-081.78E-070.83762.2891.34602TLBO2901.884221.18825.19702.78e-32104.74E-517.05149E-481.25E-47SCA8840.299820.73451.098.93E-232.66E-118.40E-1180.3471178.341077.72AMSCA9263.8210058.02467.2900004.96E-121.57E-11

算法F13BestMeanStdF14BestMeanStdF15BestMeanStdJADE12.543615.32592.3682JADE12.543615.32592.3682JADE12.5436PSOFDR2.15E+014.14E+012.25E+01PSOFDR2.15E+014.14E+012.25E+01PSOFDR2.15E+01BSA22.868945.732723.3222BSA22.868945.732723.3222BSA22.8689TLBO18.649350.679824.6432TLBO18.649350.679824.6432TLBO18.6493SCA428.4972179.231936.79SCA428.4972179.231936.79SCA428.497AMSCA608.9251832.18857.096AMSCA608.9251832.18857.096AMSCA608.925

算法F16BestMeanStdF17BestMeanStdF18BestMeanStdJADE00.23925.70E-01JADE00.23925.70E-01JADE0PSOFDR7.05E-022.071.35PSOFDR7.05E-022.071.35PSOFDR7.05E-02BSA0.00910.28370.3516BSA0.00910.28370.3516BSA0.0091TLBO000TLBO000TLBO0SCA28.541838.83233.84499SCA28.541838.83233.84499SCA28.5418AMSCA000AMSCA000AMSCA0

從表2中的數(shù)據(jù)和圖2中的函數(shù)收斂曲線可以看出，AMSCA算法的性能整體優(yōu)于SCA算法，且AMSCA算法對(duì)上述18個(gè)基準(zhǔn)函數(shù)中的F1～F3,F6～F9,F11,F14～F17等12個(gè)函數(shù)求解到理論上的最優(yōu)值。由表2中的均值和標(biāo)準(zhǔn)差可知，AMSCA算法的測(cè)試結(jié)果優(yōu)于SCA算法，表明改進(jìn)策略能夠提高SCA算法的求解精度和魯棒性。

由表2可知，AMSCA算法與JADE,PSOFDR,BSA以及TLBO算法相比，在F1～F3,F6,F7,F11,F14～F17等10個(gè)函數(shù)的實(shí)驗(yàn)結(jié)果中，AMSCA算法的求解精度遠(yuǎn)高于JADE,PSOFDR,BSA這三種算法，而且標(biāo)準(zhǔn)差也達(dá)到了理論上的最小值，這說(shuō)明AMSCA算法的性能穩(wěn)定，魯棒性較強(qiáng)。與TLBO算法相比，雖然AMSCA算法在F4～F5,F12三個(gè)函數(shù)上表現(xiàn)得不如TLBO算法，從整體分析，AMSCA算法的性能優(yōu)于TLBO算法。但是，AMSCA算法對(duì)F4,F5,F10,F12,F13和F18這6個(gè)函數(shù)的優(yōu)化時(shí)并不能展現(xiàn)出良好的性能，這說(shuō)明AMSCA算法在優(yōu)化復(fù)雜問(wèn)題時(shí)，性能有待提升。

圖2 函數(shù)收斂曲線

綜合以上分析可知，AMSCA能獲得比較好的優(yōu)化性能，特別是在優(yōu)化精度和魯棒性方面，明顯優(yōu)于其他優(yōu)化算法。

4 結(jié) 語(yǔ)

本文提出了一種自適應(yīng)多策略正余弦算法。通過(guò)計(jì)算各個(gè)策略的收斂速度和多樣性作為某種策略的指標(biāo)，利用賭輪選擇機(jī)制，避免算法陷入單一策略，在整個(gè)算法的更新過(guò)程中，根據(jù)各項(xiàng)指標(biāo)合理選擇出當(dāng)前階段最適合的策略。實(shí)驗(yàn)結(jié)果表明，自適應(yīng)多策略正余弦算法的整體性能優(yōu)于其他優(yōu)化算法，但在處理一些復(fù)雜函數(shù)上，并不能表現(xiàn)出優(yōu)異的性能，這也為SCA算法的改進(jìn)提供了新的方向。