差分進(jìn)化算法綜述概況

1、差分進(jìn)化算法 (DE )1是 Storn 和 Price 在 1995 年提出的一種基于種群差異的進(jìn)化算法， DE 是一種隨機(jī)的并行搜索算法。差分進(jìn)化計(jì)算和其他進(jìn)化計(jì)算算法一樣，都是基于群體智 能理論的優(yōu)化算法， 利用群體內(nèi)個(gè)體之間的合作與競(jìng)爭(zhēng)產(chǎn)生的群體智能模式來(lái)指導(dǎo)優(yōu)化搜索 的進(jìn)行。 與其他進(jìn)化計(jì)算不同的是， 差分進(jìn)化計(jì)算保留了基于種群的全局搜索策略， 采用實(shí) 數(shù)編碼、 基于差分的簡(jiǎn)單變異操作和一對(duì)一的競(jìng)爭(zhēng)生存策略， 降低了進(jìn)化操作的復(fù)雜性。 差 分進(jìn)化計(jì)算特有的進(jìn)化操作使得其具有較強(qiáng)的全局收斂能力和魯棒性， 非常適合求解一些復(fù) 雜環(huán)境中的優(yōu)化問(wèn)題。最初試圖使用向量差進(jìn)行向量種群的混洗， 以

2、此來(lái)解決切比雪夫多項(xiàng)式適應(yīng)性問(wèn)題。 DE 通 過(guò)種群內(nèi)個(gè)體間的合作與競(jìng)爭(zhēng)來(lái)實(shí)現(xiàn)對(duì)優(yōu)化問(wèn)題的求解， 其本質(zhì)上是一種基于實(shí)數(shù)編碼的具 有保優(yōu)思想的進(jìn)化算法。 該算法實(shí)現(xiàn)技術(shù)簡(jiǎn)單， 在對(duì)各種測(cè)試問(wèn)題的實(shí)驗(yàn)中表現(xiàn)優(yōu)異， 已經(jīng) 成為近年來(lái)進(jìn)化算法研究中的熱點(diǎn)之一。差分進(jìn)化算法基本原理基本的差分進(jìn)化算法是基于候選方案種群的算法， 在整個(gè)搜索空間內(nèi)進(jìn)行方案的搜索， 通過(guò) 使用簡(jiǎn)單的數(shù)學(xué)公式對(duì)種群中的現(xiàn)有方案進(jìn)行組合實(shí)現(xiàn)的。 如果新的方案有所改進(jìn)， 則被接 受，否則被丟棄，重復(fù)這一過(guò)程直到找到滿(mǎn)意的方案。設(shè) f 是最小化適應(yīng)度函數(shù)， 適應(yīng)度函數(shù)以實(shí)數(shù)向量的形式取一個(gè)候選方案作為參數(shù)， 給 出一個(gè)實(shí)數(shù)數(shù)值作為候

