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

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

2、關(guān)于基于自適應(yīng)和演化自適應(yīng)的組合遺傳算法的聚類分析的一篇文獻(xiàn)綜述，先介紹項(xiàng)目的由來及其研究意義，然后詳述一下國(guó)內(nèi)外相關(guān)研究現(xiàn)狀以及現(xiàn)階段存在的技術(shù)關(guān)鍵及問題，最后進(jìn)行簡(jiǎn)單總結(jié)與預(yù)測(cè)未來的發(fā)展趨勢(shì)。</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ù)對(duì)象分成類或簇的過程，使得同一簇內(nèi)的數(shù)據(jù)具有高度的相似性，不同簇內(nèi)的數(shù)據(jù)具有很高的相異度[1,30]。針對(duì)不同的應(yīng)用需求，已經(jīng)有許多聚類算法被提出。對(duì)于大數(shù)據(jù)聚類，劃分聚類已被公認(rèn)為最為重要的一類方法。K-means算法[2]在眾多的劃分聚類方法中因其的簡(jiǎn)單高效已被廣泛使用，但是存在對(duì)初始聚類中心高度依賴以及易于收斂于局部最優(yōu)值等問題。<

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、們能夠使用他們的優(yōu)勢(shì)相互的去彌補(bǔ)他們的劣勢(shì)。所以，本論文將結(jié)合兩種機(jī)制的優(yōu)勢(shì)來設(shè)計(jì)有效的參數(shù)設(shè)計(jì)方法。</p><p><b>　　參考文獻(xiàn)：</b></p><p>　　Han J, Kamber M. 數(shù)據(jù)挖掘：概念與技術(shù)[M]. 第二版. 機(jī)械工業(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>　　李敏強(qiáng)，寇繼松，林丹，李書全.遺傳算法的基本理論與應(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、許剛, 王裕國(guó). 基于遺傳算法的聚類分析[J]. 計(jì)算機(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)遺傳算法的改進(jìn)與應(yīng)用[J]. 微計(jì)

38、算機(jī)應(yīng)用, 2006, 27(4): 405-408.</p><p>　　陶林波, 沈建京, 韓強(qiáng). 一種解決早熟收斂的自適應(yīng)遺傳算法設(shè)計(jì)[J]. 微計(jì)算機(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é)報(bào), 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,簡(jiǎn)單遺傳算法：基礎(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