李亞楠 ，郭海湘 ，黎金玲，劉曉

（中國(guó)地質(zhì)大學(xué)1a.經(jīng)濟(jì)管理學(xué)院；1b.數(shù)字化商務(wù)管理研究中心；1c.中國(guó)礦產(chǎn)資源戰(zhàn)略與政策研究中心，武漢 430074；2.武漢工程科技學(xué)院，武漢 430200）

差分演化算法[1]（Differential Evolution，DE）是Price等為求解切比學(xué)夫多項(xiàng)式問題于1995 年提出的一種演化算法，是基于群體的隨機(jī)搜索算法。算法最新穎的特點(diǎn)是它的變異操作，其操作是通過對(duì)當(dāng)前個(gè)體加上2個(gè)隨機(jī)選定個(gè)體的帶權(quán)差來(lái)進(jìn)行變異。因此，在算法迭代初期因種群個(gè)體差異較大，使得算法具有較強(qiáng)的全局搜索能力，但到了算法趨于收斂的迭代后期，種群個(gè)體差異較小，使得算法具有較強(qiáng)的局部搜索能力。這種新穎的變異操作也使得差分演化算法在求解優(yōu)化問題上具有其他進(jìn)化算法不可比擬的優(yōu)點(diǎn)。主要總結(jié)為：收斂速度快、不易陷入局部最優(yōu)及通用性強(qiáng)。而其包含的控制參數(shù)主要是種群大小、個(gè)體維度、變異因子以及交叉概率，待定參數(shù)較少。因其收斂速度快、不易陷入局部最優(yōu)、通用性強(qiáng)、待定參數(shù)少等優(yōu)點(diǎn)，差分演化算法被廣泛應(yīng)用于全局優(yōu)化、運(yùn)籌管理和工程設(shè)計(jì)等領(lǐng)域[2-4]。

標(biāo)準(zhǔn)的差分演化算法在高維數(shù)、多峰值復(fù)雜函數(shù)的應(yīng)用上容易出現(xiàn)“早熟”現(xiàn)象，即容易陷入局部最?。缓笃谑諗克俣容^慢，表現(xiàn)不夠穩(wěn)??；對(duì)控制參數(shù)設(shè)置及差分策略的選擇比較敏感，會(huì)影響差分演化算法的通用性。為此，許多學(xué)者對(duì)標(biāo)準(zhǔn)的差分演化算法進(jìn)行了改進(jìn)。Brest等[5]提出了一種改進(jìn)的差分演化算法（jDE），算法對(duì)縮放因子和交叉概率進(jìn)行了自適應(yīng)的調(diào)整；Wang等[6]提出了一種策略和控制參數(shù)的混合式差分演化算法（CoDE），其中縮放因子和交叉概率選自已有研究中表現(xiàn)較好的值；Qin等[7]提出了一種自適應(yīng)策略的差分演化算法（SaDE），使得算法能夠根據(jù)具體情況進(jìn)行差分策略的選擇；Zhang等[8-9]提出了一種帶有存儲(chǔ)機(jī)制的自適應(yīng)差分演化算法（JADE），在算法中給出了一種改進(jìn)的DE/current-to-best/l差分策略；Mallipeddi等[10]提出了一種控制參數(shù)和差分策略整體自適應(yīng)的差分演化算法（EPSDE），對(duì)控制參數(shù)和差分策略進(jìn)行了匹配；Ghosh等[11]提出了一種基于適應(yīng)度值的控制參數(shù)自適應(yīng)方法的差分演化算法（FiADE），其中縮放因子和交叉概率根據(jù)目標(biāo)的適應(yīng)度值進(jìn)行自適應(yīng)調(diào)整；Pan等[12]提出了一種自適應(yīng)的差分演化算法，其中每個(gè)個(gè)體對(duì)應(yīng)一對(duì)單獨(dú)的縮放因子和交叉概率；Zou等[13]提出了一種改進(jìn)的差分演化算法（MDE），其中交叉概率分別使用高斯分布和均勻分布生成，旨在提高種群多樣性；鄭建國(guó)等[14]提出了一種改進(jìn)的差分演化算法，設(shè)計(jì)了一種新穎的DEB 準(zhǔn)則[15]用于選擇操作。雖然在提高差分演化算法的搜索能力和收斂速度方面已經(jīng)做了很多工作，但是自適應(yīng)策略變得越來(lái)越復(fù)雜，而且已有研究文獻(xiàn)的仿真結(jié)果表明，差分演化算法的性能方面還有很大的改進(jìn)空間。

