K進(jìn)制遺傳算法在聚類(lèi)問(wèn)題求解中的應(yīng)用

韓　海

（江漢大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北　武漢　430056）

K進(jìn)制遺傳算法在聚類(lèi)問(wèn)題求解中的應(yīng)用

韓海

（江漢大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北武漢430056）

文章提出了用K進(jìn)制串作為遺傳算法的染色體的方案，給出了用該算法求解聚類(lèi)問(wèn)題的一般性步驟，并對(duì)該方法的適用性進(jìn)行了分析。

聚類(lèi)；遺傳算法；K進(jìn)制串；染色體

盡管計(jì)算機(jī)在重復(fù)計(jì)算方面具有人類(lèi)無(wú)法比擬的速度，但在處理高復(fù)雜度的問(wèn)題時(shí)，窮舉法隨著數(shù)據(jù)量的增長(zhǎng)仍然會(huì)很快失效。有著廣泛應(yīng)用的聚類(lèi)問(wèn)題是典型的高復(fù)雜度問(wèn)題、TSP問(wèn)題［1］、Web文檔聚類(lèi)［2］是其中的典型應(yīng)用。窮舉法可以確保找出問(wèn)題的最優(yōu)解，但在面對(duì)計(jì)算量巨大的聚類(lèi)問(wèn)題時(shí)，窮舉法顯得無(wú)能為力。為此，遺傳算法、蟻群算法、粒子群算法、退火算法等應(yīng)運(yùn)而生，這些算法都是在解空間內(nèi)做部分搜索，在可以接受的時(shí)間內(nèi)找出已搜索到最優(yōu)解，并以此作為原問(wèn)題的解。

1　遺傳算法與聚類(lèi)問(wèn)題

遺傳算法（Genetic Algorithm）是一種通過(guò)模擬生物進(jìn)化過(guò)程搜索最優(yōu)解的方法。它模擬生物進(jìn)化過(guò)程中的自然選擇和遺傳機(jī)理，能較好地在解空間中進(jìn)行搜索。遺傳算法首先需要有一個(gè)由若干個(gè)生物體構(gòu)成的種群，每個(gè)個(gè)體都包含有一組特定的信息，稱(chēng)為染色體。染色體具有相同的結(jié)構(gòu)。遺傳就是由當(dāng)前種群把染色體所包含的信息按一定規(guī)則傳遞給下一代。傳遞規(guī)則既保證了對(duì)當(dāng)前種群的擇優(yōu)，也保證了適應(yīng)性較差的個(gè)體也能有一定的遺傳機(jī)會(huì)。遺傳算法的流程如圖1所示。

聚類(lèi)是根據(jù)數(shù)據(jù)之間的聯(lián)系緊密程度把一個(gè)數(shù)據(jù)集劃分成若干個(gè)子集，每個(gè)子集稱(chēng)為一個(gè)簇，使得在同一簇內(nèi)的數(shù)據(jù)聯(lián)系緊密，而處于不同簇內(nèi)的數(shù)據(jù)之間聯(lián)系疏松。通常用簇內(nèi)距離表示簇內(nèi)數(shù)據(jù)的聚集程度，用簇間距離表示簇與簇之間有一定的差異，并且以這兩個(gè)參數(shù)的某種綜合計(jì)算作為度量一個(gè)劃分優(yōu)劣的指標(biāo)。

設(shè)數(shù)據(jù)集中共有n個(gè)樣本，記作S1，S2，S3，…Sn，規(guī)定最多聚成k個(gè)類(lèi)，如果用窮舉法針對(duì)每一種可能的劃分進(jìn)行比較、篩選，其計(jì)算量是O（kn），因而不得不采取一些措施，用遺傳算法是一個(gè)很好的方案。

2　求解聚類(lèi)問(wèn)題的步驟

遺傳算法通常都采用定長(zhǎng)的2進(jìn)制位串作為染色體，以保證任意位串都是問(wèn)題的一個(gè)解，而最優(yōu)解顯然是其中的一個(gè)或多個(gè)特定的位串。2進(jìn)制在多數(shù)情況下可以簡(jiǎn)化編程，但并不是唯一選擇。針對(duì)聚類(lèi)問(wèn)題，采用K進(jìn)制的染色體更簡(jiǎn)潔。

圖1　遺傳算法的流程示意

不妨把染色體設(shè)計(jì)成一個(gè)長(zhǎng)度為n的K進(jìn)制數(shù)，即：

C1C2C3C4Cn

其中Ci（i=1，2，3，…n）是1位K進(jìn)制數(shù)，在0～k-1取值，表示第i個(gè)樣本歸屬于第Ci號(hào)簇。再令種群的數(shù)目為m，于是，遺傳算法的各個(gè)步驟都有相應(yīng)的進(jìn)行處理方法：

