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

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

差分進(jìn)化(differential evolution，DE)算法[1]是一種模仿生物群體進(jìn)化的全局優(yōu)化算法．與其他進(jìn)化算法相同，DE算法也是在一個(gè)隨機(jī)生成的初始種群中開始搜索，通過變異、交叉、選擇操作產(chǎn)生下一代的種群，不斷迭代求解，直至找到最終解．因其具有模型簡單、收斂性能好、魯棒性強(qiáng)等特點(diǎn)，被應(yīng)用到模式識別、數(shù)據(jù)挖掘、人工智能等各個(gè)領(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ù)的試錯(cuò)過程中計(jì)算消耗大，Wang等[4-5]提出的算法可以使每個(gè)個(gè)體在參數(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]通過使用多個(gè)差分變異算子增加種群的多樣性，從而避免了差分進(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)化時(shí)相對于傳統(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)成功的概率；．通過這個(gè)式子可以將固定概率和可變成功次數(shù)轉(zhuǎn)移到固定成功次數(shù)和可變概率中．通過式(2)可生成(n＋1)大小的n次伯恩斯坦多項(xiàng)式．其中s＜0并且s＞n，Bs,n＝0．

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

圖1 0≤t≤1時(shí)二階伯恩斯坦多項(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時(shí)，初始值x是通過經(jīng)驗(yàn)積累或者是單純的隨機(jī)猜想，可以同時(shí)使用x的相反值嘗試得到更好的解x*，使得下一代x能夠更快逼近最優(yōu)解．在種群的進(jìn)化過程中，如果該個(gè)體對應(yīng)的反向個(gè)體的適應(yīng)值優(yōu)于該個(gè)體的適應(yīng)值，則反向個(gè)體替代該個(gè)體，并進(jìn)入下一代種群．反向?qū)W習(xí)策略有助于更快地找到最優(yōu)解，并加快優(yōu)化算法的收斂速度．

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

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

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

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

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

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

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

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

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

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

交叉：將種群中個(gè)體的部分基因與變異個(gè)體的部分基因按照規(guī)則交換，以提高種群的多樣性．C為交叉概率，C值越大，交叉?zhèn)€體Ui(G)從變異個(gè)體Vi(G)中獲得的基因越多，從而更接近變異個(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)個(gè)體，適應(yīng)度越?。畬?dāng)前種群中個(gè)體的適應(yīng)度 f(Xi(G))與相應(yīng)的實(shí)驗(yàn)個(gè)體 f(Ui(G))的適應(yīng)度相比較，如果實(shí)驗(yàn)個(gè)體的適應(yīng)度小于或等于當(dāng)前個(gè)體的適應(yīng)度，則選擇實(shí)驗(yàn)個(gè)體進(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)個(gè)體提供更多機(jī)會，避免算法進(jìn)化過程中容易陷入局部最優(yōu)的問題；通過伯恩斯坦多項(xiàng)式隨機(jī)產(chǎn)生結(jié)構(gòu)參數(shù)并控制變異和交叉的過程，避免參數(shù)確定導(dǎo)致的試錯(cuò)過程，增強(qiáng)了個(gè)體的尋優(yōu)能力，從而節(jié)省了搜索時(shí)間．

算法1：BODE算法

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

2. 輸出：個(gè)體的位置信息．

3. BEGIN．

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

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

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

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

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

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

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

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

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

13. 更新個(gè)體．

14. END WHILE．

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

16. END．

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

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

(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)用時(shí)產(chǎn)生的隨機(jī)值，矩陣Q是全1矩陣．

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

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

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

算法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，種群個(gè)體的維度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個(gè)測試函數(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次時(shí)，已經(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ù)時(shí)，收斂精度和收斂速度優(yōu)勢明顯．雖然f3沒有表現(xiàn)優(yōu)秀，但在整體上對算法的收斂性能有一定的幫助．由圖2(d)—圖2(f)可知，BODE算法在測試多峰函數(shù)時(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)一步提高算法的可靠性．