文獻綜述--基于自適應(yīng)和演化自適應(yīng)的組合遺傳算法的聚類分析

1、<p>　　本科畢業(yè)設(shè)計文獻綜述</p><p><b>　?。?014屆）</b></p><p>　　論文題目 基于自適應(yīng)和演化自適應(yīng)的</p><p>　　組合遺傳算法的聚類分析</p><p>　　基于自適應(yīng)和演化自適應(yīng)的組合遺傳算法的聚類分析</p><p>　　摘要：本文是

2、關(guān)于基于自適應(yīng)和演化自適應(yīng)的組合遺傳算法的聚類分析的一篇文獻綜述，先介紹項目的由來及其研究意義，然后詳述一下國內(nèi)外相關(guān)研究現(xiàn)狀以及現(xiàn)階段存在的技術(shù)關(guān)鍵及問題，最后進行簡單總結(jié)與預(yù)測未來的發(fā)展趨勢。</p><p>　　關(guān)鍵詞：聚類分析，遺傳算法，自適應(yīng)，演化自適應(yīng)，交叉率，變異率</p><p><b>　　一、引言</b></p><p>　

3、　聚類是數(shù)據(jù)分析領(lǐng)域的常用工具，也是數(shù)據(jù)預(yù)處理的重要手段。聚類分析是依據(jù)數(shù)據(jù)內(nèi)在的結(jié)構(gòu)，將數(shù)據(jù)對象分成類或簇的過程，使得同一簇內(nèi)的數(shù)據(jù)具有高度的相似性，不同簇內(nèi)的數(shù)據(jù)具有很高的相異度[1,30]。針對不同的應(yīng)用需求，已經(jīng)有許多聚類算法被提出。對于大數(shù)據(jù)聚類，劃分聚類已被公認(rèn)為最為重要的一類方法。K-means算法[2]在眾多的劃分聚類方法中因其的簡單高效已被廣泛使用，但是存在對初始聚類中心高度依賴以及易于收斂于局部最優(yōu)值等問題。<

4、/p><p>　　因此，介于聚類分析是一類組合優(yōu)化問題以及劃分聚類是已知的NP-難問題[3]，我們可以使用啟發(fā)式全局優(yōu)化算法來解決聚類問題。而遺傳算法作為一類常見的智能優(yōu)化算法，具有很高的隱含并行性，特別適用于解決復(fù)雜的非線性和多維空間尋優(yōu)問題[4,5,6]。早有一些學(xué)者將遺傳算法用于解聚類分析問題[7,8]。然而，遺傳算法的參數(shù)會影響其性能。首先，特定的問題會有特定的參數(shù)值來決定其是否有找到最優(yōu)解或者次優(yōu)解的能力，

5、再者，這些參數(shù)值存在非線性關(guān)系，所以很難找到他們的最優(yōu)值。因此，如何選擇正確的參數(shù)設(shè)置策略諸如交叉率和變異率是一個研究熱點，也是本論文將解決的難點。</p><p>　　運行前固定參數(shù)和動態(tài)適應(yīng)是現(xiàn)有的兩種重要的遺傳算法參數(shù)設(shè)置機制[9,10,11]。運行前參數(shù)固定方法違背了算法固有的動態(tài)性和自適應(yīng)性，已很少使用。動態(tài)適應(yīng)方法主要分為演化自適應(yīng)控制（Self-adaptive parameter control）

6、和自適應(yīng)控制（Adaptive parameter control）兩種方法。本論文將結(jié)合兩種方法，提出一種新的參數(shù)設(shè)置機制用于解決聚類分析問題。</p><p><b>　　二、研究意義</b></p><p>　　演化自適應(yīng)控制（Self-adaptive parameter control）和自適應(yīng)控制（Adaptive parameter control）是目