本文提出了一種基于模擬退火的參數(shù)自適應(yīng)差分演化算法（Enhanced Self-adaptive Differential Evolution，ESADE），在算法中先對(duì)種群進(jìn)行初始化，生成2個(gè)相同的種群。同時(shí)，初始化一組控制參數(shù)，接著對(duì)這組控制參數(shù)進(jìn)行簡(jiǎn)單的差分計(jì)算，即對(duì)其進(jìn)行差分演化算法中的變異操作，生成一組新的控制參數(shù)，這兩組控制參數(shù)分別和2個(gè)種群相對(duì)應(yīng)。然后，2個(gè)種群在兩組不同的控制參數(shù)下進(jìn)行變異、交叉操作，生成兩組試驗(yàn)向量。在選擇操作中，通過對(duì)兩組試驗(yàn)向量的比較后選出適應(yīng)度表現(xiàn)最優(yōu)的試驗(yàn)向量作為下一代的目標(biāo)向量。為了提高算法的全局搜索能力，本算法將模擬退火的思想應(yīng)用在選擇操作上，并將表現(xiàn)較好的控制參數(shù)作為下一代初始化的控制參數(shù)。在這個(gè)進(jìn)化過程中，每個(gè)目標(biāo)向量對(duì)應(yīng)的控制參數(shù)都能在學(xué)習(xí)前代優(yōu)良經(jīng)驗(yàn)的基礎(chǔ)上逐步地進(jìn)行自適應(yīng)，解決了傳統(tǒng)差分演化算法對(duì)控制參數(shù)設(shè)置比較敏感這一問題。為了測(cè)試ESADE算法的性能，本文將ESADE 算法與jDE、JADE、SaDE、EPSDE及CoDE算法進(jìn)行了比較，比較結(jié)果表明，ESADE算法的性能在整體上優(yōu)于其他5 種算法。同時(shí)，為了測(cè)試ESADE 算法解決實(shí)際問題的能力，本文將ESADE 算法應(yīng)用于TSP 問題，結(jié)果表明，ESADE算法能夠有效解決TSP問題。

1 傳統(tǒng)的差分演化算法及其變形

差分演化算法的主要思想是通過變異操作產(chǎn)生變異個(gè)體，然后進(jìn)行交叉操作得到試驗(yàn)個(gè)體。最后，通過選擇操作使得較好的個(gè)體進(jìn)入下一代群體。由于差分演化算法涉及參數(shù)少，容錯(cuò)性好，有全局優(yōu)化的功能并且易于編碼實(shí)現(xiàn)，故此后被廣泛應(yīng)用于各種科學(xué)領(lǐng)域。但差分演化算法也存在缺點(diǎn)，例如對(duì)控制參數(shù)設(shè)置及策略的選擇比較敏感，這些問題影響了差分演化算法的通用性，為了解決這些問題，很多改進(jìn)的差分演化算法被提出。

1.1 傳統(tǒng)的差分演化算法

差分演化算法包括初始化種群、變異、交叉和選擇4個(gè)基本操作[16]，基本執(zhí)行過程如圖1所示。

圖1 差分演化算法的基本流程

在圖1的基礎(chǔ)上，對(duì)差分演化算法的4個(gè)基本操作做進(jìn)一步闡述。

（1）編碼。差分演化算法是一種基于種群的全局優(yōu)化算法，種群中的個(gè)體均采用實(shí)數(shù)編碼。

（2）個(gè)體結(jié)構(gòu)。用NP表示種群大小，種群中第i個(gè)個(gè)體在第G代記為

其中，D為個(gè)體所包含的維度。

（3）初始化種群。種群初始化采用公式

其中：xj，i，0為第G=0代，種群中第i個(gè)個(gè)體第j個(gè)維度的值；randi，j（0，1）∈[0，1]并且隨機(jī)生成；

為搜索空間第j個(gè)維度的下界；

為搜索空間第j個(gè)維度的上界；Xmin和Xmax分別為搜索空間的下界和上界的向量表達(dá)形式。

（4）變異。差分演化算法的差分就是體現(xiàn)在變異操作上，變異的一般過程為

式中：Xk，G為當(dāng)前種群中待變異的第k個(gè)體；Xm，G、Xi，G、Xj，G為當(dāng)前種群中隨機(jī)挑選的個(gè)體，并且k≠m≠i≠j；Vk，G為變異后的個(gè)體；F∈[0，1]為縮放因子。通常用DE/x/y/z表示不同的變異模式，DE表示差分演化算法；x為差分項(xiàng)前面的基礎(chǔ)項(xiàng)，通常有rand（基礎(chǔ)項(xiàng)是隨機(jī)從種群中選擇的個(gè)體）、best（基礎(chǔ)項(xiàng)是種群中最優(yōu)個(gè)體）、rand-to-best和current-to-best等；y為差分項(xiàng)個(gè)數(shù)，通常取1或2。z為交叉模式，通常為指數(shù)模式和二項(xiàng)式模式。

