（二）APTDE
 |
| （圖一）APTDE架構 虛擬碼 |
APTDE是採用自適應群體數的DE變形，有三個不同於基本DE的部分：A. 狀態監控、B. 減少表現差的個體、C. 增加表現好的個體。會有一組狀態監控器，去監控整個群體的表現好壞，如果整體表現連續進步，則減少表現差的個體；如果整體表現連續停滯，則增加表現好的個體。
A. 狀態監控器 (status monitor)
 |
| （圖二）狀態監控器 虛擬碼 |
有四種不同的狀態監控器，監控整體在每個世代中的表現，分別為redundance monitor (RM)、stagnation monitor (NM)、lower bound monitor (LM)、upper bound monitor (UM)。RM紀錄連續進步的世代數，NM紀錄連續停滯的世代數，LM紀錄連續群體過少的世代數，UM紀錄連續群體過多的世代數。
如果這個世代有產生比全域最優解更好的解，則認定整體表現進步；如果這世代沒有產生比全域最優解更好的解，則認定整體表現停滯。APTDE會預設兩個狀態閥值，分別為k1與k2。k1為進步與停滯的世代閥值，如果連續k1個世代進步，且群體數沒有過少，則減少差的個體；如果連續k1個世代停滯，且群體數沒有過多，則增加好的個體。k2為群體過多與過少的世代閥值，如果連續k2個世代群體過多，則減少差的個體；如果連續k2個世代群體過少，則增加好的個體。
B. 減少表現差的個體
 |
| （圖三）減少策略 虛擬碼 |
APTDE會減少表現差的個體，個體表現的好壞除了會以fitness值排名外，還會將fitness排名分等第排名，因此fitness值會分成A+, A, A-, B+, B......等不同個等第排名rnak(i)。
使用等第排名而非fitness值排名的優點就是，避免每次都移除先天差的個體。不過等第排名會有一個問題，就是如果在高同質性的群體中，新增差異大的個體，會導致這個新個體容易又被排除出去，因此設計fitness最差的三個個體的等第排名都一樣，這樣可以減少新個體太快被排除的機會。
等第區間數(𝜔)會隨著群體數而有所變化，Ω論文建議值為0.8。
雖然說是減少表現差的個體，但其實表現好的個體也會有機率被選到，因此等第排名還會轉成選取機率 (𝜏)。表現越好，等第排名越小，被選取到的機率越小；而表現越差，等第排名越大，被選取到的機率越大。
被選取到的個體會被放入IA (Inferior-Archive)中，並計算Del值，以決定刪除的個體數量。p%群體數或IA集合大小中，最小者為Del值。p值為預先定好的常數值，用以決定要減少或增加群體數的百分比值。
C. 增加表現好的個體
 |
| （圖四）增加策略 虛擬碼 |
APTDE的增加策略中，有三個重要的參數，分別為𝛿1、𝛿2、Δd。𝛿1為增加個體數、𝛿2為突變維度數、Δd為突變幅度值。
𝛿1為增加個體數，其值為p%群體數，也會隨著群體數而浮動。在增加策略中，會先取取前p%的個體，此時的排名就是指fitness排名，不會以等第排名取個體。
𝛿2為突變維度數，也就是當菁英解被選取後，會對其部分維度做突變。因此不會像DE有全突變與部分交換的過程，而是一次就部分突變，故必須先決定要突變幾個維度。
 |
| （圖五）𝛿2和世代的乙狀函數圖 |
𝛿2在世代早期與晚期的變化緩慢，而到中期的變化會加大。
𝛿2由公式(10)得出，其公式形式為一個乙狀函數 (sigmoid function)，因其形狀像S字母故得名。乙狀函數為頭尾坡緩，中間坡陡的形狀。故𝛿2早期會從𝛿2的最大值 (U_δ)緩慢下降，到世代中期下降速度增快，到世代晚期又緩慢下降至𝛿2的最小值 (L_δ)。
G為現在的世代，而Gmax為最大世代值，λ值由公式(11)得出， a為𝛿2的區間。乙狀函數的導入，可以使得早期突變維度數較多，這有利於發散；而到後期突變維度數較少，這有利於收斂。
 |
| （圖六）Δd和R的關係圖 |
Δd為突變幅度值，Δd和R值有關，（圖六）即為關係圖。頭尾坡緩，中間坡陡。R值是由平均為0、標準差為1/9 (≈0.11)的高斯分佈所隨機出來的數值，故會有68%落於[0, 0.11]，95%落於[0, 0.22]，99.7%落於[0, 0.33]。綜合以上兩點，可得知突變幅度高機率會落在Δd最小值 (L_d)附近，但也有小機率會遠離Ld。x(j, U)和x(j, L)是目標函數x的最大值與最小值，c1建議 [0.02, 0.7]、c2建議 [0, 0.02]。
相關文章
參考文獻
hu, W., Tang, Y., Fang, J.-a., & Zhang, W. (2013). Adaptive population tuning scheme for differential evolution. Information Sciences, 223, 164-191. https://doi.org/10.1016/j.ins.2012.09.019
留言
張貼留言