7、前應(yīng)用最為廣泛的兩種動態(tài)適應(yīng)參數(shù)設(shè)置機制。演化自適應(yīng)控制通過把遺傳算法的參數(shù)值編碼到個體中，然后利用算法本身來確定合適的參數(shù)值。該機制的工作原理是編碼在個體中合適的參數(shù)值將產(chǎn)生高適宜度個體，這些高適宜度個體將有高幾率生存下去并產(chǎn)生后代，因此延續(xù)了這些合適的參數(shù)值。采用這種參數(shù)設(shè)置機制，現(xiàn)有多種方法來調(diào)節(jié)遺傳算法的變異和/或交叉率。演化自適應(yīng)控制適合于在復(fù)雜的優(yōu)化問題上設(shè)置遺傳算法的交叉和變異率。然而，采用該機制，算法在運行過程中其交叉和

8、變異率往往會過快下降而陷于局部最優(yōu)[12]。自適應(yīng)控制則利用遺傳算法運行過程中的某種反饋信息來自適應(yīng)的改變參數(shù)值。已有學(xué)者提出的方法如下：利用群體適宜度的信息來實時改變算法的變異和/或交叉率；根據(jù)交叉操作對個體的相對改善程度來設(shè)置交叉率；依照父代個體的相似度來調(diào)整交叉操作的參數(shù)值。這些方法已用于聚類分析?；谧赃m應(yīng)控制機制的參數(shù)設(shè)置技術(shù)通常能給出較好的結(jié)果。但對于本項目要研究的劃分聚類問題，其解空間往往非</p><

9、p>　　三、國內(nèi)外研究現(xiàn)狀及難點</p><p>　　遺傳算法作為一種啟發(fā)式優(yōu)化算法，早已被用于聚類分析。Maulik [13]和Murthy[8]最先開創(chuàng)性地使用標(biāo)準(zhǔn)遺傳算法來解決聚類問題。他們在整個遺傳進化過程中使用固定的交叉率和變異率，其結(jié)果表明，簡單遺傳算法比K-means算法在一些人為的和實際的數(shù)據(jù)上得到的結(jié)果較優(yōu)。傅景廣[16]則不采用實數(shù)編碼，而是采用二進制對聚類中心編碼，然后在對個體進行選擇

10、、交叉和編譯，其在兩組模擬數(shù)據(jù)上產(chǎn)生的結(jié)果也明顯優(yōu)于K-means算法。然而，這些方法使用固定的參數(shù)值以至于在算法運行前可能花費很長時間找到這些參數(shù)的最優(yōu)值，更糟糕的是，簡單遺傳算法在理論上已被證明不能在有限的時間內(nèi)找到最優(yōu)解以及存在局部收斂和收斂速度慢等問題。Murthy[8]還根據(jù)進化迭代的代數(shù)去改變變異率，因為變異率是算法能否跳出局部最優(yōu)解的關(guān)鍵因素，在進化早期為了保持種群的多樣性，防止過快收斂，變異率設(shè)置的較大，而在變異后期為了

11、保證最優(yōu)解不易被破壞，變異率又要設(shè)置的較低。所以，需要尋找合適的函數(shù)去調(diào)節(jié)變異率使得其在各個進化階段保持較優(yōu)解，這可能比在整個進化過程中確定一個固定的最優(yōu)變異率值更加困難。</p><p>　　一些學(xué)者為了解決簡單遺傳算法存在的問題，提出了演化自適應(yīng)交叉率和變異率的方法。其中，最著名的是Back[14，15]等提出的在指定條件下運用一個對數(shù)函數(shù)改變變異率的值.雖然他的算法性能優(yōu)于簡單的遺傳算法，但是函數(shù)中的學(xué)習(xí)率

12、這個參數(shù)對結(jié)果影響較大，控制著自適應(yīng)速度。他們認(rèn)為學(xué)習(xí)率越高，那么收斂可能越低，收斂速度越快。因此，學(xué)習(xí)率直接影響力算法的性能，需要進一步研究。此后，Serpell[34]則在著名的旅行商問題上進一步研究了單獨的自適應(yīng)變異算子，單獨的自適應(yīng)變異率以及同時自適應(yīng)變異算子和自適應(yīng)變異率三者的性能。他測試了大量的演化自適應(yīng)遺傳算法，所有的結(jié)果均優(yōu)于簡單遺傳算法，但是在計算交叉率上花的時間較長。具體地，他使用三種不同的方法：正態(tài)分布化，隨機平均

