1996年--外文翻譯譯文--基于遺傳算法的聚類(lèi)分析研究

1、<p><b>　　中文6027字</b></p><p>　　出處：Murthy C A, Chowdhury N. In search of optimal clusters using genetic algorithms[J]. Pattern Recognition Letters, 1996, 17(8): 825-832.</p><p>　　

2、本科畢業(yè)設(shè)計(jì)外文翻譯</p><p><b>　　（2014屆）</b></p><p>　　論文題目 基于遺傳算法的聚類(lèi)分析研究</p><p>　　基于遺傳算法的聚類(lèi)分析研究</p><p>　　CA Murthy, N Chowdhury</p><p>　　摘要：遺傳算法（GAs）通常被描

3、述成能夠在一個(gè)有限樣本函數(shù)值內(nèi)尋找最優(yōu)值的搜索過(guò)程。在本文中，GAs用于嘗試尋找關(guān)于聚類(lèi)問(wèn)題的目標(biāo)函數(shù)值的最優(yōu)值。一些在模擬和實(shí)際數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果展示了這種方法的有效性。K-Means算法是解決聚類(lèi)問(wèn)題的最常用算法之一，對(duì)實(shí)驗(yàn)結(jié)果的分析也展示了本文所提出的算法也能夠改善K-Means算法的輸出結(jié)果。</p><p><b>　　引言</b></p><p>　　聚類(lèi)

4、是觀察數(shù)據(jù)內(nèi)在結(jié)構(gòu)的一種重要的手段。更具體地，聚類(lèi)分析的目標(biāo)（Anderberg, 1973; Devijver and Kittler, 1982; Jain and Dubes, 1988; Tou and Gonzalez, 1974）是將模式特別是高維空間的向量分成簇的過(guò)程，使得同一簇內(nèi)的的數(shù)據(jù)高度同質(zhì)，不同簇內(nèi)的數(shù)據(jù)高度相異。我們假設(shè)給定的模式屬于n維的歐幾里德空間，那么相異度就可以用歐氏距離來(lái)度量。</p>&

5、lt;p>　　我們假定模式集是，其中是第i個(gè)模式向量。聚類(lèi)中心數(shù)是k。如果聚類(lèi)集合用表示，那么需滿(mǎn)足以下幾個(gè)條件：</p><p>　　聚類(lèi)方法大體上可分為兩種：層次聚類(lèi)和非層次聚類(lèi)（Anderberg, 1973）K-means算法是眾多非層次方法中應(yīng)用最為廣泛的算法，其主要在給定的目標(biāo)函數(shù)上尋優(yōu)。它力求尋找到模式和其聚類(lèi)中心歐氏距離之和的最小值，但是這種算法容易收斂到局部最優(yōu)解（Selim and Is

6、mail, 1984）。</p><p>　　復(fù)雜問(wèn)題的全局最優(yōu)解已被證明不能在一個(gè)可行計(jì)算時(shí)間內(nèi)找到（Spath, 1980）。這就使得一些解決內(nèi)在優(yōu)化問(wèn)題的近似方法得以發(fā)展。許多這類(lèi)技術(shù)能夠找到局部最優(yōu)解，卻不一定能夠達(dá)到全局最優(yōu)解（Selim and Ismail, 1984）。在本文中，我們嘗試使用遺傳算法（GAs）尋找聚類(lèi)問(wèn)題的最優(yōu)解。實(shí)驗(yàn)結(jié)果將在一些模擬和實(shí)際的數(shù)據(jù)上呈現(xiàn)。</p>&l

7、t;p>　　第二部分是問(wèn)題描述，第三部分是我們所提的遺傳算法的細(xì)節(jié)，第三部分是實(shí)驗(yàn)結(jié)果與分析。</p><p><b>　　問(wèn)題描述</b></p><p>　　已有一些方法度量如何將給定數(shù)聚集進(jìn)行聚類(lèi)。一種用于聚類(lèi)的原則是盡量減少來(lái)自各個(gè)聚類(lèi)集合的數(shù)據(jù)點(diǎn)的歐氏距離平方之和。數(shù)學(xué)描述如下：</p><p>　　目標(biāo)函數(shù)是非凸的，因此聚類(lèi)問(wèn)

