孔 芝, 李事成, 趙 杰

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

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

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

1 珊瑚礁算法

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

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

②外部有性繁殖和內部有性繁殖:珊瑚蟲產(chǎn)生子代的方式分為兩種,即外部有性繁殖和內部有性繁殖;其比例分別為ξ和1-ξ,即外部有性繁殖的珊瑚蟲個數(shù)為M×ρ×ξ,內部有性繁殖的珊瑚蟲個數(shù)為M×ρ×(1-ξ).外部有性繁殖的子代由雌雄異體的兩個親代產(chǎn)生,如式(1)所示;內部有性繁殖的子代由雌雄同體產(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ù);φ為隨機變量,其產(chǎn)生方式如下:

(3)

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

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

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

⑤毀滅機制:再一次進行適應度排序,選出比例為δ的低適應度珊瑚蟲,將其毀滅.

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

2 改進的珊瑚礁算法

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

2.1 內部有性繁殖方式改進

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

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

2.2 無性繁殖方式改進

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

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

(6)

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

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

2.3 更替方式改進

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

(7)

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

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

改進珊瑚礁算法具體步驟如下:

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

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

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

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

⑤毀滅機制:與CRO算法相同.

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

3 仿真實驗與結果分析

3.1 實驗參數(shù)設置

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

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

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

3.2 實驗結果分析

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

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

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

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

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

表3 測試函數(shù)的實驗結果Table 3 Experimental results of test function

續(xù)表3

4 結 語

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