一種基于反向?qū)W習(xí)和伯恩斯坦算子的差分進(jìn)化算法

熊聰聰，楊曉藝，王 丹，李俊偉，管祥爍

(天津科技大學(xué)人工智能學(xué)院，天津300457)

差分進(jìn)化(differential evolution，DE)算法[1]是一種模仿生物群體進(jìn)化的全局優(yōu)化算法．與其他進(jìn)化算法相同，DE算法也是在一個隨機(jī)生成的初始種群中開始搜索，通過變異、交叉、選擇操作產(chǎn)生下一代的種群，不斷迭代求解，直至找到最終解．因其具有模型簡單、收斂性能好、魯棒性強(qiáng)等特點(diǎn)，被應(yīng)用到模式識別、數(shù)據(jù)挖掘、人工智能等各個領(lǐng)域[2-3]．DE算法與其他群體智能算法相比具有很多優(yōu)點(diǎn)，但隨著研究者的不斷深入探索，發(fā)現(xiàn)差分進(jìn)化算法在參數(shù)設(shè)置中存在著計(jì)算開銷大、收斂過程中存在著易陷入局部最優(yōu)和收斂精度不高的缺陷．

針對上述問題，很多研究者對算法進(jìn)行改進(jìn)，不斷提高算法的收斂速度和精度．比如，為了避免結(jié)構(gòu)參數(shù)的試錯過程中計(jì)算消耗大，Wang等[4-5]提出的算法可以使每個個體在參數(shù)池中隨機(jī)選擇參數(shù)作為結(jié)構(gòu)參數(shù)，而基于正交算子的差分進(jìn)化(orthogonal crossover differential evolution，OXDE)算法使用正交交叉概率作為結(jié)構(gòu)參數(shù)．但這些結(jié)構(gòu)參數(shù)的選擇方式都是人為設(shè)置的，由于缺乏經(jīng)驗(yàn)而導(dǎo)致的穩(wěn)定性不足還是無法避免的．于是，研究人員提出了基于自適應(yīng)的參數(shù)調(diào)節(jié)方式和隨機(jī)設(shè)置參數(shù)的方法，如Zhang等[6]提出了基于學(xué)習(xí)的變異和交叉概率的調(diào)整方法，在學(xué)習(xí)進(jìn)化過程中成功找到縮放因子和交叉概率等參數(shù)信息；Civicioglu等[7]提出了一種非遞歸并且無參數(shù)的差分進(jìn)化(Bernstain-search different evolution，BSD)算法，這種方法沒有設(shè)置控制參數(shù)的過程，使算法更加簡單、高效．

但是，上述算法只是對結(jié)構(gòu)參數(shù)的改進(jìn)，對算法性能的提升有限．為了解決差分進(jìn)化算法在進(jìn)化過程中陷入局部最優(yōu)導(dǎo)致收斂速度過慢的問題，Zhu等[8]提出了一種混合交叉算法，該多目標(biāo)進(jìn)化算法通過差分變異策略構(gòu)造出自適應(yīng)混合交叉算子，使多目標(biāo)進(jìn)化算法的全局與局部的搜索能力得到均衡；童旅楊等[9]通過使用多個差分變異算子增加種群的多樣性，從而避免了差分進(jìn)化算法在進(jìn)化過程中易于陷入局部最優(yōu)的問題；Zhang等[10]提出了一種具有排序選擇的差分進(jìn)化(differential evolution with a rank-up selection，RUSDE)算法；錢崢遠(yuǎn)等[11]提出了一種精英化島嶼的種群差分進(jìn)化算法，實(shí)現(xiàn)了全局搜索和局部搜索能力并重，使算法具有較強(qiáng)的搜索能力與穩(wěn)定性.

雖然上述文獻(xiàn)中提出的改進(jìn)算法在進(jìn)化時相對于傳統(tǒng)DE算法的性能有了一定的提升，但對算法的改進(jìn)比較單一，存在著對算法性能提升不足的問題．基于此，本文提出了一種結(jié)合參數(shù)改進(jìn)與進(jìn)化策略改進(jìn)的算法，即基于反向?qū)W習(xí)和伯恩斯坦算子的差分進(jìn)化算法(differential evolution algorithm based on opposition-based learning and Bernstain operator，BODE)．通過對國際標(biāo)準(zhǔn)測試函數(shù)進(jìn)行測試實(shí)驗(yàn)，將BODE與已有的優(yōu)化算法進(jìn)行了性能比較，結(jié)果表明本算法在搜索速度以及搜索最優(yōu)值的精度上更具有優(yōu)勢．

