畢業(yè)設(shè)計(jì)-基于自適應(yīng)和演化自適應(yīng)的組合遺傳算法的聚類分析

1、本科畢業(yè)設(shè)計(jì)文獻(xiàn)綜述（2014 屆）論文題目基于自適應(yīng)和演化自適應(yīng)的組合遺傳算法的聚類分析作者姓名 指導(dǎo)教師 學(xué)科（專業(yè)）計(jì)算機(jī)科學(xué)與技術(shù)+自動(dòng)化1001所在學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院提交日期2014年2月基于自適應(yīng)和演化自適應(yīng)的組合遺傳算法的聚類分析摘要：本文是關(guān)于基于自適應(yīng)和演化自適應(yīng)的組合遺傳算法的聚類分析的一篇文 獻(xiàn)綜述，先介紹項(xiàng)目的由來(lái)及其研究意義，然后詳述一下國(guó)內(nèi)外相關(guān)研究現(xiàn)狀以 及現(xiàn)階段存在的技術(shù)關(guān)鍵及問(wèn)題，最后進(jìn)行簡(jiǎn)單總結(jié)與預(yù)測(cè)未來(lái)的發(fā)展趨勢(shì)。關(guān)鍵詞：聚類分析，遺傳算法，自適應(yīng)，演化自適應(yīng)，交叉率，變異率、引言聚類是數(shù)據(jù)分析領(lǐng)域的常用工具，也是數(shù)據(jù)預(yù)處理的重要手段。聚類分析是 依

2、據(jù)數(shù)據(jù)內(nèi)在的結(jié)構(gòu)，將數(shù)據(jù)對(duì)象分成類或簇的過(guò)程，使得同一簇內(nèi)的數(shù)據(jù)具有 高度的相似性，不同簇內(nèi)的數(shù)據(jù)具有很高的相異度1,30。針對(duì)不同的應(yīng)用需求， 已經(jīng)有許多聚類算法被提出。對(duì)于大數(shù)據(jù)聚類，劃分聚類已被公認(rèn)為最為重要的 一類方法。K-means算法在眾多的劃分聚類方法中因其的簡(jiǎn)單高效已被廣泛使 用，但是存在對(duì)初始聚類中心高度依賴以及易于收斂于局部最優(yōu)值等問(wèn)題。因此，介于聚類分析是一類組合優(yōu)化問(wèn)題以及劃分聚類是已知的NP-難問(wèn)題，我們可以使用啟發(fā)式全局優(yōu)化算法來(lái)解決聚類問(wèn)題。而遺傳算法作為一類常 見(jiàn)的智能優(yōu)化算法，具有很高的隱含并行性，特別適用于解決復(fù)雜的非線性和多 維空間尋優(yōu)問(wèn)題4,5,6。早有

3、一些學(xué)者將遺傳算法用于解聚類分析問(wèn)題7,8。然而， 遺傳算法的參數(shù)會(huì)影響其性能。首先，特定的問(wèn)題會(huì)有特定的參數(shù)值來(lái)決定其是 否有找到最優(yōu)解或者次優(yōu)解的能力， 再者，這些參數(shù)值存在非線性關(guān)系，所以很 難找到他們的最優(yōu)值。因此，如何選擇正確的參數(shù)設(shè)置策略諸如交叉率和變異率 是一個(gè)研究熱點(diǎn)，也是本論文將解決的難點(diǎn)。運(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 contro)和自適 應(yīng)控制(Adaptive paramet

4、er control)兩種方法。本論文將結(jié)合兩種方法，提出一 種新的參數(shù)設(shè)置機(jī)制用于解決聚類分析問(wèn)題。、研究意義演化自適應(yīng)控制(Self-adaptive parameter control)和自適應(yīng)控制(Adaptiveparameter contro)是目前應(yīng)用最為廣泛的兩種動(dòng)態(tài)適應(yīng)參數(shù)設(shè)置機(jī)制。演化自適應(yīng)控制通過(guò)把遺傳算法的參數(shù)值編碼到個(gè)體中，然后利用算法本身來(lái)確定合適的參數(shù)值。該機(jī)制的工作原理是編碼在個(gè)體中合適的參數(shù)值將產(chǎn)生高適宜度個(gè)體， 這些高適宜度個(gè)體將有高幾率生存下去并產(chǎn)生后代，因此延續(xù)了這些合適的參數(shù) 值。采用這種參數(shù)設(shè)置機(jī)制，現(xiàn)有多種方法來(lái)調(diào)節(jié)遺傳算法的變異和/或交叉率。演化

