袁亦川，楊 洲，羅廷興，秦 進(jìn)

(1．貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴陽550000; 2．貴陽市信息產(chǎn)業(yè)發(fā)展中心，貴陽550000)(*通信作者電子郵箱175385745@qq．com)

0 引言

許多現(xiàn)實(shí)世界中的優(yōu)化問題都表現(xiàn)出動(dòng)態(tài)性質(zhì)，即優(yōu)化的目標(biāo)函數(shù)或待求解的問題會(huì)隨時(shí)間而發(fā)生(隨機(jī))變化。例如，目標(biāo)識(shí)別過程中，敏感組件的檢測性能會(huì)受到周圍環(huán)境的影響和制約;調(diào)度問題中，新工件可能隨時(shí)到達(dá)，機(jī)器可能發(fā)生隨機(jī)故障或逐漸磨損，資源量會(huì)隨時(shí)間不斷變化，原材料的性能可能會(huì)隨時(shí)間發(fā)生變化;金融貿(mào)易模型中的市場環(huán)境可能會(huì)突然改變［1－2］;因此，研究適合于求解這些普遍存在于現(xiàn)實(shí)世界的動(dòng)態(tài)優(yōu)化問題(Dynamic Optimization Problem，DOP)的方法和算法有重要的現(xiàn)實(shí)意義。

一般來說優(yōu)化問題可以分為兩類:靜態(tài)優(yōu)化問題(Static Optimization Problem，SOP)和動(dòng)態(tài)優(yōu)化問題(DOP)。其中，靜態(tài)優(yōu)化問題有統(tǒng)一的定義，可以認(rèn)為靜態(tài)優(yōu)化問題是只有一個(gè)解的單決策問題，然而對(duì)DOP目前尚且沒有一致的定義。簡言之，在動(dòng)態(tài)優(yōu)化問題中，其最優(yōu)解的位置會(huì)隨時(shí)間推移而改變。

求解DOP的優(yōu)化算法要求能夠在動(dòng)態(tài)環(huán)境中搜索到最優(yōu)解［3－4］。盡管傳統(tǒng)演化算法(Evolutionary Algorithm，EA)如粒子群算法、差分進(jìn)化算法、人工免疫算法等在求解靜態(tài)優(yōu)化問題上取得了很好的效果，但求解DOP需要對(duì)傳統(tǒng)EA進(jìn)行相關(guān)的改進(jìn)。

目前，動(dòng)態(tài)優(yōu)化算法主要可以分為環(huán)境變化后增加多樣性的方法、運(yùn)行過程中始終保持多樣性的方法、基于記憶機(jī)制的方法、多種群方法和基于預(yù)測機(jī)制方法5類［5］。其中，多種群方法主要應(yīng)用在一類具有多個(gè)局部最優(yōu)(多峰)函數(shù)的動(dòng)態(tài)優(yōu)化問題上，而多峰函數(shù)的優(yōu)化在現(xiàn)實(shí)中較為普遍。