8、題可能找到局部最小值而不是全局最小解（Selim and Ismail, 1984）。事實(shí)上，為了找到最優(yōu)解 ，中所有可能的聚類(lèi)中心都被考慮。因此，考慮到計(jì)算機(jī)的內(nèi)存和速度，在允許的時(shí)間內(nèi)找到問(wèn)題的精確解只有在理論上存在可能。如果通過(guò)枚舉的方式求解，那么有中可能（Anderberg, 1973; Spath, 1980），其中</p><p>　　這明顯地顯示了在有限的計(jì)算時(shí)間內(nèi)采用枚舉法解決現(xiàn)實(shí)生活中絕大多數(shù)的

9、聚類(lèi)問(wèn)題是不可能的。例如，本文所使用的原油數(shù)據(jù)（Johnson and Wichern, 1982）,精確解要求考慮種劃分（）。</p><p>　　因此，啟發(fā)式的估算方法是在尋找一種折中或者在不需要全局最優(yōu)值的情況下考慮局部最優(yōu)解。在本文中我們應(yīng)用遺傳算法尋找給定聚類(lèi)問(wèn)題的目標(biāo)函數(shù)的最優(yōu)解。下一部分將描述算法細(xì)節(jié)。</p><p>　　基于遺傳算法的聚類(lèi)分析</p><

10、;p>　　遺傳算法是基于自然基因系統(tǒng)規(guī)則的啟發(fā)式搜索方法（Goldberg, 1989; Michalewicz, 1992）。遺傳算法為了求解優(yōu)化問(wèn)題中適應(yīng)度函數(shù)的最優(yōu)值來(lái)搜索解空間。不像其他搜索方法，遺傳算法同時(shí)搜索多個(gè)可行解并且計(jì)算他們的適應(yīng)度函數(shù)值。在運(yùn)籌學(xué)，超大規(guī)模集成電路設(shè)計(jì)，模式識(shí)別，圖像處理，機(jī)器學(xué)習(xí)等領(lǐng)域，遺傳算法已經(jīng)在理論和實(shí)際運(yùn)用中被發(fā)現(xiàn)能夠找到復(fù)雜優(yōu)化問(wèn)題的全局近似解（Ankerbrandt et al.,

11、 1990; Belew and Booker, 1991; Bornholdt and Graudenz, 1992）。</p><p>　　當(dāng)用遺傳算法解決優(yōu)化問(wèn)題時(shí)，每一種可行解通常被編碼成一定長(zhǎng)度的二進(jìn)制串（稱(chēng)為染色體）。每一個(gè)串或者染色體被稱(chēng)作是一個(gè)個(gè)體，所有個(gè)體的集合稱(chēng)作種群。遺傳算法從一個(gè)隨即產(chǎn)生的大小為的種群開(kāi)始，并在每一次迭代中，同一大小的種群從當(dāng)代種群中在個(gè)體中使用兩種基本的算子產(chǎn)生。這兩種算

12、子是選擇和重組，并且重組又由交叉和變異算子組成。</p><p>　　在遺傳算法中，目前各個(gè)局部區(qū)域內(nèi)所獲得的最好的可行解將被保留為了算法在整個(gè)進(jìn)化過(guò)程中能夠報(bào)告已發(fā)現(xiàn)的最優(yōu)解。在本文中，我們采用De Jong的精英選擇方式（EGA），使得上一代發(fā)現(xiàn)的最優(yōu)解能夠被保留到當(dāng)代種群中。</p><p>　　接下來(lái)的這一節(jié)將描述用于聚類(lèi)問(wèn)題的遺傳算法的細(xì)節(jié)。首先是編碼和初始化種群，然后是基因算子

