基于聚類分析的差分算法協作研究

趙新超，陳 敏

?

基于聚類分析的差分算法協作研究

趙新超，陳 敏

（北京郵電大學 理學院，北京 100876）

針對差分進化算法存在的收斂速度慢、易陷入局部最優等不足，本文提出一種融入聚類分析的差分進化算法。首先，利用聚類分析方法將差分算法的種群進行聚類分類，抽取代表元個體，利用新的個體來替換原種群中的較差個體，去除種群中的冗余信息將種群進行優化更新，從而使得整個種群可以快速準確地收斂于全局最優解。最后本文利用MATLAB編程模擬仿真，基于CEC2005測試函數庫進行了模擬實驗，結果表明加入了聚類分析替換策略的差分進化算法不僅有效地抑制了早熟收斂、提高了收斂速度，還有著簡潔高效、魯棒性強等特性。

差分算法；聚類分析；層次聚類；群智能優化

0 引言

與傳統的優化算法相比，群智能（Swarm Intelligence）[1]的演化計算方法在近年來得到了學界極大的關注并獲得了廣泛的應用，它與人工智能，特別是遺傳算法[2]和進化策略之間有著極為緊密而特殊的聯系。這種方法模擬了自然環境中各種物種的繁衍、進化、生存等行為或過程，并將這些行為或過程抽象成為一種算法。差分進化算法（DE）[3]作為群智能算法的一種，因為它的簡單實現和高效性，已經成功應用于各種科學和工程等領域。然而，差分進化算法本身存在著收斂速度慢、產生局部最優解等缺陷。此外，差分進化算法中的控制參數，如交叉因子、縮放因子和種群大小的選擇對于算法的最終優化性具有較大的影響。近年來，國內外的相關學者提出了很多改進措施，比如控制參數的改進[4]，變異方向的改進[5]以及混合的差分進化算法[6]等，其中，混合的進化算法成為了最近研究的熱點。

Das[7]等人基于統計學習提出一種混合差分進化粒子群(DEPSO)算法，該算法在迭代過程中根據兩種策略在先前學習代數中的相對成功率來選擇算法的下一步進化策略；Wang[8]等人對經典DE算法中的選擇策略進行改進，融合模擬退火的思想以一定的概率接受較差解；張[9]等人在基本DE算法的選擇過程中融入引力搜索策略來改善實驗個體的質量；適應性調整算法參數和縮放因子的差分進化算法（jDE）[10]。上述改進雖然在一定程度上改善了算法性能，但是早熟收斂問題依然存在,而且一些改進措施還增加了算法的函數評價次數及時間復雜度。聚類分析[11-16]方法將數據集分為不同性質的類別，并可以利用這些聚類分析策略來去除冗余信息，比如降低維數等，也可以利用代表元這個富含信息量的元素進行特定的算法運算。

為進一步提高算法的收斂精度和收斂速度,本文提出了一種新的融合聚類分析算法的差分進化算法，在差分進化算法運行過程中，利用幾種不同的聚類分析方法將整個種群的信息進行分類和抽取，并利用提取的信息優化先前的部分個體，使得原種群擁有更加豐富和代表性的信息和搜索能力，從而使整個算法的綜合性能得到提高，也能減少算法落入局部最優、進入全局最優的可能性。實驗證明加入了不同聚類分析方法的差分進化算法有著簡潔高效、魯棒性強等特性，不僅對通常的單峰和多峰優化問題表現出很強的尋優能力,而且對帶最優解和函數值偏移量的優化問題也較其他算法表現要好。

1 標準差分進化算法

1.1 差分進化算法

其中i= 1, 2,…, NP，NP是種群規模大小，G是當前迭代次數。

rand(0,1)代表了服從均勻分布的[0, 1]區間中一個隨機數。

初始化群體之后，差分進化算法開始進行一系列的循環進化操作，包括變異（Mutation）, 交叉（Crossover）和選擇（Selection）。

1.1.1 變異

1.1.2 交叉

1.1.3 選擇

差分進化算法的搜索性能取決于這個算法對全局探索和局部開發能力的平衡，而這些性質在很大程度上取決于對算法的控制參數的選擇，包括種群規模的大小、縮放比例因子的大小和交叉率的大小。而相比于其他進化算法，差分進化算法所需要調節的參數較少。

2 融入聚類分析算法的差分進化算法

2.1 聚類分析算法

聚類分析僅根據在數據中發現的描述對象及其關系的信息，將數據對象分組。其目標是，組內的對象相互之間是相似的（相關的），而不同組中的對象是不同的（不相關的）。組內的的相似性（同質性）越大，組間差別越大，聚類就越好。

2.2 算法思想

