差分進化演算法 Differential evolution - 3|EPSDE、MPEDE|自適應參數、多群


(二)EPSDE


(圖七)EPSDE突變 虛擬碼

EPSDE是採用多種突變策略與自適應參數的DE變形,突變策略有3種、F值有6種、CR值有9種,故有162種 (3*6*9)組合。一開始會從這162種組合隨機分配給每個個體,接著執行相對應的突變、交換與選擇。

(圖八)EPSDE組合重新初始化

EPSDE比基本DE多一個組合重新初始化的步驟,這裡的組合是指突變策略、F值與CR值的組合。如果子代沒有比親代好,組合就重新初始化。重新初始化有兩種可能,一種是從上一代好的組合抽樣一組,另一種是從162種組合隨機選一種初始化。而如果子代有比親代好,則此組合繼續延用到下一代。

A. 多種突變策略

        EPSDE主要用三種不同性質的突變策略,分別為DE/rand/1/bin (1)、DE/current-to-rand/1/bin (3)、DE/best/2/bin (18),rand適合發散、current-to-rand中庸、best適合收斂。

B. 自適應參數

Scaling factor (F)建議落在 [0.4, 0.9],crossover rate (CR)建議落在 [0.1, 0.9],且兩參數間隔為0.1,故F值有6種可能,CR值有9種可能。低CR值適合單峰型(unimodal)解空間,高CR值適合多峰型 (multimodal)解空間。

(三)MPEDE


(圖九)MPEDE多群體與獎勵機制 虛擬碼

        MPEDE主要以突變策略分群,MPEDE採用3種突變策略,分別為DE/rand/1/bin (1)、DE/current-to-rand/1/bin (3)、DE/ current-to-best/1/bin (19),故可視為有3個子群。然而MPEDE導入獎勵機制,使得有第4子群的出現。前3子群體規模一樣大,但突變策略皆不同。第4子群比較大且特殊,其定位為獎勵 (reward)性質的子群。

        一開始前3群的突變策略是預先給定且固定的,而第4群的突變機制是隨機給予的。經歷ng個世代後,會週期性地結算各子群平均個體的表現,而第4群會依照突變機制被分群到前3群之一。

        為了紀錄各子群個體的表現p_j,每個子群都會紀錄群內個體的表現 。如果j子群個體的子代比親代好,則會累加fitness進步的幅度 (∆fj)和function evaluations (∆Fesj),∆Fesj可視為有進步的個體次數總和。ng代後,會比較各子群的表現 (pj),表現最好的子群會給予第4群的獎勵,也就是第4群的突變策略會變成表現最好的那群。

        在(圖九)最後一段,會將群體重新分配到各子群中,也就是說每代的個體有機會在不同子群中流動,個體不是固定在同一群的。

B. 自適應參數

 

(圖十)MPEDE自適應次數 虛擬碼

        各子群除了會紀錄個體的表現外,也會紀錄菁英個體所用的參數值(CR & F),其用途為更動參數值的依據。MPEDE分配CR值是用高斯分佈 ( Gaussian distribution),而分配F值是使用柯西分佈 (Cauchy distribution)。

高斯分佈又稱為常態分佈 (normal distribution),其分佈由平均值和標準差所決定。CR常態分佈的標準差設為0.1,而μCRj初始值為0.5。由於每代都會紀錄菁英解的CR值 (S(CR, j)),故可透過這些菁英值來更新μCRj,以達到自適應的目的。

柯希分佈由Lehmer mean (25)當作位置位置參數,而0.5當作尺度參數。和CR一樣,會紀錄菁英解的F值 (S(CR, j))來更新μFj。c為預設常數,用來平衡新舊平均的比例。

最後隨機出來的CR和F建議落在(0, 1],值得一得是,MPEDE的不同的突變策略和其F、CR值是獨立關係的,也就是不同子群,有不同所偏好的F、CR值。


相關文章

  1. 群體智慧|以眾人的力量尋找更好的解|蔡崇煒 - 1
  2. 群體智慧|以眾人的力量尋找更好的解|蔡崇煒 - 2
  3. 差分進化演算法 Differential evolution - 1
  4. 差分進化演算法 Differential evolution - 2|APTDE|自適應群體
  5. 差分進化演算法 Differential evolution - 3|EPSDE、MPEDE|自適應參數、多群
  6. 差分進化演算法 Differential evolution - 4|APTDE, EPSDE, MPEDE比較結果
  7. DE, APTDE, EPSDE, MDEDE source code

參考文獻

  1. Mallipeddi, R., Suganthan, P. N., Pan, Q. K., & Tasgetiren, M. F. (2011). Differential evolution algorithm with ensemble of parameters and mutation strategies. Applied Soft Computing, 11(2), 1679-1696. https://doi.org/10.1016/j.asoc.2010.04.024 
  2. Wu, G., Mallipeddi, R., Suganthan, P. N., Wang, R., & Chen, H. (2016). Differential evolution with multi-population based ensemble of mutation strategies. Information Sciences, 329, 329-345. https://doi.org/10.1016/j.ins.2015.09.009

留言