差分進化算法在極大熵聚類優(yōu)化中的應(yīng)用

文/林濤 廣東省電信規(guī)劃設(shè)計院有限公司 廣東廣州 510630

極大熵聚類算法(Maximum Entropy Clust ering，MEC)[1]是經(jīng)典的模糊聚類方法，主要利用熵模型和最大熵定理設(shè)計目標函數(shù)。文獻[2]嚴格證明了MEC算法能夠收斂到目標函數(shù)的局部極小值，但未必能收斂到全局最優(yōu)點上。

差分進化算法(Differential Evolution，DE)是一種智能優(yōu)化方法，通過變異、交叉、選擇等處理和種群更替，最終在可行域中搜索出最優(yōu)解。DE算法具有較強的全局搜索能力，常用于解決實際中的復(fù)雜優(yōu)化問題。

本文借助DE算法的全局搜索能力，處理MEC算法目標函數(shù)的優(yōu)化問題，提出一種基于差分進化的極大熵聚類算法，使其具有更好的聚類性能。

1、極大熵聚類算法

2、差分進化算法

DE算法是一種通過實數(shù)編碼，能在連續(xù)空間內(nèi)進行策略搜索，實現(xiàn)全局尋優(yōu)的優(yōu)化方法，主要通過個體優(yōu)勝劣汰和種群多樣性，驅(qū)使算法向全局最優(yōu)解搜索。DE算法包括種群初始化、變異、交叉、選擇等步驟，具體如下：

（1）種群初始化：

DE算法首先要在可行域內(nèi)隨機生成初始種群，個體以D維實數(shù)向量Xi,g表示，其中i表示第i個個體，，NP表示種群規(guī)模，表示進化代數(shù)。具體可按下式(4)隨機生成。

其中rand (0,1) 表示在[0,1]區(qū)間內(nèi)生成隨機數(shù)。

(2)變異:

對于各個體 Xi,g，需要生成對應(yīng)的變異向量 Di,g。能使算法具有較強全局搜索能力的 DE/rand/1 變異算子具體如下所示:

其中 Xr,g、Xr,g、Xr,g分別為從第 g 代種群中隨機選擇的三個個體，且縮放因子，通常

(3)交叉:

目標個體 Xi,g與變異向量Di,g經(jīng)過交叉處理，得到試驗個體 Si,g，使算法能夠在不同區(qū)域中搜索。試驗個體按式(6)生成。

(4)選擇:

假設(shè)需要最小化函數(shù)f，算法需要從試驗個體 Si,g與目標個體 Xi,g中選擇一個進入下一代種群當中，通常基于貪婪策略，具體為。

3、基于差分進化的極大熵聚類算法

研究表明，若V 和U 滿足式(2)與式(3)，則它們必為式(1)的嚴格局部極小 值點，但由于 MEC 是迭代算法，其結(jié)果未必能收斂到目標函數(shù)全局最優(yōu)點上。本 文針對其目標函數(shù)優(yōu)化問題進行研究，利用 DE 算法的全局搜索能力，解決式(1) 的優(yōu)化問題。

本文具體研究的優(yōu)化問題為:

主要是有約束的優(yōu)化問題，由于聚類中心主要分布在數(shù)據(jù)樣本內(nèi)部，因此聚類中 心應(yīng)滿足約束條件:

其中 Xk表示數(shù)據(jù)集X第k維數(shù)據(jù)。由于隸屬度和聚類中心都是實數(shù)值向量，需 要對個體向量進行編碼設(shè)計，本文采用基于聚類中心的編碼方式，具體如下:

其中i =1,2,...,NP。本文采用DE/rand/1變異算子和貪婪選擇策略，直接以式(1)作為適應(yīng)值函數(shù)，結(jié)合隸屬度更新公式(3)，提出基于差分進化的極大熵聚類算 法。

基于差分進化的極大熵聚類算法流程:

輸出:種群中最優(yōu)個體聚類中心與隸屬度矩陣。

setp1:令g=0;

step2:根據(jù)約束條件式(9)，通過式(4)隨機生成初始種群;

step3:對于種群中個體Vi,g，利用式(5)進行變異操作，得到變異向量Di,g;

step4:根據(jù)變異向量Di,g，利用式(6)進行交叉操作，得到試驗個體Si,g;

step5:對于種群中目標個體Vi,g與試驗個體Si,g，利用式(3)分別計算出對應(yīng)的隸屬度矩陣UVi,g和USi,g，并代入目標函數(shù)式(1)計算適應(yīng)值;

step6:根據(jù)所得到的適應(yīng)值，利用式(7)進行選擇操作，并置 g=g+1;

4、實驗及結(jié)果分析

本文在 Iris、Wine、Seed、Breast 數(shù)據(jù)集上進行算法性能實驗，利用 RI、 NMI 指標評估聚類性能，以 MEC 作為對比算法，檢驗本文算法性能。各數(shù)據(jù)集的 具體實驗結(jié)果見表 1 和表 2。

?

結(jié)果表明，相比于MEC算法，本文算法在各數(shù)據(jù)集上，RI指標和NMI指標都略有提升，這說明DE算法應(yīng)用到MEC算法上能夠有效提高優(yōu)化處理，改善聚類效果。

結(jié)語：

本文針對MEC算法易陷入局部最優(yōu)問題，利用DE算法對其目標函數(shù)進行有效優(yōu)化，設(shè)計出一種基于差分進化的極大熵聚類算法。經(jīng)過數(shù)據(jù)實驗檢驗，表明DE算法在一定程度上能更好地優(yōu)化MEC目標函數(shù)。