一種求解動態優化問題的改進自適應差分進化算法

劉樹強，秦 進

（貴州大學計算機科學與技術學院，貴陽 550025）

0 概述

在現實生活中很多優化問題均具有動態變化特性［1］，例如在調度問題中，隨著新任務的到達，機器可能隨時發生故障，原材料質量也會隨時間產生變化，而靜態優化方法無法有效解決上述問題，因此動態優化方法應運而生［2］。當前研究通常將動態優化問題（Dynamic Optimization Problem，DOP）視為一系列靜態優化問題（Static Optimization Problem，SOP）的組合，由于目標函數隨時改變，因此會導致最優解位置和搜索空間特征的不斷變化［3］，而解決動態優化問題的關鍵是控制解的多樣性［4］。傳統演化算法在解決靜態優化問題方面取得了較好的效果，但不能很好地解決動態優化問題，因為其在運行一段時間后會收斂到固定值，失去探索區域所需的多樣性，導致不能跟蹤到新環境下已變化的最優解［5］。在動態優化問題中，對不斷變化的最優解的快速追蹤與找到最優解本身同等重要［6］，這就要求動態優化問題的求解方法同時具備快速收斂和保持多樣性的能力。國內外許多研究人員對傳統演化算法進行了相關改進，使其能夠更好地解決動態優化問題。在過去十幾年中，研究人員提出了許多求解動態優化問題的算法及提升算法性能的策略［7］。

差分進化算法與多數演化算法相比，實現過程更簡單和直觀，具備良好的全局搜索能力，適用于處理大規模問題［8］。差分進化算法不僅在求解靜態問題方面表現出較好的性能，而且被證明可用于解決動態優化問題［9］。自適應差分進化（Self-Adaptive Differential Evolution，SADE）是差分進化的分支，通過適應性地改變算法參數值有效處理動態優化問題［10］。文獻［11］在動態自適應差分進化算法中引入種群競爭機制。文獻［12］認為動態環境下的自適應分為元啟發級別、DOP機制級別以及兩者組合3個主要的應用級別。文獻［13］提出一種動態環境下的自適應差分進化算法，不僅使用自適應控制機制改變其中的控制參數，而且采用帶老化機制的多種群方法處理停滯問題，并利用存檔的個體重新初始化得到新個體。文獻［14］提出一種改進的動態自適應差分進化算法DDEBQ，該算法使用布朗個體和自適應量子個體與差分進化個體共同維持種群的多樣性和探索能力，還利用鄰域驅動的雙變異策略控制攝動以防止過快收斂，并通過排斥規則將子種群分布到更大的搜索空間以加強最優值追蹤能力，同時使用老化機制防止算法陷入局部最優。

求解動態優化問題的進化算法需要探索與開發之間的平衡，探索對應算法的全局搜索能力，開發對應算法的局部搜索能力。進化算法既不能陷于局部最優，過分開發某一局部區域，喪失探索其他區域的能力，也不能一直在探索其他區域而不收斂或過慢收斂，忽視開發某一局部區域。差分進化算法是全局搜索能力較好的進化算法，但在演化后期通常收斂慢，局部搜索能力有待提升。自適應差分進化算法雖然通過算子的適應性變化提高了尋優精度，但是參數值的變化仍不能為種群提供足夠的多樣性。本文提出一種鄰域搜索差分進化（Neighborhood Search Differential Evolution，NSDE）算法，運用鄰域搜索機制增強差分進化算法中每個子種群的局部搜索能力，在傳統基于距離的排斥方案基礎上引入hill-valley 函數追蹤鄰近峰以提高尋優精度。

1 鄰域搜索差分進化算法

1.1 動態自適應差分進化算法

SADE 使用rand/1/bin 策略的自適應控制機制，在算法運行過程中改變控制參數F和CR，而種群規模NP 在演化過程中保持不變。自適應控制參數的計算公式如下：

其中：randj，j∈{1，2，3，4}表示取值為［0，1］的均勻隨機數；τ1和τ2分別為控制參數F和CR 的調整概率；τ1、τ2、Fl、Fu分別取固定值0.1、0.1、0.1、0.9；F取值為［0.1，1.0］的隨機數；CR 取值為［0，1］的隨機數；通常在變異前計算得到，從而影響新向量的變異、交叉和選擇。

在原始動態SADE 算法［13］中，老化機制的第i個個體的老化算法以及改進和老化算法如算法1 和算法2 所示，利用存檔的個體重新初始化算法如算法3所示，其中，subSize 是子種群大小，ARC 是關于個體的存檔，arcNum 是存檔大小，mRand（）是產生隨機數的函數，age 是個體年齡。

算法1第i個個體的老化算法

算法2改進和老化算法

算法3重新初始化算法

原始動態SADE 算法的具體內容詳見文獻［13］，本文在原始動態SADE 算法的基礎上提出NSDE 算法（如算法4 所示），主要改進為鄰域搜索和排斥算法。

算法4NSDE 算法

1.2 鄰域搜索機制

種群最優個體鄰域范圍內的解會有較高的可能性靠近最優值點，該可能性隨著維度的增加而增加。本文提出一種種群最優個體的鄰域解生成方式，首先利用自適應差分進化算法產生初步的種群最優個體，然后對種群最優個體的鄰域空間進行適當劃分，分別在不同范圍內產生候選解，構成候選解集合，最后選取集合中的最優解，對種群最優個體進行迭代，以期逼近最優值點。

組成動態優化問題的靜態優化問題可表示為：

其中，X、L、U均為n維向量，X=(x1，x2，…，xn)，L=(l，l，…，l)，U=(u，u，…，u)，X各分變量的取值均為［l，u］。

NSDE 算法利用矩形定義點的鄰域，通過同心超矩形劃分當前解分量xj(j=1，2，…，n)的鄰域空間［15］，如圖1 所示，假設分成k個空間，按式（2）劃分每個空間大小：

圖1 鄰域空間劃分Fig.1 Division of neighborhood space

在Ri（i=1，2，…，k）的每個同心矩形內隨機選取1 個點，這k個點構成當前解分量xj的候選值集合（如算法5 所示），整個候選解的產生如圖2 所示，其中，MaxIter 是迭代次數，mRand（）是產生隨機數的函數，candiNum 是鄰域候選解個數，r是鄰域半徑r0，x是某個子種群中的最優個體，xi是x的第i維的值，candiSol′是得到的候選解集合，BestSol是候選解集合中的最優解。

算法5鄰域搜索算法

圖2 候選解的產生Fig.2 Generation of candidate solutions

1.3 排斥方案

排斥方案的關鍵為將每個子種群維持在適應度（fitness）范圍內的不同峰上，子種群可以由其中的最優個體代表。每個子種群實施一種排斥方案，如果與其他子種群在同一個峰上，那么較好的子種群保持不變并重新初始化較壞的子種群。文獻［16］提出一種基于距離的排斥方案，該方案假設所有的峰均勻分布在整個搜索空間中，如果兩個子種群間的距離小于閾值，那么較壞的子種群被重新初始化，其中，n是維數，A是解的范圍，m是峰數。

基于距離的排斥方案中的兩個峰可能很接近，以至于它們之間的距離比排斥方案的閾值還小，在此情況下很難同時找到這兩個峰。本文在基于距離的排斥方案的基礎上增添一個hill-valley函數［9］，如圖3所示。當滿足基于距離的排斥方案條件時，判斷是否存在滿足f（z）＜min｛f（x），f（y）｝，如果不滿足，則最終進行排斥操作（如算法6所示），其中，x和y分別是兩個子種群中的最優個體，z=c?x+(1-c)?y，c∈{0.05，0.50，0.95}。

圖3 基于hill-valley 函數的排斥方案Fig.3 Exclusion scheme based on hill-valley function

算法6排斥算法

2 實驗與結果分析

2.1 對比算法

在求解動態優化問題的演化算法中，本文采用人工免疫網絡動態優化（Dynamic Optimization of Artificial Immune Network，dopt-aiNet）算法［17］、原始動態SADE算法（簡稱SADE）［13］、多種群競爭差分進化（Differential Evolution with Competitive Strategy Based on Multi-Population，DECS）算法［18］和改進差分進化（Modified Differential Evolution，MDE）算法［19］與NSDE 算法進行對比，具體為：1）dopt-aiNet 算法對opt-aiNet 算法［20］進行擴展，增加了分離的記憶種群、新的變異算子和種群規模最大值及控制衰退的搜索過程和親近度測量過程，可避免opt-aiNet算法的細胞數盲目擴增問題；2）SADE算法使用自適應控制機制、多種群機制與老化機制改變控制參數；3）DECS 算法將競爭機制融入多種群差分進化算法中，增強算法尋優能力；4）MDE 算法將種群分為跟蹤和搜索兩個子種群，對兩個子種群采用不同的變異策略，利用跟蹤種群判斷環境變化，采用搜索種群擴大搜索范圍。為避免算法結果的復現問題，SADE算法的實驗數據由實際仿真得到，而dopt-aiNet、DECS和MDE 算法的實驗數據來自文獻［17-18］。

2.2 測試函數與算法參數設置

本文使用GDBG 生成器［21］驗證NSDE 算法的有效性。GDBG 是一種廣義動態benchmark 生成器，構造二元空間、實空間與組合空間的動態問題，這些問題具有大量的旋轉操作和局部最優解以及更高的維度。GDBG 包含6 種測試函數和7 種變化情況，總計49 個測試問題，通用參數設置如表1 所示，其中高度范圍、起始高度和采樣頻率的單位為1。

表1 GDBG 通用參數設置Table 1 General parameter setting of GDBG

測試函數由表2所示的Sphere、Rastrigin、Weierstrass、Griewank、Ackley 這5 種函數通過旋轉、組合產生，F1 測試函數求解最大值優化問題，F2～F6 測試函數求解最小值優化問題，其中F1 分為帶有10 個峰和帶有50 個峰兩種情況，具體定義為：

F1：旋轉峰函數（10 and 50 peaks）；

F2：Sphere 函數的組合函數；

F3：Rastrigin 函數的組合函數；

F4：Griewank 函數的組合函數；

F5：Ackley 函數的組合函數；

F6：混合組合函數。

7種變化類型具體為小步變化（T1）、大步變化（T2）、隨機變化（T3）、混沌變化（T4）、周期變化（T5）、帶噪聲的周期變化（T6）和維度改變的隨機變化（T7）。

表2 GDBG 基本測試函數Table 2 Basic test function of GDBG

算法參數設置如表3 所示，種群規模、子種群數、子種群規模、F初始值、CR初始值的取值參考文獻［13］，鄰域半徑、鄰域候選解個數、迭代次數的取值通過簡單實驗計算得到。

表3 算法參數設置Table 3 Algorithm parameter setting

2.3 評價指標

本文選用平均誤差和標準差作為評價算法性能的指標，平均誤差和標準差的計算公式如下：

其中，nnum_change表示測試函數的變化次數，rruns表示算法獨立運行的次數，(t)表示算法在第i次獨立運行時第j次變化的適應度絕對誤差值，計算公式如下：

其中，f(xbest(t))和f(x*(t))分別表示算法尋得的最優值和理論最優值。

2.4 結果分析

本文在Windows 7 x86_64 操作系統、Intel?CoreTMi3-3220 CPU、3.30 GHz 主頻、8 GB RAM、C/C++編程語言環境下進行實驗。對6 個測試函數進行20 次獨立測試，實驗結果如表4、表5 所示，并將5 種算法在每個測試函數下得到的平均誤差的最小值加粗顯示。根據對比實驗結果，從測試函數角度分析可知，NSDE 算法在F1（50 peaks）、F2、F3、F4 和F5 測試問題上的精度相比SADE 算法提升最為明顯，能夠更好地應對F1（50 peaks）的峰數增加導致的環境復雜性變化以及F2、F3、F4 和F5 特征明顯不同的環境動態變化。從變化類型角度分析可知，NSDE 算法在T1、T2、T5、T6 和T7 變化類型下的平均誤差比SADE 算法小，即在小步變化、大步變化、周期變化、帶噪聲周期變化、維度改變隨機變化情況下的尋優能力相較SADE 算法更好。可以看出：NSDE 算法相比SADE 算法在49 個測試問題中有28 個測試問題的平均誤差更小，表明其具有更優的復雜問題求解能力；僅在F2、T1、T7 上劣于dopt-aiNet 算法，在49 個測試問題中有38 個測試問題的平均誤差更小；僅在F4、T3 上劣于MDE 算法，在49 個測試問題中有38 個測試問題的平均誤差更小；僅在F2、F4、T2、T7上劣于DECS，在49 個測試問題中有29 個測試問題的平均誤差更小。可見，NSDE算法相比DECS、dopt-aiNet和MDE 算法具有更優的復雜問題求解能力。

根據仿真實驗結果可以得出NSDE 算法在各類測試問題及各種變化類型下的收斂趨勢，如圖4 所示。相對誤差（E）的計算如式（7）所示：

其中，f（x）是算法尋得的最優值，f（x＊）是理論最優值。

NSDE算法收斂曲線反映了收斂速度及陷入局部最優值的次數，進而體現算法響應環境變化的能力。由于F3測試函數的基礎組成函數Rastrigin是典型的非線性多模態函數，峰與峰之間的起伏較大，并且具有大量局部極值點，因此算法在F3測試函數中的表現較差，相對而言更容易陷入局部最優而出現停滯狀態。但除此之外，NSDE算法在其他測試函數中均表現良好，具有較快的收斂速度，能及時響應環境變化并快速搜索新的全局最優值并保持種群多樣性。

表4 NSDE 與SADE 算法的實驗結果Table 4 Experimental results of NSDE and SADE algorithms

表5 NSDE、DECS、dopt-aiNet 和MDE 算法的實驗結果Table 5 Experimental results of NSDE，DECS，dopt-aiNet and MDE algorithms

續表

圖4 NSDE 算法在7 個測試問題上的收斂曲線Fig.4 Convergence curves of NSDE algorithm on seven test questions

3 結束語

本文在原始動態SADE 算法的基礎上提出一種鄰域搜索差分進化（NSDE）算法，產生初步的種群最優個體，對種群最優個體的鄰域空間進行劃分，并在不同的領域空間范圍內產生候選解構成候選解集合，選取集合中的最優解對種群最優個體進行迭代，增強算法局部搜索能力。在基于距離的排斥方案中，引入hill-valley函數提高算法尋優精度。實驗結果表明，NSDE 算法相比SADE、dopt-aiNet、DECS 和MDE 算法整體性能更優。后續將對NSDE 算法做進一步優化，提升其在處理復雜動態問題時的適用性與穩定性。