對(duì)此國內(nèi)外許多學(xué)者將多種群方法與經(jīng)典演化算法相結(jié)合后應(yīng)用到對(duì)動(dòng)態(tài)優(yōu)化問題的求解上。如:Yang等［6］使用了分層聚類的方法把種群分成多個(gè)子種群，該方法是子種群初始粒子依據(jù)在適應(yīng)值曲面的分布自動(dòng)產(chǎn)生，而不是依賴于像kmeans聚類方法中的參數(shù)k;Brest等［2］提出了自適應(yīng)參數(shù)的多種群差分進(jìn)化(Self-Adaptive Differential Evolution，jDE)算法，控制參數(shù)F和Cr能夠有效地自適應(yīng);姜立強(qiáng)等［7］提出改進(jìn)差分進(jìn)化(Modified Differential Evolution，MDE)算法，該算法將種群分為偵測和搜索兩個(gè)種群，但該算法過于簡單，在求解多峰函數(shù)時(shí)極易陷入局部最優(yōu);陳健等［8］提出多種群骨干粒子群優(yōu)化 (Multi-swarms Bare Bones Particle Swarm Optimization，MBBPSO)算法，該算法通過設(shè)置環(huán)境勘探粒子及時(shí)檢測環(huán)境的變化，環(huán)境變化后，利用上一個(gè)環(huán)境搜索的信息初始化新的種群，當(dāng)種群陷入停滯時(shí)，采用新的進(jìn)化方程以加強(qiáng)粒子的活性和使用多種群策略維持種群的多樣性，但該算法在求解大規(guī)模動(dòng)態(tài)優(yōu)化問題上表現(xiàn)不佳;Ali等［9］提出基于成功率的自適應(yīng)的種群動(dòng)態(tài)衰減的部落差分進(jìn)化算法(adaptive successbased Tribal DE algorithm with dynamic population Reduction，sTDE-dR)算法，該算法采用自適應(yīng)的策略來控制F、CR參數(shù)，并提出多種群競爭策略。算法中種群的整體規(guī)模逐漸減小，各子種群通過比較平均誤差來確定各子種群在下一代保存多少，以此來保證自適應(yīng)的最優(yōu)策略在最優(yōu)子種群中引導(dǎo)搜索最優(yōu)解和更充分地利用有限的評(píng)價(jià)代價(jià)。

雖然國內(nèi)外學(xué)者對(duì)改進(jìn)EA求解DOP作出了很多工作，但是在平衡算法的搜索操作和尋優(yōu)操作方面，在搜索過程中維持種群的多樣性方面，在算法跳出局部最優(yōu)方面以及在快速追蹤移動(dòng)的最優(yōu)解方面依然有很多不足。

本文在已有研究的基礎(chǔ)上，提出一種求解動(dòng)態(tài)優(yōu)化問題的多種群競爭差分進(jìn)化算法(Differential Evolution algorithm with Competitive Strategy based on multi-population，DECS)。該算法將一個(gè)子種群作為偵測種群，采用新的偵測方法;其余多個(gè)子種群作為搜索種群，通過各搜索種群相互競爭來增強(qiáng)種群多樣性，且更充分地利用了有限的評(píng)價(jià)代價(jià);在搜索種群搜索過程中，保證在一個(gè)局部最優(yōu)鄰域內(nèi)有且僅有一個(gè)搜索種群進(jìn)行尋優(yōu)操作。數(shù)值算例表明了該方法的有效性和可行性。

1 相關(guān)工作

1．1 動(dòng)態(tài)優(yōu)化問題的定義和描述

在文獻(xiàn)［10－12］中，DOP被定義為在一段時(shí)間內(nèi)的一系列SOP，即每個(gè)動(dòng)態(tài)函數(shù)由一個(gè)基本靜態(tài)函數(shù)和由一組動(dòng)態(tài)規(guī)則應(yīng)用到該基函數(shù)所獲得的動(dòng)態(tài)函數(shù)序列組成。定義如下:

定義1 假設(shè)ψ為搜索空間，向量x∈ψ，時(shí)間t∈T，一個(gè)動(dòng)態(tài)函數(shù)DFt描述如下:

其中:fb0(x)是帶有k個(gè)可變化特征的基準(zhǔn)靜態(tài)函數(shù);gt是在t－1時(shí)刻動(dòng)態(tài)適應(yīng)度函數(shù)的參數(shù)函數(shù);cht是在t時(shí)刻基函數(shù)所有可能的改變集合;st是t時(shí)刻特征的改變程度，最后求得t時(shí)刻新的評(píng)價(jià)值。

定義2 函數(shù)gt可以被描述為:

在靜態(tài)環(huán)境下，傳統(tǒng)EA中種群個(gè)體不斷迭代而逐漸集中在搜索空間的一個(gè)固定解或者搜索空間的一個(gè)有限區(qū)域，正常而不是過早地收斂對(duì)于傳統(tǒng)EA處理靜態(tài)優(yōu)化問題是必需的，但是，對(duì)于動(dòng)態(tài)優(yōu)化問題而言，一旦收斂，那么當(dāng)新的環(huán)境到來時(shí)，EA就失去了探索新的區(qū)域所需要的多樣性，從而不能追蹤到在新的環(huán)境下已經(jīng)變化了的最優(yōu)解，這種收斂趨勢限制了EA算法的性能;因此在動(dòng)態(tài)優(yōu)化問題的求解過程中，對(duì)不斷變化的最優(yōu)解的快速跟蹤甚至比找到最優(yōu)解本身更有意義［5］，求解DOP的主要挑戰(zhàn)在于維持種群多樣性和追蹤移動(dòng)的最優(yōu)解。

