開題報告--基于自適應和演化自適應的組合遺傳算法的聚類分析

1、<p>　　本科畢業(yè)設計開題報告</p><p><b>　?。?014屆）</b></p><p>　　論文題目 基于自適應和演化自適應的</p><p>　　組合遺傳算法的聚類分析</p><p>　　一、選題的背景與意義</p><p>　　1.1 研究開發(fā)的目的</p&g

2、t;<p>　　聚類分析作為一種重要的數(shù)據(jù)預處理技術，是數(shù)據(jù)挖掘領域極具挑戰(zhàn)性的一類組合優(yōu)化問題，其目標是將一個數(shù)據(jù)對象集或模式集劃分成若干個簇，使同一個簇中的對象具高度同質性，不同簇之間的對象具高度異質性[1,2,3]?，F(xiàn)有的不同類型的聚類算法已廣泛應用于各類領域，諸如模式識別、機器學習、決策科學、圖像處理、人工智能和商業(yè)等。傳統(tǒng)的聚類算法大體上可分為層次聚類和劃分聚類兩大類，前者是將數(shù)據(jù)對象組成一顆聚類樹，通過合并或者

3、分裂兩種方式遞歸地產(chǎn)生嵌套聚類層次而后者則同時找到K個聚類中心來劃分數(shù)據(jù)集，并采用迭代重定位技術改進數(shù)據(jù)聚類效果。本文主要研究劃分聚類并且聚類中心數(shù)目作為先驗條件，這個先驗條件對于大數(shù)據(jù)處理是十分必要的。然而，因為通常數(shù)據(jù)規(guī)模大和數(shù)據(jù)維度高，而且劃分聚類作為一種已知的NP-難問題，許多已有的聚類算法諸如K-means算法根據(jù)其規(guī)則函數(shù)只能找到局部最優(yōu)解，而無法找到全局最優(yōu)解[4]。</p><p>　　顯然，我們

4、可以通過啟發(fā)式全局隨機優(yōu)化算法來解決此類聚類問題，諸如美國Michigan大學的John Holland教授發(fā)明的遺傳算法。其作為一類進化算法，可在可行解空間內隨機化搜索最優(yōu)解，具有很高的隱含并行性，適用于解決復雜的非線性和多維空間尋優(yōu)問題以及組合優(yōu)化問題[5,6,7]。傳統(tǒng)的遺傳算法根據(jù)個體的適應度值來選擇個體，然后通過遺傳算子進行交叉、變異，產(chǎn)生新的種群。顯然，遺傳算法已成為一種重要的解決數(shù)據(jù)聚類問題的工具，然而如何設置合適的遺傳算

5、法的參數(shù)值將決定遺傳算法的性能[8,9]。其一，因為特定的問題需要特定的參數(shù)值才能找到最優(yōu)解或者近似解，其值也決定了是否能夠高效地找到可行解。其二，因為這些參數(shù)存在非線性關系以至于很難決定參數(shù)的最優(yōu)值。其三，因為在遺傳進化的不同階段，這些參數(shù)值的最優(yōu)值可能不同。因此，如何優(yōu)化如交叉率和變異率這些參數(shù)值將是本文的重點。</p><p>　　為了解決參數(shù)設置問題，本文將結合現(xiàn)有的自適應和演化自適應參數(shù)設置兩種方法來改

6、善遺傳算法的性能，提高聚類效果，為實際工程應用提供更加簡單，易行的手段。</p><p>　　1.2 國內外研究發(fā)展現(xiàn)狀</p><p>　　為遺傳算法設置合適的參數(shù)值是一個研究熱點，現(xiàn)有的參數(shù)設置機制主要由運行前確定和動態(tài)適應兩種方法[9,10,11]。運行前確定是指用戶在算法運行前找到合適的參數(shù)值并且這些參數(shù)值在運行過程中保持不變。但是，已從實踐和理論上證明了最優(yōu)參數(shù)值的組合不僅在每個

7、問題上不同，而且依據(jù)搜索的狀態(tài)和已搜索到的空間，在進化的不同階段，也不盡相同。所以，這顯然是一個十分耗時的過程。更重要的是，這種方法違背了遺傳算法固有的動態(tài)和自適應特征。</p><p>　　演化自適應控制（Self-adaptive parameter control）和自適應控制（Adaptive parameter control）是目前應用最為廣泛的兩種動態(tài)適應參數(shù)設置機制。演化自適應控制通過把遺傳算法的