（5）交叉。交叉概率Cr∈[0，1]。交叉有兩種形式：①指數(shù)模式為

式中，jrand∈[1，2，…，D]為隨機(jī)選擇的值。

（6）選擇。交叉后得到的個(gè)體Ui，G和目標(biāo)個(gè)體Xi，G分別代入目標(biāo)函數(shù)進(jìn)行比較，因?yàn)椴罘盅莼惴ㄇ蟮氖悄繕?biāo)函數(shù)極小，所以其選擇過程為

1.2 5種改進(jìn)的差分演化算法

1.2.1 jDE算法 在jDE算法[5]中，控制參數(shù)F和Cr在進(jìn)化過程中是自適應(yīng)的，在編碼時(shí)，控制參數(shù)F和Cr被編碼在個(gè)體中，它們的調(diào)整是通過2個(gè)新的調(diào)整變量τ1和τ2。新一代的控 制參數(shù)Fi，G+1和Cri，G+1在變異操作之前就產(chǎn)生了，因此，jDE的這種自適應(yīng)控制參數(shù)機(jī)制能夠影響到變異操作、交叉操作以及選擇操作生成的新個(gè)體向量。

1.2.2 JADE算法 在JADE 算法[8-9]中引入了一種新穎的變異策略（即DE/current-to-pbest 策略）和一個(gè)用于存檔次優(yōu)解的存檔向量來(lái)引導(dǎo)算法進(jìn)化的方向。這種DE/current-to-pbest 策略利用多個(gè)最佳解決方案既滿足了變異策略的貪婪性又保留了種群的多樣性，同樣地，這種存檔向量用來(lái)存儲(chǔ)除最優(yōu)解外的較優(yōu)解，能夠保留種群的多樣性。

1.2.3 SaDE算法 在SaDE算法[7]中，每一代的差分策略是從策略侯選池（DE/rand/1，DE/rand/2，DE/rand-to-best/2，DE/current-to-rand/1）中，根據(jù)每個(gè)差分策略概率的大小進(jìn)行選擇，這個(gè)概率是通過對(duì)每個(gè)差分策略在一定數(shù)量的代數(shù)上的表現(xiàn)進(jìn)行計(jì)算的，其中這個(gè)一定數(shù)量的進(jìn)化代數(shù)稱為學(xué)習(xí)期（Learning Period，LP）。

1.2.4 EPSDE算法 在EPSDE 算法[10]中引入了差分策略池和控制參數(shù)池，其中控制參數(shù)池包括縮放因子值池和交叉概率值池。

在EPSDE算法中，初始化種群中每個(gè)個(gè)體隨機(jī)地從差分策略池中選擇一種差分策略，并相應(yīng)地從縮放因子值池和交叉概率值池中分別隨機(jī)選取一個(gè)值作為其縮放因子和交叉概率。在選擇操作中，當(dāng)試驗(yàn)向量的適應(yīng)度值比目標(biāo)向量的適應(yīng)度值好時(shí)，生成試驗(yàn)向量對(duì)應(yīng)的差分策略、縮放因子和交叉概率的組合將被保存在一個(gè)成功組合池里，并進(jìn)入下一代的進(jìn)化；當(dāng)試驗(yàn)向量的適應(yīng)度值比目標(biāo)向量的適應(yīng)度值差時(shí)，目標(biāo)向量對(duì)應(yīng)的差分策略、縮放因子和交叉概率將被隨機(jī)重新初始化，該初始化過程是以相同的概率直接從成功組合池中隨機(jī)選擇，或從差分策略、縮放因子和交叉概率各自對(duì)應(yīng)的池中隨機(jī)選擇。

1.2.5 CoDE 算法 類似地，Wang等[6]提出了一種結(jié)合不同差分策略的系統(tǒng)框架，稱為復(fù)合式差分演化算法（Composite DE，CoDE）。其中差分策略和控制參數(shù)是通過研究后選取表現(xiàn)較好的策略和參數(shù)值。

在CoDE算法中，對(duì)應(yīng)3種差分策略，每個(gè)目標(biāo)向量進(jìn)行差分演化計(jì)算后生成3個(gè)試驗(yàn)向量。將3個(gè)試驗(yàn)向量中適應(yīng)度值表現(xiàn)最好的一個(gè)與目標(biāo)向量的適應(yīng)度值進(jìn)行比較，如果其適應(yīng)度值表現(xiàn)比目標(biāo)向量的適應(yīng)度值好，則該試驗(yàn)向量將進(jìn)入下一代進(jìn)化。

