基于聚類分析的差分算法協(xié)作研究

趙新超，陳 敏

?

基于聚類分析的差分算法協(xié)作研究

趙新超，陳 敏

（北京郵電大學(xué) 理學(xué)院，北京 100876）

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

差分算法；聚類分析；層次聚類；群智能優(yōu)化

0 引言

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

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

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

1 標(biāo)準(zhǔn)差分進(jìn)化算法

1.1 差分進(jìn)化算法

其中i= 1, 2,…, NP，NP是種群規(guī)模大小，G是當(dāng)前迭代次數(shù)。

rand(0,1)代表了服從均勻分布的[0, 1]區(qū)間中一個(gè)隨機(jī)數(shù)。

初始化群體之后，差分進(jìn)化算法開(kāi)始進(jìn)行一系列的循環(huán)進(jìn)化操作，包括變異（Mutation）, 交叉（Crossover）和選擇（Selection）。

1.1.1 變異

1.1.2 交叉

1.1.3 選擇

差分進(jìn)化算法的搜索性能取決于這個(gè)算法對(duì)全局探索和局部開(kāi)發(fā)能力的平衡，而這些性質(zhì)在很大程度上取決于對(duì)算法的控制參數(shù)的選擇，包括種群規(guī)模的大小、縮放比例因子的大小和交叉率的大小。而相比于其他進(jìn)化算法，差分進(jìn)化算法所需要調(diào)節(jié)的參數(shù)較少。

2 融入聚類分析算法的差分進(jìn)化算法

2.1 聚類分析算法

聚類分析僅根據(jù)在數(shù)據(jù)中發(fā)現(xiàn)的描述對(duì)象及其關(guān)系的信息，將數(shù)據(jù)對(duì)象分組。其目標(biāo)是，組內(nèi)的對(duì)象相互之間是相似的（相關(guān)的），而不同組中的對(duì)象是不同的（不相關(guān)的）。組內(nèi)的的相似性（同質(zhì)性）越大，組間差別越大，聚類就越好。

2.2 算法思想

聚類分析方法將差分進(jìn)化算法的種群進(jìn)行分布式信息的處理，即將種群劃分為不同的類別，然后取出每個(gè)類別中最富含信息的代表元進(jìn)行運(yùn)算。并利用這些代表元重新構(gòu)建更優(yōu)秀的種群，使得整個(gè)種群逐漸優(yōu)化并最終收斂于全局最優(yōu)解。由于初始化階段，解的分布信息比較分散，信息數(shù)量較為龐大，因此算法開(kāi)始階段就執(zhí)行聚類方法，可能會(huì)產(chǎn)生很多問(wèn)題，例如豐富的種群信息被過(guò)早削減，從而導(dǎo)致整個(gè)種群的提早成熟或提早收斂等,結(jié)果只會(huì)增加收斂到局部最優(yōu)點(diǎn)的概率，而更危險(xiǎn)的是聚類分析可能將具有最優(yōu)解模式、但當(dāng)前適應(yīng)值交叉的解直接排除，導(dǎo)致不能得到問(wèn)題的最終解。因此，聚類分析執(zhí)行時(shí)機(jī)的選擇非常重要，并且聚類分析也需要耗費(fèi)一定的計(jì)算量。從實(shí)際經(jīng)驗(yàn)來(lái)看也沒(méi)有必要進(jìn)行頻繁的執(zhí)行聚類分析，因?yàn)閺囊欢ń嵌瓤淳垲惙治霰旧砭褪且环N加速技術(shù)，聚類分析不但能使聚類后的解群體更好地加快整體的收斂速度，而且能在一定程度上避免種群整體信息的縮減。

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

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

2.3 算法思想

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

Step0. 群體和算法參數(shù)初始化；

Step1. 進(jìn)行和經(jīng)典差分進(jìn)化算法相同的變異操作，交叉操作和選擇操作；

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

Step3. 分別抽取這K個(gè)類別的代表元，計(jì)算這K個(gè)代表元的函數(shù)值，

If K個(gè)函數(shù)值<原來(lái)種群最差的K個(gè)個(gè)體函數(shù)值

利用代表元來(lái)替代原種群中的較差個(gè)體；

End If

Step4. If 迭代次數(shù)<最大迭代次數(shù)

回到Step 1；

Else 輸出最優(yōu)解和最優(yōu)適應(yīng)值。

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

3.1 不同聚類分析方法與差分進(jìn)化算法的協(xié)作性分析

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

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

圖1 不同算法的運(yùn)行效果對(duì)比圖

3.2 算法綜合對(duì)比實(shí)驗(yàn)

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

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

圖2 不同算法的運(yùn)行效果對(duì)比圖

4 結(jié)論

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

[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] 呂銘晟, 沈洪遠(yuǎn), 李志高,等. 多變異策略差分進(jìn)化算法的研究與應(yīng)用[J]. 計(jì)算機(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] 張英杰, 龔中漢. 基于閾值統(tǒng)計(jì)學(xué)習(xí)的差分進(jìn)化引力搜索算法[J]. 計(jì)算機(jī)研究與發(fā)展, 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. 數(shù)據(jù)挖掘?qū)д? 完整版.第2版[M]. 人民郵電出版社, 2011.

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

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

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

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

[16] 顏樂(lè)鳴. 基于工作流的軟件測(cè)試過(guò)程模型研究[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-)，男，教授，主要研究方向：群體智能、運(yùn)籌優(yōu)化及其相關(guān)應(yīng)用；陳敏(1992-)，女，研究生，主要研究方向：遺傳算法及其投資組合優(yōu)化。

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