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

1、<p>　　本科畢業(yè)設(shè)計(jì)開(kāi)題報(bào)告</p><p><b>　?。?014屆）</b></p><p>　　論文題目 基于自適應(yīng)和演化自適應(yīng)的</p><p>　　組合遺傳算法的聚類(lèi)分析</p><p>　　基于自適應(yīng)和演化自適應(yīng)的組合遺傳算法的聚類(lèi)分析</p><p>　　一、選題的背

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

3、的聚類(lèi)算法大體上可分為層次聚類(lèi)和劃分聚類(lèi)兩大類(lèi)，前者是將數(shù)據(jù)對(duì)象組成一顆聚類(lèi)樹(shù)，通過(guò)合并或者分裂兩種方式遞歸地產(chǎn)生嵌套聚類(lèi)層次而后者則同時(shí)找到K個(gè)聚類(lèi)中心來(lái)劃分?jǐn)?shù)據(jù)集，并采用迭代重定位技術(shù)改進(jìn)數(shù)據(jù)聚類(lèi)效果。本文主要研究劃分聚類(lèi)并且聚類(lèi)中心數(shù)目作為先驗(yàn)條件，這個(gè)先驗(yàn)條件對(duì)于大數(shù)據(jù)處理是十分必要的。然而，因?yàn)橥ǔ?shù)據(jù)規(guī)模大和數(shù)據(jù)維度高，而且劃分聚類(lèi)作為一種已知的NP-難問(wèn)題，許多已有的聚類(lèi)算法諸如K-means算法根據(jù)其規(guī)則函數(shù)只能找到局部

4、最優(yōu)解，而無(wú)法找到全局最優(yōu)解[4]。</p><p>　　顯然，我們可以通過(guò)啟發(fā)式全局隨機(jī)優(yōu)化算法來(lái)解決此類(lèi)聚類(lèi)問(wèn)題，諸如美國(guó)Michigan大學(xué)的John Holland教授發(fā)明的遺傳算法。其作為一類(lèi)進(jìn)化算法，可在可行解空間內(nèi)隨機(jī)化搜索最優(yōu)解，具有很高的隱含并行性，適用于解決復(fù)雜的非線性和多維空間尋優(yōu)問(wèn)題以及組合優(yōu)化問(wèn)題[5,6,7]。傳統(tǒng)的遺傳算法根據(jù)個(gè)體的適應(yīng)度值來(lái)選擇個(gè)體，然后通過(guò)遺傳算子進(jìn)行交叉、變異，

5、產(chǎn)生新的種群。顯然，遺傳算法已成為一種重要的解決數(shù)據(jù)聚類(lèi)問(wèn)題的工具，然而如何設(shè)置合適的遺傳算法的參數(shù)值將決定遺傳算法的性能[8,9]。其一，因?yàn)樘囟ǖ膯?wè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><

6、;p>　　為了解決參數(shù)設(shè)置問(wèn)題，本文將結(jié)合現(xiàn)有的自適應(yīng)和演化自適應(yīng)參數(shù)設(shè)置兩種方法來(lái)改善遺傳算法的性能，提高聚類(lèi)效果，為實(shí)際工程應(yīng)用提供更加簡(jiǎn)單，易行的手段。</p><p>　　1.2 國(guó)內(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ù)

7、值并且這些參數(shù)值在運(yùn)行過(guò)程中保持不變。但是，已從實(shí)踐和理論上證明了最優(yōu)參數(shù)值的組合不僅在每個(gè)問(wèn)題上不同，而且依據(jù)搜索的狀態(tài)和已搜索到的空間，在進(jìn)化的不同階段，也不盡相同。所以，這顯然是一個(gè)十分耗時(shí)的過(guò)程。更重要的是，這種方法違背了遺傳算法固有的動(dòng)態(tài)和自適應(yīng)特征。</p><p>　　演化自適應(yīng)控制（Self-adaptive parameter control）和自適應(yīng)控制（Adaptive parameter

