陳磊+普運偉

摘要：遺傳算法是一種隨機搜索算法，適用于解決許多復雜的智能優(yōu)化問題。然而，經(jīng)典遺傳算法具有收斂速度慢和易早熟缺陷。為了找到一種普適性高且效果好的改進遺傳算法，解決數(shù)據(jù)聚類問題，提出一種新的遺傳算法改進策略。該策略同時保留父代及交叉產(chǎn)生的個體中的絕大部分精英，用來替換掉變異后同等數(shù)量的最差個體，并且將交叉與變異概率提高到1，這樣不僅能很好地保留住已產(chǎn)生的精英個體，引導算法穩(wěn)定地向最優(yōu)解進化，還可最大限度地使算法獲得開拓新的解空間能力。實驗結果表明，該方法具有較高的聚類準確性和收斂率，平均收斂準確率為94.67%，平均收斂率為100%，且收斂速度較快，是一種適合解決數(shù)據(jù)聚類問題的可行方案。

關鍵詞：改進遺傳算法；精英保存策略；數(shù)據(jù)聚類

DOIDOI：10.11907/rjdk.171997

中圖分類號：TP301

文獻標識碼：A 文章編號：1672-7800（2017）012-0015-04

Abstract：Genetic algorithm is a stochastic search algorithm， which is applied to solving many complex intelligent optimization problems. However， the classical genetic algorithm has disadvantages of slow convergence speed and easy prematurity. In order to find an improved genetic algorithm with high universality and good effect to solve general data clustering problems， this paper proposes a new revised strategy about GA， which retains parts of the elites in the parents and in the individuals after crossover and increases the probability of cross and mutation to 1. Through these strategies， the novel improved GA makes the algorithm maximize the ability of exploiting new solution spaces， and retains the generated elites well. The experimental results show that， the proposed method has higher clustering accuracy and rate of convergence than two recent improved genetic strategies， whose average accuracy rate achieves 94.67% and average rate of convergence is 100%. In addition， the convergence speed of the proposed method is so fast that it can be as a feasible solution to solve data clustering problems.

Key Words：improved genetic algorithm；elitism strategy；data clustering

0 引言

遺傳算法是一種隨機搜索算法，其基本思想源于生物進化論和群體遺傳學，是模擬自然界生物進化過程與機制，求解極值問題的一類自組織、自適應人工智能技術[1-2]。遺傳算法對各種優(yōu)化問題通用性很強，特別是在解決一些傳統(tǒng)數(shù)學方法難以解決的復雜非線性問題時具有明顯優(yōu)勢。因此，在復雜函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調度、圖像識別和機器學習等眾多領域都獲得了成功[3-4]。但是，在實際應用中，傳統(tǒng)遺傳算法顯現(xiàn)出諸多缺點。針對這些問題，學者們提出了許多新的改進方法。如文獻[5]構建了一種小生境遺傳算法，運用分裂型社區(qū)結構發(fā)現(xiàn)算法劃分超級個體關系網(wǎng)來獲得生境，同時提取生境中的共有模式以改善算法效果；文獻[6]則將小生境技術和Nelder-Mead的單一方法有機融合，增強了算法的全局搜索能力。此外，文獻[7]采用基因空間均勻分布策略、自適應交叉和變異算子以及淘汰算子等多種改進策略，構建了一種基于多樣化策略的基因表達式編程算法DS-GEP，提高了種群多樣性，加快了算法收斂速度；文獻[8]將反向傳播神經(jīng)網(wǎng)絡融合進遺傳算法，大大提高了算法搜索到全局最優(yōu)解的概率；文獻[9]提出了一種基于智能體的多目標社會進化算法，結合了遺傳算法與關系網(wǎng)模型優(yōu)點，專門用于解決多目標優(yōu)化問題；文獻[10]提出了一種M精英協(xié)同進化算法，利用遺傳算法中的精英保存思想來增強算法的搜索能力；文獻[11]則設計了一種智能仿生遺傳算法，可以有效改善3種遺傳算子的不足?？偟膩碚f，上述改進遺傳算法主要應用在函數(shù)優(yōu)化、自動控制和圖像處理等方面，專門針對數(shù)據(jù)分類問題的研究則相對較少。