而基于群體實(shí)參數(shù)的差分進(jìn)化(DE)算法［13－14］是目前最好的隨機(jī)優(yōu)化算法之一，該方法原理簡單、受控參數(shù)少、魯棒性強(qiáng)，通過啟發(fā)式搜索策略具有自組織性、自適應(yīng)性及并行性等特點(diǎn)，并且不要求目標(biāo)函數(shù)連續(xù)、可微等信息，具有極好的全局搜索能力［15］。基于此，本文通過改進(jìn)差分進(jìn)化算法來求解DOP。

1．2 量子個(gè)體

Blackwell等［16］認(rèn)為所有個(gè)體不一定要全部按照相同的規(guī)則產(chǎn)生，因此他們提出一種類似于量子機(jī)制的量子粒子規(guī)則，在種群中最優(yōu)個(gè)體位置的鄰域內(nèi)產(chǎn)生新的個(gè)體。

在全局最優(yōu)位置Vg處，以半徑rcloud的球體，種群下一代產(chǎn)生規(guī)則如下:

這種方法在rcloud范圍內(nèi)，會(huì)有較高的可能性生成靠近最優(yōu)值的點(diǎn)。此外，隨著維度D的增加，可能性也會(huì)增加。

2 多種群競爭的差分進(jìn)化算法

2．1 偵測環(huán)境變化

如何及時(shí)監(jiān)測環(huán)境變化是任何進(jìn)化算法求解DOP必須解決的首要問題，一般是通過設(shè)置監(jiān)測點(diǎn)來實(shí)現(xiàn)。目前常用的監(jiān)測點(diǎn)選取方法是隨機(jī)選取搜索種群中任意個(gè)體或同時(shí)選擇搜索種群中最優(yōu)個(gè)體和次最優(yōu)個(gè)體［17］，當(dāng)發(fā)現(xiàn)監(jiān)測點(diǎn)的評(píng)價(jià)值改變時(shí)則判斷為環(huán)境改變，但這兩種方法都不能及時(shí)感知環(huán)境變化。

DECS專門設(shè)定一個(gè)種群作為偵測種群，該種群中任何一個(gè)個(gè)體的評(píng)價(jià)值發(fā)生變化，都將判定為環(huán)境發(fā)生改變。

而針對(duì)環(huán)境中維度改變的情況，只要偵測種群發(fā)現(xiàn)自身維度與環(huán)境維度不一致，則判定為環(huán)境發(fā)生改變。

2．2 排除規(guī)則

使用多個(gè)種群來求解動(dòng)態(tài)優(yōu)化問題需要各個(gè)子種群能有效地分開和避免尋找相同的區(qū)域，確保沒有任意兩個(gè)種群追蹤同一個(gè)局部最優(yōu)位置的鄰域(峰)［17］。

每一次迭代，將各搜索種群中評(píng)價(jià)值最優(yōu)個(gè)體依次進(jìn)行比較，如果任意兩個(gè)搜索種群中最優(yōu)個(gè)體的歐氏距離小于預(yù)先定義的閾值rexcl，則有可能兩個(gè)搜索種群在同一個(gè)局部最優(yōu)位置的鄰域?qū)?yōu)。那么，將這兩個(gè)搜索種群中最優(yōu)個(gè)體的評(píng)價(jià)值進(jìn)行比較，將較好評(píng)價(jià)值個(gè)體所在的搜索種群留下，另一個(gè)搜索種群重新初始化。

對(duì)排斥半徑rexcl的取值按照以下的經(jīng)驗(yàn)規(guī)則產(chǎn)生:假設(shè)所有的峰均勻分布在整個(gè)搜索空間，那么