13、和其使用方法，最后是遺傳算法的終止條件。</p><p>　　3.1 編碼和初始化種群</p><p>　　編碼。為了解決劃分問(wèn)題，我們必須編碼劃分使得其能夠用遺傳算子來(lái)調(diào)節(jié)。我們將一個(gè)劃分編碼成長(zhǎng)度為的染色體（是數(shù)據(jù)集的數(shù)據(jù)點(diǎn)的數(shù)目）。串中第i個(gè)元素代表被分配到哪個(gè)聚類(lèi)中心。例如，有劃分，那么被編碼成。我們使用這種編碼方式是為了能夠使用標(biāo)準(zhǔn)的單點(diǎn)交叉算子。編碼串中第i個(gè)元素代表數(shù)據(jù)集中第

14、i個(gè)數(shù)據(jù)點(diǎn)所屬的聚類(lèi)中心。因此，每一個(gè)編碼串代表一種可行的聚類(lèi)方式并且適應(yīng)度函數(shù)值是每個(gè)數(shù)據(jù)點(diǎn)到各自聚類(lèi)中心的歐氏距離平方之和。所以，這里的適應(yīng)度函數(shù)就是第2節(jié)所描述的目標(biāo)函數(shù)。</p><p>　　初始化種群。遺傳算法初始種群通常被隨機(jī)的選取。在目前的實(shí)現(xiàn)中，長(zhǎng)度為的編碼串每一位元素被指定范圍為1到的隨機(jī)數(shù)。當(dāng)然，一個(gè)聚類(lèi)中心集合必須包含一個(gè)數(shù)據(jù)點(diǎn)，否則這個(gè)編碼串將是無(wú)效的以此來(lái)避免在無(wú)效的編碼串上浪費(fèi)進(jìn)化時(shí)間

15、。</p><p>　　目前還沒(méi)有如何選擇初始種群大小的方法。在本文中，并且在整個(gè)進(jìn)化過(guò)程中種群的大小保持不變。值得注意的是，如果迭代次數(shù)是無(wú)窮的，那么遺傳算法的精英選擇方式能夠在任意初始種群的情況下提供最優(yōu)值（Bhandari et al., 1996）。</p><p><b>　　3.2 遺傳算子</b></p><p>　　選擇。選擇算

16、子類(lèi)似達(dá)爾文生物進(jìn)化論中的“適者生存，不適者淘汰”的思想。從種群中選擇出來(lái)的染色體組成一個(gè)交配池。個(gè)體被選擇的概率與其適應(yīng)度值成正比（尋找最大值）或者成反比（尋找最小值）。本文所研究的是最小值問(wèn)題，所以被選擇的概率與適應(yīng)度成反比。交配池的大小和種群大小一樣。</p><p>　　交叉。交叉改變兩個(gè)父代的基因信息并且產(chǎn)生下一代的個(gè)體。一對(duì)染色體</p><p>　　從交配池中被隨機(jī)選擇，然后

17、交叉以概率以如下方式進(jìn)行。</p><p>　　從范圍隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)pos，那么染色體和被染色體和代替，其中</p><p>　　交配池中的交叉算子通過(guò)以下方式表現(xiàn)：</p><p>　　從交配池中隨機(jī)選擇對(duì)編碼串，這樣使得交配池中的個(gè)體都直接屬于其中一對(duì)編碼串。</p><p>　　對(duì)于每對(duì)編碼串，隨即產(chǎn)生0到1的隨機(jī)數(shù)，如果那么進(jìn)行交

18、叉，否則不進(jìn)行交叉交叉操作。</p><p>　　通常在遺傳算法中，交叉率被設(shè)置成在的范圍內(nèi)。在本文中是0.8并且每一代的種群大小是6.上述所講的交叉作用在一個(gè)位置，叫做單點(diǎn)交叉算子（Michalewicz, 1992）。</p><p>　　單點(diǎn)交叉算子可能存在一個(gè)問(wèn)題。子代也許只有更少的聚類(lèi)中心。例如，如果我們?cè)诖? 2 2 3 2 1）和（1 3 3 2 2 1）中的第三個(gè)位置點(diǎn)采