如何從大型數(shù)據(jù)庫中提取出人們感興趣的知識是數(shù)據(jù)挖掘的一個重要內容。將與現(xiàn)實情況相關的各種混亂無序的數(shù)據(jù)變成搜索空間，利用改進遺傳算法隨機、非線性和混沌的特點，在大量的數(shù)據(jù)規(guī)則中去完成搜索，得到需要的數(shù)據(jù)，是數(shù)據(jù)挖掘領域重要的研究方向[12]。聚類是一種無監(jiān)督分類，其本質是在沒有先驗知識的前提下，僅根據(jù)數(shù)據(jù)的相似性將數(shù)據(jù)分成不同類別，是數(shù)據(jù)挖掘技術的一種重要手段[13]。遺傳聚類算法可較好地解決數(shù)據(jù)聚類時的優(yōu)化問題，滿足優(yōu)化目標的多樣性需求[14]。但是，現(xiàn)有的聚類算法存在穩(wěn)定性差、收斂速度慢以及算法設計復雜等問題，無法充分滿足實際應用需求。為了找到一種普適性高且聚類效果好的改進遺傳算法，本文構建了一種新的遺傳算法改進策略。本文方法同時保留父代中的部分精英個體與交叉產(chǎn)生的絕大部分精英個體，將交叉概率與變異概率增加到最大值，以較好地平衡精英保存與解空間開拓能力之間的矛盾。為了驗證算法的可行性和有效性，將所提方法用于5均勻分布數(shù)據(jù)集和IRIS數(shù)據(jù)集聚類，并和新近提出的兩種改進遺傳策略進行對比實驗。結果表明，所提方法與其它兩種方法相比具有較高的聚類準確性和收斂率，且算法收斂速度較快、適應能力強，是一種適合解決數(shù)據(jù)聚類問題的可行方案。

1 實驗方案設計

經(jīng)典遺傳算法步驟[15]：①設置種群數(shù)量N，交叉概率Pc，變異概率Pm；②問題域編碼。將實際問題編碼成解空間，可采用二進制編碼、實數(shù)編碼和符號編碼等；③初始化種群，計算種群內個體相應的適應度值；④執(zhí)行選擇、交叉和變異策略，進行精英保存，得到子代個體；⑤迭代終止條件檢測。若滿足迭代終止條件，輸出結果，否則轉步驟④。

在上述經(jīng)典遺傳算法基礎上，本文構建了一種改進遺傳策略——基于強化型精英保存策略的遺傳算法（方案三），并和基于選擇算子的遺傳算法改進（方案一）和基于改進錦標賽選擇算子的遺傳算法（方案二）進行對比，實驗方案比較如表1所示。

由表1可以看出，方案一在進化初期，采用寬松的選擇機制，因為此時個體分布較為分散，優(yōu)良個體比重相對較??；在進化后期，采用嚴格的選擇機制，以適應此時個體分布比較集中與優(yōu)良個體比重較大的情形。方案二改進了傳統(tǒng)錦標賽選擇算子，使競賽規(guī)模的大小在種群規(guī)模的60%～80%之間，以改善算法效果。

本文提出的方案三改進了傳統(tǒng)的精英保存策略。在該方案中首先設置交叉概率Pc與變異概率Pm為1，采用符號編碼初始化N個個體作為原始父代，并計算每個個體的適應度值，然后執(zhí)行方案二中改進的錦標賽選擇策略與隨機單點交叉操作，將原始父代加上交叉操作后的子代共2N個個體中的1/4優(yōu)秀個體保留下來。最后對交叉操作后N個個體進行隨機單點變異操作，用上一步保留的優(yōu)秀個體替換掉變異后等量的最差個體，完成一次迭代進化過程，得到第一代的子代種群n。以n作為下一代的父代種群，重復執(zhí)行上述操作，迭代到規(guī)定次數(shù)后得到最終進化后的種群n′，找到其中的最優(yōu)個體，解碼輸出結果。