3、選方案的輸出適應(yīng)值。 其目的是在搜索空間的所有方案 p 中找到 m 使得f(m) w f(p)。最大化是找到一個(gè)m使得f(m) > f(p)。設(shè)X=(x1, x2,xn£ ?n是種群中一個(gè)個(gè)體，基本的差分進(jìn)化算法如下所述：? 在搜索空間中隨機(jī)地初始化所有的個(gè)體。? 重復(fù)如下操作直到滿(mǎn)足終止條件(最大迭代數(shù)或者找到滿(mǎn)足適應(yīng)值的個(gè)體)o對(duì)于種群中的每個(gè)個(gè)體：隨機(jī)地從種群中選擇三個(gè)彼此不同的個(gè)體a， b 和 c。選擇一個(gè)隨機(jī)索引 R 1, ., n , n是被優(yōu)化問(wèn)題的維數(shù)。通過(guò)對(duì)每個(gè)i 1,., n進(jìn)行如下的迭代計(jì)算可能的新個(gè)體Y = y1, ., yn生成一個(gè)隨機(jī)數(shù) riU(0,

4、1) ；如果 (i=R) 或者 (ri<CR) ， yi = ai + F(bi - ci )，否則 yi = xi ；如果(f(yi) < f(xi)，則在種群中使用改進(jìn)的新生成的yi替換原來(lái)的xi,否則不變。選擇具有最小適應(yīng)度值的 xi 作為搜索的結(jié)果。需要指出的是 F 0,2 稱(chēng)為縮放因子， CR 0,1稱(chēng)為交叉因子，種群大小 NP>3。 差分進(jìn)化算法作為一種新出現(xiàn)的優(yōu)化算法在實(shí)際應(yīng)用中表現(xiàn)出了優(yōu)異的性能，被廣泛應(yīng)用到不同的領(lǐng)域， 已經(jīng)成為近年來(lái)優(yōu)化算法的研究的熱點(diǎn)之一。 研究差分進(jìn)化算法， 探索提高差 分進(jìn)化算法性能的新方法， 并將其應(yīng)用到具體工程問(wèn)題的解決中， 具有

5、重要的學(xué)術(shù)意義和應(yīng) 用價(jià)值。差分進(jìn)化計(jì)算的群體智能搜索策略分析1 個(gè)體行為及個(gè)體之間信息交互方法分析 差分進(jìn)化的個(gè)體表示方式與其他進(jìn)化計(jì)算相同，是模擬生物進(jìn)化中的關(guān)鍵因素，即生物的染色體和基因， 構(gòu)造每個(gè)解的形式， 構(gòu)成了算法的基礎(chǔ)。 一切的尋優(yōu)操作都是在個(gè)體的基礎(chǔ) 上進(jìn)行的，最優(yōu)個(gè)體是搜尋到的最優(yōu)的解。差分進(jìn)化的個(gè)體行為主要體現(xiàn)在差分變異算子和交叉算子上。1) 變異算子 在差分進(jìn)化計(jì)算中， 美國(guó)基因位的改變值取決于其他個(gè)體之間的差值， 充分利用了群體中其 他個(gè)體的信息， 達(dá)到了擴(kuò)充種群多樣性的同時(shí)， 也避免了單純?cè)趥€(gè)體內(nèi)部進(jìn)行變異操作所帶 來(lái)的隨機(jī)性和盲目性，在隨機(jī)向量差分法中每個(gè)個(gè)體的變異

6、取決于兩個(gè)隨機(jī)個(gè)體的向量差： 采用最優(yōu)解加隨機(jī)向量差分法， 每個(gè)個(gè)體由當(dāng)前最優(yōu)解決定， 分布在當(dāng)前最優(yōu)解的鄰域范圍 內(nèi)，利用了當(dāng)前最優(yōu)種群最優(yōu)個(gè)體的信息，加速了搜索速度，但同時(shí)如果種群分布密度高， 可能會(huì)導(dǎo)致算法陷入局部最優(yōu)解； 采用最優(yōu)解與隨機(jī)向量差分法， 用個(gè)體局部信息和群體全 局信息指導(dǎo)算法進(jìn)一步搜索的能力，較最優(yōu)解加隨機(jī)向量法降低了陷入局部最優(yōu)解的危險(xiǎn)。 當(dāng)向量偏差大時(shí)，導(dǎo)致個(gè)體的變異強(qiáng)度高；反之， 個(gè)體的變異強(qiáng)度低。 差分進(jìn)化計(jì)算域種群 的分布密度相關(guān)，因此如果種群分布密度高，則個(gè)體的變異強(qiáng)度較低。2) 交叉算子在差分進(jìn)化計(jì)算中， 進(jìn)行交叉操作的主體是父代個(gè)體和由它經(jīng)過(guò)差分變異操作后