8、參數(shù)值編碼到個體中，與個體一起經(jīng)歷交叉和變異，利用算法本身來確定合適的參數(shù)值。該機制的工作原理是編碼在個體中合適的參數(shù)值將產(chǎn)生高適宜度個體，這些高適宜度個體將有高幾率生存下去并產(chǎn)生后代，因此延續(xù)了這些合適的參數(shù)值。采用這種參數(shù)設置機制，現(xiàn)有多種方法來調節(jié)遺傳算法的變異和/或交叉率。Back[12,13]通過對數(shù)函數(shù)改變個體的變異率，雖然這種方法在組合優(yōu)化問題上比傳統(tǒng)的遺傳算法性能好，但是學習率對自適應速度影響大。Juha[14]則將演化

9、自適應這種方法應用于聚類分析。演化自適應控制適合于在復雜的優(yōu)化問題上設置遺傳算法的交叉和變異率。然而，采用該機制，算法在運行過程中其交叉和變異率往往會過快下降而陷于局部最優(yōu)[15]。自適應控制則利用遺傳算法運行過程中的某種反饋信息來自適應的改變參數(shù)值。如 Ghosh等[16]，Palmes 等[17]和 Srinivas 等[18]利</p><p>　　二、研究開發(fā)的基本內容、目標，擬解決的主要問題或技術關鍵&

10、lt;/p><p><b>　　2.1 研究目標</b></p><p>　　現(xiàn)有基于遺傳算法的聚類分析存在參數(shù)設置難問題。本課題將提出結合演化自適應和自適應參數(shù)設置相結合的技術來研究有效參數(shù)設置方法，以解決參數(shù)設置問題，提高遺傳聚類算法的整體性能。項目成果可應用于科學研究和工程設計，具有較強的理論價值和應用價值。</p><p>　　2.2 研究

11、的基本內容</p><p>　　項目擬通過在演化自適應控制技術中結合自適應控制技術來克服其過高下行壓力帶來的缺陷。具體的，項目擬采用自適應控制技術來調節(jié)演化自適應技術得到的交叉和變異率，其實現(xiàn)過程如下：</p><p>　　對于遺傳算法中的每個個體，在更新編碼在其中的變異和交叉率時：</p><p>　　a）首先，利用下列公式：</p><p&g

12、t;　　分別得到P1m(t+1)和P1c(t+1)，得到的值不更新到個體中；式中N(0,1)是均值為0標準差為1的正態(tài)分布隨機數(shù)，γ為控制參數(shù)；</p><p>　　b)接著，利用下列公式：</p><p>　　分別得到P2m(t+1)和P2c(t+1)；式中fave為群體的平均適宜度，fmax為群體中最優(yōu)個體的適宜度，f為個體適宜度，f＇為交叉操作雙方較優(yōu)個體的適宜度，k1，k2，k3

13、，k4為(0,1]之間常數(shù)。</p><p>　　c)假如P1m (t+1)<P2m(t+1)，則采用下列公式計算新的P1m(t+1)：</p><p>　　反之，則計算新的P1m(t+1)如下：</p><p>　　式中R(P2m(t+1)-P1m (t+1))和R(P1m (t+1)-P2m (t+1))分別產(chǎn)生[0,P2m (t+1)-P1m (t+1

14、)]和[0,P1m (t+1)-P2m (t+1)]之間的隨機數(shù)。</p><p>　　d)以同樣的方式計算P1c (t+1)，得到的P1m (t+1)和P1c (t+1)值最后更新到個體中。</p><p>　　另外，項目也可通過自適應控制技術來引導演化自適應技術對交叉和變異率的變異操作，其實現(xiàn)過程如下：</p><p>　　對于遺傳算法中的每個個體，在更新編碼

15、在其中的變異和交叉率時。首先，提取編碼在該個體中的變異和交叉率，分別為Pm(t)和Pc(t)。然后，利用公式（3）和（4）分別計算P2m (t+1)和P2c (t+1)。假如Pm(t)<P2m (t+1)，則重復執(zhí)行公式（1），直到新的變異率P1m (t+1)大于Pm(t)。反之，則重復執(zhí)行公式（1），直到新的變異率P1m (t+1)小于Pm(t)。以同樣的方式得到新的交叉率，最后把新的變異和交叉率更新到個體中。</p>

