【摘要】：仿生隨機搜索啟發(fā)式算法如演化算法和蟻群算法是一類通用的流行算法,它是通過模擬自然界現(xiàn)象、過程和一些生物特征提出來的。這些算法已被廣泛地用于解決大量的各種實際問題并且獲得了很好的效果。這些算法易于實施并且可以應用到結構不是很清楚的優(yōu)化問題上。演化算法是受到物種的自然演變的啟發(fā)而提出的,演化算法通過迭代應用變異、重組和選擇算子對問題的解進行優(yōu)化。蟻群算法來源于真正的螞蟻具有通過交換信息素從它們的巢穴到食物源的眾多路徑中找到最短路徑的能力。許多實證研究已經(jīng)證明了這類算法在許多問題上是非常有效的,但是離徹底理解算法的運行機制還是很遙遠的。本文從理論研究的角度對演化算法和蟻群算法進行了分析。本文分析了單目標演化算法和蟻群算法在組合優(yōu)化問題上的近似性能,也分析了多目標演化算法在擬布爾函數(shù)上的時間復雜度。本文主要采用常用的隨機分析方法和工具進行分析。本文的主要貢獻如下:(1)最大獨立集問題是圖論中的一個經(jīng)典組合優(yōu)化問題,也是一類NP完全問題。基于目前的計算理論,除非P=NP,最大獨立集問題將不存在多項式時間的確定性算法。許多學者設計出一些有效的近似算法來求解最大獨立集問題。演化算法是一類公認的有效的隨機算法,其近似性能的理論分析相對較少。本文從理論上分析了一個簡單的爬山演化算法(1+1)EA求解最大獨立集問題的近似性能。證明了(1+1)EA能夠在多項式的期望時間內(nèi)獲得該問題的近似比。對于一類特殊的獨立集問題——k-Set Packing問題,本文證明了(1+1)EA可以在多項式期望時間內(nèi)獲得該問題的近似比。最后,文中給出了一個最大獨立集問題的實例,并說明在該實例上(1+1)EA能獲得比3-flip局部搜索方法更優(yōu)的解。在這個實例上3-flip局部搜索算法會陷入局部最優(yōu),而(1+1)EA能夠在多項式期望運行時間找到該實例的全局最優(yōu)解。(2)長時間以來,演化算法已經(jīng)被成功的應用于解決多目標最優(yōu)化問題。然而多目標演化算法(MOEAs)的理論研究主要限于簡單的多目標演化算法(SEMO)。Pareto存檔演化策略(PAES)是一種簡單但重要的多目標演化算法,它是來源于對電信問題的研究。本文首次分析了PAES算法在擬布爾函數(shù)上的運行時間,證明了當SEMO算法采用一種簡單的變異算子時,PAES算法在PATH函數(shù)的性能優(yōu)于SEMO算法。然而,我們可以發(fā)現(xiàn)該算法在著名的LOTZ函數(shù)上卻不能以壓倒性的概率獲得它的整個Pareto前沿。之后,本文提出一種改進的Pareto存檔演化策略(IPAES)并且證明了IPAES算法可以在多項式運行時間內(nèi)找到整個LOTZ函數(shù)的Pareto前沿。最后,本文分析了IPAES算法采用兩種不同的局部變異算子在擬布爾函數(shù)上的性能�；谏鲜龇治�,我們可以發(fā)現(xiàn)對于不同的問題選擇合適的局部搜索算子是非常重要的。(3)本文也研究了兩種蟻群算法在一類特殊旅行商問題上的近似性能。這類旅行商問題的特點是任意的兩個城市之間的距離是1或者2,我們稱這種問題是TSP(1,2)問題,這是一個NP完全問題。本文證明了兩種蟻群算法能在多項式的運行時間內(nèi)獲得TSP(1,2)問題的3/2的近似比,同時也研究了信息素和啟發(fā)式信息對算法性能的影響。最后,文中構造了一個TSP(1,2)問題實例并且證明了蟻群算法在這個實例上的性能優(yōu)于局部搜索算法。
[Abstract]:......
【學位授予單位】：華南理工大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TP18

【相似文獻】

相關期刊論文 前10條