1 預(yù)備知識

1.1 伯恩斯坦多項(xiàng)式

伯恩斯坦多項(xiàng)式(Bernstain polynomial)[12]是逼近連續(xù)函數(shù)的一系列多項(xiàng)式，它們可以自然地組合成近似于[0，1]上的任何連續(xù)函數(shù)．二階伯恩斯坦多項(xiàng)式定義為

其中：n為迭代次數(shù)；t為成功的概率，取值范圍為[0，1]；s為迭代 n次后實(shí)驗(yàn)成功的概率；．通過這個式子可以將固定概率和可變成功次數(shù)轉(zhuǎn)移到固定成功次數(shù)和可變概率中．通過式(2)可生成(n＋1)大小的n次伯恩斯坦多項(xiàng)式．其中s＜0并且s＞n，Bs,n＝0．

圖1為0≤t≤1時二階伯恩斯坦多項(xiàng)式曲線圖．

圖1 0≤t≤1時二階伯恩斯坦多項(xiàng)式曲線圖Fig. 1 2nd degree Bernstain polynomials when 0≤t≤1

1.2 反向?qū)W習(xí)策略

反向?qū)W習(xí)(opposition-based learning，OBL)策略[13]是反向解與當(dāng)前解相比較，有高出近50%的概率更靠近全局最優(yōu)值．反向?qū)W習(xí)策略的主要思想是對問題進(jìn)行求解x時，初始值x是通過經(jīng)驗(yàn)積累或者是單純的隨機(jī)猜想，可以同時使用x的相反值嘗試得到更好的解x*，使得下一代x能夠更快逼近最優(yōu)解．在種群的進(jìn)化過程中，如果該個體對應(yīng)的反向個體的適應(yīng)值優(yōu)于該個體的適應(yīng)值，則反向個體替代該個體，并進(jìn)入下一代種群．反向?qū)W習(xí)策略有助于更快地找到最優(yōu)解，并加快優(yōu)化算法的收斂速度．

定義1 普通反向?qū)W習(xí)(generalized oppositionbased learning，GOBL)．假設(shè)當(dāng)前個體 xi(t)在其反向個體第j維上，可定義為

定義2 改進(jìn)的反向?qū)W習(xí)(improved oppositionbased learning，IOBL)[14]．假設(shè)當(dāng)前個體 xi(t)=(xi1,xi2,…,xiD)是當(dāng)前種群中的第i個個體，則對應(yīng)的反向個體可定義為

其中：xij屬于和k2為(0,1)之間的隨機(jī)數(shù)；表示個體xij在第j維的區(qū)間，具體表示為

本文對算法改進(jìn)所選擇的反向?qū)W習(xí)策略為普通反向?qū)W習(xí)策略．

1.3 差分進(jìn)化算法

差分進(jìn)化算法是一種基于種群和定向搜索的優(yōu)化算法，采用浮點(diǎn)矢量編碼生成種群，主要步驟為初始化、變異、交叉和選擇．通過個體間的差異獲得變異個體，將變異個體按照確定的交叉策略與初始個體進(jìn)行基因互換后得到交叉?zhèn)€體，選擇適應(yīng)值更好的個體作為新一代種群中的個體，從而在種群的進(jìn)化過程中隨機(jī)搜索，直至找到最優(yōu)值．DE有幾種最基本的形式，本文所用的是DE算法中使用最為廣泛的一種“DE/rand/1/bin”．

初始化：在D維空間中，假設(shè)種群P由N個個體組成，初始的種群在中產(chǎn)生，即

其中：Uj為搜索空間的最大值，Lj為搜索空間的最小值，r and(0,1)是在(0,1)之間產(chǎn)生的一個服從均勻分布的隨機(jī)數(shù)．

變異：對當(dāng)前種群中的每個個體 Pi(G)產(chǎn)生與之對應(yīng)的變異個體Vi(G)．F是縮放因子，決定了種群個體差分的步長．F值較大會增強(qiáng)算法的全局搜索能力，但會降低算法的收斂速度；F值較小會導(dǎo)致個體間差異較小，從而使得算法易于陷入局部最優(yōu)．變異操作可表示為

其中：G為迭代次數(shù)，r1、r2和r3為集合{1 ,2,…,N } 中任意兩兩之間互不相等的隨機(jī)數(shù)．

交叉：將種群中個體的部分基因與變異個體的部分基因按照規(guī)則交換，以提高種群的多樣性．C為交叉概率，C值越大，交叉?zhèn)€體Ui(G)從變異個體Vi(G)中獲得的基因越多，從而更接近變異個體，全局收斂的能力變強(qiáng)，但是會降低收斂速度；C值越小，全局收斂能力會越低，容易陷入局部最優(yōu)．交叉過程可表示為

