摘要

使用差分進化演算法 (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)

DE, APTDE, EPSDE, MDEDE source code

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)，會去計算所有新個體的適應度值，如果新個體適應度值較高，則選擇新個體，淘汰舊個體；反之則選擇舊個體，淘汰新個體。

參考文獻

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.

宗平方 TsungSquare

搜尋此網誌

差分進化演算法 Differential evolution - 1

摘要