其中:X為搜索范圍，peaks為在環(huán)境中峰的個(gè)數(shù)，D為搜索向量的維度。

算法在同一個(gè)峰只保留一個(gè)最優(yōu)種群，將其他種群重新初始化，以便充分利用有限的評(píng)價(jià)代價(jià)和提高種群的多樣性。

2．3 種群競爭機(jī)制

每迭代m次，就將n個(gè)搜索種群中最優(yōu)個(gè)體的評(píng)價(jià)值進(jìn)行比較，保留較優(yōu)個(gè)體所在的搜索種群，剩余n－1個(gè)搜索種群重新初始化，在不斷迭代中，多次競爭。

因?yàn)閷?duì)動(dòng)態(tài)優(yōu)化問題的求解，總的評(píng)價(jià)次數(shù)是預(yù)先設(shè)定的，而所有搜索種群在獨(dú)立尋優(yōu)的過程中，各搜索種群的每一次迭代都需要花費(fèi)一定的評(píng)價(jià)代價(jià)，如果陷入局部最優(yōu)的種群繼續(xù)迭代，會(huì)造成評(píng)價(jià)代價(jià)的浪費(fèi)。但是將競爭失敗的種群重新初始化后，就可以將其花費(fèi)的評(píng)價(jià)代價(jià)用在對(duì)環(huán)境的搜索上。一旦其找到更優(yōu)的局部最優(yōu)區(qū)域，那么，其他搜索種群又將重新初始化。

這種競爭機(jī)制保持一個(gè)搜索種群進(jìn)行尋優(yōu)操作，n－1個(gè)搜索種群進(jìn)行環(huán)境探索操作，各搜索種群通過競爭決定是尋優(yōu)操作或探索操作。以此確保在搜索最優(yōu)解的同時(shí)增加了種群的多樣性，從而有效地解決了種群容易陷入局部最優(yōu)的問題。

2．4 DECS 描述

基于以上描述，本文提出的多種群競爭差分進(jìn)化算法的主要步驟如下:

步驟1 初始化。設(shè)置算法維度D，設(shè)置算法總評(píng)價(jià)次數(shù)，種群初始化范圍［Xmin，Xmax］，峰的數(shù)量 peaks，初始化偵測種群P0，計(jì)算P0的評(píng)價(jià)值向量f(P0)，初始化各搜索種群P1，P2，…，Pn，算法迭代次數(shù) iter← 0。

步驟2 偵測環(huán)境變化算法。

1)若環(huán)境發(fā)生維度變化，則更新維度參數(shù)D，并將所有搜索種群 P1，P2，…，Pn重新初始化，iter←0，跳轉(zhuǎn)步驟8;

2)若偵測種群的評(píng)價(jià)值向量中任何一個(gè)值發(fā)生變化，則以變化后的評(píng)價(jià)值向量更新變化前的評(píng)價(jià)值向量，并將所有搜索種群 P1，P2，…，Pn重新初始化，iter← 0，跳轉(zhuǎn)步驟 8。

步驟3 對(duì)n個(gè)搜索種群執(zhí)行變異操作。

步驟4 對(duì)n個(gè)搜索種群執(zhí)行交叉操作。

步驟5 對(duì)n個(gè)搜索種群執(zhí)行選擇操作。

步驟6 排除算法:

1)計(jì)算最小排除距離 rexcl的值;計(jì)算 P1，P2，…，Pn種群的評(píng)價(jià)值向量，并找出其中最優(yōu)的個(gè)體besti(i=1，2，…，n);

2)計(jì)算種群中最優(yōu)個(gè)體的歐氏距離:rj=d(besti，best((i+1)modn))，j=1，2，…，n。如果rj＜ rexcel，則計(jì)算f(besti)與f(best((i+1)modn))，保留 besti，best((i+1)modn)中較優(yōu)評(píng)價(jià)值所在搜索種群，另一個(gè)搜索種群重新初始化。

