基于強(qiáng)化型精英保存遺傳策略的聚類(lèi)方法研究

陳磊+普運(yùn)偉

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

關(guān)鍵詞：改進(jìn)遺傳算法；精英保存策略；數(shù)據(jù)聚類(lèi)

DOIDOI：10.11907/rjdk.171997

中圖分類(lèi)號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

1 實(shí)驗(yàn)方案設(shè)計(jì)

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

在上述經(jīng)典遺傳算法基礎(chǔ)上，本文構(gòu)建了一種改進(jìn)遺傳策略——基于強(qiáng)化型精英保存策略的遺傳算法（方案三），并和基于選擇算子的遺傳算法改進(jìn)（方案一）和基于改進(jìn)錦標(biāo)賽選擇算子的遺傳算法（方案二）進(jìn)行對(duì)比，實(shí)驗(yàn)方案比較如表1所示。

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

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

該方案能最大限度地保留住父代與交叉產(chǎn)生的個(gè)體中已存在的優(yōu)秀個(gè)體，以避免因?yàn)閷⒔徊娓怕逝c變異概率提高到最大而使算法變成純隨機(jī)搜索，并指導(dǎo)算法向最優(yōu)解的進(jìn)化方向進(jìn)行，使算法可以穩(wěn)定地收斂到最優(yōu)解附近。同時(shí)，將交叉概率與變異概率提高到1，使子代具有較強(qiáng)的開(kāi)拓解空間能力，加快算法收斂速度，較好地防止了算法因保留過(guò)多的精英個(gè)體而陷入局部最優(yōu)的情況。

2 實(shí)驗(yàn)結(jié)果與數(shù)據(jù)分析

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

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

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

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

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

2.2 實(shí)驗(yàn)二：IRIS數(shù)據(jù)集

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

[2] 葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究，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] 祝希路，王伯.一種基于社團(tuán)劃分的小生境遺傳算法[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ìn)化策略的基因表達(dá)式編程算法[J].吉林大學(xué)學(xué)報(bào)：信息科學(xué)版，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] 潘曉英，劉芳，焦李成.基于智能體的多目標(biāo)社會(huì)進(jìn)化算法[J].軟件學(xué)報(bào)，2009，20（7）：1703-1713.

[10] 慕彩紅，焦李成，劉逸.求解約束優(yōu)化問(wèn)題M-精英協(xié)同進(jìn)化算法[J].西安電子科技大學(xué)學(xué)報(bào)：自然科學(xué)版，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ù)挖掘中的應(yīng)用[J].信息通信，2015（11）：120-121.

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

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

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

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

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

（責(zé)任編輯：杜能鋼）