19、用單點(diǎn)交叉，那么產(chǎn)生兩個(gè)子代（1 2 2 2 2 1）和（1 3 3 3 2 1）。值得注意的是第一個(gè)子代只有兩個(gè)聚類(lèi)中心而不是三個(gè)。為了避免這個(gè)問(wèn)題，我們同時(shí)使用采樣和替換。換句話(huà)說(shuō)，我們重復(fù)交叉直到產(chǎn)生的子代有個(gè)聚類(lèi)中心或者直到嘗試交叉的次數(shù)到達(dá)（我們限制次數(shù)是100）。如果當(dāng)限制次數(shù)達(dá)到但是還沒(méi)有找到具有個(gè)聚類(lèi)中心的子代，那么就隨機(jī)選取一個(gè)父代直接作為子代。值得注意的是，我們采取的措施在之前的文章也被應(yīng)用（Jones and Be

20、ltramo, 1991）。（另一種有效的檢查串的方法是采樣但不替換。如果最大可嘗試的交叉次數(shù)是，但是一系列無(wú)效的交叉點(diǎn)不得不被保留。）值的注意的是，無(wú)效的染色體擁有更少的聚類(lèi)中心卻擁有更大的適應(yīng)度函數(shù)值，因此它們最終將被驅(qū)除。但是為了能夠減少進(jìn)化時(shí)間的浪費(fèi)和為有效的染色體騰出空間產(chǎn)生更好的有效的下一代，這樣的染色體應(yīng)該盡早從種群中排除。</p><p>　　變異。變異是對(duì)一個(gè)字符偶爾隨機(jī)的改變。在染色體（交叉后

21、產(chǎn)生的）中的每一個(gè)字符，，都有相同的概率遭受變異。值得注意的是，任何染色體都可以從任意指定的染色體中經(jīng)過(guò)變異產(chǎn)生。</p><p>　　當(dāng)然，變異算子也能從理論上產(chǎn)生無(wú)效的后代。因此，如果需要的話(huà)，一個(gè)檢查染色體有效性的相似過(guò)程（如同交叉后）在變異后能被合并。在我們所有的實(shí)驗(yàn)中，變異沒(méi)有產(chǎn)生無(wú)效的染色體，所以也就沒(méi)有必要在變異后檢查染色體的有效性。</p><p>　　變異使得種群增加了多

22、樣性。雖然變異率經(jīng)常是非常低的，但是它卻在進(jìn)化過(guò)程中扮演著重要的角色（Michalewicz, 1992）。變異率通常被設(shè)在區(qū)間，且保持不變。有時(shí)候，它也隨著迭代次數(shù)而變化（Qi and Palmieri, 1994）。我們將考慮變化變異率的值，理由將在下一個(gè)子節(jié)中闡述。</p><p>　　精英策略。精英策略的目的是將上一代最好的個(gè)體直接遺傳至當(dāng)代。通過(guò)以下方式實(shí)現(xiàn)這個(gè)策略：</p><p&

23、gt;　　記錄初始種群中最好的個(gè)體，記作</p><p>　　種群經(jīng)歷選擇，交叉，變異算子后產(chǎn)生新的種群（）</p><p>　　根據(jù)適應(yīng)度值比較中最差的個(gè)體（）和。如果比差，那么用代替</p><p>　　記錄中最好的個(gè)體代替</p><p>　　注意。步驟b,c,d將被重復(fù)執(zhí)行直到終止條件被滿(mǎn)足。如果個(gè)體的適應(yīng)度小于，那么個(gè)體好于。因?yàn)榭?/p>

24、慮的問(wèn)題是求最小值問(wèn)題。</p><p>　　3.3 算法終止條件</p><p>　　從文獻(xiàn)(Davis and Principe, 1991; Goldberg, 1989; Michalewicz, 1992)可得，并不存在確保遺傳算法收斂到最優(yōu)解的終止條件。通常，在遺傳算法中有兩種終止條件被采用。第一種是，設(shè)置一個(gè)固定的迭代次數(shù)并且最好的個(gè)體作為最優(yōu)解。第二種是，在固定的迭代次數(shù)內(nèi)