8、control）是目前應(yīng)用最為廣泛的兩種動(dòng)態(tài)適應(yīng)參數(shù)設(shè)置機(jī)制。演化自適應(yīng)控制通過(guò)把遺傳算法的參數(shù)值編碼到個(gè)體中，與個(gè)體一起經(jīng)歷交叉和變異，利用算法本身來(lái)確定合適的參數(shù)值。該機(jī)制的工作原理是編碼在個(gè)體中合適的參數(shù)值將產(chǎn)生高適宜度個(gè)體，這些高適宜度個(gè)體將有高幾率生存下去并產(chǎn)生后代，因此延續(xù)了這些合適的參數(shù)值。采用這種參數(shù)設(shè)置機(jī)制，現(xiàn)有多種方法來(lái)調(diào)節(jié)遺傳算法的變異和/或交叉率。Back[12,13]通過(guò)對(duì)數(shù)函數(shù)改變個(gè)體的變異率，雖然這種方法在

9、組合優(yōu)化問(wèn)題上比傳統(tǒng)的遺傳算法性能好，但是學(xué)習(xí)率對(duì)自適應(yīng)速度影響大。Juha[14]則將演化自適應(yīng)這種方法應(yīng)用于聚類(lèi)分析。演化自適應(yīng)控制適合于在復(fù)雜的優(yōu)化問(wèn)題上設(shè)置遺傳算法的交叉和變異率。然而，采用該機(jī)制，算法在運(yùn)行過(guò)程中其交叉和變異率往往會(huì)過(guò)快下降而陷于局部最優(yōu)[15]。自適應(yīng)控制則利用遺傳算法運(yùn)行過(guò)程中的某種反饋信息來(lái)自適應(yīng)的改變參數(shù)值。如 Ghosh等[16]，Palmes 等[17]和 Srinivas 等[18]利</p

10、><p>　　二、研究開(kāi)發(fā)的基本內(nèi)容、目標(biāo)，擬解決的主要問(wèn)題或技術(shù)關(guān)鍵</p><p><b>　　2.1 研究目標(biāo)</b></p><p>　　現(xiàn)有基于遺傳算法的聚類(lèi)分析存在參數(shù)設(shè)置難問(wèn)題。本課題將提出結(jié)合演化自適應(yīng)和自適應(yīng)參數(shù)設(shè)置相結(jié)合的技術(shù)來(lái)研究有效參數(shù)設(shè)置方法，以解決參數(shù)設(shè)置問(wèn)題，提高遺傳聚類(lèi)算法的整體性能。項(xiàng)目成果可應(yīng)用于科學(xué)研究和工程設(shè)

11、計(jì)，具有較強(qiáng)的理論價(jià)值和應(yīng)用價(jià)值。</p><p>　　2.2 研究的基本內(nèi)容</p><p>　　項(xiàng)目擬通過(guò)在演化自適應(yīng)控制技術(shù)中結(jié)合自適應(yīng)控制技術(shù)來(lái)克服其過(guò)高下行壓力帶來(lái)的缺陷。具體的，項(xiàng)目擬采用自適應(yīng)控制技術(shù)來(lái)調(diào)節(jié)演化自適應(yīng)技術(shù)得到的交叉和變異率，其實(shí)現(xiàn)過(guò)程如下：</p><p>　　對(duì)于遺傳算法中的每個(gè)個(gè)體，在更新編碼在其中的變異和交叉率時(shí)：</p&g

12、t;<p>　　a）首先，利用下列公式：</p><p>　　分別得到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為

13、群體中最優(yōu)個(gè)體的適宜度，f為個(gè)體適宜度，f＇為交叉操作雙方較優(yōu)個(gè)體的適宜度，k1，k2，k3，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

14、(P1m (t+1)-P2m (t+1))分別產(chǎn)生[0,P2m (t+1)-P1m (t+1)]和[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)目也可通過(guò)自適應(yīng)控制技術(shù)來(lái)引導(dǎo)演化自適應(yīng)技術(shù)對(duì)交叉和變異率的變異操作，其實(shí)現(xiàn)

15、過(guò)程如下：</p><p>　　對(duì)于遺傳算法中的每個(gè)個(gè)體，在更新編碼在其中的變異和交叉率時(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)小于P

