本文關(guān)鍵詞：基于差分進(jìn)化的約束求解算法研究，由筆耕文化傳播整理發(fā)布。

【摘要】：約束滿足問題(Contraint Satisfaction Problems,CSPs)是運(yùn)籌學(xué)和人工智能研究領(lǐng)域的一個重要方向,在人們身邊,眾多實(shí)際問題都能夠轉(zhuǎn)化為CSPs來求解。CSPs研究大體上分為表示領(lǐng)域的語言方向和推理領(lǐng)域的算法方向,這兩個方向是CSPs研究的兩大重要方向,若再細(xì)分,表示可分為通用表示和專用表示,推理又可分為約束傳播和搜索。CSPs通常都是NP-hard問題,它是由一個變量集合和一個約束集合組成的,求解CSPs也就是為它的變量集合尋找一組賦值,并使其滿足它的約束集合,這樣的一組賦值就稱為CSPs的解。而求解CSPs的方法一般可分為完備性求解算法和非完備性算法。完備性求解算法是基于回溯的搜索算法(BT-backtracking algorithm),該算法在選擇實(shí)例化變量時,采用深度優(yōu)先策略,若未找到解則啟動回溯機(jī)制,直到找到一組解,或者證明該問題是無解的;非完備性求解算法一般是指群體智能算法,通過模擬生物群體的一些行為(如覓食,集聚,進(jìn)化等),經(jīng)過迭代最終尋找到最優(yōu)解,本文所涉及的群體智能算法是差分進(jìn)化算法。在差分進(jìn)化算法中,變量的每個可能解叫做參數(shù)向量或者基因,差分進(jìn)化的求解步驟與標(biāo)準(zhǔn)進(jìn)化算法(Evolutionary Algorithm,EA)大體相同,但卻不同于傳統(tǒng)進(jìn)化算法,差分進(jìn)化算法主要依賴差分向量來擾動當(dāng)前的試驗(yàn)向量,利用參數(shù)向量的差異來探索目標(biāo)區(qū)域。自上世紀(jì)90年代后期,在科學(xué)與工程領(lǐng)域的優(yōu)化問題中,差分進(jìn)化算法的影響力逐步增強(qiáng),并且有著重要的地位。它的優(yōu)勢明顯,首先,與其它進(jìn)化算法相比,差分進(jìn)化算法更易直接實(shí)現(xiàn),無論用什么程序語言,算法的主體僅需四到五行代碼就可以編寫出來;其次,在求解單峰、多峰、離散、連續(xù)等問題時,差分進(jìn)化算法展現(xiàn)出了較好的性能優(yōu)勢,超越了很多算法;再次,差分進(jìn)化算法的控制參數(shù)較少,主要包括種交叉概率CR、縮放系數(shù)F、種群規(guī)模NP三個控制參數(shù),算法的性能主要也是取決于這三個控制參數(shù);最后,與一些最有競爭力的實(shí)參優(yōu)化器(如自適應(yīng)協(xié)方差矩陣進(jìn)化策略CMA-ES)相比,差分進(jìn)化算法的空間復(fù)雜度較低。本文提出了基于弧相容技術(shù)AC的自適應(yīng)差分進(jìn)化算法——AC-FSADE算法,與SADE算法相比,該算法有著三處改進(jìn)部分,首先,對控制變異操作的縮放系數(shù)F進(jìn)行基于個體適應(yīng)度的更新,進(jìn)化開始階段,縮放系數(shù)F較大,搜索步長,有助于算法開拓探索空間,進(jìn)化后期,縮放系數(shù)F較小,搜索步短,有助于算法快速收斂;其次,對控制交叉操作的交叉概率CR也進(jìn)行基于個體適應(yīng)度的更新,進(jìn)化開始階段,交叉概率CR較小,防止早熟收斂,有助于保持種群多樣性,進(jìn)化后期,交叉概率CR較大,有助于個體保留較好的基因;最后,將弧相容技術(shù)AC融入SADE算法中,剔除變量論域中的無效值,減小變量論域,簡化算法求解的問題,提高求解成功率。實(shí)驗(yàn)結(jié)果表明,本文提出AC-FSADE算法有效地提高了算法的求解成功率,與SADE算法相比求解成功率提高了22%左右。所以,在求解CSPs時,AC-FSADE算法是一種比較有潛力的差分進(jìn)化算法,發(fā)展前景廣闊。
【關(guān)鍵詞】：約束滿足問題 差分進(jìn)化算法 弧相容 自適應(yīng) 參數(shù)調(diào)整 適應(yīng)度
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP18
【目錄】：