5、自適應(yīng)控制適合于在復(fù)雜的優(yōu)化問(wèn)題上設(shè)置遺傳算法的交叉和變異率。然 而，采用該機(jī)制，算法在運(yùn)行過(guò)程中其交叉和變異率往往會(huì)過(guò)快下降而陷于局部 最優(yōu)12。自適應(yīng)控制則利用遺傳算法運(yùn)行過(guò)程中的某種反饋信息來(lái)自適應(yīng)的改 變參數(shù)值。已有學(xué)者提出的方法如下：利用群體適宜度的信息來(lái)實(shí)時(shí)改變算法的 變異和/或交叉率；根據(jù)交叉操作對(duì)個(gè)體的相對(duì)改善程度來(lái)設(shè)置交叉率；依照父 代個(gè)體的相似度來(lái)調(diào)整交叉操作的參數(shù)值。這些方法已用于聚類分析?；谧赃m應(yīng)控制機(jī)制的參數(shù)設(shè)置技術(shù)通常能給出較好的結(jié)果。但對(duì)于本項(xiàng)目要研究的劃分聚類問(wèn)題，其解空間往往非常復(fù)雜，定義一個(gè)指標(biāo)來(lái)全面捕獲算法運(yùn)行過(guò)程中解 空間的動(dòng)態(tài)特征十分困難。上述演化自

6、適應(yīng)控制和自適應(yīng)控制機(jī)制各有優(yōu)勢(shì)和缺 陷。本論文擬結(jié)合這兩種機(jī)制的優(yōu)勢(shì)來(lái)設(shè)計(jì)有效的參數(shù)設(shè)置方法，其成果可為實(shí)際工程應(yīng)用提供更加簡(jiǎn)單，易行的手段。三、國(guó)內(nèi)外研究現(xiàn)狀及難點(diǎn)遺傳算法作為一種啟發(fā)式優(yōu)化算法，早已被用于聚類分析。Maulik 13和Murthy最先開(kāi)創(chuàng)性地使用標(biāo)準(zhǔn)遺傳算法來(lái)解決聚類問(wèn)題。他們?cè)谡麄€(gè)遺傳進(jìn)化過(guò)程中使用固定的交叉率和變異率，其結(jié)果表明，簡(jiǎn)單遺傳算法比K-means算法在一些人為的和實(shí)際的數(shù)據(jù)上得到的結(jié)果較優(yōu)。傅景廣16 則不采用實(shí)數(shù)編碼，而是采用二進(jìn)制對(duì)聚類中心編碼，然后在對(duì)個(gè)體進(jìn)行選擇、交叉和編譯，其在兩 組模擬數(shù)據(jù)上產(chǎn)生的結(jié)果也明顯優(yōu)于 K-means算法。然而，這些方

7、法使用固定 的參數(shù)值以至于在算法運(yùn)行前可能花費(fèi)很長(zhǎng)時(shí)間找到這些參數(shù)的最優(yōu)值，更糟糕的是，簡(jiǎn)單遺傳算法在理論上已被證明不能在有限的時(shí)間內(nèi)找到最優(yōu)解以及存在 局部收斂和收斂速度慢等問(wèn)題。Murthy還根據(jù)進(jìn)化迭代的代數(shù)去改變變異率， 因?yàn)樽儺惵适撬惴芊裉鼍植孔顑?yōu)解的關(guān)鍵因素，在進(jìn)化早期為了保持種群的 多樣性，防止過(guò)快收斂，變異率設(shè)置的較大，而在變異后期為了保證最優(yōu)解不易 被破壞，變異率又要設(shè)置的較低。所以，需要尋找合適的函數(shù)去調(diào)節(jié)變異率使得 其在各個(gè)進(jìn)化階段保持較優(yōu)解，這可能比在整個(gè)進(jìn)化過(guò)程中確定一個(gè)固定的最優(yōu) 變異率值更加困難。一些學(xué)者為了解決簡(jiǎn)單遺傳算法存在的問(wèn)題，提出了演化自適應(yīng)交叉率和

