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

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

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

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

5、重要的學術意義和應 用價值。差分進化計算的群體智能搜索策略分析1 個體行為及個體之間信息交互方法分析 差分進化的個體表示方式與其他進化計算相同，是模擬生物進化中的關鍵因素，即生物的染色體和基因， 構造每個解的形式， 構成了算法的基礎。 一切的尋優操作都是在個體的基礎 上進行的，最優個體是搜尋到的最優的解。差分進化的個體行為主要體現在差分變異算子和交叉算子上。1) 變異算子 在差分進化計算中， 美國基因位的改變值取決于其他個體之間的差值， 充分利用了群體中其 他個體的信息， 達到了擴充種群多樣性的同時， 也避免了單純在個體內部進行變異操作所帶 來的隨機性和盲目性，在隨機向量差分法中每個個體的變異

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

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

8、優化每個個體， 利用個體局部信息和群體全局信息指導算法 進一步搜索的能力。 這兩種方法的群體具有記憶個體最優解的能力。 在進化過程中， 充分利 用種群繁衍進程中產生的有用信息。差分進化計算作為一種模擬自然進化現象的隨機搜索算法，雖然有可能實現全局最優搜 索，但也有出現早熟的弊端。種群在開始時有較分散的隨機配置， 但是隨著進化的進行，各 代之間種群分布密度偏高， 信息的交換逐漸減少， 使得全局尋優能力逐漸下降。 種群中各個 個體的進化， 采用貪婪選擇操作， 依靠適應著的高低做簡單的好壞判斷， 缺乏深層的理性分 析。參考文獻：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.聚類分析的主要目的是通過對數據集的合理劃分來發現數據集的結構特征， 利用聚類結 果，我們能夠提取數據集中隱藏的信息， 對未來數據進行預測和分類。 例如，在許多具體問 題中，描述問題的實際數據是容易得到的， 但是隱藏在數據中的內在信息或知識卻不容易直 接獲得。因此， 需要對數據進行分析和分類， 從中提取有效信息。 而隨著數據庫技術的不斷 發展，許多應用領域都會產生遠遠超出人類的直接處理能力的大量的實際數據。 為了能更方 便的理解和表示這些數據， 需要進行數據壓縮， 同時又要盡量保持原數據的隱含信息。 這些具體問題的解決就要用到聚類及相關算法。例如，氣象災害會給國家和人民群眾帶來很大損失，將差分進化聚類算法應用于災害性天氣預報中，若能達到很好的預報準確率，可以減小氣象災害帶給國家和人民的損失，可以造福社會和人民。同時將算法應用到UCI中一些數據的聚類和分類中，女口 lris,WineData,Echocardiogram等數