• 摘要4-6
• Abstract6-11
• 第1章 緒論11-15
• 1.1 研究背景11-12
• 1.2 研究現(xiàn)狀12-13
• 1.3 本文工作13-15
• 第2章 約束滿足問題與差分進(jìn)化算法15-36
• 2.1 引言15-19
• 2.1.1 約束滿足問題15-18
• 2.1.2 差分進(jìn)化算法18-19
• 2.2 約束滿足問題19-24
• 2.2.1 基本定義20-21
• 2.2.2 約束傳播和搜索21
• 2.2.3 隨機(jī)約束滿足問題21-24
• 2.3 基本差分進(jìn)化算法24-30
• 2.3.1 問題描述25
• 2.3.2 主要流程25-29
• 2.3.3 基本思想29-30
• 2.4 改進(jìn)的自適應(yīng)差分進(jìn)化算法FSADE30-36
• 2.4.1 SADE算法控制參數(shù)的設(shè)置31-32
• 2.4.2 SADE算法控制參數(shù)的改進(jìn)32-33
• 2.4.3 FSADE算法原理33-36
• 第3章 弧相容技術(shù)與AC-FSADE算法36-46
• 3.1 弧相容技術(shù)36-44
• 3.1.1 一般弧相容定義37-39
• 3.1.2 一般弧相容算法39-44
• 3.2 基于弧相容技術(shù)的AC-FSADE算法44-46
• 第4章 AC-FSADE算法求解隨機(jī)CSPs46-52
• 4.1 AC-FSADE算法46-48
• 4.2 實(shí)驗(yàn)結(jié)果及分析48-51
• 4.2.1 實(shí)驗(yàn)設(shè)置48-49
• 4.2.2 實(shí)驗(yàn)結(jié)果及分析49-51
• 4.3 小結(jié)51-52
• 第5章 結(jié)束語52-54
• 5.1 總結(jié)52
• 5.2 展望52-54
• 參考文獻(xiàn)54-58
• 作者簡介58-59
• 致謝59

【相似文獻(xiàn)】

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

1 吳燕玲;盧建剛;孫優(yōu)賢;;基于免疫原理的差分進(jìn)化[J];控制與決策;2007年11期

2 楊啟文;蔡亮;薛云燦;;差分進(jìn)化算法綜述[J];模式識別與人工智能;2008年04期

3 許小健;黃小平;錢德玲;;自適應(yīng)加速差分進(jìn)化算法[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2008年01期

4 寧桂英;周永權(quán);;基于優(yōu)進(jìn)策略的新差分進(jìn)化算法動力學(xué)模型參數(shù)的估計[J];計算機(jī)與應(yīng)用化學(xué);2008年05期

5 譚躍;譚冠政;涂立;;一種新的混沌差分進(jìn)化算法[J];計算機(jī)工程;2009年11期

6 王培崇;錢旭;王月;虎曉紅;;差分進(jìn)化計算研究綜述[J];計算機(jī)工程與應(yīng)用;2009年28期

7 肖術(shù)駿;朱學(xué)峰;;一種改進(jìn)的快速高效的差分進(jìn)化算法[J];合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版);2009年11期

8 周蕭;王萬良;徐新黎;;解決作業(yè)車間調(diào)度問題的混合差分進(jìn)化算法[J];輕工機(jī)械;2010年05期

9 王艷宜;;改進(jìn)差分進(jìn)化算法及其應(yīng)用[J];機(jī)械設(shè)計與研究;2010年05期

10 張照生;羅健旭;;基于差分進(jìn)化算法的模糊神經(jīng)網(wǎng)絡(luò)控制器[J];計算機(jī)與應(yīng)用化學(xué);2011年12期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 陸絲馨;肖健梅;王錫淮;;基于改進(jìn)差分進(jìn)化算法的艦船電網(wǎng)重構(gòu)[A];第二十九屆中國控制會議論文集[C];2010年

2 樓洋;李均利;陳剛;;基于個體排序的差分進(jìn)化算法[A];'2010系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會議論文集[C];2010年

3 張倩;李海港;;多目標(biāo)問題的差分進(jìn)化算法研究[A];2009年中國智能自動化會議論文集（第一分冊）[C];2009年

4 裴振奎;劉真;趙艷麗;;差分進(jìn)化算法在多目標(biāo)路徑規(guī)劃中的應(yīng)用[A];中國運(yùn)籌學(xué)會模糊信息與模糊工程分會第五屆學(xué)術(shù)年會論文集[C];2010年

