差分進化演算法 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

留言

張貼留言