差分進化演算法 Differential evolution - 1


摘要

使用差分進化演算法 (Differential evolution, DE)與其三個DE變型體(APTDE, EPSDE, MPEDE)去找十個目標函數 (objective function) 的全域最優解 (global optimal solution)。APTDE採用自適應群體數;EPSED採用自適應參數;MPEDE採用多群+自適應參數。整體表現上,(優)MPEDE > EPSDE > APTDE > Basic DE(差)。

ㄧ、簡介

透過尋找函數最佳化的問題,可以來評估其演算法在連續解空間中,尋找最佳解的能力。我們會設計一個目標函數 (objective functions),來代表欲解決之問題模型,而此目標函數之解空間與實際問題之可能解相似。多數的情況下,我們會以尋找最小目標值為目標,因此,目標函數常被視為成本函數 (cost function)。

Storn and Price (1997)提出差分進化演算法 (differential evolution, DE),主要有四個部分,分別為初始化 (initialization)、突變 (mutation)、交換 (crossover)、選擇 (selection)。突變與交換的機制,可以增加DE解之多樣性與避免DE陷入區域最優解 (local optimum)的困境。

DE在函數最佳化問題表現突出,近年有不少DE相關的變形演算法被提出。Mallipeddi et al. (2011)以自適應參數 (self-adaptive parameters)與多種突變策略的觀點,提出differential evolution algorithm with ensemble of parameters and mutation strategies (EPSDE);Zhu et al. (2013)以自適應群體數的觀點,提出adaptive population tuning scheme for differential evolution (APTDE);Wu et al. (2016)以多群體與自適應參數的觀點,提出differential evolution with multi-population based ensemble of mutation strategies (MPEDE)。

自適應是非常有用的概念,在每次的搜尋中,搜尋策略會隨著個體的表現而有所回應。如果個體表現差,就會微調或改變既有的搜尋策略;而如果個體表現好,則繼續使用這種搜尋策略。這有別於固定或線性變動的策略,自適應更能因應不同型態的解空間。

在DE中,重要的參數除了scale factor (F)和crossover rate (CR)外,群體數也是可以改善的地方。在APTDE中就針對群體數做自適應的改進,基本想法為:如果群體目前表現差,代表目前陷入區域最優解的困境,此時應增加個體來突破此逆境;如果群體目前表現佳,代表目前搜尋能量餘裕,則可減少冗員以節省運算資源。

在社會性動物中,族群會被劃分成數種不同的階級與角色,每個角色在社會中都有不同的貢獻,以促進整體社會的進步。因此這種多群體 (multi-population)的概念也可以被應用於最佳化問題,在MPEDE中,不同群體就代表一種不同的搜尋策略,而不同的搜尋策略能一同為整體搜尋給予不同比例的貢獻。

在本次實驗中,會比較基本的DE (DE/rand/bin/1)以及其他三個變形 (APTDE, EPSDE, MPEDE)在十個不同目標函數的表現。

二、相關研究

(ㄧ)差分進化演算法 (Differential evolution, DE)

A. 初始化 (initialization)

隨機對NP個群體產生D個維度的參數,並假設其分佈為均勻機率分佈 (uniform probability distribution)。

B. 突變 (mutation)

(1) DE/rand/1

隨機從群體中挑出三個不同的個體,分別為x(r1,G)、x(r2,G)、x(r3,G)。以r1為參考點,取r2與r3之差,其差乘上自定義的控制因子F,最後將其與參考點相加為第i點下一代的突變位置。此種突變策略可以產生差異性大的個體,但表現也較為發散。

(2) DE/best/1

和DE/rand/1不同的是,其參考點不是隨機選取的,而是以目前最好的點當作參考點。此種突變策略可以產生較好的個體,但也容易掉入區域最優解的困境。

(3) DE/current-to-best/1

參考點是以目前的點 (i)為基礎,並往最好點和隨機點移動。此種策略可以平衡rand和best的優缺點,為較中庸的策略。

C. 交換 (crossover)

CR為自定義的交換機率 (crossover rate),rand(i,j) [0,1]為0~1的隨機機率值。對每個個體中不同維度之資料,決定是否要接受突變的結果?也就是交換。如果rand(i,j) [0,1] ≤ CR或j = jrand,則接突變結果;反之則不接突變的結果。

透過親代與突變體的部分交換,可以平衡子代與親代的相似度,讓子代不會過於相似或歧異。

D. 選擇 (selection)

目標函數被當成適應度函數 (fitness function),會去計算所有新個體的適應度值,如果新個體適應度值較高,則選擇新個體,淘汰舊個體;反之則選擇舊個體,淘汰新個體。


相關文章

  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

參考文獻

Storn, R., & Price, K. (1997). Differential evolution - A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), 341-359.

留言