16、;<p>　　上述兩種方法通過自適應控制技術得到的變異、交叉率，分別來調節(jié)和引導演化自適應技術的變異、交叉率。初步應用結果顯示，結合演化自適應和自適應的參數(shù)設置方法可有效設置遺傳聚類算法的參數(shù)值，其效果明顯好于單單采用演化自適應或自適應控制技術。因此，進一步在不同聚類問題上對設計的參數(shù)設置方法進行分析、比較以及與其它方法的對比來確立其優(yōu)勢，成為本課題的重要內容。</p><p>　　2.3 需要解決

17、的技術難點</p><p>　　(1) 如何結合演化自適應和自適應參數(shù)控制機制來有效設置遺傳算法的參數(shù)值，是本課題需要突破的技術要點和難點。</p><p>　　（2）用C++面向對象思想，基于GALib庫編程，尋找相應的數(shù)據(jù)集，測試算法性能</p><p>　　三、研究開發(fā)的方法、技術路線和步驟</p><p>　　系統(tǒng)平臺：Microso

18、ft Windows 7</p><p>　　編程語言：C++、R語言</p><p>　　C++是一種使用非常廣泛的面向對象編程語言，由貝爾實驗室的Bjarne Stroustrup在C的基礎上推出。C++是一種靜態(tài)數(shù)據(jù)類型檢查的、支持多重編程范式的通用程序設計語言。它支持過程化程序設計、資料抽象化、面向對象程序設計、泛型程序設計等多種程序設計風格[22]。</p><

19、;p>　　R語言主要用于統(tǒng)計分析、繪圖、數(shù)據(jù)挖掘，是一款強大的統(tǒng)計分析軟件。</p><p>　　系統(tǒng)開發(fā)工具：Microsoft Visual C++ 2008 Express</p><p>　　Microsoft Visual C++是微軟公司的C++集成開發(fā)工具，可編輯C語言，C++以及C++/CLI等編程語言，擁有語法高亮，自動編譯，高級除錯等功能[23]。</p&g

20、t;<p><b>　　GALib庫</b></p><p>　　GALib是有美國MIT的Matthew Wall用C++開發(fā)的一套免費的遺傳算法類庫，包括基因組類、適應度定標方法類、進化群體類、遺傳算法類等主要類。</p><p><b>　　數(shù)據(jù)來源</b></p><p>　　本課題用于測試的數(shù)據(jù)集主

21、要來自于美國加州大學信息與計算機科學系提供的數(shù)據(jù)[24]以及自己用R語言生成的數(shù)據(jù)。</p><p><b>　　實現(xiàn)步驟</b></p><p>　　編碼：采用實數(shù)編碼K個聚類中心，那么對于N維的解空間，其染色體長度是N*K。例如2維的數(shù)據(jù)，3個聚類中心，染色體為(51.5 72.3 18.3 15.4 29.1 30.9),那么聚類中心為(51.5,72.3)(

22、18.3,15.4)( 29.1,30.9)。</p><p>　　種群初始化：種群的大小代表著一代有多少個染色體（個體）參與運算，其值對遺傳算法的性能也有一定影響，若設置太小，容易收斂到局部最優(yōu)值，若設置太大，計算時間則很大。本課題在算法運行前變確定它的值。</p><p>　　適應度計算：度量群體中各個體在優(yōu)化計算中可能達到或接近最優(yōu)解的優(yōu)良程度。本課題采用歐幾里德距離來度量。<

23、/p><p>　　選擇：從種群中選擇一定數(shù)量的個體，進行基因操作（交叉，變異），產(chǎn)生下一代的個體，遵循適者生存的自然法則，即適應度值越大，有更大的概率被選擇。采用輪盤賭（roulette wheel selection）選擇方式。</p><p>　　交叉：通過交換兩個父代的染色體信息產(chǎn)生兩個子代個體。</p><p>　　變異：對于每個染色體的基因位都遭受變異操作。&

24、lt;/p><p>　　終止條件：設定迭代次數(shù)或者參看個體適應度之間的差異</p><p>　　四、研究工作總體安排與時間進度</p><p><b>　　參考文獻</b></p><p>　　[1] Jain, Anil K. "Data clustering: 50 years beyond K-means.&

