一　遺傳算法

?遺傳算法(GA)作為一種經(jīng)典的進(jìn)化算法，自 Holland提出之后在國際上已經(jīng)形成了一個(gè)比較活躍的研究領(lǐng)域. 人們對(duì) GA 進(jìn)行了大量的研究，提出了各種改進(jìn)算法用于提高算法的收斂速度和精確性. 遺傳算法采用選擇，交叉，變異操作，在問題空間搜索最優(yōu)解.經(jīng)典遺傳算法首先對(duì)參數(shù)進(jìn)行編碼，生成一定數(shù)目的個(gè)體，形成初始種群其中每個(gè)個(gè)體可以是一維或多維矢量，以二進(jìn)制數(shù)串表示，稱為染色體.染色體的每一位二進(jìn)制數(shù)稱為基因.根據(jù)自然界生物優(yōu)勝劣汰的選擇思想，算法中設(shè)計(jì)適應(yīng)度函數(shù)作為評(píng)判每個(gè)個(gè)體性能優(yōu)劣的標(biāo)準(zhǔn)，性能好的個(gè)體以一定概率被選擇出來作為父代個(gè)體參加以后的遺傳操作以生成新一代種群.算法中基本的遺傳算子為染色體選擇，染色體上基因雜交和基因變異.生成新一代種群后算法循環(huán)進(jìn)行適應(yīng)度評(píng)價(jià)、遺傳操作等步驟，逐代優(yōu)化，直至滿足結(jié)束條件.

標(biāo)準(zhǔn)遺傳算法的流程如下：

? ? ? ? Stepl：初始化群體．

? ? ? ? Step2：計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值．

? ? ? ? Step3：按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將進(jìn)入下一代的個(gè)體．

? ? ? ? Step4：按概率cp 進(jìn)行雜交操作．

? ? ? ? Step5：按概率mp 進(jìn)行變異操作．

? ? ? ? Step6：若滿足某種停止條件，則執(zhí)行 Step7，否則執(zhí)行 Step2．

? ? ? ? Step7：輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解.

? ? ? ?

? ? ? 一般情況下，算法的終止條件包括：1、完成了預(yù)先給定的進(jìn)化代數(shù)；2、種群中的最優(yōu)個(gè)體在連續(xù)若干代沒有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒有改進(jìn)；3、所求問題最優(yōu)值小于給定的閾值.

?

? ? ? ? 粒子群(PSO)算法是近幾年來最為流行的進(jìn)化算法，最早是由Kenned和Eberhart于1995年提出.PSO 算法和其他進(jìn)化算法類似，也采用“群體”和“進(jìn)化”的概念，通過個(gè)體間的協(xié)作與競(jìng)爭(zhēng)，實(shí)現(xiàn)復(fù)雜空間中最優(yōu)解的搜索．PSO 先生成初始種群，即在可行解空間中隨機(jī)初始化一群粒子，每個(gè)粒子都為優(yōu)化問題的一個(gè)可行解，并由目標(biāo)函數(shù)為之確定一個(gè)適應(yīng)值(fitness value)．PSO 不像其他進(jìn)化算法那樣對(duì)于個(gè)體使用進(jìn)化算子，而是將每個(gè)個(gè)體看作是在n 維搜索空間中的一個(gè)沒有體積和重量的粒子，每個(gè)粒子將在解空間中運(yùn)動(dòng)，并由一個(gè)速度決定其方向和距離.通常粒子將追隨當(dāng)前的最優(yōu)粒子而運(yùn)動(dòng)，并經(jīng)逐代搜索最后得到最優(yōu)解．在每一代中，粒子將跟蹤兩個(gè)極值，一為粒子本身迄今找到的最優(yōu)解 pbest ，另一為全種群迄今找到的最優(yōu)解 gbest．由于認(rèn)識(shí)到 PSO 在函數(shù)優(yōu)化等領(lǐng)域所蘊(yùn)含的廣闊的應(yīng)用前景，在 Kenned 和 Eberhart 之后很多學(xué)者都進(jìn)行了這方面的研究.目前已提出了多種 PSO改進(jìn)算法，并廣泛應(yīng)用到許多領(lǐng)域.

?

二、差分進(jìn)化算法

? ? ? ? 差分進(jìn)化算法在 1997 年日本召開的第一屆國際進(jìn)化優(yōu)化計(jì)算競(jìng)賽(ICEO)]表現(xiàn)突出，已成為進(jìn)化算法(EA)的一個(gè)重要分支，很多學(xué)者開始研究 DE 算法，并取得了大量成果．2006年 CEC 國際會(huì)議將其作為專題討論，由此可見 DE 算法已成為學(xué)者的研究熱點(diǎn)，具有很大的發(fā)展空間.

?

DE算法的基本原理：

