開題報(bào)告--基于自適應(yīng)和演化自適應(yīng)的組合遺傳算法的聚類分析

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

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

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

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

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

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

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

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

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

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

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

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

13、，k4為(0,1]之間常數(shù)。</p><p>　　c)假如P1m (t+1)<P2m(t+1)，則采用下列公式計(jì)算新的P1m(t+1)：</p><p>　　反之，則計(jì)算新的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)]之間的隨機(jī)數(shù)。</p><p>　　d)以同樣的方式計(jì)算P1c (t+1)，得到的P1m (t+1)和P1c (t+1)值最后更新到個(gè)體中。</p><p>　　另外，項(xiàng)目也可通過自適應(yīng)控制技術(shù)來引導(dǎo)演化自適應(yīng)技術(shù)對(duì)交叉和變異率的變異操作，其實(shí)現(xiàn)過程如下：</p><p>　　對(duì)于遺傳算法中的每個(gè)個(gè)體，在更新編碼

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

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

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

18、ft Windows 7</p><p>　　編程語言：C++、R語言</p><p>　　C++是一種使用非常廣泛的面向?qū)ο缶幊陶Z言，由貝爾實(shí)驗(yàn)室的Bjarne Stroustrup在C的基礎(chǔ)上推出。C++是一種靜態(tài)數(shù)據(jù)類型檢查的、支持多重編程范式的通用程序設(shè)計(jì)語言。它支持過程化程序設(shè)計(jì)、資料抽象化、面向?qū)ο蟪绦蛟O(shè)計(jì)、泛型程序設(shè)計(jì)等多種程序設(shè)計(jì)風(fēng)格[22]。</p><

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

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

21、要來自于美國加州大學(xué)信息與計(jì)算機(jī)科學(xué)系提供的數(shù)據(jù)[24]以及自己用R語言生成的數(shù)據(jù)。</p><p><b>　　實(shí)現(xiàn)步驟</b></p><p>　　編碼：采用實(shí)數(shù)編碼K個(gè)聚類中心，那么對(duì)于N維的解空間，其染色體長(zhǎng)度是N*K。例如2維的數(shù)據(jù)，3個(gè)聚類中心，染色體為(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>　　種群初始化：種群的大小代表著一代有多少個(gè)染色體（個(gè)體）參與運(yùn)算，其值對(duì)遺傳算法的性能也有一定影響，若設(shè)置太小，容易收斂到局部最優(yōu)值，若設(shè)置太大，計(jì)算時(shí)間則很大。本課題在算法運(yùn)行前變確定它的值。</p><p>　　適應(yīng)度計(jì)算：度量群體中各個(gè)體在優(yōu)化計(jì)算中可能達(dá)到或接近最優(yōu)解的優(yōu)良程度。本課題采用歐幾里德距離來度量。<

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

24、lt;/p><p>　　終止條件：設(shè)定迭代次數(shù)或者參看個(gè)體適應(yīng)度之間的差異</p><p>　　四、研究工作總體安排與時(shí)間進(jìn)度</p><p><b>　　參考文獻(xiàn)</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ù)挖掘：概念與技術(shù)[M]. 第二版. 機(jī)械工業(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] 王小平,曹立明.遺傳算法--理論應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,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)化問題的混合自適應(yīng)正交遺傳算法”，軟件學(xué)報(bào)，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: