基本介紹
- 中文名：差分進化算法
- 外文名：Differential Evolution Algorithm
- 簡寫：DE
歷史發展,基本原理,進化流程,控制參數,改進方法,
歷史發展
差分進化算法(Differential Evolution，DE)由Storn和Price於1995年首次提出。主要用於求解實數最佳化問題。該算法是一類基於群體的自適應全局最佳化算法，屬於演化算法的一種，由於其具有結構簡單、容易實現、收斂快速、魯棒性強等特點，因而被廣泛套用在數據挖掘、模式識別、數字濾波器設計、人工神經網路、電磁學等各個領域。1996年在日本名古屋舉行的第一屆國際演化計算(ICEO)競賽中，差分進化算法被證明是速度最快的進化算法。
和遺傳算法一樣，差分進化算法也是一種基於現代智慧型理論的最佳化算法，通過群體內個體之間的相互合作與競爭產生的群體智慧型來指導最佳化搜尋的方向。該算法的基本思想是：從一個隨機產生的初始種群開始，通過把種群中任意兩個個體的向量差與第三個個體求和來產生新個體，然後將新個體與當代種群中相應的個體相比較，如果新個體的適應度優於當前個體的適應度，則在下一代中就用新個體取代舊個體，否則仍保存舊個體。通過不斷地進化，保留優良個體，淘汰劣質個體，引導搜尋向最優解逼近。
為了使更多研究者了解和研究差分進化算法，Storn和Price於1997年建立了差分進化算法的官方網站，該網站的建立得到了廣大研究者的關注和支持，為相關人員進行差分演化算法的理論和套用研究提供了極大的方便。此外，Store和Price在差分進化算法上沒有申請任何形式的專利，這也為推動差分進化算法的研究和套用起到了重要的作用。
基本原理
DE算法通過採用浮點矢量進行編碼生成種群個體。在DE算法尋優的過程中，首先，從父代個體間選擇兩個個體進行向量做差生成差分矢量；其次，選擇另外一個個體與差分矢量求和生成實驗個體；然後，對父代個體與相應的實驗個體進行交叉操作，生成新的子代個體；最後在父代個體和子代個體之間進行選擇操作，將符合要求的個體保存到下一代群體中去。
進化流程
其具體進化流程如下：
(1)確定差分進化算法控制參數，確定適應度函式。差分進化算法控制參數包括：種群大小NP、縮放因子F與雜交機率CR。
(2)隨機產生初始種群。
(3)對初始種群進行評價，即計算初始種群中每個個體的適應度值。
(4)判斷是否達到終止條件或進化代數達到最大。若是，則終止進化，將得到最佳個體作為最優解輸出；若否，繼續。
(5)進行變異和交叉操作，得到中間種群。
(6)在原種群和中間種群中選擇個體，得到新一代種群。
(7)進化代數g=g+1，轉步驟(4).
控制參數
DE算法主要的控制參數包括：種群規模(NP)、縮放因子(F)和交叉機率(CR)。
NP主要反映算法中種群信息量的大小，NP值越大種群信息包含的越豐富，但是帶來的後果就是計算量變大，不利於求解。反之，使種群多樣性受到限制，不利於算法求得全局最優解，甚至會導致搜尋停滯。
CR主要反映的是在交叉的過程中，子代與父代、中間變異體之間交換信息量的大小程度。CR的值越大，信息量交換的程度越大。反之，如果CR的值偏小，將會使種群的多樣性快速減小，不利於全局尋優。
相對於CR，F對算法性能的影響更大，F主要影響算法的全局尋優能力。F越小，算法對局部的搜尋能力更好，F越大算法越能跳出局部極小點，但是收斂速度會變慢。此外，F還影響種群的多樣性。
改進方法
基本DE算法在求解的過程中，隨著進化代數的增加，會使種群的多樣性變小，過早的收斂到局部極小點，或者致使算法停滯，這對依靠種群差異來進行進化的算法來說無疑是致命的，使算法的性能在進化的過程中變差。
為了解決基本DE算法的上述缺陷，針對DE算法的特點，目前主要的改進方法是針對進化模式和控制參數的最佳化，還有一些改進方法是將DE算法與其他一些智慧型算法進行結合仲用。