8、變異率的方法。其中，最著名的是 Back，15等提出的在指定條件下運(yùn)用一個(gè)對(duì)數(shù) 函數(shù)改變變異率的值.雖然他的算法性能優(yōu)于簡(jiǎn)單的遺傳算法，但是函數(shù)中的學(xué) 習(xí)率這個(gè)參數(shù)對(duì)結(jié)果影響較大，控制著自適應(yīng)速度。他們認(rèn)為學(xué)習(xí)率越高，那么 收斂可能越低，收斂速度越快。因此，學(xué)習(xí)率直接影響力算法的性能，需要進(jìn)一 步研究。此后，Serpell17則在著名的旅行商問(wèn)題上進(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ī)

9、平均化和離散化去演化自適應(yīng)變異率。結(jié)果表明正態(tài)分布化和隨機(jī)平均化兩種方法終止搜索過(guò)程比離散化早，也就是說(shuō)他們更不容易跳出局部最優(yōu)解。因?yàn)橐坏┳儺惵士臻g進(jìn)入適應(yīng)度中立值區(qū)域，那么變異率就會(huì)有下行壓力。更進(jìn)一步 地, Matthew和Sycard12深入的研究了演化自適應(yīng)變異率存在很高的下行壓力的 原因：可行解碗狀空間的影響，變異率和選擇壓的關(guān)系，隱含的內(nèi)在自適應(yīng)等等。 總之，演化自適應(yīng)控制適合于在復(fù)雜的優(yōu)化問(wèn)題上設(shè)置遺傳算法的交叉和變異 率。因此，這種方法也已經(jīng)被應(yīng)用于聚類分析問(wèn)題上。Kivij? rvi17在聚類問(wèn)題上演化自適應(yīng)地改變了交叉方法，變異率和擾動(dòng)范圍。與此同時(shí)，自適應(yīng)機(jī)制也是改變參

10、數(shù)值的另一種方法，能同時(shí)兼顧種群多樣性和收斂速度18,19。Ghosh20, PalmeS21 and Srinivas22基于個(gè)體的適應(yīng)度值實(shí)時(shí) 地改變交叉率和變異率的值。Srin ivas22以保證種群多樣性的同時(shí)又要有一定的 收斂能力為目標(biāo)來(lái)改變交叉率和變異率。具體地，在解空間中若種群分布越分散， 那么變異率和交叉率的值將減少，相反，若種群陷入局部最優(yōu)解，那么他們的值 將增大。種群的收斂程度用種群的平均適應(yīng)度和最大適應(yīng)度來(lái)評(píng)價(jià)。同時(shí)，交叉率和變異率的值也依賴于父代的適應(yīng)度值，這樣使得高適應(yīng)度的個(gè)體能夠被保留 下來(lái)不被破壞，而低適應(yīng)度的個(gè)體更容易被交叉和變異，產(chǎn)生優(yōu)秀基因。但是，這種算法對(duì)

11、于進(jìn)化初期十分不利。因?yàn)樵谶M(jìn)化初期，一些高適應(yīng)度的個(gè)體擁有較 低的交叉率和變異率幾乎處于不變的狀態(tài)，而其他個(gè)體很快被淘汰，加速了收斂速度，陷入局部最優(yōu)解，出現(xiàn)早熟現(xiàn)象。所以，此后有很多學(xué)者提出了改進(jìn)策略， 如史明霞23，陶林波24o Kenn嚴(yán)則提出了一種基于種群多樣性的自適應(yīng)遺傳算 法，并在帶有時(shí)間窗的車輛路徑問(wèn)題上得到很好的結(jié)果。他通過(guò)在基因空間內(nèi)染色體的海明距離來(lái)度量種群多樣性。然后，基于這個(gè)海明距離去改變交叉率和變 異率，這樣便能保持種群多樣性，減少早熟現(xiàn)象產(chǎn)生的可能。然而，函數(shù)中的敏 感性常數(shù)大小決定了參數(shù)的值。一個(gè)越小的敏感性常數(shù)改變交叉率和變異率越平 滑，相反，敏感性常數(shù)越大，他