5 劉國帥;楊侃;陳靜;周景舒;周冉;鄭姣;;差分進(jìn)化算法在三峽電站廠內(nèi)經(jīng)濟(jì)運(yùn)行中的應(yīng)用[A];中國水文科技新發(fā)展——2012中國水文學(xué)術(shù)討論會論文集[C];2012年

6 劉瀟;桂衛(wèi)華;王雅琳;王曉麗;陽春華;;一種改進(jìn)的多目標(biāo)差分進(jìn)化算法研究[A];中國自動化學(xué)會中南六�。▍^(qū)）2010年第28屆年會·論文集[C];2010年

7 趙娟;蔡濤;鄧方;楊紅偉;;基于改進(jìn)差分進(jìn)化算法的脈沖控制方法[A];中國自動化學(xué)會控制理論專業(yè)委員會B卷[C];2011年

8 袁沈堅;顧幸生;;基于差分進(jìn)化的膜計算優(yōu)化算法[A];上海市化學(xué)化工學(xué)會2010年度學(xué)術(shù)年會論文集（自動化專題）[C];2010年

9 姜立強(qiáng);郭錚;劉光斌;;差分進(jìn)化算法縮放因子取值策略研究[A];2007'儀表，自動化及先進(jìn)集成技術(shù)大會論文集（二）[C];2007年

10 倪惠康;杜文莉;錢鋒;;基于改進(jìn)差分進(jìn)化算法的PID參數(shù)優(yōu)[A];2009年中國智能自動化會議論文集（第一分冊）[C];2009年

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

1 孫浩;差分進(jìn)化多目標(biāo)優(yōu)化算法及其在鋁熱連軋軋制規(guī)程中應(yīng)用[D];燕山大學(xué);2015年

2 陳盈果;面向任務(wù)的快速響應(yīng)空間衛(wèi)星部署優(yōu)化設(shè)計方法研究[D];國防科學(xué)技術(shù)大學(xué);2014年

3 謝宇;差分進(jìn)化的若干問題及其應(yīng)用研究[D];南京理工大學(xué);2015年

4 丁青鋒;基于元胞自動機(jī)的差分進(jìn)化算法及其在通信系統(tǒng)中的應(yīng)用研究[D];上海大學(xué);2015年

5 賈東立;改進(jìn)的差分進(jìn)化算法及其在通信信號處理中的應(yīng)用研究[D];上海大學(xué);2011年

6 劉榮輝;多階段自適應(yīng)差分進(jìn)化算法及應(yīng)用研究[D];東華大學(xué);2012年

7 郭鵬;差分進(jìn)化算法改進(jìn)研究[D];天津大學(xué);2012年

8 王旭;改進(jìn)差分進(jìn)化算法及其在可逆邏輯綜合中的應(yīng)用[D];東華大學(xué);2013年

9 董明剛;基于差分進(jìn)化的優(yōu)化算法及應(yīng)用研究[D];浙江大學(xué);2012年

10 王天意;大地電磁迭代有限元與改進(jìn)差分進(jìn)化正反演算法研究[D];中國地質(zhì)大學(xué)(北京);2015年

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

1 高靜;量子差分進(jìn)化算法在油田開發(fā)中的應(yīng)用研究[D];浙江大學(xué);2015年

2 萬婧;基于離散微粒群算法和混合差分進(jìn)化算法的復(fù)雜生產(chǎn)調(diào)度問題求解[D];昆明理工大學(xué);2015年

3 張轉(zhuǎn);基于差分進(jìn)化算法的混凝土德拜模型的研究[D];長安大學(xué);2015年

4 江華;差分進(jìn)化算法的改進(jìn)及其在K-means聚類算法中的應(yīng)用[D];華中師范大學(xué);2015年

5 周志剛;基于差分進(jìn)化算法的信用風(fēng)險度量模型研究[D];華中師范大學(xué);2015年

6 任甜甜;差分進(jìn)化算法在反演問題中的研究與應(yīng)用[D];新疆大學(xué);2015年

7 楊洋;基于差分進(jìn)化的模糊C-均值聚類算法研究[D];電子科技大學(xué);2015年

8 王丹;基于輔助函數(shù)的自適應(yīng)差分進(jìn)化算法研究[D];西安電子科技大學(xué);2014年

9 劉家華;基于進(jìn)化計算的軋制生產(chǎn)過程操作優(yōu)化算法與系統(tǒng)開發(fā)[D];東北大學(xué);2013年

10 王旦平;圓形對稱振子陣列天線基于差分進(jìn)化算法的綜合[D];西安電子科技大學(xué);2014年

  本文關(guān)鍵詞：基于差分進(jìn)化的約束求解算法研究，，由筆耕文化傳播整理發(fā)布。

本文編號：254825