其中：r andj(0,1)為(0,1)之間的任意隨機(jī)數(shù)，jrand為[1 ,D]內(nèi)的隨機(jī)整數(shù)．

選擇：將所需要求解的問題換成適應(yīng)度函數(shù)，越接近目標(biāo)個體，適應(yīng)度越?。畬?dāng)前種群中個體的適應(yīng)度 f(Xi(G))與相應(yīng)的實(shí)驗(yàn)個體 f(Ui(G))的適應(yīng)度相比較，如果實(shí)驗(yàn)個體的適應(yīng)度小于或等于當(dāng)前個體的適應(yīng)度，則選擇實(shí)驗(yàn)個體進(jìn)入下一代種群．選擇操作可表示為

其中 f (.)為適應(yīng)度函數(shù)，函數(shù)的具體形式是由求解的問題決定的．

2 改進(jìn)算法

差分進(jìn)化算法的性能與結(jié)構(gòu)參數(shù)值F和C的選擇有很大程度上的依賴性，在進(jìn)化過程中也存在陷入局部最優(yōu)而導(dǎo)致收斂速度降低的問題．本文提出一種改進(jìn)算法為基于反向?qū)W習(xí)和伯恩斯坦算子的差分進(jìn)化算法(differential evolution algorithm based on opposition-based learning and Bernstain operator，BODE)．利用反向?qū)W習(xí)產(chǎn)生反向群體，擴(kuò)大了種群的搜索空間，為找到潛在的最優(yōu)個體提供更多機(jī)會，避免算法進(jìn)化過程中容易陷入局部最優(yōu)的問題；通過伯恩斯坦多項(xiàng)式隨機(jī)產(chǎn)生結(jié)構(gòu)參數(shù)并控制變異和交叉的過程，避免參數(shù)確定導(dǎo)致的試錯過程，增強(qiáng)了個體的尋優(yōu)能力，從而節(jié)省了搜索時間．

算法1：BODE算法

1. 輸入：隨機(jī)向量Xi．

2. 輸出：個體的位置信息．

3. BEGIN．

4. 隨機(jī)初始化種群．

5. 按照反向?qū)W習(xí)策略生成反向種群．

6. 計(jì)算種群中個體的適應(yīng)值，選擇適應(yīng)值更好的個體作為下一代種群．

7. WHILE(終止條件是否滿足)．

8. 由伯恩斯坦算子控制生成突變控制矩陣M．

9. 由伯恩斯坦算子控制生成進(jìn)化步長F．

10. 生成實(shí)驗(yàn)個體．

11. 判斷實(shí)驗(yàn)個體邊界．

12. 由反向?qū)W習(xí)策略實(shí)現(xiàn)反向跳轉(zhuǎn)．

13. 更新個體．

14. END WHILE．

15. 得到最優(yōu)個體．

16. END．

基于反向?qū)W習(xí)和伯恩斯坦算子的差分進(jìn)化算法具體流程如下：

(1)在初始化階段，按照式(7)產(chǎn)生種群P，同時按照式(11)產(chǎn)生反向種群P′，在種群P和P′中選擇適應(yīng)值更好的個體組成初始種群．

(2)BODE通過式(12)和式(13)突變控制矩陣M．M的初始值由式(12)定義．

其中：隨機(jī)數(shù)ρ的取值由式(2)產(chǎn)生，u向量為

permute(1 :D)函數(shù)可以隨機(jī)交換(.)中元素的序列．

(3)在BODE中的進(jìn)化步長F定義為其中：k2、k3、η和λ是在每次調(diào)用時產(chǎn)生的隨機(jī)值，矩陣Q是全1矩陣．

(4)在BODE中，實(shí)驗(yàn)個體的生成階段是一個隨機(jī)交叉的過程，按照式(16)生成實(shí)驗(yàn)個體．

(5)如果實(shí)驗(yàn)個體超過了搜索范圍，即Ti,j＜Lj或者Ti,j＞Uj，則個體采用式(17)進(jìn)行更新，其中δ為(0,1)之間的隨機(jī)數(shù)．(6)按照式(18)生成反向跳轉(zhuǎn)的個體，Wmin和Wmax分別為當(dāng)前種群中個體的最小值和最大值．

(7)分別求出實(shí)驗(yàn)個體、反向?qū)嶒?yàn)個體和原個體的適應(yīng)度，按照式(10)選擇適應(yīng)度更好的個體組成新一代種群．