12、們的值改變的越快。因此，特定的問(wèn)題需要特定 的敏感性常數(shù)。Gi nley26 貝U同時(shí)考慮了種群多樣性和適應(yīng)度。他采用描述種群解 空間多樣性的標(biāo)準(zhǔn)種群多樣性 SPD (standard population diversity)指標(biāo)來(lái)改變交 叉率和變異率，同時(shí)，提出一種基于個(gè)體適應(yīng)度的健康種群多樣性指標(biāo)HPD(healthy population diversity )來(lái)調(diào)節(jié)選擇算子。算法的目標(biāo)是創(chuàng)造并保持一個(gè) 高適應(yīng)度的多樣性種群并且有能力自適應(yīng)適應(yīng)度空間的改變。具體地，SPD通過(guò)平均個(gè)體標(biāo)準(zhǔn)差的協(xié)方差度量。HPD則通過(guò)帶有適應(yīng)度權(quán)重的協(xié)方差來(lái)度量。 Liu27提出了用父代表現(xiàn)來(lái)排名的方法而

13、不是適應(yīng)度值改變交叉率和變異率。同 樣，高適應(yīng)度的個(gè)體易于保留而低適應(yīng)度的個(gè)體擁有高交叉率。Islam19等根據(jù)交叉操作對(duì)個(gè)體的相對(duì)改善程度來(lái)設(shè)置交叉率；江中央等28則依照父代個(gè)體的相似度來(lái)調(diào)整交叉操作的參數(shù)值。這些方法已用于聚類分析。如Wang等29采用Srini vas等22方法的變種來(lái)自適應(yīng)的調(diào)節(jié)遺傳聚類算法的變異和交叉率?；谧?適應(yīng)控制機(jī)制的參數(shù)設(shè)置技術(shù)通常能給出較好的結(jié)果。但對(duì)于本論文要研究的劃分聚類問(wèn)題，其解空間往往非常復(fù)雜，定義一個(gè)指標(biāo)來(lái)全面捕獲算法運(yùn)行過(guò)程中 解空間的動(dòng)態(tài)特征十分困難。所以，上述演化自適應(yīng)和自適應(yīng)控制機(jī)制各有優(yōu)勢(shì)和缺陷。如何結(jié)合兩種機(jī)制的優(yōu)勢(shì)，達(dá)到互補(bǔ)的效果將

14、是本論文的重點(diǎn)和難點(diǎn)。四、總結(jié)與展望聚類分析是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)極具挑戰(zhàn)性的研究熱點(diǎn)。其目標(biāo)是將一個(gè)數(shù)據(jù)對(duì)象集劃分成若干個(gè)簇，使同一個(gè)簇中的對(duì)象具高度同質(zhì)性，不同簇之間的 對(duì)象具高度異質(zhì)性。 聚類分析在人工智能、機(jī)器學(xué)習(xí)、模式識(shí)別、圖像分析、生物信息、決策科學(xué)和商業(yè)等領(lǐng)域具有廣泛應(yīng)用前景和潛在經(jīng)濟(jì)價(jià)值31,32。聚類分析方法可分為層次聚類和劃分聚類，本論文研究劃分聚類。劃分聚類是一個(gè)已知的NP-難問(wèn)題。近來(lái)，遺傳算法已成為研究劃分聚類的重要方法， 其作為具有系統(tǒng)優(yōu)化、適應(yīng)和學(xué)習(xí)的高性能計(jì)算和建模方法的研究漸趨成熟。遺傳算法具有進(jìn)化計(jì)算的所有特征，同時(shí)又具有自身的特點(diǎn)33:（ 1）搜索過(guò)程既不受