13、化和離散化去演化自適應(yīng)變異率。結(jié)果表明正態(tài)分布化和隨機平均化兩種方法終止搜索過程比離散化早，也就是說他們更不容易跳出局部最優(yōu)解。因為一旦變異率空間進入適應(yīng)度中立值區(qū)域，那么變異率就會有下行壓力。更進一步地，Matthew和Sycara[12]深入的研究了演化自適應(yīng)變異率存在很高的下行壓力的原因：可行解碗狀空間的影響，變異率和選擇壓的關(guān)系</p><p>　　與此同時，自適應(yīng)機制也是改變參數(shù)值的另一種方法，能同時兼

14、顧種群多樣性和收斂速度[18,19]。Ghosh[20], Palmes[21] and Srinivas[22]基于個體的適應(yīng)度值實時地改變交叉率和變異率的值。Srinivas[22]以保證種群多樣性的同時又要有一定的收斂能力為目標(biāo)來改變交叉率和變異率。具體地，在解空間中若種群分布越分散，那么變異率和交叉率的值將減少，相反，若種群陷入局部最優(yōu)解，那么他們的值將增大。種群的收斂程度用種群的平均適應(yīng)度和最大適應(yīng)度來評價。同時，交叉率和變異

15、率的值也依賴于父代的適應(yīng)度值，這樣使得高適應(yīng)度的個體能夠被保留下來不被破壞，而低適應(yīng)度的個體更容易被交叉和變異，產(chǎn)生優(yōu)秀基因。但是，這種算法對于進化初期十分不利。因為在進化初期，一些高適應(yīng)度的個體擁有較低的交叉率和變異率幾乎處于不變的狀態(tài)，而其他個體很快被淘汰，加速了收斂速度，陷入局部最優(yōu)解，出現(xiàn)早熟現(xiàn)象。所以，此后有很多學(xué)者提出了改進策略，如史明霞[23]，陶林波[24]。Kenny[25]則提出了一種基于種群多樣性的自適應(yīng)遺傳算法，

16、并在帶有時間窗的車輛路徑問題上得到很好的結(jié)果。他通過在基因空間內(nèi)</p><p>　　所以，上述演化自適應(yīng)和自適應(yīng)控制機制各有優(yōu)勢和缺陷。如何結(jié)合兩種機制的優(yōu)勢，達(dá)到互補的效果將是本論文的重點和難點。</p><p><b>　　四、總結(jié)與展望</b></p><p>　　聚類分析是數(shù)據(jù)挖掘領(lǐng)域的一個極具挑戰(zhàn)性的研究熱點。其目標(biāo)是將一個數(shù)據(jù)對象

17、集劃分成若干個簇，使同一個簇中的對象具高度同質(zhì)性，不同簇之間的對象具高度異質(zhì)性。 聚類分析在人工智能、機器學(xué)習(xí)、模式識別、 圖像分析、生物信息、決策科學(xué)和商業(yè)等領(lǐng)域具有廣泛應(yīng)用前景和潛在經(jīng)濟價值[31,32]。</p><p>　　聚類分析方法可分為層次聚類和劃分聚類，本論文研究劃分聚類。劃分聚類是一個已知的 NP-難問題。近來，遺傳算法已成為研究劃分聚類的重要方法，其作為具有系統(tǒng)優(yōu)化、適應(yīng)和學(xué)習(xí)的高性能計算和建

18、模方法的研究漸趨成熟。遺傳算法具有進化計算的所有特征，同時又具有自身的特點[33]：（1）搜索過程既不受優(yōu)化函數(shù)的連續(xù)性約束，也沒有優(yōu)化函數(shù)導(dǎo)數(shù)必須存在的要求（2）遺傳算法采用多點搜索或者說是群體搜索，具有很高的隱含并行性，因而可以提高計算速度（3）遺傳算法是一種自適應(yīng)搜索技術(shù)，其選擇交叉變異等運算都是以一種概率方式來進行，從而增加了搜索過程的靈活性，具有較好的全局優(yōu)化求解能力（4）遺傳算法直接以目標(biāo)函數(shù)值為搜索信息，對函數(shù)的性態(tài)無要求