算法2：反向?qū)W習(xí)策略

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

為了驗(yàn)證改進(jìn)后算法的性能，選擇了6種比較經(jīng)典的測試函數(shù)，主要分為兩大類，其中f1—f3為單峰函數(shù)，f4—f6為多峰函數(shù)，見表1．

表1 6種測試函數(shù)Tab. 1 Six benchmark functions

3.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

實(shí)驗(yàn)環(huán)境：Win 10操作系統(tǒng)，運(yùn)行內(nèi)存為8GB，運(yùn)行軟件為MATLAB 2017a．

基本參數(shù)設(shè)置：種群大小N＝48，種群個體的維度D＝30，最大迭代次數(shù)為5000次，各算法獨(dú)立運(yùn)行次數(shù)為20次，縮放因子F＝0.5，交叉概率C＝0.9．

3.2 仿真實(shí)驗(yàn)結(jié)果

BODE算法與DE算法、粒子群優(yōu)化(particle swarm optimization，PSO)算法及BSD算法的比較結(jié)果見表2，其中PSO算法的實(shí)驗(yàn)結(jié)果來源于文獻(xiàn)[15]．

表2 4種算法在6個測試函數(shù)的實(shí)驗(yàn)結(jié)果Tab. 2 Experimental results of four algorithms on six benchmark functions

由表2可知，BODE算法不僅在單峰函數(shù)f1—f3中有絕對優(yōu)勢，在多峰函數(shù)f4—f6中也有明顯優(yōu)勢．在單峰函數(shù)f1和f2中，BODE算法的收斂精度明顯高于DE算法和PSO算法的；在函數(shù)f3中，BODE算法的收斂精度遠(yuǎn)高于PSO算法和BSD算法的．多峰函數(shù)f6在進(jìn)化到5000次時，已經(jīng)達(dá)到了收斂的最優(yōu)值0．由此可知，加入反向?qū)W習(xí)策略和伯恩斯坦算子對增強(qiáng)算法的尋優(yōu)能力以及提高算法的收斂精度有著重要作用．

測試函數(shù)結(jié)果對比如圖2所示．

圖2 測試函數(shù)結(jié)果對比Fig. 2 Comparison of bechmark functions

由圖2可知，本文的BODE算法在收斂進(jìn)度上與其他算法大致相同，但BODE算法的反向?qū)W習(xí)策略和伯恩斯坦算子可以加快收斂速度并提高收斂精度，有效地防止了算法的早熟現(xiàn)象，能夠更快找到最優(yōu)值．從圖2(a)—圖2(c)可知，BODE算法在處理單峰測試函數(shù)時，收斂精度和收斂速度優(yōu)勢明顯．雖然f3沒有表現(xiàn)優(yōu)秀，但在整體上對算法的收斂性能有一定的幫助．由圖2(d)—圖2(f)可知，BODE算法在測試多峰函數(shù)時，能夠解決多峰函數(shù)易于陷入局部最優(yōu)的問題，幫助其快速找到全局最優(yōu)值，且在收斂速度和精度上也表現(xiàn)突出．對易于陷入局部最優(yōu)的函數(shù)f6，表現(xiàn)出了較強(qiáng)的搜索能力．

4 結(jié) 語

為了提升DE算法的性能，本文對算法中結(jié)構(gòu)參數(shù)以及搜索策略進(jìn)行改進(jìn)，解決算法過早陷入局部最優(yōu)的問題，以達(dá)到提高算法的收斂精度和速度、減少計(jì)算消耗的效果．通過采用反向?qū)W習(xí)策略增加種群的多樣性，擴(kuò)大搜索范圍；而伯恩斯坦算子控制進(jìn)化過程中的變異和交叉階段，避免了參數(shù)的設(shè)定，增強(qiáng)了算法的搜索能力，提高了算法的收斂精度，使得算法更加高效．通過對國際標(biāo)準(zhǔn)測試函數(shù)的對比實(shí)驗(yàn)結(jié)果表明：BODE算法與其他算法相比有著更好的整體收斂性能，在進(jìn)化階段可以跳出局部最優(yōu)，收斂速度更快，精度更高．測試函數(shù)對比圖進(jìn)一步說明了本文算法在收斂速度和收斂精度方面有更好的表現(xiàn)．后續(xù)工作可以在進(jìn)化過程中加入更加高效的優(yōu)化策略以及驗(yàn)證和分析改進(jìn)后算法的性能這兩方面進(jìn)行，進(jìn)一步提高算法的可靠性．