珊瑚礁算法的改進(jìn)研究

孔 芝, 李事成, 趙 杰

(東北大學(xué)秦皇島分校 控制工程學(xué)院, 河北 秦皇島 066004)

珊瑚礁優(yōu)化(coral reef optimization,CRO)算法是Salcedo-Sanz等[1]在2013年，受到珊瑚蟲繁衍生存過程的啟發(fā)而提出的一種智能優(yōu)化算法,用于處理多峰值函數(shù)優(yōu)化問題.2014年，Pastor-Sanchez等[2]提出一種基于混合珊瑚礁-極限學(xué)習(xí)機(jī)的方法,并將其應(yīng)用于風(fēng)速預(yù)測系統(tǒng)中的特征選擇,體現(xiàn)出優(yōu)異的性能.2015年,Salce-Sanz等[3]提出一種具有和聲搜索算子的珊瑚礁優(yōu)化算法,并將其應(yīng)用于風(fēng)速預(yù)測中,得到良好結(jié)果.2016年, Pastor-Sanchez等[4]將珊瑚礁優(yōu)化算法應(yīng)用于多目標(biāo)優(yōu)化問題中,在計(jì)算資源有限的情況下表現(xiàn)出優(yōu)異性能.同年, Salcedo-Sanz等[5]將珊瑚礁算法應(yīng)用于微電網(wǎng)最佳電池優(yōu)化調(diào)度問題,大大節(jié)省了總電費(fèi).2017年,Magdaleno等[6]利用珊瑚礁優(yōu)化算法對調(diào)諧質(zhì)量阻尼器進(jìn)行結(jié)構(gòu)振動控制,產(chǎn)生了極好的效果.同年,Jimenez-Fernandez等[7]提出一種物種珊瑚礁優(yōu)化算法,并將其有效地應(yīng)用于太陽能全球輻射重要參數(shù)縮減中.2018年,Duran-Rosal等[8]將珊瑚礁優(yōu)化算法應(yīng)用于縮減時(shí)間序列最佳尺寸中,顯示出強(qiáng)大的分割能力.

目前為止,人們已經(jīng)提出了許多改進(jìn)的珊瑚礁優(yōu)化算法[9-12],但這些算法在精度、收斂速度與避免陷入局部最優(yōu)能力方面仍有待進(jìn)一步提高.本文提出一種改進(jìn)的珊瑚礁(improved coral reef optimization,ICRO)算法,通過對原珊瑚礁優(yōu)化算法內(nèi)部有性繁殖、無性繁殖和更替機(jī)制的改進(jìn),可以有效避免算法陷入局部最優(yōu),提高精度,并通過具體的測試函數(shù)證明了算法的優(yōu)越性.

1 珊瑚礁算法

珊瑚礁優(yōu)化算法是受到珊瑚蟲繁衍生存過程的啟發(fā)而提出的一種元啟發(fā)式算法.珊瑚礁優(yōu)化算法基本執(zhí)行過程如下[13]:

①初始化:假設(shè)存在大小為M的珊瑚礁,即礁上存在M個節(jié)點(diǎn)空間供珊瑚蟲生存;開始時(shí),珊瑚礁上已有比例為ρ的空間被珊瑚蟲占據(jù),即礁上珊瑚蟲的個數(shù)為M×ρ.

②外部有性繁殖和內(nèi)部有性繁殖:珊瑚蟲產(chǎn)生子代的方式分為兩種,即外部有性繁殖和內(nèi)部有性繁殖;其比例分別為ξ和1-ξ,即外部有性繁殖的珊瑚蟲個數(shù)為M×ρ×ξ,內(nèi)部有性繁殖的珊瑚蟲個數(shù)為M×ρ×(1-ξ).外部有性繁殖的子代由雌雄異體的兩個親代產(chǎn)生,如式(1)所示;內(nèi)部有性繁殖的子代由雌雄同體產(chǎn)生,如式(2)所示.

c1,α=[(1+φ)C1,α+(1-φ)C2,α]/2 ,c2,α=[(1-φ)C1,α+(1+φ)C2,α]/2 ，α=1,…,ψ.}

(1)

(2)

式中:C1和C2表示兩個雌雄異體珊瑚蟲,c1和c2表示其產(chǎn)生的兩個子代;C表示雌雄同體珊瑚蟲,c表示其產(chǎn)生的子代;α為迭代次數(shù);φ為隨機(jī)變量,其產(chǎn)生方式如下:

(3)

式中:κ為交叉常數(shù);τ為0到1的隨機(jī)數(shù).