步驟7 競爭算法:每迭代m次，計(jì)算P1，P2，…，Pn種群中最優(yōu)個(gè)體評(píng)價(jià)值f(best1)，f(best2)，…，f(bestn);保留f(best1)，f(best2)，…，f(bestn)中最優(yōu)評(píng)價(jià)值所對(duì)應(yīng)的種群，其他種群重新初始化;并對(duì)保留的唯一種群的下一代執(zhí)行量子個(gè)體生成機(jī)制。

步驟8 迭代次數(shù)iter←iter+1，如果達(dá)到總評(píng)價(jià)次數(shù)，則算法結(jié)束;否則，跳轉(zhuǎn)步驟2。

圖1 多種群競爭差分進(jìn)化算法的流程Fig．1 Flowchart of multi-population-based competitive differential evolution algorithm

3 實(shí)驗(yàn)設(shè)置與測試函數(shù)

仿真實(shí)驗(yàn)環(huán)境為 Windows 10系統(tǒng)，其中 CPU為 Inter Core i5-4590/3．30 GHz，4核，內(nèi)存為 8 GB，實(shí)驗(yàn)使用 Matlab進(jìn)行編碼。

為了驗(yàn)證算法的性能，這里選取了IEEE CEC 2009提出的標(biāo)準(zhǔn)動(dòng)態(tài)優(yōu)化問題集 GDBG benchmark進(jìn)行測試，此benchmark構(gòu)建了峰的位置、高度、寬度、維度會(huì)變化的動(dòng)態(tài)環(huán)境，具體函數(shù)形式見文獻(xiàn)［18］，并將計(jì)算結(jié)果與復(fù)位粒子群優(yōu)化(restart Particle Swarm Optimization，rPSO)算法［19］(經(jīng)典算法PSO求解動(dòng)態(tài)環(huán)境問題的改進(jìn)算法，一旦環(huán)境變化，種群將重新初始化)、人工免疫算法(Artificial Immune Network for Dynamic optimization，Dopt-aiNet)算法［19］和 MDE 算法［7］進(jìn)行比較。GDBG中的測試函數(shù)見表1。其中F1函數(shù)為Rotation peak函數(shù)，具體形式見文獻(xiàn)［18］，F(xiàn)2函數(shù)是Sphere函數(shù)的混合函數(shù)，F(xiàn)3函數(shù)是Rastrigin函數(shù)的混合函數(shù)，F(xiàn)4函數(shù)是Griewank函數(shù)的混合函數(shù)，F(xiàn)5函數(shù)是Ackley函數(shù)的混合函數(shù)，F(xiàn)6函數(shù)是表1中所有函數(shù)的混合函數(shù)。

表1 測試基準(zhǔn)函數(shù)Tab．1 Details of the basic benchmark functions

對(duì)GDBG benchmark中每一個(gè)測試函數(shù)進(jìn)行7種改變方式，包括小步改變(T1)、大步改變(T2)、隨機(jī)改變(T3)、混沌改變(T4)、周期性改變(T5)、帶噪聲的周期性變化(T6)和維度改變(T7)，以此模擬了49個(gè)標(biāo)準(zhǔn)動(dòng)態(tài)變化問題。其中僅F1是求最大值問題，且需要分別求解10個(gè)峰和50個(gè)峰兩種情況;F2～F6函數(shù)都是求最小值問題。

對(duì)于49個(gè)動(dòng)態(tài)問題中每一個(gè)動(dòng)態(tài)問題，獨(dú)立運(yùn)行5次，總評(píng)價(jià)次數(shù)為7．5E06，每評(píng)價(jià)1．5E05次環(huán)境改變，因此單個(gè)問題每次運(yùn)行時(shí)環(huán)境改變10次。

每當(dāng)環(huán)境改變時(shí)，記錄本次變化期間的離線誤差:

其中:f(xbest(t))為當(dāng)前環(huán)境中理論最優(yōu)評(píng)估值，f(x*(t))為當(dāng)前算法求解的實(shí)際最優(yōu)評(píng)估值。