2 基于模擬退火的參數(shù)自適應(yīng)差分演化算法

針對(duì)傳統(tǒng)差分演化算法對(duì)控制參數(shù)設(shè)置和差分策略選擇比較敏感，以及局部搜索能力較差導(dǎo)致的演化后期收斂速度變慢等問題，已經(jīng)有很多學(xué)者對(duì)傳統(tǒng)差分演化算法提出了改進(jìn)策略，雖然在提高差分演化算法的搜索能力和收斂速度方面已經(jīng)做了很多工作，但是自適應(yīng)策略變得越來(lái)越復(fù)雜，而且已有研究文獻(xiàn)的仿真結(jié)果表明，差分演化算法的性能方面還有很大的改進(jìn)空間?；谶@種情況，本文提出了一種基于模擬退火的參數(shù)自適應(yīng)差分演化算法（ESADE），其步驟如下：

（1）個(gè)體編碼。編碼個(gè)體包括三部分：候選解向量、控制參數(shù)和適應(yīng)度值。編碼個(gè)體結(jié)構(gòu)如圖2所示。

圖2 個(gè)體的編碼

（2）初始化。初始化包括控制參數(shù)初始化和種群初始化兩部分。其中，控制參數(shù)初始化包括種群大小NP，模擬退火中初始溫度參數(shù)t0，每個(gè)個(gè)體對(duì)應(yīng)的縮放因子oFi，G和每個(gè)個(gè)體對(duì)應(yīng)的交叉概率oCri，G。其中，oFi，G和oCri，G的動(dòng)態(tài)更新如下：

式中，oFi，G、oCri，G分別是以μF和μCr為均值通過柯西和正態(tài)分布生成的。μF、μCr初始值設(shè)置為0.5，每一代的更新過程分別為：

式中：SF是用來(lái)存儲(chǔ)成功進(jìn)化縮放因子的數(shù)組，即用來(lái)存儲(chǔ)能夠進(jìn)入下一代的試驗(yàn)向量對(duì)應(yīng)的縮放因子值的數(shù)組；SCr是用來(lái)存放成功進(jìn)化交叉因子的數(shù)組，即用來(lái)存儲(chǔ)能夠進(jìn)入下一代的試驗(yàn)向量對(duì)應(yīng)的交叉因子值的數(shù)組。

種群初始化是在相應(yīng)范圍內(nèi)均勻分布，

并且

則在G=0代時(shí)，第i個(gè)個(gè)體第j個(gè)屬性的初始化為

（3）參數(shù)變異。通過對(duì)控制參數(shù)oF和oCr進(jìn)行變異操作，得到一組新的控制參數(shù)mF和mCr，其變異過程為：

式中，r1、r2的取值是在1，2，…，NP中隨機(jī)抽取不同的整數(shù)。

生成2個(gè)相同的種群：①標(biāo)記為populationo，與控制參數(shù)oFi，G、oCri，G對(duì)應(yīng)進(jìn)行差分演化計(jì)算；②標(biāo)記為populationm，與控制參數(shù)mFi，G、mCri，G對(duì)應(yīng)進(jìn)行差分演化計(jì)算。

（4）種群變異操作。種群populationo的差分策略是DE/current-to-pbest/1，其變異操作過程為

種群populationm的差分策略是DE/current-topbest/1，其變異操作過程為

（5）種群交叉操作。種群populationo的交叉操作是二項(xiàng)交叉，其操作過程為

種群populationm的交叉操作是二項(xiàng)交叉，其操

作過程為

（5）種群選擇操作。種群選擇操作的過程是通過比較目標(biāo)向量Xi，G、種群poplutiono生成的試驗(yàn)向量oUi，G以及種群poplutionm生成的試驗(yàn)向量mUi，G選擇出適應(yīng)度值最優(yōu)的進(jìn)化到下一代。在該過程中，模擬退火的思想被加入到選擇操作中用來(lái)增強(qiáng)算法的全局搜索能力，t0為模擬退火中的初始化溫度參數(shù)，tG為第G代溫度參數(shù)，其中，tG更新與選擇操作過程為：

式中：G為進(jìn)化的第G代；f（oUi，G）為oUi，G的適應(yīng)度值；f（mUi，G）為mUi，G的適應(yīng)度值；f（Xi，G）為Xi，G的適應(yīng)度值。

