本文關(guān)鍵詞：隨機啟發(fā)式搜索算法的性能分析，由筆耕文化傳播整理發(fā)布。

【摘要】：隨機啟發(fā)式搜索算法如演化算法、蟻群算法及人工免疫算法等是通過模擬大自然現(xiàn)象、過程及一些生物特性等提出的一類通用算法。實踐證明,這類隨機啟發(fā)式搜索算法在科學(xué)研究及工程實際問題中獲得了極大的成功,尤其是針對一些結(jié)構(gòu)不清晰的復(fù)雜優(yōu)化問題,以及在計算資源有限的情況下表現(xiàn)出了卓越的性能。為了更好的理解隨機啟發(fā)式搜索算法的工作機制,進一步指導(dǎo)算法設(shè)計及應(yīng)用,研究人員迫切希望為這類算法建立嚴密的理論基礎(chǔ)。然而,由于隨機啟發(fā)式搜索算法的隨機性、群體性等特點,使得算法在運行過程中表現(xiàn)出非常復(fù)雜的動態(tài)隨機行為,增加了理論研究的難度。當(dāng)前,理論研究成果相對偏少。本文從隨機啟發(fā)式搜索算法的理論研究角度出發(fā),關(guān)注隨機啟發(fā)式搜索算法求解優(yōu)化問題的時間復(fù)雜性,以及在NP-完全(難)優(yōu)化問題上的近似性能;研究問題類型與算法特征之間的關(guān)系;進一步探索隨機啟發(fā)式搜索算法求解典型優(yōu)化問題的有效性,以期完善和增強隨機啟發(fā)式搜索算法的理論基礎(chǔ)。本文的主要工作如下:(1)研究了演化算法求解最多葉子生成樹問題(MLST)的性能。最多葉子生成樹問題是NP完全理論中一個經(jīng)典的組合優(yōu)化問題,在網(wǎng)絡(luò)設(shè)計及電路布局等實際問題上有較強的應(yīng)用背景。該問題是在一個無向連通圖中找出一棵生成樹,使得生成樹中所含葉子節(jié)點最多。許多啟發(fā)式算法如演化算法用于求解該問題。然而,對于演化算法在NP難問題的求解性能方面我們?nèi)灾跎�。本文從理論上研究了演化算法求解MLST問題的近似性能。指出對于MLST問題,算法(1+1)EA能夠分別在期望多項式時間2O(nm)和4O(nm)內(nèi)獲得5近似比和3近似比,其中n為無向連通圖中的節(jié)點數(shù),m為邊數(shù)。同時,我們研究了(1+1)EA算法在兩個MLST問題實例上的性能,并且指出局部搜索算法在該實例上容易陷入局部最優(yōu),而(1+1)EA算法能夠逃脫局部最優(yōu)并最終獲得最優(yōu)解。(2)研究了蟻群算法在二次指派問題(QAP)上的性能。二次指派問題是最具挑戰(zhàn)性的組合優(yōu)化問題之一。該問題在物流運輸和選址等許多實際問題中有著廣泛的應(yīng)用。理論上研究了ACO算法在極其難的QAP問題上的性能。給出了一個簡單的(1+1)MMAA算法在QAP問題上的最壞情況界。并指出對于QAP問題,(1+1)MMAA算法能夠獲得一定的近似保證。最后,通過構(gòu)建一個QAP實例,表明蟻群優(yōu)化算法在該實例上要優(yōu)于2-exchange局部搜索算法,進一步證實了蟻群算法的有效性。(3)分析比較了基于免疫的超變異算子與標(biāo)準(zhǔn)位變異算子在優(yōu)化問題上的性能。人工免疫系統(tǒng)在許多復(fù)雜的真實優(yōu)化問題中獲得了廣泛的應(yīng)用并取得了極大成功。然而,人工免疫算法的理論研究遠遠滯后于其在許多領(lǐng)域的應(yīng)用研究。對于人工免疫算法的運行機制以及其有效性研究還處于探索的初級階段,當(dāng)前也迫切需要為這類算法建立堅實的理論基礎(chǔ)。本文從理論上分析了一種被用于免疫算法中的連續(xù)高頻變異算子在優(yōu)化問題上的性能,并在兩個擬布爾函數(shù)及兩個真實組合優(yōu)化問題的實例上分析比較了連續(xù)高頻變異算子與標(biāo)準(zhǔn)位變異算子、局部變異算子的性能,證明了連續(xù)高頻變異算子在這些實例上要優(yōu)于標(biāo)準(zhǔn)位變異算子及局部變異算子。也進一步揭示了問題類型與算法特征之間的關(guān)系,從理論上證實了連續(xù)高頻變異算子的有效性。
【關(guān)鍵詞】：隨機啟發(fā)式搜索 最優(yōu)化問題 算法分析 時間復(fù)雜度分析 近似性能
【學(xué)位授予單位】：華南理工大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：TP18
【目錄】：

