芯耀
615
本文提出了一種新的jSO變體APSM-jSO，通過簡單有效的修改來提高其性能。
APSM-jSO和jSO之間有三個(gè)主要區(qū)別。
首先，設(shè)計(jì)了一種新的自適應(yīng)選擇機(jī)制（APSM）來從歷史記憶中選擇條目，以充分利用歷史記憶中更好的條目。隨后，利用先進(jìn)先出（FIFO）方法更新外部檔案，以保持人口多樣性，避免過度使用外部檔案。
最后，采用基于秩的選擇壓力（RSP）的新突變策略來增強(qiáng)APSM-jSO的開發(fā)。文章于2023發(fā)表在中科院1區(qū)頂刊Swarm and Evolutionary Computation上。
2. 差分進(jìn)化算法變體簡介
2.1. 差分進(jìn)化
經(jīng)典差分進(jìn)化（DE）[1] 是一種基于種群的進(jìn)化算法，其中三個(gè)操作：變異、交叉和選擇操作，在進(jìn)化過程中執(zhí)行。
初始種群??使用均勻分布生成，如公式(1)所示。
其中 rand ∈ ( 0 , 1 ) 是均勻分布的隨機(jī)數(shù)，i∈{1,2,3,?,NP} 是個(gè)體索引，NP是種群大小，j∈{1,2,3,?,D} 是維度索引， D是維度，Lj和Uj是問題特定的第 J 維的下界和上界[11]。
DE中生成變異向量??的四種廣泛使用的經(jīng)典的變異策略，DE/best/2、DE/rand/2 和 DE/current-to-best/1、DE/current-to-rand/1，描述如下(2)、(3)、(4)、(5)。
其中 r 1 , r 2 , r 3 , r 4 , r 5 ∈ { 1 , 2 , 3 , ? ? , N P } 是均勻分布的隨機(jī)索引，彼此不同。 F是縮放因子，x best 是到目前為止獲得的最佳個(gè)體。此外，當(dāng) vi 超出下界或上界時(shí)，采用修正策略，如公式(6)所示。
采用二項(xiàng)式交叉操作生成試驗(yàn)向量 ，ui 基于變異向量，如公式(7)所示。
其中 jrand∈{1,2,3,?,D} 表示均勻隨機(jī)索引，CR是交叉率。
基于貪婪策略的選擇操作用于更新種群，如公式(8)所示。
其中f ( ? ) 表示特定問題的適應(yīng)度函數(shù)。
2.2. SHADE[2]
SHADE 于2013年提出，采用外部存檔方案和基于歷史的參數(shù)調(diào)整方案。外部存檔??被引入DE以豐富種群多樣性。如果試驗(yàn)向量??優(yōu)于其目標(biāo)向量?，則將其保存在外部存檔中。否則，它將在下一代中保留，如公式(8)所示。一旦存檔的大小??達(dá)到預(yù)定大小，隨機(jī)丟棄一個(gè)個(gè)體以為新插入的個(gè)體騰出空間。
基于歷史的參數(shù)調(diào)整方案用于調(diào)整??和?。所有成功的??和??保存到??和??中以更新歷史記憶??和?，使用加權(quán)勒梅爾平均值，如公式(9)、(10)、(11)、(12)所示。?從1開始，每代遞增1。此外，如果超過內(nèi)存大小??[13]，則??重置為1。在一代中，如果所有試驗(yàn)向量都比相應(yīng)的目標(biāo)向量差，則??和??不更新。
在公式(11)中，?表示??或?。?和??對(duì)于個(gè)體??通過從柯西分布（如公式(13)所示）和正態(tài)分布（如公式(15)所示）中采樣創(chuàng)建。?和??進(jìn)一步使用公式(14)和公式(16)進(jìn)行修正。
其中??表示隨機(jī)索引。此外，使用外部存檔的變異策略“DE/current-to-pbest/1”在SHADE中生成變異向量?，如公式(17)所示。
其中??表示從包括前??個(gè)個(gè)體的主導(dǎo)種群中隨機(jī)選擇的個(gè)體，?表示貪婪因子。?是從??和??的組合中選擇的隨機(jī)個(gè)體，與?、?或??不同。
由于個(gè)體的交叉率不同，公式(7)已被修改為公式(18)。
其中??表示均勻隨機(jī)索引，?是交叉率。
每個(gè)個(gè)體??都有一個(gè)相關(guān)的?，使用公式(19)通過代計(jì)算。
2.3 L-SAHDE[3]
L-SHADE [15] 通過引入線性種群規(guī)?？s減（LPSR）策略來平衡開發(fā)和探索。在 L-SHADE 中，種群規(guī)模??在進(jìn)化過程中使用線性函數(shù)更新，如公式(20)所示。
其中??和??是最小和最大種群規(guī)模。?和??分別是最大和當(dāng)前評(píng)估次數(shù)。每一代結(jié)束時(shí)，從??中丟棄最差的個(gè)體以滿足更新的?。
此外，對(duì)歷史記憶??的更新進(jìn)行了一些修改，如公式(21)所示。具體來說，當(dāng)??更新時(shí)，如果??等于終端值 ⊥ 或?，則??設(shè)置為 ⊥。因此，如果??被分配 ⊥，?將固定在終端值，這將鎖定??直到搜索結(jié)束，如公式(22)所示。
在 L-SHADE 中，貪婪因子??設(shè)置為常數(shù)而不是使用公式(19)生成。外部存檔大小設(shè)置為?，?是外部存檔大小的控制參數(shù)。注意，外部存檔大小在進(jìn)化過程中根據(jù)??更新。
2.4. iL-SHADE[4]
iL-SHADE [16] 是 L-SHADE 的擴(kuò)展版本。與 L-SHADE 不同的主要特征如下。
首先，當(dāng)前代的??和??被考慮用于更新歷史記憶，如公式(23)和公式(24)所示。所有??的條目在開始時(shí)設(shè)置為 0.8（在 L-SHADE 中設(shè)置為 0.5），歷史記憶的一個(gè)條目保持固定值，即??和??在進(jìn)化過程中始終設(shè)置為 0.9。
其次，?的非常低的值和??的非常高的值在進(jìn)化的早期階段受到限制[16]。具體來說，使用公式(22)和公式(13)生成的??和??將被調(diào)整如下。
最后，使用公式(27)生成一代中所有個(gè)體的貪婪因子?。
在 iL-SHADE 中，=0.2 和?=0.1 在進(jìn)化過程中。
2.5. jSO[5]
jSO [17] 是 iL-SHADE 的改進(jìn)變體，采用新的加權(quán)版本的變異策略“DE/current-to-pbest-w/1”，如公式(28)所示。
在新的變異策略中，進(jìn)化過程的早期階段采用較小的因子?，而在后期階段，采用較高的因子??以調(diào)整探索和開發(fā)[20]。
此外，在進(jìn)化過程中，=0.25 和?=，?值在 jSO 中初始化為 0.3。
2.6. LSHADE-RSP[6]
LSHADE-RSP 是 jSO 的最近增強(qiáng)版本，通過引入 RSP 和調(diào)整??和??來實(shí)現(xiàn)。RSP 基于的變異策略，DE/current-to-pbest-w/r，如公式(30)所示。
其中??表示基于排名概率從種群??中選擇的向量，?是基于排名概率從??中選擇的向量或從??中隨機(jī)選擇的向量。個(gè)體??的選擇概率使用公式(31)計(jì)算。
其中最大和最小的排名分別分配給最佳和最差的個(gè)體。?表示種群中排序適應(yīng)度數(shù)組的索引。?是調(diào)整排名選擇貪婪度的控制因子[20]。
此外，使用公式(13)和公式(22)在進(jìn)化過程中生成的??和??調(diào)整如下。
最后，LSHADE-RSP 中與 jSO 不同的參數(shù)設(shè)置如下：公式(27)中的??設(shè)置為 0.17，公式(32)中的??設(shè)置為 3，所有??的條目初始化為 0.3。
3. 提出的APSM-jSO算法[7]
在過去二十年中，針對(duì)差分進(jìn)化（DE）及其變體在自適應(yīng)控制參數(shù)設(shè)置和變異策略修改方面進(jìn)行了一系列研究。DE最具競爭力的變體是jSO，由Brest于2017年提出，它結(jié)合了近年來提出的DE有效改進(jìn)，并成為IEEE CEC 2017競賽的獲勝者。然而，jSO中的自適應(yīng)機(jī)制可能沒有完全發(fā)揮其優(yōu)化潛力。在本文中，開發(fā)了一種基于jSO的APSM-jSO，通過對(duì)其縮放因子選擇、交叉率選擇和外部存檔更新機(jī)制進(jìn)行簡單有效的修改，以充分利用其優(yōu)化性能。提出的APSM-jSO的詳細(xì)信息如下。
3.1. 自適應(yīng)參數(shù)選擇機(jī)制（APSM）
在jSO框架中，縮放因子??和交叉率??對(duì)其性能[17]起著重要作用。此外，成功的?和??歷史記憶顯著提高了jSO的有效性。然而，由于??和??中的條目是隨機(jī)選擇用于現(xiàn)有SHADE變體中的，因此歷史記憶中的更好條目沒有被更頻繁地使用以加速進(jìn)化過程。為了充分利用歷史記憶中的更好條目，提出了一種新的自適應(yīng)參數(shù)選擇機(jī)制，用于從??和??中選擇條目以生成合適的??和?。在此機(jī)制中，根據(jù)上一代的歷史使用信息為??和??中的條目分配不同的概率。具體來說，（）中條目??的選擇概率在每一代計(jì)算，如公式(35)所示。
其中??表示在?（）中條目??生成??和??的調(diào)用次數(shù)，?表示條目??生成的??和??指示??生成的個(gè)體優(yōu)于??的次數(shù)。此外，如果??和??中的新更新條目等于?，則成功次數(shù)??設(shè)置為等于?。此外，如果試驗(yàn)個(gè)體比相應(yīng)目標(biāo)個(gè)體差，則??和??中條目的所有概率將重置為?。需要注意的是，僅在進(jìn)化過程中更新??和??中從 1 到??的條目。
3.2. 先進(jìn)先出方法（FIFO）
在jSO框架中，如果外部存檔大小?=?達(dá)到預(yù)定大小，則隨機(jī)丟棄一個(gè)個(gè)體以為新插入的個(gè)體騰出空間。由于隨機(jī)更新機(jī)制，外部存檔中的一些個(gè)體可能在許多代中不會(huì)被丟棄，這導(dǎo)致外部存檔中的一些元素在優(yōu)化后期被過度使用。為了避免過度使用??并豐富種群多樣性，引入了先進(jìn)先出（FIFO）方法，如果存檔大小??達(dá)到預(yù)定大小，則最早保存的個(gè)體將被新插入的個(gè)體替換。
3.3. 基于RSP的新變異策略
為了增強(qiáng)APSM-jSO的利用，使用LSHADE-RSP中描述的RSP策略提出了一種新的基于RSP的變異策略，如公式(31)~(32)所示。與LSHADE-RSP不同，RSP僅用于APSM-jSO中的??而不是??和?，如公式(30)所述。從??和??的組合中隨機(jī)選擇??的優(yōu)勢在于，外部存檔機(jī)制可以在進(jìn)化的后期充分發(fā)揮作用，這可以有效提高種群多樣性。此外，基于排名的選擇壓力策略使??具有優(yōu)于??的更高概率，即種群的進(jìn)化方向具有向更好方向進(jìn)化的更高概率，如圖1(a)所示。如圖1(b)所示。
因此，新的基于RSP的變異策略如公式(37)所述。
其中??是從與?、?或??不同的??和??的組合中隨機(jī)選擇的個(gè)體。
參考文獻(xiàn)
[1]DE: Storn, R., Price, K. Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces. Journal of Global Optimization 11, 341–359 (1997). https://doi.org/10.1023/A:1008202821328
[2] SHADE：R. Tanabe and A. Fukunaga, "Evaluating the performance of SHADE on CEC 2013 benchmark problems," 2013 IEEE Congress on Evolutionary Computation, Cancun, Mexico, 2013, pp. 1952-1959, doi:?10.1109/CEC.2013.6557798
[3] L-SHADE：R. Tanabe and A. S. Fukunaga, "Improving the search performance of SHADE using linear population size reduction," 2014 IEEE Congress on Evolutionary Computation (CEC), Beijing, China, 2014, pp. 1658-1665, doi:?10.1109/CEC.2014.6900380
[4] J. Brest, M. S. Mau?ec and B. Bo?kovi?, "iL-SHADE: Improved L-SHADE algorithm for single objective real-parameter optimization," 2016 IEEE Congress on Evolutionary Computation (CEC), Vancouver, BC, Canada, 2016, pp. 1188-1195, doi:?10.1109/CEC.2016.7743922
[5] jSO：J. Brest, M. S. Mau?ec and B. Bo?kovi?, "Single objective real-parameter optimization: Algorithm jSO," 2017 IEEE Congress on Evolutionary Computation (CEC), Donostia, Spain, 2017, pp. 1311-1318, doi:?10.1109/CEC.2017.7969456
[6] LSHADE-RSP：V. Stanovov, S. Akhmedova and E. Semenkin, "LSHADE Algorithm with Rank-Based Selective Pressure Strategy for Solving CEC 2017 Benchmark Problems," 2018 IEEE Congress on Evolutionary Computation (CEC), Rio de Janeiro, Brazil, 2018, pp. 1-8, doi:10.1109/CEC.2018.8477977
[7]?APSM-jSO：Yintong Li, Tong Han, Huan Zhou, Yujie Wei, Yuan Wang, Mulai Tan, Changqiang Huang. APSM-jSO: A novel jSO variant with an adaptive parameter selection mechanism and a new external archive updating mechanism. Swarm and Evolutionary Computation, https://doi.org/10.1016/j.swevo.2023.101283
