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