聚類分析方法將差分進化算法的種群進行分布式信息的處理，即將種群劃分為不同的類別，然后取出每個類別中最富含信息的代表元進行運算。并利用這些代表元重新構建更優秀的種群，使得整個種群逐漸優化并最終收斂于全局最優解。由于初始化階段，解的分布信息比較分散，信息數量較為龐大，因此算法開始階段就執行聚類方法，可能會產生很多問題，例如豐富的種群信息被過早削減，從而導致整個種群的提早成熟或提早收斂等,結果只會增加收斂到局部最優點的概率，而更危險的是聚類分析可能將具有最優解模式、但當前適應值交叉的解直接排除，導致不能得到問題的最終解。因此，聚類分析執行時機的選擇非常重要，并且聚類分析也需要耗費一定的計算量。從實際經驗來看也沒有必要進行頻繁的執行聚類分析，因為從一定角度看聚類分析本身就是一種加速技術，聚類分析不但能使聚類后的解群體更好地加快整體的收斂速度，而且能在一定程度上避免種群整體信息的縮減。

得到整個種群聚類分析的結果之后，第一，對于每一個類之中的聚類結果，可以在選出代表元之后利用經典的計算方法來對這個富含信息量的代表元進行快速收斂；第二，如何將新提取出來的代表元個體放回到種群之中。

在本文中，作者先將每一個聚類中心對應的適應值求出，并且根據聚類中心適應值進行排序，然后跟原始種群中最差解向量個體進行比較。如果聚類中心的適應值優于原始種群中的適應值，則使用聚類中心對應的解替代原始種群中較差的那些解，在這種情況下種群規模大小并不會發生改變。這種方法可以被認為是一種比較保守的競爭機制，在不降低整個種群規模的情況下，把最差的部分解進行了篩選淘汰，從而促進整個種群適應性能的提高，而整個種群的規模并不改變，其優點是魯棒性好，減緩算法陷入局部最優。

2.3 算法思想

下面給出基于聚類分析的差分進化算法的基本步驟。

Step0. 群體和算法參數初始化；

Step1. 進行和經典差分進化算法相同的變異操作，交叉操作和選擇操作；

Step2. 迭代一定次數之后，在某一次迭代選擇操作結束之后，對整個種群使用一種特定的聚類分析算法，將整個種群聚集為K個類別；

Step3. 分別抽取這K個類別的代表元，計算這K個代表元的函數值，

If K個函數值<原來種群最差的K個個體函數值

利用代表元來替代原種群中的較差個體；

End If

Step4. If 迭代次數<最大迭代次數

回到Step 1；

Else 輸出最優解和最優適應值。

3 仿真實驗與結果分析

實驗仿真環境為Win8.1，仿真軟件為MATLAB 2016b，為驗證本文提出的混合算法對復雜函數優化的收斂速度與收斂精度等性能，引入若干基準測試函數對算法進行測試，以全面考察算法對于不同類型優化問題的性能。文中基準測試函數實驗參數設置：種群規模設置為100；最大函數評價次數(FES)設為100000；為減少實驗誤差，所有實驗獨立運行50次，取最優適應值的平均結果進行比較。文中對比算法DE/rand/1和本文提出的混合算法基本參數設置為F=0.5, CR=0.95。

3.1 不同聚類分析方法與差分進化算法的協作性分析

本文采用了三種經典的聚類分析方法，分別為：k-means算法，k-medoids算法和層次聚類算法[11]。首先對采用三種聚類分析的差分進化算法和經典差分算法進行了比較，對比結果如下：

從圖1可以看出，基于k-means聚類分析方法的差分進化算法性能相對于另外兩種算法來說較差，并且不很穩定；而基于k-medoids的聚類分析方法在與差分進化算法協作研究中表現出很好的效果，但是相比之下基于層次聚類分析方法的差分進化算法在這三個混合算法中表現是最優秀的，它不但能提高差分算法的收斂速度，而且也不會陷入局部最優。上述仿真實驗和結果分析表明,無論是單模態還是多模態函數優化問題, 層次聚類分析方法的尋優能力通常都優于另外兩種聚類算法，因此本文后續的混合算法都采用層次聚類分析方法與差分進化算法的融合。

圖1 不同算法的運行效果對比圖

3.2 算法綜合對比實驗

為了更好的分析差分-聚類算法的收斂速度、收斂速度和收斂精度等性能，本文將層次聚類分析方法（Clustering）融合標準差分進化（DE）算法形成混合進化算法DEClu。本文采用廣泛采用的標準差分算法DE/rand/1和一種經典的改進DE變形（jDE）的兩種差分進化算法作為比較對象，研究對比分析基于層次聚類的混合差分進化算法與兩種經典的DE算法性能的比較。

從圖2中的進化曲線可以看出在f1，f2，f6和f10函數中，加入了層次聚類的差分進化算法對比于先前的算法本身收斂速度和收斂精度都有所提高，其中基于層次聚類的進化算法對函數f8能非常有效地使標準DE快速收斂并取得全局最優解。結果表明，無論對于廣為采用的基準差分算法， 還是經典的改進版本的差分進化，融入層次聚類 分析方法能使算法的收斂速度和收斂精度有所 提高。

圖2 不同算法的運行效果對比圖