? ? ? ? DE 算法主要用于求解連續(xù)變量的全局優(yōu)化問題，其主要工作步驟與其他進(jìn)化算法基本一致，主要包括變異(Mutation)、交叉(Crossover)、選擇(Selection)三種操作。算法的基本思想是從某一隨機(jī)產(chǎn)生的初始群體開始，利用從種群中隨機(jī)選取的兩個(gè)個(gè)體的差向量作為第三個(gè)個(gè)體的隨機(jī)變化源，將差向量加權(quán)后按照一定的規(guī)則與第三個(gè)個(gè)體求和而產(chǎn)生變異個(gè)體，該操作稱為變異。然后，變異個(gè)體與某個(gè)預(yù)先決定的目標(biāo)個(gè)體進(jìn)行參數(shù)混合，生成試驗(yàn)個(gè)體，這一過程稱之為交叉。如果試驗(yàn)個(gè)體的適應(yīng)度值優(yōu)于目標(biāo)個(gè)體的適應(yīng)度值，則在下一代中試驗(yàn)個(gè)體取代目標(biāo)個(gè)體，否則目標(biāo)個(gè)體仍保存下來，該操作稱為選擇。在每一代的進(jìn)化過程中，每一個(gè)體矢量作為目標(biāo)個(gè)體一次，算法通過不斷地迭代計(jì)算，保留優(yōu)良個(gè)體，淘汰劣質(zhì)個(gè)體，引導(dǎo)搜索過程向全局最優(yōu)解逼近。

DE算法的求解步驟：

(1)基本參數(shù)的設(shè)置，包括NP， F， CR
(2)初始化種群
(3)計(jì)算種群適應(yīng)度值
(4)終止條件不滿足時(shí)，進(jìn)行循環(huán)，依次執(zhí)行變異、交叉、選擇運(yùn)算，直到終止運(yùn)算。

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖2.1給出了算法的具體流程：

?

?

控制參數(shù)對(duì)一個(gè)全局優(yōu)化算法的影響是很大的，DE的控制變量選擇也有一些經(jīng)驗(yàn)規(guī)則.

（1）種群數(shù)量.根據(jù)經(jīng)驗(yàn)，種群數(shù)量 NP 的合理選擇在5 D ? 10D之間，必須滿足 NP ≥4以確保DE具有足夠的不同的變異向量.

（2）變異算子.變異算子 F ∈ [0,2]是一個(gè)實(shí)常數(shù)因數(shù)，它決定偏差向量的放大比例.迄今為止的研究表明，小于0.4和大于1的 F 值僅偶爾有效， F = 0.5通常是一個(gè)較好的初始選擇.若種群過早收斂，那么 F 或 NP 應(yīng)該增加.

（3）交叉算子.交叉算子CR 是一個(gè)范圍在[0,1]的實(shí)數(shù)，它是控制一個(gè)試驗(yàn)向量來自隨機(jī)選擇的變異向量而不是原來向量的概率的參數(shù).CR 的一個(gè)較好的選擇是0.1，但較大的CR 通常加速收斂，為了看是否可能獲得一個(gè)快速解，可以首先嘗試 CR = 0.9或 CR = 1.0.

（4）最大進(jìn)化代數(shù).它表示DE算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止運(yùn)行，并將當(dāng)前群體中的最佳個(gè)體作為所求問題的最優(yōu)解輸出.一般取值范圍為100－200，當(dāng)然根據(jù)問題的需要，可以增大最大進(jìn)化代數(shù)以提高算法的求解精度，不過這樣往往使得算法的運(yùn)行時(shí)間過長.

（5）終止條件.除最大進(jìn)化代數(shù)可作為DE的終止條件，還需要其它判定準(zhǔn)則.一般當(dāng)適應(yīng)度值小于閥值時(shí)程序終止，閥值常選為610 .

上述參數(shù)中，F ，CR 與 NP 一樣，在搜索過程中是常數(shù)，一般 F 和CR 影響搜索過程的收斂速度和魯棒性，它們的優(yōu)化值不僅依賴于目標(biāo)函數(shù)的特性，還與 NP 有關(guān).通?？赏ㄟ^在對(duì)不同值做一些試驗(yàn)之后利用試驗(yàn)和結(jié)果誤差找到 F ，CR 和 NP 合適值。

?

參數(shù)設(shè)置：

? ? ? ? 種群規(guī)模NP：多樣性，ＮＰ大，增加搜索到最優(yōu)解的概率，但是計(jì)算量加大。

? ? ? ? 縮放因子F：對(duì)基向量擾動(dòng)程度，F大，擾動(dòng)大，能夠在更大范圍尋找解。0.4~1

? ? ? ? 交叉概率CR：種群多樣性，CR大，更多個(gè)體改變，利于尋找最優(yōu)解。0.6~1

區(qū)別：