15、優(yōu)化函數(shù)的連續(xù)性約束，也沒(méi)有優(yōu)化函數(shù)導(dǎo)數(shù)必須存在的要求（2）遺傳算法采用多點(diǎn)搜索或者說(shuō)是群體搜索，具有很高的隱含并行性，因而可以提高計(jì)算 速度（3）遺傳算法是一種自適應(yīng)搜索技術(shù)，其選擇交叉變異等運(yùn)算都是以一種 概率方式來(lái)進(jìn)行，從而增加了搜索過(guò)程的靈活性，具有較好的全局優(yōu)化求解能力（4）遺傳算法直接以目標(biāo)函數(shù)值為搜索信息，對(duì)函數(shù)的性態(tài)無(wú)要求，具有較好 的普適性和易擴(kuò)充性（5）遺傳算法更適合大規(guī)模復(fù)雜問(wèn)題的優(yōu)化。但現(xiàn)有遺傳 聚類算法存在諸多問(wèn)題。首先，這些算法在運(yùn)行之前通常需要設(shè)置若干參數(shù)。這些參數(shù)的值，比如交叉和變異率，決定著算法的行為和性能。由于這些參數(shù)之間 存在非線性關(guān)系并依賴于具體的聚類問(wèn)

16、題，況且其最佳值往往需要隨算法運(yùn)行階 段的不同而改變，再加上參數(shù)值的多樣性，使得正確設(shè)置這些參數(shù)變得異常困難。 因此，如何有效設(shè)置這些參數(shù)值，使算法性能最優(yōu)化成為一項(xiàng)重要的研究課題。演化自適應(yīng)機(jī)制適合于在復(fù)雜的優(yōu)化問(wèn)題上設(shè)置遺傳算法的交叉和變異 率。然而，采用該機(jī)制，算法在運(yùn)行過(guò)程中其交叉和變異率往往過(guò)快下降而陷入 局部最優(yōu)解。自適應(yīng)機(jī)制往往能夠防止遺傳算法陷入局部最優(yōu)（早熟現(xiàn)象） ，但 是定義一個(gè)指標(biāo)來(lái)全面捕獲算法運(yùn)行過(guò)程中解空間的動(dòng)態(tài)特征卻十分困難。幸運(yùn)的是，自適應(yīng)機(jī)制能夠阻止過(guò)早收斂的優(yōu)勢(shì)能彌補(bǔ)演化自適應(yīng)過(guò)早陷入局部最優(yōu) 的缺點(diǎn)。同時(shí)，演化自適應(yīng)能夠削弱自適應(yīng)機(jī)制中選取的函數(shù)的影響。因此

17、，雖 然演化自適應(yīng)和自適應(yīng)兩種機(jī)制各有優(yōu)缺點(diǎn)， 但是我們能夠使用他們的優(yōu)勢(shì)相互 的去彌補(bǔ)他們的劣勢(shì)。所以，本論文將結(jié)合兩種機(jī)制的優(yōu)勢(shì)來(lái)設(shè)計(jì)有效的參數(shù)設(shè) 計(jì)方法。參考文獻(xiàn):1 Han J, Kamber M.數(shù)據(jù)挖掘：概念與技術(shù)M.第二版.機(jī)械工業(yè)出版社, 2007.2 Hartigan, J.A. and Wong, M.A.: A k-means clustering algorithm. Applied Statistics, 28(1979) 100-1103 M.Garey and D.Joh nson, Computers and in tractability-a guide to

18、 the theory of NP-complete ness, W.H.Freema n, San Fran cisco, 1979.4 李敏強(qiáng)，寇繼松，林丹，李書(shū)全.遺傳算法的基本理論與應(yīng)用M.北京：科 學(xué)出版社，200235 L.Davis, Han dbook of Gen etic Algorithms, van Nostra nd Rei n hold, New York，1991. 劉勇，等.非數(shù)值并行算法(二)遺傳算法M 北京：科學(xué)出版社，1995.7 Hruschka, Eduardo R., and Nels on FF Ebecke n. A gen etic algor

