韓　海

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

K進制遺傳算法在聚類問題求解中的應(yīng)用

韓海

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

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

聚類；遺傳算法；K進制串；染色體

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

1　遺傳算法與聚類問題

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

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

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

2　求解聚類問題的步驟

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

圖1　遺傳算法的流程示意

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

C1C2C3C4Cn

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

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

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

（3）記錄最優(yōu)個體。簡單的求最小值問題。

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

（5）交叉與變異。設(shè)置一個固定值Ta，0<=Ta<=m，針對前Ta個個體以兩兩配對的方式進行染色體交叉，以一個隨機的位置為界，兩個染色體交換后一半；再設(shè)置一個固定值Tb，0

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

3　效果分析

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

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

圖2　400個仿真數(shù)據(jù)進行實驗的效果

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

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

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

［3］左倪娜.基于改進遺傳算法的K-means聚類方法［J］.軟件導刊，2016（4）：32-34.

［4］李芳，趙天洋.遺傳算法理論及其應(yīng)用進展探析［J］.技術(shù)與市場，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— ），男，江蘇南京，碩士，副教授；研究方向：圖形圖像與模式識別。