該方案能最大限度地保留住父代與交叉產(chǎn)生的個體中已存在的優(yōu)秀個體，以避免因為將交叉概率與變異概率提高到最大而使算法變成純隨機搜索，并指導算法向最優(yōu)解的進化方向進行，使算法可以穩(wěn)定地收斂到最優(yōu)解附近。同時，將交叉概率與變異概率提高到1，使子代具有較強的開拓解空間能力，加快算法收斂速度，較好地防止了算法因保留過多的精英個體而陷入局部最優(yōu)的情況。

2 實驗結果與數(shù)據(jù)分析

2.1 實驗一：5均勻分布數(shù)據(jù)集

以（150，150）、（650，150）、（850，350）、（650，650）和（250，650）為中心點，在每個中心點附近隨機均勻地生成10個點，每個數(shù)據(jù)包含X與Y兩個坐標值。

采用表1的3種方案對上述5均勻分布數(shù)據(jù)集進行聚類，每一種方案獨立運行100次。種群規(guī)模為50，最大迭代次數(shù)為500。在方案一和方案二中，交叉概率設置為0.9，變異概率設置為0.1，方案二與方案三的競賽規(guī)模設置為種群規(guī)模的60%。在方案三中，交叉概率與變異概率均設置為1，從父代及交叉產(chǎn)生的個體中保留最優(yōu)的個體數(shù)量為25。

表2給出了3種方案的收斂率、收斂準確率和平均收斂代數(shù)的結果對比。其中，收斂率是指成功收斂次數(shù)所占的百分比，收斂準確率是指方案成功收斂時，被準確聚類數(shù)據(jù)占全部測試數(shù)據(jù)的百分比，平均收斂代數(shù)是100次隨機實驗收斂代數(shù)的平均值。同時，某次采用本文方案對5均勻分布數(shù)據(jù)集的聚類結果如圖1所示，某次三種方案的平均收斂代數(shù)對比結果如圖2所示。

由表2可以看出，方案三與方案二的收斂率最高，達到100%，方案一略低，這顯示出基于錦標賽選擇策略的遺傳算法比基于輪盤賭選擇策略的遺傳算法具有更好的穩(wěn)定性。在收斂準確率方面，3種方案的實驗結果分別為99.74%、99.80%和100%，可見，本文提出的方案三具有一定優(yōu)勢。這是因為在本文的設計方案中，強化型精英保留策略能留住進化過程中的大多數(shù)精英個體，使得算法在絕大多數(shù)情況下均能尋找到最優(yōu)解。此外，從圖1可以看出，所有測試數(shù)據(jù)均被正確聚類，顯示出本文方法良好的聚類準確性。在收斂速度上，方案三的平均收斂代數(shù)為41代，比方案一的354代提高了8.63倍，比方案二的203代提高了4.95倍，說明在本文方法中較高的交叉與變異概率使算法能夠更快速地收斂到最優(yōu)解。從圖2的收斂代數(shù)對比情況不難發(fā)現(xiàn)，方案三的收斂曲線較為陡峭，較少出現(xiàn)方案一和方案二中的局部“小平臺”，表明本文方法在保證較快的收斂速度的同時，還具有較強的逃逸局部最優(yōu)能力。

2.2 實驗二：IRIS數(shù)據(jù)集

IRIS數(shù)據(jù)集是由3種不同種類的鳶尾花的各50個樣本組成，每個樣本共4種屬性，分別代表花萼長度、花萼寬度、花瓣長度和花瓣寬度。

該實驗中除了最大迭代次數(shù)調整為900以外，其它參數(shù)均與實驗一相同。表3給出了3種方案在收斂率、收斂準確率和平均收斂代數(shù)上的結果對比，圖3為某次本文方案對IRIS數(shù)據(jù)集的聚類結果，圖4為某次3種方案的平均收斂代數(shù)對比結果。