25、，最好的個(gè)體的適應(yīng)度值并沒(méi)有得到多大的改善，那么終止運(yùn)行，并且最好的個(gè)體作為最優(yōu)解。在實(shí)驗(yàn)中我們采用第一種方式。注意到在所有實(shí)驗(yàn)中種群大小是6。如果有一個(gè)更高的種群大小，那么對(duì)于同一個(gè)搜索空間可能只需要更少的迭代次數(shù)終止算法運(yùn)行。如果種群大小相同，但是搜索空間大小不同，那么終止時(shí)間（基于遺傳算法的聚類(lèi)方法最大的迭代次數(shù)）也將不同（詳見(jiàn)第4部分）。一些關(guān)于遺傳算法精英模型終止時(shí)間理論方面的討論也被討論（Murthy et al., 199

26、6）。</p><p>　　為了獲得最優(yōu)解，我們必須保持種群的多樣性，也就是，要有高的變異率值。另一方面，隨著最優(yōu)解被鄰近，在指定的方向我們只需稍微改變?nèi)旧w。這也就是說(shuō)，變異率應(yīng)該隨著迭代次數(shù)的增大而減少。有時(shí)，在算法的任意階段，為了得到最優(yōu)解，當(dāng)代最好的個(gè)體需要做出很多改變。因此，為了有一個(gè)高效的搜索過(guò)程，變異率的變化應(yīng)該隨著迭代次數(shù)的變化而變化。一些變異率變化的方式在圖1（a-d）中展示。我們將采用圖1（a

27、）的變化函數(shù)來(lái)改變變異率的值。事實(shí)上，我們開(kāi)始設(shè)定變異率的值是0.5，然后它的值隨著一個(gè)階梯函數(shù)而變化直到。那么，變異率的最小值被設(shè)定在。</p><p>　　圖1.在實(shí)驗(yàn)中可采用的變異率隨著迭代次數(shù)可能的變化方式</p><p><b>　　實(shí)驗(yàn)結(jié)果和分析</b></p><p>　　在模擬和實(shí)際的數(shù)據(jù)集上來(lái)評(píng)價(jià)所提算法的有效性。實(shí)驗(yàn)和實(shí)驗(yàn)結(jié)

28、果如下。</p><p>　　實(shí)驗(yàn)1。這個(gè)實(shí)驗(yàn)的目的是確認(rèn)基于遺傳算法的聚類(lèi)方法能否早沒(méi)有搜索整個(gè)可行解的空間的情況下，收斂到最優(yōu)值。為了這個(gè)目的，我們生成三個(gè)數(shù)據(jù)集，每個(gè)包含10個(gè)實(shí)數(shù)范圍內(nèi)隨機(jī)產(chǎn)生的數(shù)據(jù)點(diǎn)。然后，通過(guò)窮舉的方法對(duì)每個(gè)數(shù)據(jù)集計(jì)算有2個(gè)聚類(lèi)中心的目標(biāo)函數(shù)的最優(yōu)值。那么總共要遍歷511個(gè)劃分（）才能得到最優(yōu)解。之后，用上述基于遺傳算法的方法求解三個(gè)數(shù)聚集的最優(yōu)解。最大的迭代次數(shù)被設(shè)置成50。對(duì)于每個(gè)

29、數(shù)據(jù)集，我們都5次隨機(jī)產(chǎn)生初始種群，然后運(yùn)行。表1顯示在絕大多數(shù)情況遺傳算法都能夠在少于20次迭代的情況下找到最優(yōu)解，其中最大迭代次數(shù)是26。注意到，因?yàn)榉N群規(guī)模是6，那么在每次迭代中可測(cè)試6種劃分。所以，為了找到最優(yōu)解，算法需要測(cè)試最多156種劃分。</p><p>　　表1</p><p>　　規(guī)模是10的三個(gè)數(shù)據(jù)集的結(jié)果</p><p&

