混合元胞遺傳算法與多層元胞遺傳算法的研究

1、學(xué)校代碼：10406分類號： TP301.6 學(xué)號：090081002106南昌航空大學(xué) 南昌航空大學(xué)碩 士 學(xué) 位 論 文（學(xué)位研究生）混合 元胞 遺傳算 法與 多層元 胞遺 傳算 混合 元胞 遺傳算 法與 多層元 胞遺 傳算法的 研究 法的 研究碩士研究生： 揭麗琳導(dǎo) 師： 黎明申請學(xué)位級別：碩士學(xué)科、專業(yè)： 信號與信息處理所在單位： 信息工程學(xué)院答辯日期： 2012.6授予學(xué)位單位：南昌航空大學(xué)I摘要 摘要現(xiàn)實(shí)世界許多領(lǐng)域存在的問

2、題都具有高度復(fù)雜性、多目標(biāo)、多約束的要求，采用傳統(tǒng)的搜索方法處理十分困難， 求解效果不夠理想， 如何找到對問題本身具有更強(qiáng)求解能力的算法就成為一個(gè)迫切需要解決的問題。遺傳算法(GeneticAlgorithms)作為進(jìn)化算法中產(chǎn)生最早且影響最大的概率性搜索算法， 它是通過模擬自然界生物進(jìn)化過程的自然選擇與遺傳信息規(guī)律而形成的一種高效全局尋優(yōu)方法，具有適用性強(qiáng)、魯棒性好及并行計(jì)算等優(yōu)勢，已成功應(yīng)用于求解傳統(tǒng)搜索技術(shù)難以解決的復(fù)雜優(yōu)化問題。

3、但是標(biāo)準(zhǔn)遺傳算法(Standard Genetic Algorithms)不考慮空間結(jié)構(gòu)環(huán)境和生物進(jìn)化過程中種群局部個(gè)體間的相互作用， 個(gè)體之間沒有位置關(guān)系， 且遺傳算子具有隨機(jī)性、 無方向性， 因此種群多樣性容易過早丟失，導(dǎo)致算法陷入局部最優(yōu)。 元胞自動機(jī)是一種離散的數(shù)學(xué)模型， 通過離散空間上大量元胞個(gè)體簡單的相互作用而形成整體上的復(fù)雜行為， 特別適合于計(jì)算機(jī)模擬實(shí)施復(fù)雜動態(tài)系統(tǒng)。元胞遺傳算法(Cellular Genetic Alg

4、orithm）是一種將遺傳算法和元胞自動機(jī)原理有機(jī)地結(jié)合的算法，明顯改善了遺傳算法的全局收斂性能， 已成為解決復(fù)雜問題的一種有效方法。 但是元胞遺傳算法每次評價(jià)個(gè)體的適應(yīng)度時(shí)計(jì)算量較大，在解決非常復(fù)雜的優(yōu)化問題時(shí)存在優(yōu)化速度一般比較慢的缺點(diǎn)。 同時(shí)進(jìn)一步提高元胞遺傳算法的全局收斂率也還有很大的研究發(fā)展空間。本文圍繞如何解決一般元胞遺傳算法在提高全局收斂率的同時(shí)一定程度降低搜索效率的問題進(jìn)行了研究，主要研究內(nèi)容如下：1.提出了一種粒子群與

5、多種群元胞遺傳混合優(yōu)化算法(A Hybrid ParticleSwarm and Multi-Population Cellular Genetic Algorithm)。該算法首先將群體分割成多個(gè)元胞子種群，選擇合適的遷移策略，子種群之間相互通信共享進(jìn)化信息，適度降低算法的選擇壓力， 從而更好地保持種群的多樣性。 算法的變異操作被粒子群算法替代， 使得局部搜索能力明顯提高。 元胞群體分割和粒子群變異較好地均衡了全局探索和局部尋優(yōu)之間的

6、關(guān)系。 最后分析了混合算法的選擇壓力和多樣性變化規(guī)律， 通過對六種典型函數(shù)的優(yōu)化問題求解討論了混合算法的性能， 實(shí)驗(yàn)結(jié)果表明，該算法與 CGA 相比，在保證搜索效率高的同時(shí)還顯著提高元胞遺傳算法的全局收斂率，且穩(wěn)定性得到明顯的改善。2.著重分析和討論了相關(guān)控制參數(shù)對混合元胞遺傳算法性能及優(yōu)化效率的影響。針對優(yōu)化四種不同類型的目標(biāo)函數(shù)，通過采用不同的分割數(shù)目實(shí)驗(yàn)比較，分析選擇壓力和多樣性的變化規(guī)律，得出種群分割數(shù)目為 10 時(shí)更有利于求解