16、m(t)。以同樣的方式得到新的交叉率，最后把新的變異和交叉率更新到個(gè)體中。</p><p>　　上述兩種方法通過(guò)自適應(yīng)控制技術(shù)得到的變異、交叉率，分別來(lái)調(diào)節(jié)和引導(dǎo)演化自適應(yīng)技術(shù)的變異、交叉率。初步應(yīng)用結(jié)果顯示，結(jié)合演化自適應(yīng)和自適應(yīng)的參數(shù)設(shè)置方法可有效設(shè)置遺傳聚類(lèi)算法的參數(shù)值，其效果明顯好于單單采用演化自適應(yīng)或自適應(yīng)控制技術(shù)。因此，進(jìn)一步在不同聚類(lèi)問(wèn)題上對(duì)設(shè)計(jì)的參數(shù)設(shè)置方法進(jìn)行分析、比較以及與其它方法的對(duì)比來(lái)確立

17、其優(yōu)勢(shì)，成為本課題的重要內(nèi)容。</p><p>　　2.3 需要解決的技術(shù)難點(diǎn)</p><p>　　(1) 如何結(jié)合演化自適應(yīng)和自適應(yīng)參數(shù)控制機(jī)制來(lái)有效設(shè)置遺傳算法的參數(shù)值，是本課題需要突破的技術(shù)要點(diǎn)和難點(diǎn)。</p><p>　?。?）用C++面向?qū)ο笏枷?，基于GALib庫(kù)編程，尋找相應(yīng)的數(shù)據(jù)集，測(cè)試算法性能</p><p>　　三、研究開(kāi)發(fā)

18、的方法、技術(shù)路線和步驟</p><p>　　系統(tǒng)平臺(tái)：Microsoft Windows 7</p><p>　　編程語(yǔ)言：C++、R語(yǔ)言</p><p>　　C++是一種使用非常廣泛的面向?qū)ο缶幊陶Z(yǔ)言，由貝爾實(shí)驗(yàn)室的Bjarne Stroustrup在C的基礎(chǔ)上推出。C++是一種靜態(tài)數(shù)據(jù)類(lèi)型檢查的、支持多重編程范式的通用程序設(shè)計(jì)語(yǔ)言。它支持過(guò)程化程序設(shè)計(jì)、資料抽象

19、化、面向?qū)ο蟪绦蛟O(shè)計(jì)、泛型程序設(shè)計(jì)等多種程序設(shè)計(jì)風(fēng)格[22]。</p><p>　　R語(yǔ)言主要用于統(tǒng)計(jì)分析、繪圖、數(shù)據(jù)挖掘，是一款強(qiáng)大的統(tǒng)計(jì)分析軟件。</p><p>　　系統(tǒng)開(kāi)發(fā)工具：Microsoft Visual C++ 2008 Express</p><p>　　Microsoft Visual C++是微軟公司的C++集成開(kāi)發(fā)工具，可編輯C語(yǔ)言，C++以

20、及C++/CLI等編程語(yǔ)言，擁有語(yǔ)法高亮，自動(dòng)編譯，高級(jí)除錯(cuò)等功能[23]。</p><p><b>　　GALib庫(kù)</b></p><p>　　GALib是有美國(guó)MIT的Matthew Wall用C++開(kāi)發(fā)的一套免費(fèi)的遺傳算法類(lèi)庫(kù)，包括基因組類(lèi)、適應(yīng)度定標(biāo)方法類(lèi)、進(jìn)化群體類(lèi)、遺傳算法類(lèi)等主要類(lèi)。</p><p><b>　　數(shù)據(jù)來(lái)

21、源</b></p><p>　　本課題用于測(cè)試的數(shù)據(jù)集主要來(lái)自于美國(guó)加州大學(xué)信息與計(jì)算機(jī)科學(xué)系提供的數(shù)據(jù)[24]以及自己用R語(yǔ)言生成的數(shù)據(jù)。</p><p><b>　　實(shí)現(xiàn)步驟</b></p><p>　　編碼：采用實(shí)數(shù)編碼K個(gè)聚類(lèi)中心，那么對(duì)于N維的解空間，其染色體長(zhǎng)度是N*K。例如2維的數(shù)據(jù)，3個(gè)聚類(lèi)中心，染色體為(51.5

22、72.3 18.3 15.4 29.1 30.9),那么聚類(lèi)中心為(51.5,72.3)( 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ì)算：度量群