當(dāng)一個(gè)動(dòng)態(tài)問題達(dá)到總評(píng)價(jià)次數(shù)時(shí)，計(jì)算算法的平均離線誤差期望(Average mean，Avg_mean)、平均離線誤差標(biāo)準(zhǔn)差(STandard Deviation，STD)。計(jì)算公式見文獻(xiàn)［18］。

DECS參數(shù)如表2所示，rPSO算法、Dopt-aiNet算法和MDE算法的參數(shù)設(shè)置分別見文獻(xiàn)［7，18－19］。

表2 DECS參數(shù)Tab．2 Parameter settings for DECS

4 實(shí)驗(yàn)結(jié)果

表3～9給出了三種算法在GDBG benchmark上的測試結(jié)果，包括平均離線誤差期望(Avg_mean)、平均離線誤差標(biāo)準(zhǔn)差(STD)，表中較優(yōu)實(shí)驗(yàn)結(jié)果用加粗字體表示。

圖2～3表示在部分問題上，DECS一次獨(dú)立求解的離線誤差收斂圖、算法實(shí)際最優(yōu)評(píng)價(jià)值和理論最優(yōu)評(píng)價(jià)值的收斂圖。其中:實(shí)線表示實(shí)際最優(yōu)評(píng)價(jià)值，虛線表示理論最優(yōu)評(píng)價(jià)值;橫軸為評(píng)價(jià)次數(shù)，一次獨(dú)立運(yùn)行的評(píng)價(jià)次數(shù)為1．5E06，每評(píng)價(jià)1．5E05次環(huán)境改變。

表3 10個(gè)峰的F1函數(shù)的Average mean和STD性能值Tab．3 Average mean and STD for F1 with 10 peaks

表4 50個(gè)峰的F1函數(shù)的Average mean和STD性能值Tab．4 Average mean and STD for F1 with 50 peaks

表5 F2函數(shù)的Average mean和STD性能值Tab．5 Average mean and STD for F2

表6 F3函數(shù)的Average mean和STD性能值Tab．6 Average mean and STD for F3

表7 F4函數(shù)的Average mean和STD性能值Tab．7 Average mean and STD for F4

表8 F5函數(shù)的Average mean和STD性能值Tab．8 Average mean and STD for F5

表9 F6函數(shù)的Average mean和STD性能值Tab．9 Average mean and STD for F6

圖2 不同動(dòng)態(tài)優(yōu)化問題的離線誤差收斂趨勢Fig．2 Convergence trend of off-line error for different DOP

圖3 不同動(dòng)態(tài)優(yōu)化問題的評(píng)價(jià)值收斂趨勢Fig．3 Convergence trend of evaluation value for different DOP

實(shí)驗(yàn)中主要衡量的評(píng)估量是平均離線誤差期望和平均離線誤差標(biāo)準(zhǔn)差，平均離線誤差期望為離線誤差函數(shù)Elast(t)在多次獨(dú)立運(yùn)行過程中多次動(dòng)態(tài)變化的離線誤差期望，能夠有效衡量算法對(duì)動(dòng)態(tài)環(huán)境問題的求解性能。平均誤差標(biāo)準(zhǔn)差則反映算法在求解DOP時(shí)的魯棒性。

從表3～表9中可以看出，在10個(gè)峰F1函數(shù)的T1～T4和T7變化問題，50個(gè)峰F1函數(shù)的T2、T3、T7變化問題，F(xiàn)2函數(shù)的T3、T5變化問題，F(xiàn)3函數(shù)的T1～T7變化問題，F(xiàn)4函數(shù)的T2、T3、T5變化問題，F(xiàn)5、F6函數(shù)的T1～T7變化問題上DECS的平均誤差期望小于Dopt-aiNet算法。這些結(jié)果統(tǒng)計(jì)表明DECS在49個(gè)問題中有34個(gè)問題的求解結(jié)果優(yōu)于DoptaiNet算法，49個(gè)問題中所有問題的求解結(jié)果優(yōu)于rPSO算法和MDE算法。