• 摘要5-7
• ABSTRACT7-14
• 主要符號表14-15
• 第一章 緒論15-38
• 1.1 引言15-17
• 1.2 隨機啟發(fā)式搜索算法17-24
• 1.2.1 演化算法17-20
• 1.2.2 蟻群算法20-22
• 1.2.3 人工免疫系統(tǒng)22-23
• 1.2.4 其它隨機搜索算法23-24
• 1.3 相關(guān)工作24-36
• 1.3.1 演化算法時間復(fù)雜度和近似性能研究相關(guān)工作24-30
• 1.3.2 蟻群優(yōu)化算法性能研究相關(guān)工作30-33
• 1.3.3 基于免疫的B細胞算法性能研究相關(guān)工作33-35
• 1.3.4 其它研究成果35-36
• 1.4 本文概述和主要工作36-38
• 第二章 隨機啟發(fā)式搜索算法理論研究基礎(chǔ)38-47
• 2.1 引言38
• 2.2 隨機啟發(fā)式搜索算法的計算復(fù)雜度38-40
• 2.3 隨機啟發(fā)式搜索算法理論研究方法40-46
• 2.3.1 偏差不等式40-42
• 2.3.2 標(biāo)準(zhǔn)變異42-43
• 2.3.3 適應(yīng)值劃分43-44
• 2.3.4 期望倍增距離減少44-46
• 2.4 小結(jié)46-47
• 第三章 演化算法求解最多葉子生成樹問題的性能分析47-62
• 3.1 引言47-48
• 3.2 最多葉子生成樹問題及(1+1) EA算法48-49
• 3.3 (1+1) EA算法求解MLST問題的近似保證49-51
• 3.4 (1+1) EA算法在兩個MLST問題實例上的性能分析51-60
• 3.4.1 在一個MLST實例上(1+1) EA算法優(yōu)于 1-change鄰域局部搜索方法51-55
• 3.4.2 在一個MLST實例上(1+1) EA算法優(yōu)于 2-change鄰域局部搜索方法55-60
• 3.5 小結(jié)60-62
• 第四章 蟻群優(yōu)化算法在二次指派問題上的性能分析62-79
• 4.1 引言62
• 4.2 問題和算法62-65
• 4.2.1 二次指派問題62-63
• 4.2.2 ACO算法63-65
• 4.3 (1+1) MMAA算法求解QAP問題的近似性能分析65-72
• 4.4 (1+1) MMAA算法求解QAP實例的分析72-78
• 4.5 小結(jié)78-79
• 第五章 基于免疫的超變異算子與標(biāo)準(zhǔn)位變異算子的性能比較79-99
• 5.1 引言79-80
• 5.2 基本定義及相關(guān)算法介紹80-82
• 5.2.1 基本定義80-81
• 5.2.2 算法81-82
• 5.3 基于免疫的超變異算子在一些人工函數(shù)上優(yōu)于標(biāo)準(zhǔn)位變異算子82-87
• 5.3.1 TRAP函數(shù)82-84
• 5.3.2 H-IFF函數(shù)84-87
• 5.4 基于免疫的超變異、標(biāo)準(zhǔn)位變異及局部變異算子在最大割問題實例上的性能比較87-93
• 5.4.1 最大割問題87-89
• 5.4.2 不同變異算子在實例MC(s, p) 上的行為分析89-93
• 5.5 基于免疫的超變異算子在最小S-T割問題的一個實例上優(yōu)于標(biāo)準(zhǔn)位變異算子93-97
• 5.5.1 最小s-t割問題93-96
• 5.5.2 變異算子CHM2在實例ST(k, l) 上的分析96-97
• 5.6 小結(jié)97-99
• 結(jié)論99-101
• 參考文獻101-116
• 攻讀博士學(xué)位期間取得的研究成果116-118
• 致謝118-119