? ? ? ? 不同之處在于遺傳算法是根據(jù)適應(yīng)度值來控制父代雜交，變異后產(chǎn)生的子代被選擇的概率值，在最大化問題中適應(yīng)值大的個(gè)體被選擇的概率相應(yīng)也會(huì)大一些。而差分進(jìn)化算法變異向量是由父代差分向量生成，并與父代個(gè)體向量交叉生成新個(gè)體向量，直接與其父代個(gè)體進(jìn)行選擇。顯然差分進(jìn)化算法相對(duì)遺傳算法的逼近效果更加顯著。

遺傳算法，粒子群算法，差分進(jìn)化算法都屬于進(jìn)化算法的分枝，很多學(xué)者對(duì)這些算法進(jìn)行了研究，通過不斷的改進(jìn)，提高了算法的性能，擴(kuò)大了應(yīng)用領(lǐng)域因此很有必要討論這些算法的特點(diǎn)，針對(duì)不同應(yīng)用領(lǐng)域和算法的適應(yīng)能力，推薦不同的算法供使用將是十分有意義的工作．在文獻(xiàn)中，作者針對(duì)廣泛使用的 34 個(gè)基準(zhǔn)函數(shù)分別對(duì) DE，EA，PSO 進(jìn)行了系列實(shí)驗(yàn)分析，對(duì)各種算法求解最優(yōu)解問題進(jìn)行了討論.通過實(shí)驗(yàn)分析，DE 算法獲得了最優(yōu)性能，而且算法比較穩(wěn)定，反復(fù)運(yùn)算都能收斂到同一個(gè)解；PSO 算法收斂速度次之，但是算法不穩(wěn)定，最終收斂結(jié)果容易受參數(shù)大小和初始種群的影響；EA 算法收斂速度相對(duì)比較慢，但在處理噪聲問題方面，EA 能夠很好的解決而 DE 算法很難處理這種噪聲問題.

?

通過實(shí)驗(yàn)和文獻(xiàn)分析，我們對(duì)遺傳算法、粒子群算法、差分進(jìn)化算法的一些指標(biāo)分別進(jìn)行分析現(xiàn)歸納如下：

（1）編碼標(biāo)準(zhǔn)?? ? GA 采用二進(jìn)制編碼，PSO、DE 都采用浮點(diǎn)實(shí)數(shù)編碼，近年來許多學(xué)者通過整數(shù)編碼將GA 算法、PSO 算法應(yīng)用與求解離散型問題，特別是 0-1 非線性優(yōu)化為題，整數(shù)規(guī)劃問題、混合整數(shù)規(guī)劃問題，而離散的 DE 算法則研究的比較少，而采用混合編碼技術(shù)的 DE 算法則研究更少.

（2）參數(shù)設(shè)置問題?? ?DE 算法主要有三個(gè)參數(shù)（種群大小NP、縮放因子F、交叉概率CR）要調(diào)整，而且參數(shù)設(shè)置對(duì)結(jié)果影響不太明顯，因此更容易使用.相對(duì)于 GA 和 PSO 算法的參數(shù)過多，不同的參數(shù)設(shè)置對(duì)最終結(jié)果影響也比較大，因此在實(shí)際使用中，要不斷調(diào)整，加大了算法的使用難度．高維問題在實(shí)際問題中，由于轉(zhuǎn)化為個(gè)體的向量維數(shù)非常高，因此算法對(duì)高維問題的處理，將是很重要的.只有很好的處理高維問題，算法才能很好的應(yīng)用于實(shí)際問題.

（3）高維問題?? ??GA 對(duì)高維問題收斂速度很慢甚至很難收斂，但是 PSO 和 DE 則能很好解決.尤其是DE 算法，收斂速度很快而且結(jié)果很精確.

（4）收斂性能?? ? ?對(duì)于優(yōu)化問題，相對(duì) GA，DE 和 PSO 算法收斂速度比較快，但是 PSO 容易陷入局部最優(yōu)解，而且算法不穩(wěn)定.

（5）應(yīng)用廣泛性?? ? ? 由于 GA 算法發(fā)明比較早，因此應(yīng)用領(lǐng)域比較廣泛，PSO 算法自從發(fā)明以來，已成為研究熱點(diǎn)問題，這方面應(yīng)用也比較多，而 DE 算法近幾年才引起人們的關(guān)注而且算法性能好，因此應(yīng)用領(lǐng)域?qū)?huì)增多.

DE缺點(diǎn)：

1、搜索停滯：種群個(gè)體較少，且生成新一代個(gè)體的適應(yīng)值比原種群個(gè)體適應(yīng)值差，導(dǎo)致個(gè)體難以更新，沒有收斂到極值點(diǎn)。

2、早熟收斂：參數(shù)設(shè)置不當(dāng)，收斂過快，局部最優(yōu)問題。

總結(jié)

以上是生活随笔為你收集整理的遗传算法　差分进化算法　粒子群优化算法区别的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。