23、體中各個(gè)體在優(yōu)化計(jì)算中可能達(dá)到或接近最優(yōu)解的優(yōu)良程度。本課題采用歐幾里德距離來(lái)度量。</p><p>　　選擇：從種群中選擇一定數(shù)量的個(gè)體，進(jìn)行基因操作（交叉，變異），產(chǎn)生下一代的個(gè)體，遵循適者生存的自然法則，即適應(yīng)度值越大，有更大的概率被選擇。采用輪盤(pán)賭（roulette wheel selection）選擇方式。</p><p>　　交叉：通過(guò)交換兩個(gè)父代的染色體信息產(chǎn)生兩個(gè)子代個(gè)體。

24、</p><p>　　變異：對(duì)于每個(gè)染色體的基因位都遭受變異操作。</p><p>　　終止條件：設(shè)定迭代次數(shù)或者參看個(gè)體適應(yīng)度之間的差異</p><p>　　四、研究工作總體安排與時(shí)間進(jìn)度</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] Jain, Anil K. &q

25、uot;Data clustering: 50 years beyond K-means." Pattern Recognition Letters 31.8 (2010): 651-666. </p><p>　　[2] Jain, Anil K., M. Narasimha Murty, and Patrick J. Flynn. "Data clustering: a

26、 review." ACM computing surveys (CSUR) 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 i

27、ntractability-a guide to the theory of NP-completeness, W.H.Freeman, San Francisco, 1979.</p><p>　　[5] Weise, Thomas. "Global optimization algorithms–theory and application." Self-Published, (2009)

28、. </p><p>　　[6] Mitchell, Melanie. An introduction to genetic algorithms. MIT press, 1998.</p><p>　　[7] 王小平,曹立明.遺傳算法--理論應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2002.</p><p>　　[8] Maulik, Ujjwal, an

29、d Sanghamitra Bandyopadhyay. "Genetic algorithm-based clustering technique." Pattern recognition 33.9 (2000): 1455-1465.</p><p>　　[9] Eiben, Agoston Endre, Robert Hinterding, and Zbigniew Michalewi

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

31、rol in practice." Parameter setting in evolutionary algorithms. Springer Berlin Heidelberg, 2007. 277-294.</p><p>　　[11] De Jong, Kenneth. "Parameter setting in EAs: a 30 year perspective."Par

32、ameter Setting in Evolutionary Algorithms. Springer Berlin Heidelberg, 2007. 1-18.</p><p>　　[12] Bäck, Thomas, and Martin Schütz. "Intelligent mutation rate control in canonical genetic algori

33、thms." Foundations of intelligent systems. Springer Berlin Heidelberg, 1996. 158-167.</p><p>　　[13] Back, Eiben, “An empirical study on Gas “without parameters”,” Lecture Notes in Computer Science

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

35、</p><p>　　[15] Glickman, Matthew R., and Katia Sycara. "Reasons for premature convergence of self-adapting mutation rates." Evolutionary Computation, 2000. Proceedings of the 2000 Congress on.

36、 Vol. 1. IEEE, 2000.</p><p>　　[16] Ghosh, Arnob, et al. "An improved differential evolution algorithm with fitness-based adaptation of the control parameters." Information Sciences 181.18

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

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

39、: 656-667. </p><p>　　[19] Islam, Sk Minhazul, et al. "An adaptive differential evolution algorithm with novel mutation and crossover strategies for global numerical optimization." Systems, Man

40、, and Cybernetics, Part B: Cybernetics, IEEE Transactions on 42.2 (2012): 482-500. </p><p>　　[20] 江中央，蔡自興，王勇，“求解全局優(yōu)化問(wèn)題的混合自適應(yīng)正交遺傳算法”，軟件學(xué)報(bào)，21卷，6 期，2010.</p><p>　　[21] Wang, Jing, et al. "

41、;Alternative Fuzzy Cluster segmentation of remote sensing images based on Adaptive Genetic Algorithm." Chinese Geographical Science19.1 (2009): 83-88. </p><p>　　[24] MerzC, Murphy P, Aha D. UCI rep