③更替機(jī)制:新產(chǎn)生的子代珊瑚蟲需要占據(jù)珊瑚礁生存,此時(shí)珊瑚礁上有未被占據(jù)和已被占據(jù)的空間,其數(shù)量分別為M×(1-ρ)和M×ρ.若子代選擇未被占據(jù)珊瑚礁,則可直接占據(jù);若子代選擇已被占據(jù)的珊瑚礁,則需與其上原有珊瑚蟲進(jìn)行適應(yīng)度f(p)比較:若子代適應(yīng)度高則占據(jù)該處,否則失敗,繼續(xù)嘗試其他空間;若在最大占據(jù)次數(shù)μ內(nèi)未完成占據(jù),則子代珊瑚蟲死亡.

④無性繁殖:當(dāng)所有子代珊瑚蟲完成珊瑚礁占據(jù)后,對現(xiàn)有珊瑚礁上的珊瑚蟲進(jìn)行適應(yīng)度排序,選出比例為γ的高適應(yīng)度珊瑚蟲,讓其通過無性繁殖(復(fù)制)的方式產(chǎn)生子代,并進(jìn)行珊瑚礁的占據(jù).

⑤毀滅機(jī)制:再一次進(jìn)行適應(yīng)度排序,選出比例為δ的低適應(yīng)度珊瑚蟲,將其毀滅.

進(jìn)入循環(huán),重復(fù)步驟②～⑤,直至滿足終止條件,即達(dá)到最大迭代次數(shù)ψ.得出最優(yōu)解.

2 改進(jìn)的珊瑚礁算法

為了克服珊瑚礁優(yōu)化算法的不足,本文對珊瑚礁優(yōu)化算法進(jìn)行了改進(jìn),主要涉及三個方面:內(nèi)部有性繁殖方式、無性繁殖方式和更替方式.

2.1 內(nèi)部有性繁殖方式改進(jìn)

原始珊瑚礁算法的內(nèi)部有性繁殖方式為遺傳算法等經(jīng)典算法傳統(tǒng)意義上的變異方式,其受自身的影響較大,且變優(yōu)趨勢是隨機(jī)的,不利于收斂.粒子群優(yōu)化(PSO)算法是受到飛鳥集群活動規(guī)律性的啟發(fā),進(jìn)而利用群體智能建立的一個簡化模型,它通過追隨當(dāng)前搜索到的最優(yōu)個體來尋找全局最優(yōu);而改進(jìn)粒子群優(yōu)化(IPSO)算法[14]是對PSO算法的更替方式進(jìn)行了改進(jìn),具有向優(yōu)收斂效果好、收斂速度快的優(yōu)點(diǎn).因此在CRO算法內(nèi)部有性繁殖部分加入IPSO算法的改進(jìn)以提高其向優(yōu)收斂效果和收斂速度.本文受IPSO算法的啟發(fā),將內(nèi)部有性繁殖公式(2)改為公式(4)和公式(5).

xi,j(t+1)=xi,j(t)+2r1[pbest(t)-xi,j(t)] ,

(4)

xi,j(t+1)=xi,j(t)+2r2[gbest(t)-xi,j(t)] .

(5)

改進(jìn)后的珊瑚礁算法以自身最優(yōu)珊瑚蟲和全局最優(yōu)珊瑚蟲為參考對象,減少了差解的占比,并且設(shè)置了與代數(shù)相關(guān)的選擇概率;前期有利于局部搜索,后期有利于全局搜索,不僅保持種群多樣性,還提高了向優(yōu)收斂速度.

2.2 無性繁殖方式改進(jìn)

原無性繁殖部分是將當(dāng)前所有珊瑚蟲中最好的珊瑚蟲按比例γ進(jìn)行完全復(fù)制,產(chǎn)生幼蟲.這樣雖然增加了優(yōu)秀珊瑚蟲的比例,但使種群更容易陷入局部最優(yōu),不利于后期進(jìn)一步搜索和提高精度.高斯變異是重點(diǎn)搜索原個體附近的某個局部區(qū)域,具有提高精度的優(yōu)點(diǎn);因此在CRO無性繁殖部分加入高斯變異,以提高搜索精度.本文受高斯變異[15]的啟發(fā),將無性繁殖方式改進(jìn)為式(6).

xi=gbest,i+gbest,i·N(0,1) .

(6)

式中:i為比例為γ的高適應(yīng)度珊瑚蟲的序號;gbest, i表示從當(dāng)前最優(yōu)到次優(yōu)依次排列的解;N(0,1)為正態(tài)分布.

改進(jìn)后的無性繁殖部分不是單純地復(fù)制最優(yōu)珊瑚蟲,而是按高斯變異的方式在最優(yōu)解附近根據(jù)正態(tài)分布變異,這種變異方式在搜索后期種群趨于穩(wěn)定后,仍可以對最優(yōu)解進(jìn)行微調(diào),進(jìn)一步提高搜索精度.

2.3 更替方式改進(jìn)

原始珊瑚礁算法的更替方式為比較子代珊瑚蟲與父代珊瑚蟲的適應(yīng)度大小,若子代適應(yīng)度更好則代替父代,否則不代替.這種單純的優(yōu)勢代替劣勢,雖然使種群向優(yōu)勢種群收斂,但大大縮減了種群的多樣性,未考慮到劣勢種群的潛力,對于多峰值函數(shù)問題,極易陷入局部最優(yōu).模擬退火算法來源于固體退火原理,具有保留種群多樣性、易于跳出局部最優(yōu)的優(yōu)點(diǎn).因此在CRO更替方式部分加入模擬退火算法改進(jìn)以保留其種群多樣性,提高其跳出局部最優(yōu)的能力.本文受到模擬退火算法[16]的啟發(fā)對其進(jìn)行改進(jìn),將更替方式改為式(7).

(7)

式中:fi為第i個珊瑚蟲的適應(yīng)度;i+1為第i個珊瑚蟲的子代;T表示溫度,溫度隨著代數(shù)的增長而下降,即T=0.7T.適用度的值越小,表示適應(yīng)度越好,當(dāng)子代適應(yīng)度好于父代時(shí),子代代替父代(即代替概率P為1);當(dāng)子代適用度未好于父代時(shí),以代替概率P代替父代.

改進(jìn)后珊瑚礁算法的更替方式,不再是單純地優(yōu)勢代替劣勢,而是以一定的概率保留了適應(yīng)度差的珊瑚蟲,使其可以在下一代中作為父代產(chǎn)生新的子代珊瑚蟲,增加了前期種群的多樣性,避免種群因收斂過快而陷入局部最優(yōu);即使在后期種群陷入某個峰值,也有一定概率跳出局部最優(yōu).

改進(jìn)珊瑚礁算法具體步驟如下:

①初始化:同CRO算法相同.

②外部有性繁殖和內(nèi)部有性繁殖:外部有性繁殖方式與CRO算法相同,內(nèi)部有性繁殖方式采用式(4)和式(5).

③更替機(jī)制:更替方式采用式(7).

④無性繁殖:無性繁殖方式采用式(6).

⑤毀滅機(jī)制:與CRO算法相同.

⑥進(jìn)入循環(huán),重復(fù)步驟②～⑤,直至滿足終止條件,即達(dá)到最大迭代次數(shù).得出最優(yōu)解.

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)環(huán)境為64位操作系統(tǒng),內(nèi)存為4 GB,CPU為Inter(R)Core(TM)i5-3337U@1.80 GHz,程序采用MATLAB 2014a 編程實(shí)現(xiàn).

將本文算法與原始珊瑚礁優(yōu)化算法(CRO)[17]、高斯變異珊瑚礁優(yōu)化算法(CRO(G))、柯西變異珊瑚礁優(yōu)化算法(CRO(C))、高斯與柯西變異珊瑚礁優(yōu)化算法(CRO(GC))[18]、粒子群優(yōu)化算法(PSO)[19]、改進(jìn)權(quán)重粒子群優(yōu)化算法(IWPSO)、改進(jìn)粒子群優(yōu)化算法(IPSO)[14]、飛蛾撲火優(yōu)化算法(MFO)[20]、多神經(jīng)優(yōu)化算法(MVO)[21]和正余弦優(yōu)化算法(SCA)[22]在測試函數(shù)下進(jìn)行比較.

在仿真實(shí)驗(yàn)中,統(tǒng)一設(shè)置種群規(guī)模為30,最大迭代次數(shù)為1 000.低維測試函數(shù)見表1,高維測試函數(shù)見表2.各算法均實(shí)驗(yàn)30次,求其平均值與標(biāo)準(zhǔn)差.針對15個低維和5個高維測試函數(shù),算法結(jié)果見表3,對應(yīng)的平均值曲線見圖1.由于CRO(GC)已在文獻(xiàn)[18]中被證明優(yōu)于CRO(G)和CRO(C)，因此本文表中未列出CRO(G)和CRO(C)的數(shù)據(jù).

3.2 實(shí)驗(yàn)結(jié)果分析

針對低維測試函數(shù),從表3可以看出,ICRO在測試函數(shù)f1上要明顯好于CRO,PSO,IWPSO,IPSO,MFO,MVO和SCA算法,并且從圖1的f1可以看出其收斂速度極快,僅僅比CRO(C)差一點(diǎn).在測試函數(shù)f2上,ICRO要明顯好于CRO,IWPSO和MFO算法,比CRO(G),CRO(C)和MVO精確度更高,雖與SCA算法在平均值上相等,但標(biāo)準(zhǔn)差要比SCA算法更精確,比IPSO要稍差,但從圖1的f2可以看出其收斂速度比IPSO要快得多,在第12代即達(dá)到穩(wěn)定.而在測試函數(shù)f3上,雖然CRO(G),CRO(GC),IWPSO,MVO和SCA可以達(dá)到較好效果,CRO(C)能夠達(dá)到8.3526E-15,但I(xiàn)CRO可以達(dá)到平均值和標(biāo)準(zhǔn)差都為0,且從圖1的f3可以看出,ICRO穩(wěn)定后在780代時(shí)跳出局部最優(yōu),進(jìn)一步搜索最優(yōu)值.針對測試函數(shù)f4和f9這種很難得到滿意最優(yōu)值的函數(shù),ICRO對于f4可以達(dá)到3.986 6E-06,且從圖1的f4可以明顯看出ICRO曲線的波動,很好地展示了其跳出局部最優(yōu)的能力,對于f9,甚至可以達(dá)到平均值與標(biāo)準(zhǔn)差都為0,且圖1的f9進(jìn)一步證明其跳出局部最優(yōu)的能力.針對測試函數(shù)f5,PSO,IWPSO,MFO,MVO和ICRO都可以達(dá)到理論最優(yōu)值-1.801 3,而ICRO算法與效果最好的IPSO和MFO達(dá)到了相同的平均值和標(biāo)準(zhǔn)差,且從圖1的f5可以看出其收斂速度明顯好于這兩種算法,其在第10代達(dá)到穩(wěn)定,而IPSO和MVO在100代左右才達(dá)到穩(wěn)定.針對測試函數(shù)f6,雖然從圖1的f6可以看到ICRO具有極高的收斂速度，但其精確度較差,與大部分對比算法一樣未能達(dá)到1以下的效果,而IPSO可以精確到0.04.在測試函數(shù)f7,f11,f13,f14和f15上,ICRO算法精確度要明顯好于其他算法.針對測試函數(shù)f8,ICRO可以達(dá)到0.039 51,且具有較高的收斂速度,比大部分算法要好,但SCA達(dá)到了1.525 1E-5.在測試函數(shù)f10上,雖然SCA達(dá)到了2.903 0E-245,但I(xiàn)CRO更加精確,達(dá)到了1.510 3E-251,且標(biāo)準(zhǔn)差為0.在測試函數(shù)f12上,ICRO能與對比算法中效果最好的IPSO達(dá)到相同的平均值,在標(biāo)準(zhǔn)差上稍微差一點(diǎn),但從圖1的f12可以看出其收斂速度明顯好于IPSO.

表1 低維測試函數(shù)Table 1 Low-dimensional test functions

表2 高維測試函數(shù)Table 2 High-dimensional test functions

針對高維函數(shù),從表3可看出,在測試函數(shù)f16上,ICRO也能達(dá)到最優(yōu)的效果.在測試函數(shù)f17上,雖然CRO(G)可以達(dá)到7.401 5E-18,但I(xiàn)CRO在平均值和標(biāo)準(zhǔn)差上都達(dá)到0.且從圖1的f17可以看出其收斂速度極快.在測試函數(shù)f18上可以看出,ICRO雖然收斂速度極快,但收斂精度效果有待提高.在測試函數(shù)f19上可以看出大部分算法都達(dá)不到一個較好的平均值,雖然CRO(C)平均值達(dá)到了5.199 3E-11,但I(xiàn)CRO可以在平均值和標(biāo)準(zhǔn)差上都達(dá)到0.在測試函數(shù)f20上,即使維度提高到1 000,ICRO仍然能達(dá)到算法中的最優(yōu)效果8.881 8E-16.

總的來說,在所有測試函數(shù)中ICRO都具有極高的收斂速度,這要?dú)w功于ICRO在內(nèi)部有性繁殖部分的改進(jìn),既保留了種群多樣性,又極大地提高了收斂速度.在測試函數(shù)f1,f3,f4,f5,f7,f9,f10,f11,f13,f14,f15,f16,f17,f18和f20中,ICRO的精度都是最高的,這要?dú)w功于其無性繁殖部分的改進(jìn),大大提高了搜索精度.此外,在測試函數(shù)f3,f4和f9上,ICRO很好地展示了其跳出局部最優(yōu)的能力,這要?dú)w功于其更替方式的改進(jìn),一定程度上豐富了種群的多樣性,避免因種群收斂過快而陷入局部最優(yōu),即使其陷入了某個峰值,也有很高的概率跳出局部最優(yōu).

表3 測試函數(shù)的實(shí)驗(yàn)結(jié)果Table 3 Experimental results of test function

續(xù)表3

4 結(jié) 語

本文針對現(xiàn)有珊瑚礁算法存在的不足,提出了改進(jìn)的珊瑚礁算法,在測試函數(shù)下證明了其相比其他算法可以更好地跳出局部最優(yōu),有效地改善了其原本易于陷入局部最優(yōu)的缺點(diǎn).相比其他算法,改進(jìn)的珊瑚礁算法還具有更快的收斂速度和更高的搜索精度,即使在高維測試函數(shù)下仍然可以保持良好的性能.