（7）記錄優(yōu)良的控制參數(shù)。當(dāng)試驗(yàn)向量能夠成功進(jìn)化到下一代時(shí)，說(shuō)明其對(duì)應(yīng)的控制參數(shù)表現(xiàn)較好，這些表現(xiàn)較優(yōu)良的控制參數(shù)將分別被存入成功進(jìn)化縮放因子數(shù)組SF和成功進(jìn)化交叉因子數(shù)組SCr中。其過程為：

若Xi，G+1=oUi，G，則oFi，G→SF，oCri，G→SCr；若Xi，G+1=mUi，G，則mFi，G→SF，mCri，G→SCr。

當(dāng)數(shù)組SF、SCr內(nèi)存儲(chǔ)的控制參數(shù)數(shù)量超過一個(gè)上限值時(shí)，數(shù)組SF、SCr將被清空。

（8）更新控制參數(shù)。如果SF不是空集，則根據(jù)（7）、（5）對(duì)控制參數(shù)oF進(jìn)行更新，更新過程：

如果SCr不是空集，則根據(jù)（8）、（6）對(duì)控制參數(shù)oCr進(jìn)行更新，更新過程：

3 ESADE 算法與差分演化算法的其他變形的比較

3.1 實(shí)驗(yàn)設(shè)置

3.1.1 基準(zhǔn)函數(shù) 影響差分演化算法計(jì)算效果的因素主要包含實(shí)驗(yàn)環(huán)境、測(cè)試函數(shù)和控制參數(shù)的設(shè)置以及差分策略的選擇。為了測(cè)試ESADE 算法的性能，本文將ESADE算法與其他改進(jìn)差分演化算法在相同條件下進(jìn)行測(cè)試。因?yàn)楦倪M(jìn)的差分演化算法大多是針對(duì)變異因子、交叉概率以及差分策略進(jìn)行的改進(jìn)，因此，本文設(shè)置的相同條件主要包括相同的實(shí)驗(yàn)環(huán)境（電腦型號(hào)Dell-XPS8500和軟件型號(hào)Matlab-R2010a）、相同的測(cè)試函數(shù)以及相同的基本參數(shù)（種群大小、個(gè)體維度、算法進(jìn)化的代數(shù)以及獨(dú)立運(yùn)行次數(shù)）。本文使用17（f1～f17）個(gè)全局最小值的基準(zhǔn)函數(shù)作為測(cè)試函數(shù)，這些函數(shù)都是從參考文獻(xiàn)[15]中選擇的國(guó)際通用的測(cè)試函數(shù)，其維度均可以自由變化。其中，f1～f5是單峰函數(shù)，f6～f9是基本多峰函數(shù)，f10是擴(kuò)展多峰函數(shù)，f11～f17是混合組成函數(shù)。這些函數(shù)的最優(yōu)值f（x*）、最優(yōu)取值時(shí)x*的取值和x的初始范圍如表1所示，函數(shù)的詳細(xì)表達(dá)形式見附錄A。

表1 基準(zhǔn)函數(shù)的基本介紹

3.1.2 參數(shù)設(shè)置 為了比較ESADE 算法和其他改進(jìn)差分演化算法的性能，本文設(shè)置統(tǒng)一參數(shù)：進(jìn)行基準(zhǔn)函數(shù)測(cè)試的維度大小D=30；種群大小NP=50；每個(gè)函數(shù)的最大進(jìn)化代數(shù)為10 000；每個(gè)函數(shù)獨(dú)立運(yùn)行次數(shù)為25。另外，本文提出的算法所涉及模擬退火中的初始化溫度參數(shù)t0=1 000。

3.2 ESADE算法和其他改進(jìn)差分演化算法性能的比較

ESADE算法性能的評(píng)估是通過和其他改進(jìn)差分演化算法的性能進(jìn)行比較而得出的，這些改進(jìn)差分演化算法是上文所介紹的jDE、JADE、SaDE、EPSDE和CoDE等5種算法。

為了避免一次運(yùn)算導(dǎo)致的結(jié)果偏差較大這一現(xiàn)象，本文設(shè)置的獨(dú)立運(yùn)行次數(shù)為25，即每個(gè)函數(shù)進(jìn)行25次獨(dú)立進(jìn)化，對(duì)進(jìn)化的最優(yōu)值求平均作為算法求得的平均最優(yōu)值。表2給出了17個(gè)基準(zhǔn)函數(shù)在維度取值為30、獨(dú)立運(yùn)行次數(shù)為25 時(shí)的平均值。為了進(jìn)一步分析算法的性能，本文采用威爾科克森秩和檢驗(yàn)分別對(duì)ESADE算法和jDE、JADE、SaDE、EPSDE及CoDE算法進(jìn)行了比較，其中威爾科克森秩和檢驗(yàn)的置信區(qū)間為0.05，其比較結(jié)果如表3所示。