1 龔文引;謝丹;;針對本科生的演化算法教學探討[J];計算機時代;2012年07期

2 熊盛武,李元香,康立山,陳毓屏;用演化算法求解拋物型方程擴散系數(shù)的識別問題[J];計算機學報;2000年03期

3 曾三友,康立山,丁立新;基于偏序關系的演化算法[J];計算機工程;2001年08期

4 周永華,毛宗源;基于混合雜交與間歇變異的演化算法[J];計算機工程與應用;2003年06期

5 閆震宇,康立山,陳毓屏,付朋輝;一種新的多目標演化算法——穩(wěn)態(tài)淘汰演化算法[J];武漢大學學報(理學版);2003年01期

6 王濤,李歧強;基于空間收縮的并行演化算法[J];中國工程科學;2003年03期

7 何國良,李元香;多個粒子參與交叉的一種動態(tài)演化算法[J];計算機工程與應用;2004年08期

8 劉敏忠,鄒秀芬,康立山;一種基于偏序排名的高效的多目標演化算法[J];小型微型計算機系統(tǒng);2004年12期

9 王龍奎,汪祖柱;關于多目標演化算法的策略分析[J];安徽大學學報(自然科學版);2005年03期

10 田麗,林錦國,劉建峰,張光云;基于演化算法的客戶關系管理系統(tǒng)研究[J];微處理機;2005年03期

相關會議論文 前3條

1 馮珊;李鋒;周凱波;;面向演化算法應用的智能體系統(tǒng)建模與仿真研究[A];西部開發(fā)與系統(tǒng)工程——中國系統(tǒng)工程學會第12屆年會論文集[C];2002年

2 張文俊;謝曉鋒;馬君;;并行演化算法在半導體器件綜合中的應用[A];2006年全國開放式分布與并行計算學術會議論文集（二）[C];2006年

3 謝柏橋;戴光明;鄭蔚;王劍文;;有指導的多目標演化算法在區(qū)域星座設計中的應用[A];中國宇航學會深空探測技術專業(yè)委員會第四屆學術年會論文集[C];2007年

相關博士學位論文 前10條

1 俞揚;演化計算理論分析與學習算法的研究[D];南京大學;2011年

2 庫俊華;自適應差分演化算法及其應用研究[D];中國地質(zhì)大學;2015年

3 彭雪;演化算法和蟻群算法的性能分析[D];華南理工大學;2016年

4 彭晟;演化算法的靜電場論模型[D];武漢大學;2011年

5 陳明;演化算法漸近行為的若干問題研究[D];武漢大學;2012年

6 彭飛;實值演化算法投資組合研究[D];中國科學技術大學;2011年

7 萬書振;動態(tài)環(huán)境下差分演化算法研究與應用[D];武漢理工大學;2012年

8 魏波;交互式與自適應演化算法研究[D];武漢大學;2013年

9 賴鑫生;演化算法與混合算法的性能研究[D];華南理工大學;2014年

10 武志峰;差異演化算法及其應用研究[D];北京交通大學;2009年

相關碩士學位論文 前10條

1 楊穎;一種多差分向量的自適應差分演化算法[D];浙江大學;2015年

2 陳偉;隊伍演化算法及其在微波電路設計中的應用[D];杭州電子科技大學;2015年

3 吳昊;多群體并行演化算法的研究[D];南京郵電大學;2015年

4 要婷婷;基于模因演化算法的有限容量弧路徑問題研究[D];北京交通大學;2016年

5 邢雪;基于Pi演算的關系演化算法的研究與實現(xiàn)[D];吉林大學;2016年

6 黃星;遺傳遞增演化算法配筋優(yōu)化設計[D];湖南大學;2016年

7 溫志超;基于演化算法及改進詞袋模型的病蟲害分類識別技術研究[D];華南農(nóng)業(yè)大學;2016年

8 左磊;改進的差分演化算法研究及其應用[D];華南農(nóng)業(yè)大學;2016年

9 張盛鑫;基于新型變異與交叉算子的差分演化算法研究[D];暨南大學;2016年

10 戴志晃;一種基于熵量守恒的改進演化算法的研究[D];江西理工大學;2010年

，

本文編號：2296837