7、得到的 新個(gè)體，雖然這種方法看似沒(méi)有進(jìn)行個(gè)體之間的信息交互，但由于新個(gè)體經(jīng)過(guò)差分變異 而來(lái)，本身保存有種群中其他個(gè)體的信息，因此差分進(jìn)化的交叉算子同樣具有個(gè)體之間 信息交互的機(jī)制。2 群體進(jìn)化分析與其他進(jìn)化計(jì)算相同， 差分進(jìn)化計(jì)算模擬生物進(jìn)化過(guò)程， 使得種群的衍化想著更好的方向 前進(jìn)。 通過(guò)每一代群體的變異、 交叉操作產(chǎn)生新的種群， 并通過(guò)貪婪選擇的方式選擇優(yōu)秀的 個(gè)體， 組成下一代的進(jìn)化群體。 這種方式可以保證群體的優(yōu)良性， 并加快尋優(yōu)速度，但也有 其不足，即容易陷入局部最優(yōu)。差分進(jìn)化計(jì)算的群體在尋優(yōu)的過(guò)程中， 具有協(xié)同搜索的特點(diǎn)， 搜索能力強(qiáng)。 最優(yōu)解加隨機(jī)向 量差分法充分利用當(dāng)前最優(yōu)解來(lái)

8、優(yōu)化每個(gè)個(gè)體， 利用個(gè)體局部信息和群體全局信息指導(dǎo)算法 進(jìn)一步搜索的能力。 這兩種方法的群體具有記憶個(gè)體最優(yōu)解的能力。 在進(jìn)化過(guò)程中， 充分利 用種群繁衍進(jìn)程中產(chǎn)生的有用信息。差分進(jìn)化計(jì)算作為一種模擬自然進(jìn)化現(xiàn)象的隨機(jī)搜索算法，雖然有可能實(shí)現(xiàn)全局最優(yōu)搜 索，但也有出現(xiàn)早熟的弊端。種群在開(kāi)始時(shí)有較分散的隨機(jī)配置， 但是隨著進(jìn)化的進(jìn)行，各 代之間種群分布密度偏高， 信息的交換逐漸減少， 使得全局尋優(yōu)能力逐漸下降。 種群中各個(gè) 個(gè)體的進(jìn)化， 采用貪婪選擇操作， 依靠適應(yīng)著的高低做簡(jiǎn)單的好壞判斷， 缺乏深層的理性分 析。參考文獻(xiàn)：1Storn R, Price K. Differential Evol

9、ution - A Simple and Efficient Heuristic for GlobalOptimizati on over Contin uous SpacesJ. Journal of Global Optimizatio n. 1997(11): 341 -359.聚類(lèi)分析的主要目的是通過(guò)對(duì)數(shù)據(jù)集的合理劃分來(lái)發(fā)現(xiàn)數(shù)據(jù)集的結(jié)構(gòu)特征， 利用聚類(lèi)結(jié) 果，我們能夠提取數(shù)據(jù)集中隱藏的信息， 對(duì)未來(lái)數(shù)據(jù)進(jìn)行預(yù)測(cè)和分類(lèi)。 例如，在許多具體問(wèn) 題中，描述問(wèn)題的實(shí)際數(shù)據(jù)是容易得到的， 但是隱藏在數(shù)據(jù)中的內(nèi)在信息或知識(shí)卻不容易直 接獲得。因此， 需要對(duì)數(shù)據(jù)進(jìn)行分析和分類(lèi)， 從中提取有效信息。 而隨著數(shù)據(jù)庫(kù)技術(shù)的不斷 發(fā)展，許多應(yīng)用領(lǐng)域都會(huì)產(chǎn)生遠(yuǎn)遠(yuǎn)超出人類(lèi)的直接處理能力的大量的實(shí)際數(shù)據(jù)。 為了能更方 便的理解和表示這些數(shù)據(jù)， 需要進(jìn)行數(shù)據(jù)壓縮， 同時(shí)又要盡量保持原數(shù)據(jù)的隱含信息。 這些具體問(wèn)題的解決就要用到聚類(lèi)及相關(guān)算法。例如，氣象災(zāi)害會(huì)給國(guó)家和人民群眾帶來(lái)很大損失，將差分進(jìn)化聚類(lèi)算法應(yīng)用于災(zāi)害性天氣預(yù)報(bào)中，若能達(dá)到很好的預(yù)報(bào)準(zhǔn)確率，可以減小氣象災(zāi)害帶給國(guó)家和人民的損失，可以造福社會(huì)和人民。同時(shí)將算法應(yīng)用到UCI中一些數(shù)據(jù)的聚類(lèi)和分類(lèi)中，女口 lris,WineData,Echocardiogram等數(shù)