【關(guān)于差分進(jìn)化算法的探究6500字（論文）】

關(guān)于差分進(jìn)化算法的研究摘要差分進(jìn)化算法(DE)是一種基于群體差異的啟發(fā)式全局優(yōu)化算法，該算法具有良好的全局收斂特性和魯棒性?，F(xiàn)已被廣泛應(yīng)用于眾多科研和商業(yè)領(lǐng)域,如數(shù)字濾波設(shè)計、化工、多處理器合成、機器人、生物信息、神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)、食品安全等。DE作為一種高效的并行搜索算法，對其進(jìn)行理論和應(yīng)用研究具有重要的學(xué)術(shù)意義和工程價值。本文主要是關(guān)于差分進(jìn)化算法的研究。關(guān)鍵詞：差分進(jìn)化算法；研究；理論和應(yīng)用目錄引言 2一差分進(jìn)化算法原理和研究現(xiàn)狀 21.1差分進(jìn)化算法原理 31.2差分進(jìn)化算法研究現(xiàn)狀和應(yīng)用 3第二章差分進(jìn)化算法特點 32.1差分進(jìn)化算法核心思想 42.2差分進(jìn)化算法特點 4三標(biāo)準(zhǔn)差分進(jìn)化算法中的優(yōu)化問題的設(shè)待求解 53.1標(biāo)準(zhǔn)差分進(jìn)化算法 53.2差分進(jìn)化算法的執(zhí)行過程 53.3差分進(jìn)化算法的常用變體 7四差分進(jìn)化算法的參數(shù)控制研究 84.1控制參數(shù) 84.2各個參數(shù)對該算法的性能的影響 94.3既有的改進(jìn)差分進(jìn)化算法 10引言針對多元函數(shù)極值求解此類不可微、多極值的優(yōu)化問題，給出了此類問題的一種新的容易實現(xiàn)且計算成功率高的有效算法——差分進(jìn)化算法來搜索最優(yōu)解。在理論上，差分進(jìn)化算法(DifferentialEvolution，DE)是一種新興的進(jìn)化計算技術(shù)。它是RainerStorn和KennethPrice等人于1995年提出的，最初的設(shè)想是用于解決切比雪夫多項式問題,后來發(fā)現(xiàn)DE也是解決復(fù)雜優(yōu)化問題的有效技術(shù)。DE和微粒群算法(ParticleSwarmOptimization,PSO)一樣，都是基于群體智能理論的優(yōu)化算法，通過群體內(nèi)個體間的合作與競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索。但相比于進(jìn)化算法，DE保留了基于種群的全局搜索策略，采用實數(shù)編碼、基于差分的簡單變異操作和一對一的競爭生存策略，降低了遺傳操作的復(fù)雜性。同時，DE特有的記憶能力使其可以動態(tài)跟蹤當(dāng)前的搜索情況，以調(diào)整其搜索策略，且不需要借助問題的特征信息，適于求解一些利用常規(guī)的數(shù)學(xué)規(guī)劃方法所無法求解的復(fù)雜環(huán)境中的優(yōu)化問題。因此，DE作為一種高效的并行搜索算法，對其進(jìn)行理論和應(yīng)用研究具有重要的學(xué)術(shù)意義和工程價值。在現(xiàn)實中，差分進(jìn)化算法(DE)是一種基于群體差異的啟發(fā)式全局優(yōu)化算法，該算法具有良好的全局收斂特性和魯棒性?，F(xiàn)已被廣泛應(yīng)用于眾多科研和商業(yè)領(lǐng)域,如數(shù)字濾波設(shè)計、化工、多處理器合成、機器人、生物信息、神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)、食品安全等。一差分進(jìn)化算法原理和研究現(xiàn)狀1.1差分進(jìn)化算法原理差分進(jìn)化算法原理：差分進(jìn)化算法由NP(種群規(guī)模)個D(決策變量個數(shù))維參數(shù)矢量(i=1，2，…，NP；j=1，2，…，D)在搜索空間進(jìn)行并行直接的搜索。DE的基本操作包括變異(Mutation、交叉(Crossover)和選擇(Selection)三種操作。隨機選擇兩個不同的個體矢量相減生成差分矢量，將差分矢量賦予權(quán)值之后加到第三個隨機選擇的個體矢量上，生成變異矢量，該操作稱為變異。變異矢量與目標(biāo)矢量進(jìn)行參數(shù)混合，生成試驗矢量，這一過程稱之為交叉。如果試驗矢量的適應(yīng)度優(yōu)于目標(biāo)矢量的適應(yīng)度，則用試驗矢量取代目標(biāo)矢量而形成下一代，該操作稱為選擇。在每一代的進(jìn)化過程中，每一個體矢量作為目標(biāo)矢量一次。初始種群是在搜索空間隨機生成的，且要求初始種群覆蓋整個搜索空間。初始群體一般采用均勻分布的隨機函數(shù)來產(chǎn)生。1.2差分進(jìn)化算法研究現(xiàn)狀和應(yīng)用目前，差分進(jìn)經(jīng)算法已引起了人們的廣泛關(guān)注，在國外的各研究領(lǐng)域得到了廣泛的應(yīng)用，已成為進(jìn)化算法(EA)的一個重要分支。J.Vestertron等人將DE與微粒群優(yōu)化算法(ParticleSwarmOptimization,PSO)和其它進(jìn)化算法用34個廣泛應(yīng)用的BenchmarkProblems進(jìn)行了深入的比較研究，實驗結(jié)果表明，DE的性能優(yōu)于PSO和其它進(jìn)化算法。但目前，DE在國內(nèi)的研究和應(yīng)用較少。近年來，DE在約束優(yōu)化計算，模糊控制器優(yōu)化設(shè)計，神經(jīng)網(wǎng)絡(luò)優(yōu)化，濾波器設(shè)計等方面得到了廣泛的應(yīng)用。此外，DE還在線性系統(tǒng)的優(yōu)化、多傳感器信息融合、系統(tǒng)建模，集成電路設(shè)計等問題中得到了應(yīng)用。DE是根據(jù)父代個體間的差分矢量進(jìn)行變異、交叉和選擇操作，與其它進(jìn)化算法(如遺傳算法)一樣容易限入局部最優(yōu)，存在早熟收斂現(xiàn)象。目前的解決方法主要是增加種群的規(guī)模，但這樣會增加算法的運算量，也不能從根本上克服早熟收斂的問題。因而進(jìn)一步對差分進(jìn)化算法進(jìn)行分析和改進(jìn)，提高全局搜索能力，加快收斂速度，提高算法的魯棒性，使之適合于各種實際工程優(yōu)化問題，仍是值得進(jìn)一步研究的內(nèi)容。第二章差分進(jìn)化算法特點2.1差分進(jìn)化算法核心思想自然界的生物體在遺傳、選擇和變異等一系列作用下，優(yōu)勝劣汰，不斷地由低級到高級進(jìn)化和發(fā)展，人們將這種適者生存的進(jìn)化規(guī)律的實質(zhì)加以形式化而構(gòu)成一種優(yōu)化算法,即進(jìn)化算法。進(jìn)化算法是一系列的搜索技術(shù)，包括遺傳算法、進(jìn)化編程、進(jìn)化策略、遺傳編程等，它們在函數(shù)優(yōu)化、模式識別、機器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、智能控制等眾多領(lǐng)域都有著廣泛的應(yīng)用。盡管進(jìn)化算法有很多變化，但它們的核心思想都是起源于達(dá)爾文的自然選擇學(xué)說，包括過度繁殖、生存競爭、遺傳和變異與適者生存。為了求解切比雪夫多項式問題，RainerStorn和KennethPrice根據(jù)這種進(jìn)化思想于1995年提出了差分進(jìn)化算法。它是一種采用實數(shù)編碼、在連續(xù)空間中進(jìn)行隨機搜索、基于群體迭代的新興進(jìn)化算法，具有結(jié)構(gòu)簡單性能高效的特點。隨著對算法的深入研究，發(fā)現(xiàn)DE算法也是解決復(fù)雜優(yōu)化問題的有效技術(shù)。DE是基于群體智能理論、通過群體內(nèi)個體間的合作與競爭產(chǎn)生的群體智能來指導(dǎo)優(yōu)化搜索的優(yōu)化算法。DE不僅具有記憶個體最優(yōu)解和種群內(nèi)信息共享以及較強的全局搜索收斂能力和魯棒性等特點，而且不需要借助問題的特征信息，不受問題性質(zhì)的限制，有效地求解復(fù)雜環(huán)境中的優(yōu)化問題。與確定性算法相比，DE算法具有普遍的適應(yīng)性，DE已成為一種求解非線性、不可微、多極值和高維的復(fù)雜函數(shù)的一種有效和魯棒的方法。從工程角度看差分進(jìn)化算法是一種自適應(yīng)的迭代尋優(yōu)過程，從數(shù)學(xué)角度看它是一種隨機搜索算法。2.2差分進(jìn)化算法特點算法基本思想是基于達(dá)爾文生物進(jìn)化論中適者生存的競爭策略，根據(jù)父代個體間的差分矢量進(jìn)行變異（Mutation）、交叉（Crossover）和選擇（Selection）操作，即從某一隨機產(chǎn)生的初始種群開始，隨機選擇種群中任意兩個不同的個體，然后將它們的差向量加權(quán)后按一定的規(guī)則與第三個個體向量求和來產(chǎn)生新個體，這一過程被稱為“變異”。然后將新個體的參數(shù)與當(dāng)代種群中某個預(yù)先確定的目標(biāo)個體的參數(shù)按照一定的規(guī)則來產(chǎn)生試驗個體向量，該操作稱為“交叉”。如果試驗個體的適應(yīng)度值優(yōu)于與之相比較的個體的適應(yīng)度值，則在下一代中就用試驗個體取代目標(biāo)個體，否則目標(biāo)個體仍保存下來，此過程稱為“選擇”。這樣種群通過不斷地迭代計算，淘汰劣質(zhì)個體，保留優(yōu)良個體，引導(dǎo)搜索過程向最優(yōu)解逼近。在每一代的進(jìn)化過程中，每一個個體向量都必須作為目標(biāo)個體向量一次，以便在下一代中出現(xiàn)相同個競爭者。與傳統(tǒng)的優(yōu)化算法相比，差分進(jìn)化算法具有以下特點：⑴簡單的算法原理，容易實現(xiàn)，不需要確定性的規(guī)則，采用概率轉(zhuǎn)移規(guī)則。⑵具有記憶個體最優(yōu)解的能力和極強的群體搜索能力；⑶差分進(jìn)化算法具有內(nèi)在的并行性，可協(xié)同搜索，具有利用個體局部信息和群體全局信息指導(dǎo)算法進(jìn)一步搜索的能力，在同樣精度要求下，DE算法具有更快的收斂速度；⑷DE算法操作十分簡單，易編程實現(xiàn)，尤其擅長求解高維的函數(shù)優(yōu)化問題；⑸算法通用，可直接對結(jié)構(gòu)對象進(jìn)行操作，不依賴于問題信息，不存在對目標(biāo)函數(shù)的限定。三標(biāo)準(zhǔn)差分進(jìn)化算法中的優(yōu)化問題的設(shè)待求解3.1標(biāo)準(zhǔn)差分進(jìn)化算法差分進(jìn)化算法的操作流程與其他進(jìn)化算法類似，包括群體初始化、個體適應(yīng)度值評價、通過交叉和變異算子對種群進(jìn)行進(jìn)化操作等?；綝E算法涉及到五個控制參數(shù)，分別是種群規(guī)模N，變異算子F及交叉概率因子CR，最大迭代次數(shù)T和終止條件。算法通常包括四個環(huán)節(jié)：初始化、變異、交叉和選擇。標(biāo)準(zhǔn)差分進(jìn)化算法，即簡單差分進(jìn)化算法(SimpleDifferentialEvolutionAlgorithm)采用的選擇、交叉、變異這三種基本差分操作是算法的基礎(chǔ)。其詳細(xì)實現(xiàn)過程如下：3.2差分進(jìn)化算法的執(zhí)行過程DE算法的數(shù)學(xué)描述如下。設(shè)待求解的優(yōu)化問題為，則DE算法為:步驟1：編碼及初始化：DE算法采用實數(shù)編碼，假設(shè)種群規(guī)模為N,所求問題的自變量有D維，指定一個最大迭代次數(shù)T，變異因子F∈[0,2],交叉概率因子CR∈[0,1],當(dāng)前進(jìn)化代數(shù)為t;則第t代種群中第i個個體Xi,t表示如下變量的指定搜索空間范圍為：，上式中每個參數(shù),jitx在指定的值域minmax[X,X]內(nèi)隨機地產(chǎn)生，其值域表示如下：初始化種群往往在該值域內(nèi)隨機地產(chǎn)生。令進(jìn)化代數(shù)t=0，在minmax[X,X]范圍內(nèi)隨機產(chǎn)生N個個體，構(gòu)成初始種群步驟2：個體評價:計算每個個體Xi,t的適應(yīng)度函數(shù)值,fXit；步驟3：變異操作：對種群中每個個體Xi,t，隨機生成三個互不相同的整數(shù)123r,r,r∈{1,2,,N}，且要求123r,r,r,i四個數(shù)互不相同，然后按式生成變異個體Vi,t若Vi,t不在minmax[X,X]范圍內(nèi)，則令,minmaxmin(0,1)()itV=X+rand?X?X，其中rand(0,1)為(0,1)內(nèi)均勻分布的隨機數(shù)。差分變異操作是差分進(jìn)化算法中最重要的操作，這也是算子名稱的由來。步驟4交叉操作：交叉操作按每個個體向量的分量進(jìn)行。將變異產(chǎn)生的變異個體與目標(biāo)個體按照下面的公式進(jìn)行交叉操作，具體執(zhí)行過程如下：首先生成一個隨機整數(shù)irandn，然后對變異個體i,tV和種群的目標(biāo)個體Xi,t按（2.4）式得到試驗個體12,,,,(,,,),1,2,,DititititU=uuui=N,為了保證個體的進(jìn)化，首先通過隨機選擇使i,tU至少有一位由i,tV貢獻(xiàn)，其它位由交叉概率CR來決定具體哪位由Xi,t貢獻(xiàn)哪位由i,tV貢獻(xiàn)：式中rand，是位于[[0,1]間的均勻分布的隨機實數(shù)，而randn，是屬于{1,2,}}-,D}內(nèi)隨機產(chǎn)生的維數(shù)索引號，其保證了川，至少有一位由變異向量側(cè)，貢獻(xiàn)。此處CR為交叉概率因子，也是位于[[0,1]間的一個常數(shù)。差分進(jìn)化算法引入交叉操作是為了增加種群的多樣性。步驟5選擇操作:選擇操作采用的是“貪婪選擇”策略，經(jīng)變異以及交叉操作后生成的候選個體Ua.t與目標(biāo)個體戈.t進(jìn)行競爭:上式中f是適應(yīng)度函數(shù)替換原來的第t代個體，在隊.t和戈.t中選擇適應(yīng)度函數(shù)值最優(yōu)者作為第t+1代個體并使迭代計數(shù)器t增加1。需要指出的是式(2.5適合最小化問題的處理。步驟6終止檢驗：如果種群Xi,t滿足終止條件或達(dá)到最大迭代次數(shù)T，則輸出最優(yōu)解；否則轉(zhuǎn)步2.下面給出標(biāo)準(zhǔn)差分進(jìn)化算法流程圖，見圖2-1：圖：標(biāo)準(zhǔn)差分進(jìn)化算法流程3.3差分進(jìn)化算法的常用變體差分進(jìn)化算法采用不同的變異、交叉和選擇策略，能夠得到差分進(jìn)化算法的不同變體。前面介紹的差分算法原理是差分進(jìn)化算法的一種基本形式，RainerStorn和KennethPrice提出了多種差分進(jìn)化算法的變化形式，為了表示方便，統(tǒng)一采用DE/x/y/z的形式來描述。x表示變異操作中被變異的個體矢量的選擇方式，x可以為“rand”（表示從種群中隨機選擇的一個個體）或“best”（表示當(dāng)前種群中適應(yīng)值最優(yōu)的個體）。y表示所用差分矢量的數(shù)目。z表示交叉操作的方式，通常采用伯努力（Binomail）實驗方式來進(jìn)行交叉操作，用“bin”表示。按照上述規(guī)定，則前述差分進(jìn)化算法可表示為DE/rand/1/bin。為了使差分進(jìn)化算法的收斂速度得到提高，學(xué)者們針對差分進(jìn)化算法的核心部分——變異向量的構(gòu)造形式提出了多種的擴展模式，以適應(yīng)更廣泛的優(yōu)化問題。根據(jù)差分向量構(gòu)造方式的不同，RainerStorn和KennethPrice提出的DE變化方式如下:常用的變異操作算子:①DE/best/1/bin,其中:②DE/rand/2/bin,,其中:③DE/best/2/bin,其中:④DE/rand-to-best/1/bin,其中:其中1234i,r,r,r,r互不相同，即1234r,r,r,r∈{1,2,,N}是伴隨目標(biāo)個體Xi,t產(chǎn)生的互不相等的隨機整數(shù)，其各自代表種群中不同個體的索引號，且不等于目標(biāo)個體的索引號i。best,tX為第t代種群中的最優(yōu)個體，而變異率F∈[0,2]是用來控制差分向量的縮放步長。各種變化方式有各自的特點，但RainerStorn和KennethPrice經(jīng)過大量實驗研究表明，DE/rand/1/bin（式2.3）和DE/best/2/bin（式2.8）的性能較其他方式要好，在實際工程設(shè)計過程中也應(yīng)用最多。還有在交叉操作中利用指數(shù)交叉的情況，如DE/rand/1/exp，DE/best/1/exp，DE/rand-to-best/1/exp，DE/best/2/exp等。這幾種形式的變異過程與上述相應(yīng)方式相同，只是交叉操作不同。四差分進(jìn)化算法的參數(shù)控制研究4.1控制參數(shù)從上文對標(biāo)準(zhǔn)差分進(jìn)化算法的介紹可知，該算法參數(shù)較少，共有五個控制參數(shù)：種群大小N，變異因子F，交叉概率因子CR，最大迭代次數(shù)T及終止條件。這也是差分進(jìn)化算法深受人們喜愛的原因。DE算法的性能發(fā)揮極大地依賴于DE算法中操作算子的選取和相關(guān)參數(shù)的設(shè)置，為此針對具體問題需要通過反復(fù)試驗來確定。Storn等在文獻(xiàn)中指出種群N的大小合適范圍位于5D和10D（D代表問題的維數(shù)）之間，F(xiàn)值的初始值設(shè)置為0.5為宜，而F的取值位于[0.4,1]之間時優(yōu)化效果較為顯著。Qin等[28]提出了一種自適應(yīng)的差分進(jìn)化算法SADE，其在一定程度上改善了變異操作策略的選取及相關(guān)參數(shù)的設(shè)置問題。該算法的思想是：通過建立由DE算法高效的變異操作算子來構(gòu)成變異操作算子池，并且利用對進(jìn)化過程中經(jīng)驗知識的概率學(xué)習(xí)，進(jìn)而自適應(yīng)地確定針對具體個體所采用的變異操作算子。通常這些控制參數(shù)會影響算法搜尋最優(yōu)解的收斂速度，為保證算法的性能和收斂速度，針對具體問題往往需要進(jìn)行特定設(shè)置。4.2各個參數(shù)對該算法的性能的影響各個參數(shù)對該算法的性能的影響分別為：（1）種群大小N對算法性能的影響：群體規(guī)模N一般介于5?D與10?D之間，但不能少于4，否則不能進(jìn)行變異操作。N越大，種群多樣性越強，大規(guī)模的種群必然會增加種群中個體的多樣性，相對地也擴大了尋優(yōu)空間的范圍，提高獲得最優(yōu)解概率；但大規(guī)模的種群必然會加大適應(yīng)度函數(shù)的評價次數(shù)，從而提高算法運行的時間復(fù)雜度；而種群規(guī)模過小則使算法收斂速度加快，導(dǎo)致尋優(yōu)空間過小，易導(dǎo)致局部最優(yōu)或因算法早熟而使進(jìn)化停止。（2）變異因子F對算法的影響：變異因子F是控制種群多樣性和收斂性的重要參數(shù)，它決定偏差向量的放大比例，一般在[0,2]之間取值。F取值較小導(dǎo)致群體差異度減小，會加速算法收斂，同樣也會導(dǎo)致算法局部收斂，而較大的F值則會加大算法跳出局部最優(yōu)解的可能性，但是會導(dǎo)致收斂速度過慢。因此F值的最佳設(shè)置與具體問題有關(guān)，F(xiàn)有規(guī)律的動態(tài)可大可小的改變更有利于問題求解。（3）交叉概率CR對算法的影響：交叉因子CR可控制個體參數(shù)的各維對交叉的參與程度，以及全局與局部搜索能力的平衡，一般在[0,1]之間取值。不同的CR值設(shè)置對所求問題必然會產(chǎn)生較大的差異，對不同的問題應(yīng)采用不同的CR設(shè)置。交叉因子CR越小，種群多樣性減小，容易過早收斂，CR越大，收斂速度越大，但過大可能會因擾動大于群體的差異度導(dǎo)致收斂變慢。根據(jù)文獻(xiàn)一般應(yīng)選在0.6到0.9之間。通常而言，比如多模態(tài)問題，可對CR設(shè)置較小的值即可取得較優(yōu)的尋優(yōu)結(jié)果；而對于單一極值點的優(yōu)化問題，設(shè)置較大的CR所得的優(yōu)化效果較為突出。（4）最大迭代次數(shù)T對算法的影響：最大迭代次數(shù)一般作為算法運行結(jié)束條件的一個參數(shù)，表示DE算法運行到指定的進(jìn)化代數(shù)后就停止運行。迭代次數(shù)越大，最優(yōu)解越精確，但是計算時間會更長，需要根據(jù)具體問題而定。一般取值范圍為100～200。終止條件對算法的影響：除最大進(jìn)化代數(shù)可作為DE的終止條件，還需要其它判定準(zhǔn)則。一般當(dāng)目標(biāo)函數(shù)值小于閾值時程序終止，閾值常選為610?。這幾個參數(shù)對差分進(jìn)化算法的求解結(jié)果和求解效率都有一定的影響，因此要根據(jù)具體問題合理地設(shè)定這些參數(shù)才能獲得較好的尋優(yōu)效果。通?？赏ㄟ^在對不同值做一些試驗之后利用試驗結(jié)果誤差找到各參數(shù)的合適值。4.3既有的改進(jìn)差分進(jìn)化算法Das等提出DE算法的兩種改進(jìn)策略：第一，首先設(shè)定變異算子F的最大值與最小值，該策略使得改進(jìn)的DE算法在開始時具有較大的F值，此時具有較強的全局搜索能力，其次讓變異算子F隨著迭代次數(shù)的增大而線性遞減，使得進(jìn)化的后半部分擁有足夠的局部搜索能力；第二，利用在取值范圍(0.5,1)隨機生成的變異因子F的值，來改進(jìn)差分進(jìn)化算法。Das等人還通過在取值范圍(0.5,1.5)內(nèi)生成滿足正態(tài)分布的隨機數(shù)作為變異率F的值來提高差分進(jìn)化算法的性能。參考文獻(xiàn)[1]MichalewiczZ,JanikowCZ,KrawcazykJB.Amodifiedgeneticalgorithmforoptimalcontrolproblems[J].ComputerMathAppli,1992,23(12):83-94.[2]STORNR,PRICEK.Differentialevolution:asimpleandefficientadaptiveschemeforglobaloptimizationovercontinuousspaces[EB/OL].2010,10,25.http://www.IcsiB./storn/TR-95-012.pdf.[3]STORNR.Systemdesignbyconstraintadaptationanddifferentialevolution[J].IEEE.TransactionsonEvolutionaryComputation,1999,3(1):22-24.[4]THOMSENR.Flexibleliganddockingusingdifferentialevolution[C]//Proceedingsofthe2003IEEECongressonEvolution.Computation.Canberra,Australia,2003:2354-2361.[5]陳安，陳寧，周龍驤等.數(shù)據(jù)挖掘技術(shù)及應(yīng)用.北京：科學(xué)出版社,2006:1-1