30、gt;<b>　　表2</b></p><p>　　規(guī)模是50的數(shù)據(jù)集結(jié)果</p><p><b>　　表3</b></p><p>　　在規(guī)模是50的數(shù)據(jù)集上通過(guò)遺傳算法改善K-means算法的輸出結(jié)果的實(shí)驗(yàn)結(jié)果</p><p>　　實(shí)驗(yàn)2。在實(shí)驗(yàn)中，我們隨機(jī)產(chǎn)生擁有4個(gè)聚類(lèi)中心的50個(gè)二維數(shù)據(jù)點(diǎn)

31、。數(shù)據(jù)點(diǎn)到其聚類(lèi)中心的平均值均小于這些數(shù)據(jù)點(diǎn)到其他聚類(lèi)中心的平均值。數(shù)據(jù)點(diǎn)和4個(gè)聚類(lèi)中心在圖2中展示。實(shí)驗(yàn)的目的是檢驗(yàn)基于遺傳算法的方法能否找到與表圖一樣的聚類(lèi)效果。值得注意的是窮舉數(shù)據(jù)集是非常耗時(shí)的（）。</p><p>　　表2展示了產(chǎn)生5次初始種群的實(shí)驗(yàn)結(jié)果。最大的迭代此時(shí)設(shè)置成10000。表2顯示了基于遺傳算法的方法獲得的目標(biāo)函數(shù)值和需要的迭代次數(shù)。在所有的5次實(shí)驗(yàn)中，此方法都得到了滿(mǎn)意的結(jié)果并且需要的迭

32、代次數(shù)都遠(yuǎn)遠(yuǎn)小于窮舉的次數(shù)。</p><p>　　實(shí)驗(yàn)3。因?yàn)镵-means算法可能收斂到局部最優(yōu)，而無(wú)法找到最優(yōu)解（Selim and Ismail, 1984），所以本實(shí)驗(yàn)的目的是能否用遺傳算法來(lái)改善K-means算法得到的結(jié)果（其作為遺傳算法的初始種群中的個(gè)體）。為了達(dá)到這個(gè)目標(biāo)，我們另外人工生成了規(guī)模是50的二維數(shù)據(jù)集。數(shù)據(jù)點(diǎn)從5個(gè)靠的很近的聚類(lèi)中心中隨機(jī)產(chǎn)生。初始產(chǎn)生5個(gè)隨機(jī)的聚類(lèi)中心，然后用K-mea

33、ns算法運(yùn)行直到收斂得到5個(gè)最終的聚類(lèi)中心。然后，這5個(gè)聚類(lèi)中心作為遺傳算法的初始種群的個(gè)體，剩余的個(gè)體隨機(jī)產(chǎn)生。最大的迭代次數(shù)設(shè)置成2000，最終結(jié)果在表3中。由表可得，遺傳算法在最大1026的迭代次數(shù)的情況下，能夠減少K-means算法輸出結(jié)果的目標(biāo)函數(shù)值，從而有改善其結(jié)果的性能。在實(shí)驗(yàn)中，K-means算法收斂的迭代次數(shù)小于等于16次。</p><p>　　圖2. 實(shí)驗(yàn)2中數(shù)據(jù)點(diǎn)分布和聚類(lèi)結(jié)果</p&

34、gt;<p>　　實(shí)驗(yàn)4.此次實(shí)驗(yàn)的目的是比較K-means算法和基于遺傳算法的方法在實(shí)際數(shù)據(jù)集上的效果。原油數(shù)據(jù)（Johnson and Wichern, 1982）有56個(gè)數(shù)據(jù)點(diǎn)，5個(gè)特征和3個(gè)聚類(lèi)中心。K-means算法在數(shù)據(jù)集上運(yùn)行（直到收斂）50次。基于遺傳算法的方法也在隨即產(chǎn)生的初始種群上運(yùn)行50次，其最大迭代次數(shù)是10000。在所有的50次實(shí)驗(yàn)中，遺傳算法找到的目標(biāo)函數(shù)值是278.9651，而K-means算