表2 ESADE算法和jDE、JADE、SaDE、EPSDE及CoDE算法在17個(gè)測(cè)試函數(shù)上進(jìn)行25次進(jìn)化的測(cè)試結(jié)果

表3 威爾科克森秩和檢驗(yàn)的比較結(jié)果

表4給出了ESADE 算法和其他改進(jìn)差分演化算法之間的比較結(jié)果。表4清楚地表明，本文提出的ESADE算法整體上比其他5種算法的性能都要好。如ESADE 算法在13 個(gè)測(cè)試函數(shù)上性能比jDE算法好，在3個(gè)測(cè)試函數(shù)上性能和jDE相似；在10個(gè)測(cè)試函數(shù)上性能比JADE 算法好，在4個(gè)測(cè)試函數(shù)上性能和JADE相似；在14個(gè)測(cè)試函數(shù)上性能比SaDE算法好，在3 個(gè)測(cè)試函數(shù)上性能和SaDE相似；在9個(gè)測(cè)試函數(shù)上性能比EPSDE 算法好，在2個(gè)測(cè)試函數(shù)上性能和EPSDE相似；在9個(gè)測(cè)試函數(shù)上性能比CoDE 算法好，在5個(gè)測(cè)試函數(shù)上性能和CoDE相似。

表4 ESADE算法和CoDE、JADE、j DE、EPSDE算法及SaDE在威爾科克森秩和檢驗(yàn)下的比較結(jié)果

為了進(jìn)一步闡明ESADE 算法和其他改進(jìn)差分演化算法性能之間的關(guān)系，本文在圖3中給出6個(gè)測(cè)試函數(shù)在幾種不同算法上的進(jìn)化收斂圖。由圖3可見，ESADE算法的整體收斂速度比其他5 種算法都要快，而且沒有出現(xiàn)陷入局部最優(yōu)的情況。圖3中所選取的6個(gè)測(cè)試函數(shù)都是有代表性的函數(shù)。從ESADE 算法和其他改進(jìn)差分演化算法的比較表明，ESADE算法的性能在整體上優(yōu)于其他5 種算法，與其他5種算法相比，ESADE 算法的優(yōu)勢(shì)很明顯。這是因?yàn)楸疚奶岢龅腅SADE 算法能夠自適應(yīng)地調(diào)整控制參數(shù)以便滿足不同問題需求，而且在選擇操作中加入了模擬退火的思想，能夠提高全局搜索能力。

圖3 ESADE、jDE、JADE、SaDE、EPSDE和CoDE算法在6個(gè)函數(shù)上的進(jìn)化收斂圖

3.3 模擬退火中初始溫度參數(shù)對(duì)ESADE 算法性能的影響

模擬退火中初始溫度參數(shù)的設(shè)置可能會(huì)影響ESADE算法的性能，為了使ESADE算法的性能達(dá)到最優(yōu)，本文對(duì)模擬退火中初始溫度參數(shù)t0的取值進(jìn)行了測(cè)試。在t0=10，100，1 000，10 000時(shí)，分別測(cè)試了ESADE算法的結(jié)果并給出了ESADE 算法在6個(gè)函數(shù)上的收斂圖，如圖4所示。圖中表明，當(dāng)t0=10 000 時(shí)，ESADE 的性能較差；但是當(dāng)t0=10，100，1 000時(shí)，并無(wú)明顯區(qū)別。為了進(jìn)一步說(shuō)明t0取值對(duì)ESADE 算法性能的影響，本文使用威爾科克森秩和檢驗(yàn)分別對(duì)取不同t0值的ESADE算法和jDE、JADE、SaDE、EPSDE 及CoDE 算法進(jìn)行了比較，其中威爾科克森秩和檢驗(yàn)的置信區(qū)間為0.05，其比較結(jié)果如表5 所示。表中說(shuō)明，當(dāng)t0=1 000時(shí)，ESADE算法的性能最好。故將初始溫度參數(shù)設(shè)置為t0=1 000。

表5 t0取不同值時(shí)，ESADE 算法和CoDE、JADE、jDE、EPSDE 及SaDE算法的比較結(jié)果

圖4 t0取不同值時(shí)，ESADE算法在6個(gè)函數(shù)上的收斂圖

3.4 ESADE算法在解決TSP問題上的應(yīng)用

為了測(cè)試ESADE算法在解決現(xiàn)實(shí)問題上的性能，本文將ESADE 算法用于解決TSP 問題，并將結(jié)果與CoDE、JADE、jDE、EPSDE 及SaDE 算法進(jìn)行比較。

3.4.1 TSP問題描述 TSP（Traveling Saleman Problem）即旅行商問題，簡(jiǎn)稱為TSP 問題，是最基本的路線問題，該問題是在尋求單一旅行者由起點(diǎn)出發(fā)，通過所有給定的需求點(diǎn)之后，最后再回到原點(diǎn)的最小路徑成本[16]。在算法中，通過目標(biāo)函數(shù)來(lái)評(píng)價(jià)新解的優(yōu)劣，從而保證產(chǎn)生新解的質(zhì)量，有利于算法的快速收斂。本文使用的目標(biāo)向量為

式中：n為城市個(gè)數(shù)；dij為城市i、j之間的距離；xij為決策變量，其表達(dá)式為

3.4.2 實(shí)驗(yàn)設(shè)置 所有算法的最大進(jìn)化代數(shù)統(tǒng)一設(shè)置為10 000，種群大小為100，獨(dú)立運(yùn)行次數(shù)為25次，城市個(gè)數(shù)分別為10和14（城市的具體坐標(biāo)見附錄B）。

3.4.3 實(shí)驗(yàn)結(jié)果與分析 表6給出了當(dāng)ESADE、CoDE、JADE、jDE、EPSDE 及SaDE 算法用于TSP問題的結(jié)果以及時(shí)間消耗。結(jié)果表明，當(dāng)城市個(gè)數(shù)為10 和14 時(shí)，ESADE 算 法 能 夠 得 到 與jDE、JADE、SADE 及CoDE 算法相同的平均值和中值，并且這一均值是目前已有研究中的最小值；同時(shí)，因?yàn)镋SADE 算法中采取的雙種群策略以及加入模擬退火機(jī)制的選擇策略，相對(duì)于jDE 和JADE 算法，ESADE時(shí)間耗費(fèi)會(huì)翻倍，但比SaDE、EPSDE 和CoDE 算法的時(shí)間耗費(fèi)，ESADE 算法更高效。表7給出了在0.05置信區(qū)間內(nèi)，本文采用威爾科克森秩和檢驗(yàn)分別對(duì)ESADE 算法和jDE、JADE、SaDE、EPSDE及CoDE算法應(yīng)用于TSP問題上的結(jié)果進(jìn)行了比較，比較結(jié)果表明，ESADE算法在TSP問題上的表現(xiàn)優(yōu)于EPSDE 算法，類似于jDE、JADE、SADE及CoDE算法。以上結(jié)果表明，ESADE算法能夠有效解決TSP問題。

表6 ESADE、CoDE、JADE、jDE、EPSDE及SaDE算法應(yīng)用于TSP問題的結(jié)果

表7 ESADE算法和CoDE、JADE、j DE、EPSDE及SaDE算法在TSP問題上的比較結(jié)果

4 結(jié)語(yǔ)

差分演化算法作為一種高效的優(yōu)化算法，被廣泛應(yīng)用于科學(xué)與工程領(lǐng)域。在差分演化算法中，進(jìn)化策略和控制參數(shù)會(huì)對(duì)算法的性能有重要影響。但是因?yàn)椴煌瑔栴}甚至是相同問題的不同進(jìn)化階段需要的最優(yōu)設(shè)置都是不同的，使得選擇合適的進(jìn)化策略和相關(guān)參數(shù)成為一個(gè)較困難的問題。為了解決該問題，本文提出了一種ESADE算法。ESADE算法生成一組控制參數(shù)oF和oCr，再通過對(duì)這組控制參數(shù)進(jìn)行變異操作生成一組新的控制參數(shù)mF和mCr，然后根據(jù)這兩組控制參數(shù)分別對(duì)2個(gè)相同的種群進(jìn)行變異和交叉操作，生成兩組試驗(yàn)向量，最后進(jìn)行選擇操作。為了增強(qiáng)算法的全局搜索能力，ESADE算法中的選擇操作加入了模擬退火的思想。為了對(duì)ESADE 算法的性能進(jìn)行測(cè)試，本文從CEC2005中選擇了17個(gè)函數(shù)作為測(cè)試函數(shù)，并將ESADE算法的測(cè)試結(jié)果與其他改進(jìn)差分演化算法的測(cè)試結(jié)果進(jìn)行了比較。比較結(jié)果顯示，ESADE算法有很強(qiáng)的全局搜索能力，并且性能在整體上優(yōu)于其他算法。同時(shí)，本文還測(cè)試了模擬退火中初始溫度參數(shù)對(duì)ESADE 算法性能的影響，結(jié)果表明，當(dāng)初始溫度參數(shù)為1 000時(shí)，ESADE算法的性能較好。最后，將ESADE算法應(yīng)用于TSP問題，結(jié)果表明，ESADE 算法能夠取得與jDE、JADE、SADE及CoDE算法相同的最小值，并且這一最小值是目前已知最小值，這說(shuō)明，ESADE算法能夠有效解決TSP問題。

