劉樹強，秦 進

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

0 概述

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

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

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

1 鄰域搜索差分進化算法

1.1 動態(tài)自適應差分進化算法

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

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

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

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

算法2改進和老化算法

算法3重新初始化算法

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

算法4NSDE 算法

1.2 鄰域搜索機制

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

組成動態(tài)優(yōu)化問題的靜態(tài)優(yōu)化問題可表示為：

其中，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）劃分每個空間大?。?/p>

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

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

算法5鄰域搜索算法

圖2 候選解的產(chǎn)生Fig.2 Generation of candidate solutions

1.3 排斥方案

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

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

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

算法6排斥算法

2 實驗與結果分析

2.1 對比算法

在求解動態(tài)優(yōu)化問題的演化算法中，本文采用人工免疫網(wǎng)絡動態(tài)優(yōu)化（Dynamic Optimization of Artificial Immune Network，dopt-aiNet）算法［17］、原始動態(tài)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］進行擴展，增加了分離的記憶種群、新的變異算子和種群規(guī)模最大值及控制衰退的搜索過程和親近度測量過程，可避免opt-aiNet算法的細胞數(shù)盲目擴增問題；2）SADE算法使用自適應控制機制、多種群機制與老化機制改變控制參數(shù)；3）DECS 算法將競爭機制融入多種群差分進化算法中，增強算法尋優(yōu)能力；4）MDE 算法將種群分為跟蹤和搜索兩個子種群，對兩個子種群采用不同的變異策略，利用跟蹤種群判斷環(huán)境變化，采用搜索種群擴大搜索范圍。為避免算法結果的復現(xiàn)問題，SADE算法的實驗數(shù)據(jù)由實際仿真得到，而dopt-aiNet、DECS和MDE 算法的實驗數(shù)據(jù)來自文獻［17-18］。

2.2 測試函數(shù)與算法參數(shù)設置

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

表1 GDBG 通用參數(shù)設置Table 1 General parameter setting of GDBG

測試函數(shù)由表2所示的Sphere、Rastrigin、Weierstrass、Griewank、Ackley 這5 種函數(shù)通過旋轉(zhuǎn)、組合產(chǎn)生，F(xiàn)1 測試函數(shù)求解最大值優(yōu)化問題，F(xiàn)2～F6 測試函數(shù)求解最小值優(yōu)化問題，其中F1 分為帶有10 個峰和帶有50 個峰兩種情況，具體定義為：

F1：旋轉(zhuǎn)峰函數(shù)（10 and 50 peaks）；

F2：Sphere 函數(shù)的組合函數(shù)；

F3：Rastrigin 函數(shù)的組合函數(shù)；

F4：Griewank 函數(shù)的組合函數(shù)；

F5：Ackley 函數(shù)的組合函數(shù)；

F6：混合組合函數(shù)。

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

表2 GDBG 基本測試函數(shù)Table 2 Basic test function of GDBG

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

表3 算法參數(shù)設置Table 3 Algorithm parameter setting

2.3 評價指標

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

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

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

2.4 結果分析

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

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

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

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

表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

續(xù)表

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

3 結束語

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