從以上實(shí)驗(yàn)結(jié)果看出，DECS在F3函數(shù)、F5函數(shù)、F6函數(shù)上所有變化的求解都要優(yōu)于Dopt-aiNet算法、rPSO算法、MDE算法。F3函數(shù)的基準(zhǔn)函數(shù)為Rastrigin函數(shù)，其有多個(gè)局部最優(yōu)值，是高度多模態(tài)的多峰函數(shù)，但多個(gè)峰的最小值位置是規(guī)律分布的。F5函數(shù)的基準(zhǔn)函數(shù)為Ackley函數(shù)，其圖像特征是外部區(qū)域有多個(gè)局部最小值鄰域，中心區(qū)域有一個(gè)較大鄰域的全局最優(yōu)位置，且相對(duì)全局最優(yōu)位置的鄰域來說，外部區(qū)域幾乎是平坦的。F6函數(shù)的基準(zhǔn)函數(shù)具有5個(gè)函數(shù)的眾多特征。這說明，DECS能夠有效求解環(huán)境中特征明顯的動(dòng)態(tài)優(yōu)化問題。

DECS在F2函數(shù)和F4函數(shù)上所有變化的求解都是只有3個(gè)變化超過Dopt-aiNet算法，所有變化超過rPSO算法和MDE算法。F2函數(shù)的基準(zhǔn)函數(shù)為 Sphere函數(shù)，其在［－5．12，5．12］內(nèi)是一個(gè)連續(xù)的、凸的、單峰的球面函數(shù)，盡管本實(shí)驗(yàn)中該函數(shù)搜索范圍［－100，100］較大，但該函數(shù)相比本實(shí)驗(yàn)中其它函數(shù)卻不具有較大的復(fù)雜性。F4函數(shù)的基準(zhǔn)函數(shù)為Griewank函數(shù)，其有許多廣泛分布的局部最小值區(qū)域，而且是規(guī)律分布的，這種復(fù)雜性在搜索范圍放大的情況下會(huì)體現(xiàn)出來，本實(shí)驗(yàn)中該函數(shù)的搜索范圍［－100，100］遠(yuǎn)大于Rastrigin函數(shù)的搜索范圍［－5，5］，其峰的數(shù)量也遠(yuǎn)遠(yuǎn)大于Rastrigin函數(shù)峰的數(shù)量。實(shí)驗(yàn)數(shù)據(jù)表明，對(duì)于F2函數(shù)問題，DECS能夠找到最優(yōu)解的鄰域，但Dopt-aiNet算法卻具有更好的求解性能。而對(duì)于F4函數(shù)這種具有較大復(fù)雜性的環(huán)境，DECS性能優(yōu)于rPSO算法和MDE算法，但和Dopt-aiNet算法性能相近，因此DECS在較大復(fù)雜性的環(huán)境中不具備明顯優(yōu)勢。

DECS在10峰的F1函數(shù)的7個(gè)變化中有5種變化超過Dopt-aiNet算法，全部超過rPSO算法和MDE算法，但對(duì)于50個(gè)峰的F1函數(shù)，之所以在T1、T4變化上DECS效果要弱于Dopt-aiNet算法，那是因?yàn)橄鄬?duì)于50個(gè)峰，實(shí)驗(yàn)用的搜索種群數(shù)量太少。但由于總評(píng)價(jià)次數(shù)是一定的，搜索種群數(shù)量太多，會(huì)加大對(duì)評(píng)價(jià)代價(jià)的消耗，因此搜索種群并不是越多越好。

對(duì)于49個(gè)函數(shù)中T1～T7的變化問題，在T3變化中的7個(gè)函數(shù)問題中，DECS比Dopt-aiNet算法、rPSO算法、MDE算法都要好;因?yàn)門3變化是隨機(jī)變化，GDBG benchmark中T3變化的環(huán)境變化偏置量為一個(gè)服從正態(tài)分布的隨機(jī)量與一個(gè)常數(shù)的乘積。這說明DECS能夠有效求解環(huán)境隨機(jī)變化的動(dòng)態(tài)優(yōu)化問題。

在T2變化的7個(gè)函數(shù)問題中，DECS比Dopt-aiNet算法在6個(gè)問題中更好，比rPSO算法和MDE算法都要好;T2變化為環(huán)境大步的改變，這說明DECS能夠有效求解環(huán)境變化明顯的動(dòng)態(tài)優(yōu)化問題。