由表3可以看出，3種方案全部成功收斂，顯示出基于遺傳機制的聚類方法在數(shù)據(jù)聚類問題上的有效性。但在收斂準確率和平均收斂代數(shù)方面，本文提出的方案三效果更好。從圖3可以看出，盡管IRIS數(shù)據(jù)集內部較復雜，但本文方法依然能對絕大部分數(shù)據(jù)進行有效聚類，只有極少數(shù)的幾個數(shù)據(jù)沒有被正確分開。圖4的3種方案平均收斂代數(shù)對比中，方案三具有較為明顯的優(yōu)勢，平均收斂代數(shù)僅為110代，比方案一和方案二分別提高6.71倍和3.58倍，且在進化過程中較少陷入局部最優(yōu)。可見，本文方法具有較好的穩(wěn)健性、較高的準確率和較強的收斂能力。

3 結語

為解決數(shù)據(jù)的自動聚類問題，本文構建了一種基于強化型精英保存策略的改進遺傳算法。該算法能夠保留住算法進化過程中的絕大多數(shù)精英個體，有效指導了算法的進化方向，增強了算法穩(wěn)定性，使得算法收斂到最優(yōu)解的概率顯著提高。本文方案將交叉概率和變異概率提高到最大，最大限度地增強了算法的收斂速度，防止了算法因保留過多精英個體而陷入局部最優(yōu)的情況。實驗結果對比表明，本文方法具有收斂速度快、平均收斂率高和準確性好等優(yōu)點，是一種解決數(shù)據(jù)聚類問題的可行方案。如何進一步增強算法的通用性并用于更復雜的數(shù)據(jù)聚類問題，將是下一步的研究重點。

參考文獻：

[1] 王福林，朱會霞，王吉權，等.遺傳算法的一種改進進化策略[J].生物數(shù)學學報，2015，30（1）：69-74.

[2] 葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計算機應用研究，2008，25（10）：2911-2916.

[3] MANTSWY A H，ABDEL-MAGID Y L，SELIM S Z.Integration genetic algorithm，tabu search，and simulated annealing for the unit commitment problem [J].IEEE Transactions on Power Systems，1999，14（3）：829-836.

[4] MCHALEWICZ Z.Genetic algorithm +data structure=evolution programs[M].New York：Spring-Verlag，1994.

[5] 祝希路，王伯.一種基于社團劃分的小生境遺傳算法[J].控制與決策，2010，25（7）：1113-1116.

[6] WEI LING YUN，ZHAO MEI.A niche hybrid genetic algorithm for global optimization of continuous multimodal functions[J].Applied Mathematics and Computation，2005，160（3）：649-661.

[7] 吳江，李太勇，姜玥，等.基于多樣化進化策略的基因表達式編程算法[J].吉林大學學報：信息科學版，2010，28（4）：396-403.

[8] JAVADI A A，F(xiàn)ARMANI R，TAN T P.A hybrid intelligent genetic algorithm[J].Advanced Engineering Informmatics，2005，19（4）：255-262.

[9] 潘曉英，劉芳，焦李成.基于智能體的多目標社會進化算法[J].軟件學報，2009，20（7）：1703-1713.

[10] 慕彩紅，焦李成，劉逸.求解約束優(yōu)化問題M-精英協(xié)同進化算法[J].西安電子科技大學學報：自然科學版，2010，37（5）：852-861.

[11] LI FA-CHAO，XU LI-DA，JIN CHEN-XIA，et al.Intelligent bionic genetic algotithm （IB-GA） and its convergence[J].Expert Systems with Applications，2011，38（7）：8804-8811.

[12] 陳晶晶.遺傳算法在數(shù)據(jù)挖掘中的應用[J].信息通信，2015（11）：120-121.

[13] 戴陽陽，李朝鋒，徐華.初始點優(yōu)化與參數(shù)自適應的密度聚類算法[J].計算機工程，2016，42（1）：203-209.

[14] 馮少榮，潘煒煒，林子雨.基于改進k-medoids算法的XML文檔聚類[J].計算機工程，2015，41（9），57-62.

[15] 郭廣頌，王燕芳.包含交叉和變異操作的交互式遺傳算法[J].計算機工程，2015，41（3），183-185.

[16] 董妍汝.基于選擇算子的遺傳算法改進[J].辦公自動化，2015 （8）：59-61.

[17] 張琛，詹志輝.遺傳算法選擇策略比較[J].計算機工程與設計，2009，30（23）：5471-5474.

（責任編輯：杜能鋼）