19、，具有較好的普適性和易擴充性（5）遺傳算法更適合大規(guī)模復(fù)雜問題的優(yōu)化。但現(xiàn)有遺傳聚類算法存在諸多問題。首先，這些算法在運行之前通常需要設(shè)置若干參數(shù)。這些參數(shù)的值，比如交叉和變異率，決定著算法的行為和性能。由于這些參數(shù)之間存在非線性關(guān)系并依賴于具體的聚類問題，況且其最佳值往往需要隨算法運行階段的不同而改變，再加上參數(shù)值的多樣性，使得正確設(shè)置這些參數(shù)變得異常困難。因此，如何有效</p><p>　　演化自適應(yīng)機制適合

20、于在復(fù)雜的優(yōu)化問題上設(shè)置遺傳算法的交叉和變異率。然而，采用該機制，算法在運行過程中其交叉和變異率往往過快下降而陷入局部最優(yōu)解。自適應(yīng)機制往往能夠防止遺傳算法陷入局部最優(yōu)（早熟現(xiàn)象），但是定義一個指標(biāo)來全面捕獲算法運行過程中解空間的動態(tài)特征卻十分困難。幸運的是，自適應(yīng)機制能夠阻止過早收斂的優(yōu)勢能彌補演化自適應(yīng)過早陷入局部最優(yōu)的缺點。同時，演化自適應(yīng)能夠削弱自適應(yīng)機制中選取的函數(shù)的影響。因此，雖然演化自適應(yīng)和自適應(yīng)兩種機制各有優(yōu)缺點，但是我

21、們能夠使用他們的優(yōu)勢相互的去彌補他們的劣勢。所以，本論文將結(jié)合兩種機制的優(yōu)勢來設(shè)計有效的參數(shù)設(shè)計方法。</p><p><b>　　參考文獻：</b></p><p>　　Han J, Kamber M. 數(shù)據(jù)挖掘：概念與技術(shù)[M]. 第二版. 機械工業(yè)出版社, 2007.</p><p>　　Hartigan, J.A. and Wong,

22、M.A.: A k-means clustering algorithm. Applied Statistics, 28(1979) 100-110</p><p>　　M.Garey and D.Johnson, Computers and intractability-a guide to the theory of NP-completeness, W.H.Freeman, San Francisco, 1

23、979.</p><p>　　李敏強，寇繼松，林丹，李書全.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2002.3．</p><p>　　L.Davis, Handbook of Genetic Algorithms, van Nostrand Rei－nhold, New York，1991．</p><p>　　劉勇，等． 非數(shù)值并行算法（二） 遺傳算法

24、[M]．北京: 科學(xué)出版社，1995．</p><p>　　Hruschka, Eduardo R., and Nelson FF Ebecken. "A genetic algorithm for cluster analysis." Intelligent Data Analysis 7.1 (2003): 15-25.</p><p>　　Murthy, Chiv

25、ukula A., and Nirmalya Chowdhury. "In search of optimal clusters using genetic algorithms." Pattern Recognition Letters 17.8 (1996): 825-832.</p><p>　　Eiben, Agoston Endre, Robert Hinterding, and Z

26、bigniew Michalewicz. "Parameter control in evolutionary algorithms." Evolutionary Computation, IEEE Transactions on 3.2 (1999): 124-141.</p><p>　　Michalewicz, Zbigniew, and Martin Schmidt. "Pa

27、rameter control in practice." Parameter setting in evolutionary algorithms. Springer Berlin Heidelberg, 2007. 277-294.</p><p>　　De Jong, Kenneth. "Parameter setting in EAs: a 30 year perspective.&q

28、uot;Parameter Setting in Evolutionary Algorithms. Springer Berlin Heidelberg, 2007. 1-18.</p><p>　　Glickman, Matthew R., and Katia Sycara. "Reasons for premature convergence of self-adapting mutation ra

29、tes." Evolutionary Computation, 2000. Proceedings of the 2000 Congress on. Vol. 1. IEEE, 2000.</p><p>　　Maulik, Ujjwal, and Sanghamitra Bandyopadhyay. "Genetic algorithm-based clustering technique.