本研究未來(lái)的工作主要集中于兩點(diǎn)：①將小生境算法的思想加入到變異操作中，改變個(gè)體的選擇方式，使得個(gè)體的選取更加具有代表性；② 將ESADE算法應(yīng)用于解決更多的實(shí)際問題，例如，將ESADE算法用于解決多目標(biāo)優(yōu)化問題；將ESADE算法用于解決油層識(shí)別問題，包括特征選擇和規(guī)則提取等。

附錄A

基準(zhǔn)函數(shù)的詳細(xì)表達(dá)形式。

f1：Shifted sphere function，其公式為，z=x-o，其中，-100≤x（i）≤100，o=（o（1），o（2），…，o（n））為轉(zhuǎn)移全局最優(yōu)取值，即全局最優(yōu)值在x*=o時(shí)取得，全局最優(yōu)值f（x*）=0。

f2：Shifted schwefel's problem 1.2，其公式為，z=x-o，其中，-100≤x（i）≤100，o=（o（1），o（2），…，o（n））為轉(zhuǎn)移全局最優(yōu)取值，即全局最優(yōu)值在x*=o時(shí)取得，全局最優(yōu)值f（x*）=0。

f3：Shifted rotated high conditioned elliptic function，其公式為，z=（x-o）M，其中，-100≤x（i）≤100，o=（o（1），o（2），…，o（n））為轉(zhuǎn)移全局最優(yōu)取值，即全局最優(yōu)值在x*=o時(shí)取得，全局最優(yōu)值f（x*）=0，M為正交變換矩陣。

f4：Shifted schwefel's problem 1.2 with noise in fitness，其公式為

其中，-100≤x（i）≤100，o=（o（1），o（2），…，o（n））為轉(zhuǎn)移全局最優(yōu)取值，即全局最優(yōu)值在x*=o時(shí)取得，全局最優(yōu)值f（x*）=0。

f5：Schwefel's problem 2.6 with global optimum on bounds，其公式為，其中，-100≤x（i）≤100，A為D×D的矩陣，aij是取值范圍在[-500，500]的隨機(jī)整數(shù)，det（A）≠0，Ai是矩陣A的第i行，Bi=Ai˙o，o是D×1的向量，oi是取值范圍在[-100，100]的隨機(jī)整數(shù)，o=（o（1），o（2），…，o（n））為轉(zhuǎn)移全局最優(yōu)取值，即全局最優(yōu)值在x*=o時(shí)取得，全局最優(yōu)值f（x*）=0。

f6：Shifted rosenbrock's function，其公式為

其中，-100≤x（i）≤100，o=（o（1），o（2），…，o（n））為轉(zhuǎn)移全局最優(yōu)取值，即全局最優(yōu)值在x*=o時(shí)取得，全局最優(yōu)值f（x*）=0。

f7：Shifted rotated griewank's function without bounds，其公式為

其中，0≤x（i）≤600，o=（o（1），o（2），…，o（n））為轉(zhuǎn)移全局最優(yōu)取值，即全局最優(yōu)值在x*=o時(shí)取得，全局最優(yōu)值f（x*）=0，M為正交變換矩陣。

f8：Shifted rotated ackley's function with global optimum on bounds，其公式為

其中，-32≤x（i）≤32，o=（o（1），o（2），…，o（n））為轉(zhuǎn)移全局最優(yōu)取值，即全局最優(yōu)值在x*=o時(shí)取得，全局最優(yōu)值f（x*）=0，M為正交變換矩陣。

f9：Shifted rastrigin's function，其公式為，z=x-o，其中，-5 ≤x（i）≤5，o=（o（1），o（2），…，o（n））為轉(zhuǎn)移全局最優(yōu)取值，即全局最優(yōu)值在x*=o時(shí)取得，全局最優(yōu)值f（x*）=0。f10：Shifted expanded griewank's plus rosenbrock's function，其公式為

其中，-3 ≤x（i）≤1，o=（o（1），o（2），…，o（n））為轉(zhuǎn)移全局最優(yōu)取 值，即全局最優(yōu)值在x*=o時(shí)取 得，全 局最優(yōu)值f（x*）=0。

f11～f17：函數(shù)f11～f17分別由10個(gè)基本函數(shù)組合而成，詳細(xì)描述請(qǐng)參考文獻(xiàn)[15]。

附錄B

城市坐標(biāo)

表1 10點(diǎn)TSP問題

表2 14點(diǎn)TSP問題