1. 差分進化算法簡介
（以下描述扯饶，均不是學術(shù)用語，僅供大家快樂的閱讀）
差分進化算法（Differential Evolution Algorithm砰琢，DE）是一種基于群體的進化算法胡桨，它模擬了群體中的個體的合作與競爭的過程。算法原理簡單烫堤，控制參數(shù)少荣赶，只有交叉概率和縮放比例因子，魯棒性強鸽斟，易于實現(xiàn)拔创。
差分進化算法中，每一個個體的基因表示待求問題的一個候選解富蓄。每次迭代將先進行變異操作剩燥，選擇一個或多個個體的基因作為基，然后選擇不同的個體的差分來構(gòu)成差分基因立倍，最后將作為基的基因與差分基因相加來得出新的個體躏吊。交叉操作將新的個體將于父代的對應個體交叉，然后進行選擇操作帐萎，比較交叉后的個體與父代的對應個體比伏，選擇較優(yōu)的個體保留至下一代。在迭代完成之后將選擇種群中最優(yōu)個體的基因作為解疆导。
差分進化算法可以算是我所使用過的優(yōu)化算法中大魔王級別的算法赁项，雖然它每個方面都沒有強到離譜，但是綜合起來的效果好于大多數(shù)算法。它就像一個每個科目都能考到90分（百分制）的學生悠菜，雖然沒門課都不是最優(yōu)秀的舰攒，但是論綜合，論總分悔醋，它有極大的概率是第一名摩窃。
在我研究優(yōu)化算法的小路上，我的目標就是找到一個能打敗大魔王或是能在大多數(shù)方面壓制魔王的算法淘太。
2. 算法流程
這次的主角就選魔王軍吧（或者蟻王軍姻僧，為了與蟻群算法區(qū)別還是叫魔王軍吧），個體則稱之為魔王兵蒲牧。
魔王兵的能力取決于它們的基因撇贺，它們可以根據(jù)環(huán)境或者需要改變自己的基因使得自己更加強大，更方便的處理問題冰抢，問題的維度與基因維度相同松嘶。
表示第i個魔王兵在進化了第t次后的基因，該個體有D位基因晒屎。
與遺傳算法同為進化算法的差分進化算法喘蟆，它們的操作（算子）也都非常相似的缓升，都是交叉鼓鲁，變異和選擇，流程也幾乎一樣（遺傳算法先交叉后變異港谊，差分進化算法先變異后交叉）骇吭。
2.1變異
說到差分進化算法中的變異，我就想到一句論語“三人行歧寺，必有我?guī)熝稍镎衿渖普叨鴱闹洳簧普叨闹笨稹龙致！?/strong>，其實這句論語已經(jīng)向我們說明了差分進化算法的整個流程：
“三人行顷链，必有我?guī)熝伞薄儺惸看徊妗?br>
“擇其善者而從之，其不善者而改之”——選擇。
差分進化算法中榛了，當一個魔王兵變異時在讶，它會先找來3個小伙伴，當然是隨機找來3個小伙伴霜大，避免同化构哺。在一個小伙伴的基因上加上另外兩個小伙伴基因之差作為自己的目標基因。其變異公式如下：
表示第i個魔王兵找到了編號為r1战坤、r2和r3的三個魔王兵曙强，當然了i、r1湖笨、r2旗扑、r3為互不相同的整數(shù)，F(xiàn)為縮放比例因子慈省，通常 臀防，一般取F=0.5。為第i個魔王兵交叉后的目標基因圖紙边败，不過這是個半成品袱衷，再經(jīng)過交叉后，目標基因圖紙才算完成笑窜。
其實現(xiàn)在我們已經(jīng)有了5個基因圖紙了致燥，接下來將進行交叉操作。由于變異操作排截，差分進化算法的種群中個體數(shù)至少為4嫌蚤，即魔王軍中至少有4個小兵。
2.2交叉
交叉操作中断傲，魔王兵i會將目標基因圖紙 進行加工得到
脱吱，加工過程如下：
其中 。 為交叉概率认罩，其值越大箱蝠，發(fā)生交叉的概率越大，一般取 垦垂。 為{1,2,…,D}中的隨機整數(shù)宦搬，其作用是保證交叉操作中至少有一維基因來自變異操作產(chǎn)生的基因，不能讓交叉操作的努力白費劫拗。
從公式上可以看出交叉操作實際上是從變異操作得出的基因圖紙上選擇至少一位基因來替換自己的等位基因间校，得到最終的基因圖紙。
2.3選擇
選擇操作相對簡單页慷，魔王兵i拿到了最終的基因圖紙 憔足，大喊一聲聂渊，進化吧，魔王兵i的基因改變了四瘫。它拿出了能力測量器fitness function,如果發(fā)現(xiàn)自己變強了汉嗽，那么就將基因 保留到下一代，否則它選擇放棄進化找蜜，讓自己還原成
饼暑。
3. 實驗初步
實驗又來啦，還是那個實驗洗做，簡單弓叛、易算、好畫圖诚纸。
實驗1：參數(shù)如下
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 小兵數(shù)量(種群數(shù)) | 20 |
| 進化次數(shù)(最大迭代次數(shù)) | 50 |
| CR（交叉率） | 0.3 |
| F（放縮因子） | 0.5 |
| 取值范圍 | （-100撰筷，100） |
| 實驗次數(shù) | 10 |
圖中可以看出在第20代時，群體已經(jīng)非常集中了畦徘，在來看看最終得出的結(jié)果毕籽。
| 值 | |
|---|---|
| 最優(yōu)值 | 1.0917867028293985E-8 |
| 最差值 | 2.9361020954274757E-6 |
| 平均值 | 5.847453820715603E-7 |
這結(jié)果真是好到令人發(fā)指，惡魔在心中低語“把其他的優(yōu)化算法都丟掉吧”井辆。不過別往心里去关筒，任何算法都有優(yōu)缺點，天下沒有免費的午餐杯缺，要想獲得某種能力必須付出至少相應的代價蒸播。
實驗2：
將交叉率CR設為0,即每次交叉只選擇保留一位變異基因。
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 小兵數(shù)量(種群數(shù)) | 20 |
| 進化次數(shù)(最大迭代次數(shù)) | 50 |
| CR（交叉率） | 0.0 |
| F（放縮因子） | 0.5 |
| 取值范圍 | （-100萍肆，100） |
| 實驗次數(shù) | 10 |
看看了看圖袍榆，感覺跟實驗1中相比沒有什么變化，那我們再來看看結(jié)果塘揣。
| 值 | |
|---|---|
| 最優(yōu)值 | 2.922699066690564E-10 |
| 最差值 | 1.5170095944418442E-7 |
| 平均值 | 1.9533094363773728E-8 |
結(jié)果總體來說比實驗1好了一個數(shù)量級包雀。為什么呢？個人感覺應該是每次只改變一位基因的局部搜索能力比改變多位基因更強勿负。下面我們將交叉率CR設為1來看看是否是這樣馏艾。
實驗3：
將交叉率CR設為1,即每次交叉只選擇保留一位原有基因劳曹。
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 小兵數(shù)量(種群數(shù)) | 20 |
| 進化次數(shù)(最大迭代次數(shù)) | 50 |
| CR（交叉率） | 1.0 |
| F（放縮因子） | 0.5 |
| 取值范圍 | （-100奴愉，100） |
| 實驗次數(shù) | 10 |
實驗3的圖與實驗1和實驗2相比好像也沒什么差別,只是收斂速度好像快了那么一點點。再來看看結(jié)果铁孵。
| 值 | |
|---|---|
| 最優(yōu)值 | 1.247729854010192E-10 |
| 最差值 | 2.3424955950460443E-8 |
| 平均值 | 4.089766498652818E-9 |
發(fā)現(xiàn)結(jié)果比實驗2的結(jié)果還要好锭硼？那說明了實驗2我得出的結(jié)論是可能是錯誤的，交叉率在該問題上對差分進化算法的影響不大蜕劝，它們結(jié)果的差異可能只是運氣的差異檀头，畢竟是概率算法轰异。
實驗4：
將變異放縮因子設為0，即變異只與一個個體有關(guān)暑始。
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 小兵數(shù)量(種群數(shù)) | 20 |
| 進化次數(shù)(最大迭代次數(shù)) | 50 |
| CR（交叉率） | 0.3 |
| F（放縮因子） | 0.0 |
| 取值范圍 | （-100搭独，100） |
| 實驗次數(shù) | 10 |
收斂速度依然很快，不過怎么感覺結(jié)果不對廊镜，而且個體收斂的路徑好像遺傳算法牙肝，當F=0，時嗤朴，差分進化算法退化為了沒有變異配椭、選擇操作的遺傳算法，結(jié)果一定不會太好雹姊。
| 值 | |
|---|---|
| 最優(yōu)值 | 0.453120676982517 |
| 最差值 | 286.3408283178992 |
| 平均值 | 106.1719276191775 |
果然如此股缸。下面我們再看看F=2時的實驗。
實驗5：
將變異放縮因子設為2吱雏。
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 小兵數(shù)量(種群數(shù)) | 20 |
| 進化次數(shù)(最大迭代次數(shù)) | 50 |
| CR（交叉率） | 0.3 |
| F（放縮因子） | 2.0 |
| 取值范圍 | （-100敦姻，100） |
| 實驗次數(shù) | 10 |
實驗5的圖可以明顯看出，群體的收斂速度要慢了許多歧杏，到第50代時替劈，種群還未完全收斂于一點，那么在50代時其結(jié)果也不會很好得滤，畢竟算法還未收斂就停止進化了陨献。
| 參數(shù) | 值 |
|---|---|
| 最優(yōu)值 | 0.003982238947037151 |
| 最差值 | 1.1517176365886543 |
| 平均值 | 0.23692008026134745 |
結(jié)果不算很好但也算相對穩(wěn)定。
通過上面5個實驗懂更，我們大致了解了差分進化算法的兩個參數(shù)的作用眨业。
交叉率CR，影響基因取自變異基因的比例沮协，由于至少要保留一位自己的基因和變異的基因?qū)е翪R在該問題上對算法性能的影響不大（這個問題比較簡單龄捡，維度較低，影響不大）慷暂。
變異放縮因子F聘殖，影響群體的收斂速度，F(xiàn)越大收斂速度越慢行瑞，F(xiàn)絕對值越小收斂速度越快奸腺，當F=0是群體之間只會交換基因，不會變異基因血久。
4. 探究與改進
差分進化算法大魔王已經(jīng)如此強大了突照，那么還有什么可以改進的呢？當然有下面一一道來氧吐。
方案1.將3人行修改為5人行讹蘑，以及推廣到2n+1人行末盔。
實驗6：
將3人行修改為5人行，變異公式如下：
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 小兵數(shù)量(種群數(shù)) | 20 |
| 進化次數(shù)(最大迭代次數(shù)) | 50 |
| CR（交叉率） | 0.3 |
| F1（放縮因子） | 0.5 |
| F2（放縮因子） | 0.5 |
| 取值范圍 | （-100座慰，100） |
| 實驗次數(shù) | 10 |
五人行的實驗圖看起來好像與之前并沒有太大的變化陨舱，我們再來看看結(jié)果。
| 參數(shù) | 值 |
|---|---|
| 最優(yōu)值 | 1.7892717650452213E-8 |
| 最差值 | 4.573249741855863E-6 |
| 平均值 | 1.0415260793972972E-6 |
結(jié)果沒有明顯提升版仔，反而感覺比之前的結(jié)果差了隅忿。反思一下五人行的優(yōu)缺點，優(yōu)點邦尊，取值范圍更大背桐，缺點，情況太多蝉揍，減慢搜索速度链峭。
上圖為
上圖為
對于交叉操作來所表窘，“五人行”的選擇更多典予，搜索能力應該更強，但這個問題的適應度函數(shù)過于簡單乐严，可能無法發(fā)揮其優(yōu)勢瘤袖，所以此時“五人行”的結(jié)果差于“三人行”的結(jié)果。
方案2昂验，變異放縮因子隨機化
第3節(jié)中我們可以明顯看出變異放縮因子F對差分進化算法的影響明顯大于交叉率CR,F能影響算法的收斂速度捂敌。注意到差分進化算法沒有跳出局部最優(yōu)的操作，如果算法收斂太快容易陷入局部最優(yōu)既琴，而收斂太慢又會影響求解速度占婉。因此我向隨機化F來均衡一下算法的收斂速度。
實驗7：
F取值為（0,2）內(nèi)的隨機數(shù)呛梆。
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 小兵數(shù)量(種群數(shù)) | 20 |
| 進化次數(shù)(最大迭代次數(shù)) | 50 |
| CR（交叉率） | 0.3 |
| F（放縮因子） | (0,2) |
| 取值范圍 | （-100锐涯，100） |
| 實驗次數(shù) | 10 |
可以看出算法的收斂速度比之前的變慢了一點磕诊，再看看結(jié)果填物。
| 參數(shù) | 值 |
|---|---|
| 最優(yōu)值 | 1.002461804484959E-8 |
| 最差值 | 1.5000010808013516E-4 |
| 平均值 | 2.5148494598068475E-5 |
比之前差纹腌。
探究過程中失敗是難免的，F(xiàn)為（0,2）內(nèi)的隨機數(shù)滞磺，那么F的期望為1升薯，其收斂速度變慢導致結(jié)果變差也是難免，畢竟最大迭代次數(shù)只有50击困，而且適應度函數(shù)過于簡單涎劈。
方案3：為差分進化算法新增跳出局部最優(yōu)的操作。
這個方案沒有試驗阅茶，差分進化算法是否需要該操作還是未知數(shù)蛛枚？差分進化算法有著優(yōu)秀的搜索能力，那么跳出局部最優(yōu)能力是否需要呢脸哀？一個攻擊能力超強的戰(zhàn)士是否需要加強防御能力呢蹦浦？
其實我認為還是必要的，因為現(xiàn)在我們需要用優(yōu)化算法去解決的實際問題大多是動態(tài)的而不是實驗中的靜態(tài)還是撞蜂，在處理動態(tài)問題時盲镶，一點跳出局部最優(yōu)能力能夠讓優(yōu)化算法快速做出反應而不是再緩慢的進化。只是如何給差分進化算法優(yōu)雅的添加跳出局部最優(yōu)性能的方案還沒有想到蝌诡。
5. 總結(jié)
差分進化算法的學習在此也告一段落溉贿。差分進化算法很強大，也很簡單浦旱、簡潔宇色，算法的描述都充滿了美感，不愧是大魔王颁湖。不過這里并不是結(jié)束代兵，這只是個開始，終將找到打敗大魔王的方法爷狈，讓新的魔王誕生植影。
由于差分進化算法足夠強，而文中實驗的問題較為簡單導致算法的改進甚至越改越差（其實我也不知道改的如何涎永，需要大量實驗驗證）思币。在遙遠的將來，也會有更加復雜的問題來檢驗魔王的能力羡微，總之谷饿，后會無期。
以下指標純屬個人yy,僅供參考
| 指標 | 星數(shù) |
|---|---|
| 復雜度 | ★★★☆☆☆☆☆☆☆ |
| 收斂速度 | ★★★★★★★★☆☆ |
| 全局搜索 | ★★★★★★★★☆☆ |
| 局部搜索 | ★★★★★★★★☆☆ |
| 優(yōu)化性能 | ★★★★★★★★☆☆ |
| 跳出局部最優(yōu) | ☆☆☆☆☆☆☆☆☆☆ |
| 改進點 | ★★☆☆☆☆☆☆☆☆ |
