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

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 龔文引;謝丹;;針對(duì)本科生的演化算法教學(xué)探討[J];計(jì)算機(jī)時(shí)代;2012年07期

2 熊盛武,李元香,康立山,陳毓屏;用演化算法求解拋物型方程擴(kuò)散系數(shù)的識(shí)別問(wèn)題[J];計(jì)算機(jī)學(xué)報(bào);2000年03期

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

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

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

6 王濤,李歧強(qiáng);基于空間收縮的并行演化算法[J];中國(guó)工程科學(xué);2003年03期

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

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

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

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

相關(guān)會(huì)議論文 前3條

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

2 張文俊;謝曉鋒;馬君;;并行演化算法在半導(dǎo)體器件綜合中的應(yīng)用[A];2006年全國(guó)開(kāi)放式分布與并行計(jì)算學(xué)術(shù)會(huì)議論文集（二）[C];2006年

3 謝柏橋;戴光明;鄭蔚;王劍文;;有指導(dǎo)的多目標(biāo)演化算法在區(qū)域星座設(shè)計(jì)中的應(yīng)用[A];中國(guó)宇航學(xué)會(huì)深空探測(cè)技術(shù)專(zhuān)業(yè)委員會(huì)第四屆學(xué)術(shù)年會(huì)論文集[C];2007年

相關(guān)博士學(xué)位論文 前10條

1 俞揚(yáng);演化計(jì)算理論分析與學(xué)習(xí)算法的研究[D];南京大學(xué);2011年

2 庫(kù)俊華;自適應(yīng)差分演化算法及其應(yīng)用研究[D];中國(guó)地質(zhì)大學(xué);2015年

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

4 彭晟;演化算法的靜電場(chǎng)論模型[D];武漢大學(xué);2011年

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

6 彭飛;實(shí)值演化算法投資組合研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年

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

8 魏波;交互式與自適應(yīng)演化算法研究[D];武漢大學(xué);2013年

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

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

相關(guān)碩士學(xué)位論文 前10條

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

2 陳偉;隊(duì)伍演化算法及其在微波電路設(shè)計(jì)中的應(yīng)用[D];杭州電子科技大學(xué);2015年

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

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

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

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

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

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

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

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

，

本文編號(hào)：2296837