K進制遺傳算法在聚類問題求解中的應用

韓　海

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

K進制遺傳算法在聚類問題求解中的應用

韓海

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

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

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

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

1　遺傳算法與聚類問題

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

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

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

2　求解聚類問題的步驟

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

圖1　遺傳算法的流程示意

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

C1C2C3C4Cn

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

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

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

（3）記錄最優個體。簡單的求最小值問題。

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

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

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

3　效果分析

對于n個數據的樣本集，通常規定聚成不超過m個類，總是有m

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

圖2　400個仿真數據進行實驗的效果

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

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

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

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

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