在T5、T7各自的7個(gè)函數(shù)變化問題中，DECS比DoptaiNet算法都是在5個(gè)問題上更好，比rPSO算法和MDE算法都要好。這說明DECS在求解周期的變化問題和維度變化問題上具有較好的性能。

在T1、T4、T6各自的7個(gè)函數(shù)變化問題中，DECS比DoptaiNet算法分別在3個(gè)、3個(gè)和4個(gè)問題上表現(xiàn)更好，比rPSO算法和MDE算法都要好，實(shí)驗(yàn)表明在這類問題上，DECS與Dopt-aiNet算法性能相差不多。這說明DECS在環(huán)境小步變化、混沌變化和帶噪聲的周期變化等問題上不具備明顯優(yōu)勢。

在上述問題中，DECS之所以在基函數(shù)環(huán)境特征較明顯的動(dòng)態(tài)優(yōu)化問題上具有良好性能，是因?yàn)槠淠芸焖俑兄h(huán)境變化并且在尋優(yōu)過程中仍有較好的種群多樣性。而對(duì)環(huán)境隨機(jī)變化、大步變化、周期性變化和維度變化等問題上也具有良好性能，是因?yàn)镈ECS引入競爭機(jī)制后，平衡了種群的探索與尋優(yōu)，使算法具有非常好的環(huán)境探索能力。

在DECS與Dopt-aiNet算法比較中，DECS在優(yōu)于DoptaiNet算法的34個(gè)問題中有23個(gè)問題的平均誤差標(biāo)準(zhǔn)差優(yōu)于Dopt-aiNet算法，這說明在求解49個(gè)動(dòng)態(tài)優(yōu)化問題中，DECS不僅平均性能超過Dopt-aiNet算法，而且具有較好的魯棒性。DECS與MDE算法比較過程中，DECS在所有49個(gè)問題中的平均誤差期望均優(yōu)于MDE算法，而在這49個(gè)問題中有41個(gè)問題的平均誤差標(biāo)準(zhǔn)差要優(yōu)于MDE算法;在DECS與rPSO算法的比較中，DECS在所有動(dòng)態(tài)問題中的平均誤差期望均優(yōu)于rPSO算法，而在49個(gè)問題中有48個(gè)問題的平均誤差標(biāo)準(zhǔn)差要優(yōu)于rPSO算法，這說明在求解49個(gè)動(dòng)態(tài)優(yōu)化問題中，DECS不僅平均性能遠(yuǎn)遠(yuǎn)超過rPSO算法和MDE算法，而且具有更好的魯棒性。

從圖3看出一旦環(huán)境變化，環(huán)境中理論最優(yōu)的評(píng)價(jià)值也變化，而DECS的實(shí)際最優(yōu)評(píng)價(jià)值卻能夠及時(shí)監(jiān)測并且快速追蹤。由此看出DECS具備求解動(dòng)態(tài)問題的能力。

5 結(jié)語

本文提出一種稱為DECS的改進(jìn)算法來求解DOP，并在統(tǒng)計(jì)學(xué)上表明是有效的。該算法在傳統(tǒng)的DE算法框架內(nèi)引入了多種群方法和競爭策略，使用多個(gè)種群并行搜索來增強(qiáng)搜索過程中的多樣性。同時(shí)，多個(gè)搜索種群之間互相競爭，大大提高了算法的搜索能力，更高效地利用了有限的評(píng)估代價(jià)。排除規(guī)則和量子個(gè)體生成機(jī)制使搜索種群在搜索空間上具有更好的種群多樣性;而獨(dú)立的偵測種群，能夠迅速感知環(huán)境變化。

實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)表明，DECS與其他演化算法相比表現(xiàn)出更好的優(yōu)化性能和更好的魯棒性。未來的工作可以使搜索種群之間互相交流，淘汰掉的個(gè)體往往具有更優(yōu)的多樣性;也可以使用交叉概率、放縮因子與變異策略自適應(yīng)地調(diào)整來提高算法的性能。