19、ithm for cluster analysis. Intelligent Data Analysis 7.1 (2003): 15-25.8 Murthy, Chivukula A., and Nirmalya Chowdhury. In search of optimal clusters using genetic algorithms. Pattern Recognition Letters 17.8 (1996): 825-832.9 Eibe n, Agost on En dre, Robert Hin terdi ng, and Zbig niew Michalewicz. P

20、arameter control in evolutionary algorithms. Evolutionary Computation, IEEE Transactions on 3.2 (1999): 124-141.10 Michalewicz, Zbig ni ew, and Marti n Schmidt. Parameter con trol in practice. Parameter setting in evolutionary algorithms. Springer Berlin Heidelberg, 2007. 277-294.11 De Jong, Kenn et

21、h. Parameter sett ing in EAs: a 30 year perspective.Parameter Setti ng in Evoluti on ary Algorithms. Spri nger Berlin Heidelberg, 2007. 1-18.12 Glickma n, Matthew R., and Katia Sycara. Reas ons for premature conv erge nee of self-adapti ng mutatio n rates. Evoluti onary Computatio n, 2000. Proceedi

22、ngs of the 2000 Congress on. Vol. 1. IEEE, 2000.13 Maulik, Ujjwal, and Sanghamitra Bandyopadhyay. Genetic algorithm-basedclusteri ng tech nique. Pattern recog ni tion 33.9 (2000): 1455-1465.14 B?ck, Thomas, and Martin Schtiz. Intelligent mutation rate control in canonical genetic algorithms. Foundat

23、ions of intelligent systems. Springer Berlin Heidelberg, 1996. 158-167.15 Back, Eibe n, “ An empirical study on Gas “ withoutparameters ” ,Lecture Notes in Computer Scie nee, pp.315-324, 2000.16 傅景廣，許剛，王裕國(guó).基于遺傳算法的聚類分析J.計(jì)算機(jī)工程，2004, 30(4): 122-124.17 Kivij? rvi, Juha, Pasi Fr?nti, and Olli Nevalainen.

24、 Self-adaptive genetic algorithm for clusteri ng. Journal of Heuristics 9.2 (2003): 113-129.18 Herrera F, Loza no M. Adaptatio n of gen etic algorithm parameters based on fuzzy logic controllersJ. Genetic Algorithms and Soft Computing, 1996, 8: 95-125.19 Islam S M, Das S, Ghosh S, et al. An adaptive

25、 differential evolution algorithm with novel mutation and crossover strategies for global numerical optimizationJ. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Tran sactio ns on, 2012, 42(2): 482-500.20 Ghosh A, Das S, Chowdhury A, et al. An improved differential evolution algorithm with

26、 fitness-based adaptation of the control parametersJ. In formation Scie nces, 2011, 181(18): 3749-3765.21 Palmes P P, Hayasaka T, Usui S. Mutati on-based gen etic n eural n etworkJ. Neural Networks, IEEE Transactions on, 2005, 16(3): 587-600.22 Srini vas M, Pat naik L M. Adaptive probabilities of cr

27、ossover and mutati on in genetic algorithmsJ. Systems, Man and Cybernetics, IEEE Transactionson, 1994, 24(4): 656-667.23 史明霞，陶林波，沈建京.自適應(yīng)遺傳算法的改進(jìn)與應(yīng)用J.微計(jì)算機(jī)應(yīng) 用，2006, 27(4): 405-408.24 陶林波，沈建京，韓強(qiáng).一種解決早熟收斂的自適應(yīng)遺傳算法設(shè)計(jì)J.微計(jì)算機(jī)信息，2006 (12S): 268-270.25 Zhu K Q. A diversity-controlling adaptive genetic algorithm for the vehicle routing problem with time windowsC/Tools with Artificial Intelligenee, 2003. Proceedi ngs. 15th IEEE In ternatio nal Co nference on .IEEE, 2003: 176-183.26 MeGinley B, Maher J, ORiordan C, et al. Maintaining healthy population diversity using adaptive crossover, mutation,