35、法只有39次達(dá)到這個(gè)值，其中最高的目標(biāo)函數(shù)值是296.4848。表4顯示了K-means的5次運(yùn)行結(jié)果，表5是基于遺傳算法的方法的結(jié)果。在所有的50次運(yùn)行中，K-means算法的迭代次數(shù)均小于等于23次。</p><p>　　值得注意的是，在上述的實(shí)驗(yàn)中每次運(yùn)行的初始種群都是不同的，并且在表1-5中遺傳算法的迭代次數(shù)也能夠收斂（也就是說(shuō)在迭代后適應(yīng)度值都是相同的）。雖然在每次實(shí)驗(yàn)中直到收斂的迭代次數(shù)均小于終止時(shí)間

36、，但是過(guò)早收斂的現(xiàn)象（也就是說(shuō)在某次迭代后，種群中絕大多數(shù)個(gè)體適應(yīng)度值是相同的）沒(méi)有發(fā)現(xiàn)。</p><p><b>　　表4</b></p><p>　　在原油數(shù)據(jù)集上K-means算法的結(jié)果</p><p><b>　　表5</b></p><p>　　在原油數(shù)據(jù)集上基于遺傳算法方法的結(jié)果<

37、/p><p><b>　　總結(jié)和討論</b></p><p>　　本文的目的是觀察在沒(méi)有搜索整個(gè)解空間的情況下，基于遺傳算法的聚類(lèi)問(wèn)題能否找到最優(yōu)解。實(shí)驗(yàn)1的確展示了所提方法的確能夠在沒(méi)有搜索整個(gè)解空間的情況下找到最優(yōu)解。在實(shí)驗(yàn)2中，數(shù)據(jù)點(diǎn)的最優(yōu)聚類(lèi)中心是已知的，基于遺傳算法的方法也能夠找到滿(mǎn)意解。實(shí)驗(yàn)3展示了K-means算法的輸出通過(guò)所提的方法得到進(jìn)一步的改善。在實(shí)驗(yàn)

38、4中，通過(guò)觀察K-means算法和基于遺傳算法的方法在實(shí)際數(shù)據(jù)集上獨(dú)自地運(yùn)行后，我們發(fā)現(xiàn)在所有的50次運(yùn)行中K-means算法得到較高的目標(biāo)函數(shù)值。</p><p>　　值得注意的是，在實(shí)驗(yàn)4中，K-means算法更早的收斂，但是收斂到了局部最優(yōu)解。遺傳算法則不存在這樣的問(wèn)題，因?yàn)閺睦碚撋现v，他都可能從一個(gè)劃分移到任意的其他劃分中。在本文中，基于遺傳算法的方法已經(jīng)被發(fā)現(xiàn)能夠在所有的數(shù)據(jù)集上提供好的結(jié)果。</

39、p><p>　　雖然搜索空間的規(guī)模每個(gè)問(wèn)題都不一樣，我們都設(shè)定種群規(guī)模是6。但是我們根據(jù)搜索空間的規(guī)模使用了不同的終止時(shí)間（最大迭代次數(shù)）。極有可能在給定的搜索空間上終止時(shí)間和種群規(guī)模存在關(guān)系，但這部分理論上的結(jié)論是非常少的（Murthy et al., 1996）。對(duì)于一個(gè)更大的種群規(guī)模，可能只要更小的終止時(shí)間就能找到相似的解。</p><p>　　當(dāng)用遺傳算法解決優(yōu)化問(wèn)題時(shí)，我們可能需要在

