演化算法和蟻群算法的性能分析

演化算法和蟻群算法的性能分析

ID:35090174

大?。?.53 MB

頁數(shù):112頁

時間:2019-03-17

演化算法和蟻群算法的性能分析_第1頁
演化算法和蟻群算法的性能分析_第2頁
演化算法和蟻群算法的性能分析_第3頁
演化算法和蟻群算法的性能分析_第4頁
演化算法和蟻群算法的性能分析_第5頁
資源描述:

《演化算法和蟻群算法的性能分析》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、寺為;f^乂葦Sou化ChinaUniversityofTechnology博±學(xué)位論文演化算法和蟻群算法的性能分析羅’..,':v...’^VV山卻與.巧苗靖扣式靖請苗擊靖茍裝'誠..;巧其r'".7.作者姓名^學(xué)科專業(yè)計算機軟件與理論指導(dǎo)教師周育人教授所在學(xué)院計算機科學(xué)與工程學(xué)院論文提交日期2016年4月12日OnthePerformanceAnalysisofEvolutionaryAlgorithmandAntColonyAlgorit

2、hmADissertationSubmittedfortheDegreeofDoctorofPhilosophyCandidate:PengXueSupervisor:Prof.ZhouYurenSouthChinaUniversityofTechnologyGuangzhou,China分類號:TP301學(xué)校代號:10561學(xué)號:201210102090華南理工大學(xué)博士學(xué)位論文演化算法和蟻群算法的性能分析作者姓名:彭雪指導(dǎo)教師姓名、職稱:周育人、教授申請學(xué)位級別:工學(xué)博士學(xué)科專業(yè)名稱:計算機軟件與理論研究方向:計算智能論文提交日

3、期:2016年4月12日論文答辯日期:2016年6月7日學(xué)位授予單位:華南理工大學(xué)學(xué)位授予日期:年月日答辯委員會成員:主席:湯庸委員:張平鄧輝舫張星明周育人華南理工大學(xué)學(xué)位論文原創(chuàng)性聲明本人鄭重聲明:所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨立進行研巧所。,取得的研究成果除了文中特別加^^標(biāo)注引用的內(nèi)容外本論文不包含任何其他個人或集體己經(jīng)發(fā)表或撰寫的成果作品。對本文的研究做出重要貢獻的個人和集體,均已在文中明確方式標(biāo)明。本人完全意識到本聲明的法律后果由本人承擔(dān)。作者簽名;:日期妒《年月7日學(xué)位論文版權(quán)使

4、用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留,目P:研究生在校攻讀學(xué)、使用學(xué)位論文的規(guī)定位期間論文王作的知識產(chǎn)權(quán)單位屬華南理工大學(xué)。學(xué)校有權(quán)保存并向國家有關(guān)部口或機構(gòu)送交論文的復(fù)印件和電子版,允許學(xué)位論文被查閱(除在保密期內(nèi)的保密論文外);學(xué)校可W公布學(xué)位論文的全部或部分內(nèi)容,可W允許采用影印、縮印或其它復(fù)制手段保存、匯編學(xué)位論文。本人電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致。本學(xué)位論文屬于:□保密(校保密委員會審定為涉密學(xué)位論文時間:月日),年__于^月日解密后適用本授權(quán)書。._____^不保密同

5、意在校園網(wǎng)上發(fā)布,,供校內(nèi)師生和與學(xué)校有共享協(xié)議的單位瀏覽;同意將本人學(xué)位論文提交中國學(xué)術(shù)期刊(光盤版)電子雜志社全文出版和編入CNKI《中國知識資源總庫》,傳播學(xué)位論文的全部或部分內(nèi)容。"V"(請在上相應(yīng)方框內(nèi)打)作者簽名:日期:指導(dǎo)教師簽名:巧日期:摘要仿生隨機搜索啟發(fā)式算法如演化算法和蟻群算法是一類通用的流行算法,它是通過模擬自然界現(xiàn)象、過程和一些生物特征提出來的。這些算法已被廣泛地用于解決大量的各種實際問題并且獲得了很好的效果。這些算法易于實施并且可以應(yīng)用到結(jié)構(gòu)不是很清楚的優(yōu)化問題上。演化算法

6、是受到物種的自然演變的啟發(fā)而提出的,演化算法通過迭代應(yīng)用變異、重組和選擇算子對問題的解進行優(yōu)化。蟻群算法來源于真正的螞蟻具有通過交換信息素從它們的巢穴到食物源的眾多路徑中找到最短路徑的能力。許多實證研究已經(jīng)證明了這類算法在許多問題上是非常有效的,但是離徹底理解算法的運行機制還是很遙遠的。本文從理論研究的角度對演化算法和蟻群算法進行了分析。本文分析了單目標(biāo)演化算法和蟻群算法在組合優(yōu)化問題上的近似性能,也分析了多目標(biāo)演化算法在擬布爾函數(shù)上的時間復(fù)雜度。本文主要采用常用的隨機分析方法和工具進行分析。本文的主要貢獻如下:(1)最大獨立集問

7、題是圖論中的一個經(jīng)典組合優(yōu)化問題,也是一類NP完全問題?;谀壳暗挠嬎憷碚?,除非P=NP,最大獨立集問題將不存在多項式時間的確定性算法。許多學(xué)者設(shè)計出一些有效的近似算法來求解最大獨立集問題。演化算法是一類公認(rèn)的有效的隨機算法,其近似性能的理論分析相對較少。本文從理論上分析了一個簡單的爬山演化算法(1+1)EA求解最大獨立集問題的近似性能。證明了(1+1)EA能夠在多項式的期望時間內(nèi)獲得該問題的近似比。對于一類特殊的獨立集問題——k-SetPacking問題,本文證明了(1+1)EA可以在多項式期望時間內(nèi)獲得該問題的近似比。最后,文

8、中給出了一個最大獨立集問題的實例,并說明在該實例上(1+1)EA能獲得比3-flip局部搜索方法更優(yōu)的解。在這個實例上3-flip局部搜索算法會陷入局部最優(yōu),而(1+1)EA能夠在多項式期望運行時間找到該實例的全局最優(yōu)解。(2)長時間以來,演化算法

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。