4 結論

本文將層次聚類方法與不同版本的差分算法相結合提出了一種基于聚類的差分協同算法框架。利用擇優的競爭方式使得種群在進化過程中能夠不斷向優秀的解所在方向逐步進化，從而生成更優秀的子種群和提高子代群體的平均適應性能，提高了算法群體在探索新的搜索方向與開發現有的潛力區域之間的平衡。除此之外，聚類分析方法被包裝成模塊化的部分，能夠適用于所有變種的差分進化算法以及其他的進化算法，并且能夠簡單高效地提高相應差分進化算法的性能。通過對測試函數進行模擬實驗，結果分析表明該算法框架具有較好地收斂速度與收斂精度，能有效的避免早熟收斂，跳出局部最優解，并且具有較好的魯棒性。

[1] Beni G, Wang J., Swarm Intelligence in Cellular Robotic Systems[M]. Robots and Biological Systems: Towards a New Bionics. 1993: 703-712.

[2] Holland JH, Adaptation in natural and artificial systems[J]. Ann Arbor, 1975, 6(2): 126-137.

[3] Storn and K. Price, Differential evolution a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, vol.11, no. 4, pp.341-359, 1997.

[4] Pe?u?uri F, Cab C, Carvente O, et al. A Study of the Classical Differential Evolution Control Parameters[J]. Swarm & Evolutionary Computation, 2016, 26: 86-96.

[5] 呂銘晟, 沈洪遠, 李志高,等. 多變異策略差分進化算法的研究與應用[J]. 計算機工程, 2014, 40(12): 146-150.

[6] Cui C Y, Jiao Y C, Zhang L. Synthesis of Some Low Sidelobe Linear Arrays Using Hybrid Differential Evolution Algorithm Integrated with Convex Programming[J]. IEEE Antennas & Wireless Propagation Letters, 2017, 16(99): 2444-2448.

[7] Das S, Abraham A, Konar A. Particle Swarm Optimization and Differential Evolution Algorithms: Technical Analysis, Applications and Hybridization Perspectives[J]. 2010, 116: 1-38.

[8] Wang P C, Qian X, Zhou Y, et al. A novel Differential Evolution algorithm based on simulated annealing[C]// Chinese Control and Decision Conference. 20-10: 7-10.

[9] 張英杰, 龔中漢. 基于閾值統計學習的差分進化引力搜索算法[J]. 計算機研究與發展, 2014, 51(10): 2187-2194.

[10] Brest J, Greiner S, Boskovic B, et al. Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(6): 646-657. 2006.

[11] Pang-NingTan, MichaelSteinbach, VipinKumar. 數據挖掘導論: 完整版.第2版[M]. 人民郵電出版社, 2011.

[12] 左黎斌, 何傲, 王昕, 等. 基于FCM聚類算法的電能表標準裝置監測數據分析與研究[J]. 軟件, 2018, 39(6): 89-95.

[13] 何傲, 左黎斌, 王昕, 等. 基于K-means算法的電能表檢定誤差分析與研究[J]. 軟件, 2018, 39(6): 64-73.

[14] 陳曦斌, 焦明海, 劉昊汧, 等. 移動機器人養老服務路徑規劃的粒子群算法研究[J]. 軟件, 2018, 39(6): 135-138.

[15] 劉露萍, 賈文生. 基于方體剖分和量子免疫粒子群算法的Nash均衡求解[J]. 軟件, 2018, 39(6): 01-03.

[16] 顏樂鳴. 基于工作流的軟件測試過程模型研究[J]. 軟件, 2018, 39(5): 160-165.

Cooperation Research on Differential Evolution Algorithm Based on Clustering Analysis

ZHAO Xin-chao, CHEN Min

(School of Science, Beijing University of Posts and Telecommunications, Beijing 100876)

Aiming at the shortcomings of differential evolution (DE) algorithm, such as slow convergence speed and easy to fall into local optimal solution, a differential evolution algorithm that incorporates cluster analysis is proposed in this paper. Cluster analysis is firstly used to classify populations, and typical new individuals are extracted. New individuals are used to replace poor individuals in the original population and redundant information in the population is removed. The population is optimized and updated so that the entire population can quickly and accurately converge to the global optimum. Finally, this paper does simulation experiments with CEC2005 test function using MATLAB simulation. The results show that differential evolution algorithm with cluster analysis replacing strategy not only effectively inhibits premature convergence, improves the convergence speed, but also has simple, efficient, and robust characteristics.

Differential algorithm; Cluster analysis; Hierarchical clustering; Swarm intelligence optimization

TP315

A

10.3969/j.issn.1003-6970.2018.10.018

趙新超(1976-)，男，教授，主要研究方向：群體智能、運籌優化及其相關應用；陳敏(1992-)，女，研究生，主要研究方向：遺傳算法及其投資組合優化。

趙新超，陳敏. 基于聚類分析的差分算法協作研究[J]. 軟件，2018，39（10）：87-91