40、遺傳算法沖突的兩個(gè)方面找到折中點(diǎn)。一方面，保持種群的多樣性使得運(yùn)行過(guò)程在搜索空間的不同區(qū)域?qū)ふ易顑?yōu)解們。另一方面，當(dāng)遺傳算法運(yùn)行到越加接近最優(yōu)解，當(dāng)前最優(yōu)解的位變化更少。也就是說(shuō)，當(dāng)搜索接近到最優(yōu)解時(shí)，搜索空間需要被限制在當(dāng)前最優(yōu)解的鄰域內(nèi)。如果要保持種群多樣性，那么滿(mǎn)足個(gè)體得到更少的變化這一方面十分困難。反過(guò)來(lái)，如果搜索過(guò)程只照顧到第二個(gè)方面，那么很有可能過(guò)早收斂。在我們的方法中，我們通過(guò)讓圖1的方式改變變異率都照顧到了兩方面。在實(shí)驗(yàn)

41、中，我們使用圖1（a）中的函數(shù)來(lái)改變變異率。所以，在本文中過(guò)早收斂的現(xiàn)象在所有的實(shí)驗(yàn)中都沒(méi)有被發(fā)現(xiàn)。</p><p><b>　　致謝</b></p><p>　　作者感謝D. Bhandari在工作期間內(nèi)的幫助，也真誠(chéng)地感謝審稿人提出的建設(shè)性建議。</p><p><b>　　參考文獻(xiàn)：</b></p>&

42、lt;p>　　Anderberg, M.R. (1973). Cluster Analysis for Application. Academic Press, New York. </p><p>　　Ankerbrandt, C.A., B.P. Unckles and EE. Petry (1990). Scene recognition using genetic algorithms with s

43、emantic nets. Pattern Recognition Lett. 11,285-293. </p><p>　　Belew, R. and L. Booker, Eds. (1991). Proceedings of the Fourth International Conference on Genetic Algorithms. Morgan </p><p>　　Kau

44、fmann, Los Altos, CA. Bhandari, D., C.A. Murthy and S.K. Pal (1996). Genetic algorithm with elitist model and its convergence, lnternat. J. Pattern Recognition Artificial Intelligence, Accepted. </p><p>　　B

45、omholdt, S. and D. Graudenz (1992). Genetic asymptotic and neural networks and structure design by genetic algorithms. Neural Networks 5, 327-334. </p><p>　　Davis, T.E. and C.J. Principe (1991). A simulated

46、annealing like convergence theory for the simple genetic algorithm. In: (Belew and Booker, 1991), 174-181. </p><p>　　Devijver, P.A. and J. Kittler (1982). Pattern Recognition: A Statistical Approach. Prenti

47、ce-Hall International, Heme| Hemstead, Hertfordshire, UK. </p><p>　　Goldberg, D.E. (1989). Genetic Algorithms: Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA. </p><p>　　J

48、ain, A.K. and R.C. Dubes (1988). Algorithms for Clustering Data. Prentice-Hall, Englewood Cliffs, NJ. </p><p>　　Johnson, R.A. and D.W. Wichern (1982). Applied Multivariate Statistical Analysis. Prentice-Hal

49、l, Englewood Cliffs, NJ. </p><p>　　Jones, D.R. and M.A. Beltramo (1991). Solving partitioning problems with genetic algorithms. In: (Belew and Booker, 1991 ), 442-449. </p><p>　　Michalewicz, Z.

50、 (1992). Genetic Algorithms + Data Structure = Evolution Programs. Springer, Berlin. </p><p>　　Murthy, C.A., D. Bhandari and S.K. Pal (1996). Epsilon optimal stopping time for genetic algorithms with Elitist

51、 model. IEEE Trans. Syst. Man Cybernet., Submitted. </p><p>　　Selim, S.Z. and M.A. Ismail (1984). K-means type algorithms: A generalized convergence theorem and characterization of local optimality. IEEE Tra

52、ns. Pattern Anal. Mach. lntell. 6 (1), 81- 87. </p><p>　　Spath, H. (1980). Cluster Analysis Algorithms. Ellis Horwood, Chichester, UK. Tou, </p><p>　　Tou, T.J. and C.R. Gonzalez (1974). Pattern

53、 Recognition Principles. Addision-Wesley, Reading, MA</p><p>　　Qi, Xiaofeng and E Palmieri (1994). Theoretical analysis of evolutionary algorithms with an infinite population size in continuous space, Part