（1）初始化。可創(chuàng)建m×n的數(shù)組，記作W，并把數(shù)組每個(gè)元素賦值為一個(gè)0到k-1之間的隨機(jī)值。以W［i］［j］表示第i號(hào)染色體第j個(gè)位置的值，設(shè)該值為x，則表示按照第i號(hào)染色體劃分子集時(shí)第j號(hào)樣本應(yīng)歸屬于x簇。

其中ni是第i個(gè)簇中的樣本個(gè)數(shù)，X（i）表示第i簇中的一個(gè)樣本，簇的中心之間的距離。一個(gè)個(gè)體的適應(yīng)度是各個(gè)簇的是第i個(gè)簇的中心，｜X（i）-X（j）｜表示第i個(gè)簇與第j個(gè)除以再求和。

（3）記錄最優(yōu)個(gè)體。簡(jiǎn)單的求最小值問(wèn)題。

（4）挑選較優(yōu)個(gè)體。這是生成下一代種群的第一步。挑選的方法較多，但總的原則都是令適應(yīng)度較好的個(gè)體優(yōu)先被選中。不妨先將種群中的m個(gè)個(gè)體按適應(yīng)度排序，對(duì)適應(yīng)度好的個(gè)體賦以較大的權(quán)值，經(jīng)實(shí)驗(yàn)，可以令第i個(gè)個(gè)體的權(quán)值為（m-i）^2。然后做m次循環(huán)，每次產(chǎn)生一個(gè)m^2以?xún)?nèi)的隨機(jī)數(shù)x，對(duì)（m-i）^2>=x求最大i值，即本次循環(huán)選中的是第i個(gè)個(gè)體。

（5）交叉與變異。設(shè)置一個(gè)固定值Ta，0<=Ta<=m，針對(duì)前Ta個(gè)個(gè)體以?xún)蓛膳鋵?duì)的方式進(jìn)行染色體交叉，以一個(gè)隨機(jī)的位置為界，兩個(gè)染色體交換后一半；再設(shè)置一個(gè)固定值Tb，0

不妨以固定次數(shù)的循環(huán)進(jìn)行控制，不論設(shè)置循環(huán)次數(shù)為多少，循環(huán)終止時(shí)都可以得到一個(gè)本次搜索的最優(yōu)解。遺傳算法本身決定了找到的是一個(gè)比較好的解，但不保證是最優(yōu)解。

3　效果分析

對(duì)于n個(gè)數(shù)據(jù)的樣本集，通常規(guī)定聚成不超過(guò)m個(gè)類(lèi)，總是有m

在一臺(tái)主頻為3.4G的普通個(gè)人電腦上以VC環(huán)境編程實(shí)現(xiàn)上述算法，可以在以秒計(jì)的時(shí)間內(nèi)解決數(shù)百個(gè)樣本、數(shù)千次循環(huán)的聚類(lèi)問(wèn)題。如圖2所示，是以400個(gè)仿真數(shù)據(jù)進(jìn)行實(shí)驗(yàn)的效果。

圖2　400個(gè)仿真數(shù)據(jù)進(jìn)行實(shí)驗(yàn)的效果

當(dāng)然，用上述算法求解聚類(lèi)問(wèn)題時(shí)，隨著樣本數(shù)n的增加，不得不減少循環(huán)次數(shù)p，否則其計(jì)算量仍然是單臺(tái)計(jì)算機(jī)無(wú)法勝任的。不過(guò)，該算法的特點(diǎn)決定了可以考慮用多核并行的方式求解規(guī)模稍大一點(diǎn)的聚類(lèi)問(wèn)題。

［1］張雁翔，祁育仙.改進(jìn)遺傳算法求解TSP［J］.山西電子技術(shù)（應(yīng)用實(shí)踐），2016（1）：28-30.

［2］馬艷英.基于遺傳算法的Web文檔聚類(lèi)算法［J］.現(xiàn)代電子技術(shù)，2016（1）：148-152.

［3］左倪娜.基于改進(jìn)遺傳算法的K-means聚類(lèi)方法［J］.軟件導(dǎo)刊，2016（4）：32-34.

［4］李芳，趙天洋.遺傳算法理論及其應(yīng)用進(jìn)展探析［J］.技術(shù)與市場(chǎng)，2016（1）：87.

Application of K binary genetic algorithm in solving clustering problem

Han Hai
（Mathematics and Computer Science of Jianghan University， Wuhan 430056， China）

In this paper， a scheme of using K string string as the chromosome of genetic algorithm was put forward， and the general steps of using this algorithm were given to solve clustering problem， the applicability of the method was analyzed.

clustering； genetic algorithm； K string； chromosome

韓海（1968— ），男，江蘇南京，碩士，副教授；研究方向：圖形圖像與模式識(shí)別。