30、" Pattern recognition 33.9 (2000): 1455-1465.</p><p>　　Bäck, Thomas, and Martin Schütz. "Intelligent mutation rate control in canonical genetic algorithms." Foundations of intelligen

31、t systems. Springer Berlin Heidelberg, 1996. 158-167.</p><p>　　Back, Eiben, “An empirical study on Gas “without parameters”,” Lecture Notes in Computer Science, pp.315-324, 2000.</p><p>　　傅景廣,

32、許剛, 王裕國. 基于遺傳算法的聚類分析[J]. 計算機工程, 2004, 30(4): 122-124.</p><p>　　Kivijärvi, Juha, Pasi Fränti, and Olli Nevalainen. "Self-adaptive genetic algorithm for clustering." Journal of Heuristics 9

33、.2 (2003): 113-129.</p><p>　　Herrera F, Lozano M. Adaptation of genetic algorithm parameters based on fuzzy logic controllers[J]. Genetic Algorithms and Soft Computing, 1996, 8: 95-125.</p><p>　

34、　Islam S M, Das S, Ghosh S, et al. An adaptive differential evolution algorithm with novel mutation and crossover strategies for global numerical optimization[J]. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE

35、Transactions on, 2012, 42(2): 482-500.</p><p>　　Ghosh A, Das S, Chowdhury A, et al. An improved differential evolution algorithm with fitness-based adaptation of the control parameters[J]. Information Scienc

36、es, 2011, 181(18): 3749-3765.</p><p>　　Palmes P P, Hayasaka T, Usui S. Mutation-based genetic neural network[J]. Neural Networks, IEEE Transactions on, 2005, 16(3): 587-600.</p><p>　　Srinivas M,

37、 Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. Systems, Man and Cybernetics, IEEE Transactions on, 1994, 24(4): 656-667.</p><p>　　史明霞, 陶林波, 沈建京. 自適應(yīng)遺傳算法的改進與應(yīng)用[J]. 微計

38、算機應(yīng)用, 2006, 27(4): 405-408.</p><p>　　陶林波, 沈建京, 韓強. 一種解決早熟收斂的自適應(yīng)遺傳算法設(shè)計[J]. 微計算機信息, 2006 (12S): 268-270.</p><p>　　Zhu K Q. A diversity-controlling adaptive genetic algorithm for the vehicle routin

39、g problem with time windows[C]//Tools with Artificial Intelligence, 2003. Proceedings. 15th IEEE International Conference on. IEEE, 2003: 176-183.</p><p>　　McGinley B, Maher J, O'Riordan C, et al. Mainta

40、ining healthy population diversity using adaptive crossover, mutation, and selection[J]. Evolutionary Computation, IEEE Transactions on, 2011, 15(5): 692-714.</p><p>　　Liu Z, Zhou J, Lai S. New adaptive gene

41、tic algorithm based on ranking[C]//Machine Learning and Cybernetics, 2003 International Conference on. IEEE, 2003, 3: 1841-1844.</p><p>　　江中央, 蔡自興, 王勇. 求解全局優(yōu)化問題的混合自適應(yīng)正交遺傳算法[J]. 軟件學(xué)報, 2010, 21(6): 1296-1307.&

42、lt;/p><p>　　Wang J, Tang J, Liu J, et al. Alternative Fuzzy Cluster segmentation of remote sensing images based on Adaptive Genetic Algorithm[J]. Chinese Geographical Science, 2009, 19(1): 83-88.</p><

43、;p>　　Kantardzic, Mehmed. Data mining: concepts, models, methods, and algorithms. John Wiley & Sons, 2011.</p><p>　　Jain, Anil K., M. Narasimha Murty, and Patrick J. Flynn. "Data clustering: a rev

44、iew." ACM computing surveys (CSUR) 31.3 (1999): 264-323.</p><p>　　Jain, Anil K. "Data clustering: 50 years beyond K-means." Pattern Recognition Letters 31.8 (2010): 651-666.</p><p&g

45、t;　　Vose ,Michael D,簡單遺傳算法：基礎(chǔ)和理論[M].MIT Press，Cambridge，MA，1999．</p><p>　　Serpell, Martin, and James E. Smith. "Self-adaptation of mutation operator and probability for permutation representations in ge