25、quot; Pattern Recognition Letters 31.8 (2010): 651-666. </p><p>　　[2] Jain, Anil K., M. Narasimha Murty, and Patrick J. Flynn. "Data clustering: a review." ACM computing surveys (CSU

26、R) 31.3 (1999): 264-323. </p><p>　　[3] Han J, Kamber M. 數(shù)據(jù)挖掘：概念與技術[M]. 第二版. 機械工業(yè)出版社, 2007. </p><p>　　[4] M.Garey and D.Johnson, Computers and intractability-a guide to the theory of NP-comp

27、leteness, W.H.Freeman, San Francisco, 1979.</p><p>　　[5] Weise, Thomas. "Global optimization algorithms–theory and application." Self-Published, (2009). </p><p>　　[6] Mitchell, Melanie

28、. An introduction to genetic algorithms. MIT press, 1998.</p><p>　　[7] 王小平,曹立明.遺傳算法--理論應用與軟件實現(xiàn)[M].西安:西安交通大學出版社,2002.</p><p>　　[8] Maulik, Ujjwal, and Sanghamitra Bandyopadhyay. "Genetic alg

29、orithm-based clustering technique." Pattern recognition 33.9 (2000): 1455-1465.</p><p>　　[9] Eiben, Agoston Endre, Robert Hinterding, and Zbigniew Michalewicz. "Parameter control in evolutionary al

30、gorithms." Evolutionary Computation, IEEE Transactions on 3.2 (1999): 124-141.</p><p>　　[10] Michalewicz, Zbigniew, and Martin Schmidt. "Parameter control in practice." Parameter setting in ev

31、olutionary algorithms. Springer Berlin Heidelberg, 2007. 277-294.</p><p>　　[11] De Jong, Kenneth. "Parameter setting in EAs: a 30 year perspective."Parameter Setting in Evolutionary Algorithms. Spr

32、inger Berlin Heidelberg, 2007. 1-18.</p><p>　　[12] Bäck, Thomas, and Martin Schütz. "Intelligent mutation rate control in canonical genetic algorithms." Foundations of intelligent sy

33、stems. Springer Berlin Heidelberg, 1996. 158-167.</p><p>　　[13] Back, Eiben, “An empirical study on Gas “without parameters”,” Lecture Notes in Computer Science, pp.315-324, 2000.</p><p>　　[14]

34、 Kivijärvi, Juha, Pasi Fränti, and Olli Nevalainen. "Self-adaptive genetic algorithm for clustering." Journal of Heuristics 9.2 (2003): 113-129.</p><p>　　[15] Glickman, Matthew

35、R., and Katia Sycara. "Reasons for premature convergence of self-adapting mutation rates." Evolutionary Computation, 2000. Proceedings of the 2000 Congress on. Vol. 1. IEEE, 2000.</p><p>　　[16

36、] Ghosh, Arnob, et al. "An improved differential evolution algorithm with fitness-based adaptation of the control parameters." Information Sciences 181.18 (2011): 3749-3765.</p><p>　　[17]

37、 Palmes, Paulito P., Taichi Hayasaka, and Shiro Usui. "Mutation-based genetic neural network." Neural Networks, IEEE Transactions on 16.3 (2005): 587-600.</p><p>　　[18] Srinivas, M., and

38、Lalit M. Patnaik. "Adaptive probabilities of crossover and mutation in genetic algorithms." Systems, Man and Cybernetics, IEEE Transactions on 24.4 (1994): 656-667. </p><p>　　[19] Islam,

39、Sk Minhazul, et al. "An adaptive differential evolution algorithm with novel mutation and crossover strategies for global numerical optimization." Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE T

40、ransactions on 42.2 (2012): 482-500. </p><p>　　[20] 江中央，蔡自興，王勇，“求解全局優(yōu)化問題的混合自適應正交遺傳算法”，軟件學報，21卷，6 期，2010.</p><p>　　[21] Wang, Jing, et al. "Alternative Fuzzy Cluster segmentation of rem

41、ote sensing images based on Adaptive Genetic Algorithm." Chinese Geographical Science19.1 (2009): 83-88. </p><p>　　[22] 百度百科.http://baike.baidu.com/view/824.htm</p><p>　　[23] 百度百科.http

42、://baike.baidu.com/view/3450746.htm</p><p>　　[24] MerzC, Murphy P, Aha D. UCI repository of Machine Learning databases. Depantment of Information and Computer Science, University of California, Irvine, http: