劉樹強(qiáng)，秦 進(jìn)

（貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴陽(yáng) 550025）

0 概述

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

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

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

1 鄰域搜索差分進(jìn)化算法

1.1 動(dòng)態(tài)自適應(yīng)差分進(jìn)化算法

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

其中：randj，j∈{1，2，3，4}表示取值為［0，1］的均勻隨機(jī)數(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］的隨機(jī)數(shù)；CR 取值為［0，1］的隨機(jī)數(shù)；通常在變異前計(jì)算得到，從而影響新向量的變異、交叉和選擇。

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

算法1第i個(gè)個(gè)體的老化算法

算法2改進(jìn)和老化算法

算法3重新初始化算法

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

算法4NSDE 算法

1.2 鄰域搜索機(jī)制

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

組成動(dòng)態(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 算法利用矩形定義點(diǎn)的鄰域，通過同心超矩形劃分當(dāng)前解分量xj(j=1，2，…，n)的鄰域空間［15］，如圖1 所示，假設(shè)分成k個(gè)空間，按式（2）劃分每個(gè)空間大?。?/p>

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

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

算法5鄰域搜索算法

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

1.3 排斥方案

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

基于距離的排斥方案中的兩個(gè)峰可能很接近，以至于它們之間的距離比排斥方案的閾值還小，在此情況下很難同時(shí)找到這兩個(gè)峰。本文在基于距離的排斥方案的基礎(chǔ)上增添一個(gè)hill-valley函數(shù)［9］，如圖3所示。當(dāng)滿足基于距離的排斥方案條件時(shí)，判斷是否存在滿足f（z）＜min｛f（x），f（y）｝，如果不滿足，則最終進(jìn)行排斥操作（如算法6所示），其中，x和y分別是兩個(gè)子種群中的最優(yōu)個(gè)體，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 實(shí)驗(yàn)與結(jié)果分析

2.1 對(duì)比算法

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

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

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

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

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

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）、隨機(jī)變化（T3）、混沌變化（T4）、周期變化（T5）、帶噪聲的周期變化（T6）和維度改變的隨機(jī)變化（T7）。

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

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

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

2.3 評(píng)價(jià)指標(biāo)

本文選用平均誤差和標(biāo)準(zhǔn)差作為評(píng)價(jià)算法性能的指標(biāo)，平均誤差和標(biāo)準(zhǔn)差的計(jì)算公式如下：

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

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

2.4 結(jié)果分析

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

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

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

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

表4 NSDE 與SADE 算法的實(shí)驗(yàn)結(jié)果Table 4 Experimental results of NSDE and SADE algorithms

表5 NSDE、DECS、dopt-aiNet 和MDE 算法的實(shí)驗(yàn)結(jié)果Table 5 Experimental results of NSDE，DECS，dopt-aiNet and MDE algorithms

續(xù)表

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

3 結(jié)束語(yǔ)

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