【共引文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 孫慧;;Multiple People Picking Assignment and Routing Optimization Based on Genetic Algorithm[J];科技視界;2014年01期

2 吳果林;李學(xué)遷;;求解二次分配問題的預(yù)處理快速螞蟻系統(tǒng)[J];上海理工大學(xué)學(xué)報;2014年02期

3 王濤;卿鵬;魏迪;漆鋒濱;;基于聚類分析的進程拓撲映射優(yōu)化[J];計算機學(xué)報;2015年05期

4 張睿;李樹剛;;基于復(fù)雜網(wǎng)絡(luò)的微吧話題流行度預(yù)測研究[J];科學(xué)技術(shù)與工程;2015年17期

5 王長軍;徐琪;賈永基;;單機下異構(gòu)任務(wù)調(diào)度的解性質(zhì)研究[J];管理科學(xué)學(xué)報;2015年07期

6 張宇山;郝志峰;黃翰;林智勇;;進化算法首達時間分析的停時理論模型[J];計算機學(xué)報;2015年08期

7 QIAN Chao;YU Yang;ZHOU Zhi-Hua;;Variable solution structure can be helpful in evolutionary optimization[J];Science China(Information Sciences);2015年11期

8 孫慧;張柯;張富金;張紀(jì)會;;基于遺傳算法的雙區(qū)型倉庫人工揀貨路徑優(yōu)化[J];青島大學(xué)學(xué)報(工程技術(shù)版);2014年01期

9 黃翰;徐威迪;張宇山;林智勇;郝志峰;;基于平均增益模型的連續(xù)型(1+1)進化算法計算時間復(fù)雜性分析[J];中國科學(xué):信息科學(xué);2014年06期

10 林浩;林瀾;;圖的最小控制樹問題（英文）[J];數(shù)學(xué)季刊(英文版);2014年01期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前4條

1 張宇山;進化算法的收斂性與時間復(fù)雜度分析的若干研究[D];華南理工大學(xué);2013年

2 任海豹;QoS保障的基站節(jié)能機制研究[D];中國科學(xué)技術(shù)大學(xué);2014年

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

4 張鶴立;分層異構(gòu)網(wǎng)絡(luò)中干擾管理、用戶連接及自組織技術(shù)研究[D];北京郵電大學(xué);2014年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 趙婷;三類平行機博弈排序問題的協(xié)調(diào)機制研究[D];中國海洋大學(xué);2013年

2 陳戈;純電驅(qū)動轎車動力傳動系統(tǒng)耦合分析與多目標(biāo)優(yōu)化設(shè)計[D];合肥工業(yè)大學(xué);2013年

3 景莉;現(xiàn)代鐵路物流中心功能設(shè)計與基于改進SLP方法的功能區(qū)布局[D];中南大學(xué);2013年

4 許金輝;面向動態(tài)需求的魯棒性車間布局研究[D];華中科技大學(xué);2013年

5 陳朝霞;NSGA-Ⅱ在多品種變批量軍工制造企業(yè)數(shù)字化車間設(shè)備布局的算法研究[D];杭州電子科技大學(xué);2014年

6 范國強;若干排序博弈問題的協(xié)調(diào)機制研究[D];中國海洋大學(xué);2014年

7 胡丹;兩類平行機并行分批排序問題的協(xié)調(diào)機制和算法研究[D];中國海洋大學(xué);2014年

8 楊藝;求解二次分配問題的魚群算法研究[D];湘潭大學(xué);2014年

9 康春建;降低數(shù)據(jù)中心能耗提高網(wǎng)絡(luò)服務(wù)質(zhì)量優(yōu)化算法研究[D];天津大學(xué);2014年

10 楊力;眾核處理器核級冗余拓撲重構(gòu)算法研究[D];東華大學(xué);2015年

  本文關(guān)鍵詞：隨機啟發(fā)式搜索算法的性能分析，由筆耕文化傳播整理發(fā)布。

，

本文編號：341822