本文關(guān)鍵詞：基于蟻群算法的約束求解

  更多相關(guān)文章： 約束滿足問題 弧相容 蟻群算法 TSP問題

【摘要】：約束滿足問題是人工智能中一個(gè)非常重要的分支,現(xiàn)實(shí)中很多問題都可以被抽象成用約束算法來解決的問題,向生產(chǎn)調(diào)度和資源配置就常用約束算法來求解,在實(shí)際問題中問題的規(guī)模可能會(huì)非常大,也肯能是NP難問題,如果用傳統(tǒng)的方法可能很難在在合理的時(shí)間內(nèi)得到滿意的解,而約束求解算法在解決這類問題時(shí)有著很高的效率,約束算法中常用的是回溯算法如MAC算法,在回溯算法中也會(huì)嵌入弧相容的算法,弧相容是用來刪除一些不相容的值,來壓縮解空間,從而提高求解效率。通過仿生學(xué)的研究,人們發(fā)現(xiàn)個(gè)體行為簡(jiǎn)單的螞蟻可以在沒有群體指揮的情況下完成復(fù)雜的任務(wù),通過進(jìn)一步的研究發(fā)現(xiàn)螞蟻通過釋放信息素來完成合作交流的。在這個(gè)過程的啟發(fā)下意大利學(xué)者M(jìn).Dorigo,V.Maniezzo等人提出了蟻群算法,由于蟻群的覓食過程和TSP問題很相似,所以蟻群算法通常用來解決TSP問題。同樣蟻群算法也被用于生產(chǎn)調(diào)度,組合優(yōu)化,數(shù)據(jù)挖掘等領(lǐng)域。約束求解技術(shù)雖然在求解約束滿足問題時(shí)有著很好的效率,但在實(shí)際問題中,如果問題規(guī)模很大,對(duì)時(shí)間的要求很高,使用回溯算法和相容性技術(shù)需要更多的時(shí)間,但如果使用蟻群算法來求解約束滿足問題,因?yàn)椴恍枰厮菀矝]有因使用相容性技術(shù)簡(jiǎn)化網(wǎng)絡(luò)時(shí)所帶來的巨大的時(shí)間開銷,所以求解效率會(huì)更高。本文以約束求解算法和基本的蟻群算法為基礎(chǔ),使用蟻群算法來求解約束滿足問題。(1)本文分析討論了算法框架MAC,和嵌入在MAC算法中的一些弧相容算法,如AC3,AC4,AC6,AC2001算法,分析解釋了MAC算法如何回溯和如何選擇分支策略,AC3,AC4,AC6,AC2001算法檢查方式和檢查次數(shù)有關(guān)的各自具有的數(shù)據(jù)結(jié)構(gòu)。介紹了蟻群算法的原理和基本蟻群算法求解TSP問題。(2)將適用于約束求解的benchmark數(shù)據(jù)建立成相應(yīng)的TSP問題的模型,把每個(gè)變量的變量值映射成TSP問題中的一個(gè)城市,螞蟻在爬行的時(shí)候并不會(huì)走完每個(gè)城市,只會(huì)走每個(gè)變量的一個(gè)值(3)螞蟻在對(duì)下一個(gè)節(jié)點(diǎn)進(jìn)行選擇時(shí)所遵循的概率公式會(huì)有所不同,本文提出了兩個(gè)公式,公式一螞蟻只遵循信息素濃度,公式二中會(huì)有信息素濃度因素,但同樣會(huì)有想基本蟻群算法概率公式中的距離這種局部因素,這里的局部因素是待選擇節(jié)點(diǎn)與螞蟻已走過節(jié)點(diǎn)之間所增加的沖突數(shù)。(4)通過與MAC-AC3算法進(jìn)行對(duì)比,說明了算法的有效性。
【關(guān)鍵詞】：約束滿足問題 弧相容 蟻群算法 TSP問題
【學(xué)位授予單位】：長春工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18
【目錄】：

• 摘要3-4
• Abstract4-7
• 第一章 緒論7-12
• 1.1 研究背景及現(xiàn)狀7-10
• 1.2 本文主要工作10-12
• 第二章 約束滿足問題基本算法12-26
• 2.1 約束滿足問題相關(guān)概念12-13
• 2.2 AC3算法13-15
• 2.3 MAC算法15-18
• 2.4 AC4算法18-20
• 2.5 AC6算法20-23
• 2.6 AC2001算法23-25
• 2.7 AC算法的比較25-26
• 第三章 蟻群算法研究26-37
• 3.1 蟻群算法的提出26
• 3.2 蟻群算法的基本原理26-32
• 3.2.1 螞蟻的覓食行為和覓食策略26-29
• 3.2.2 蟻群算法的原理分析29-30
• 3.2.3 人工蟻和真實(shí)螞蟻的異同30-32
• 3.3 基本蟻群算法32-35
• 3.4 基本蟻群算法求解TSP問題35-37
• 第四章 基于蟻群算法的約束求解37-43
• 4.1 約束網(wǎng)絡(luò)建模37-40
• 4.2 算法描述40-43
• 第五章 實(shí)驗(yàn)結(jié)果及分析43-48
• 致謝48-49
• 參考文獻(xiàn)49-52
• 作者簡(jiǎn)介52
• 攻讀碩士學(xué)位期間研究成果52

【相似文獻(xiàn)】

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

1 葛磊;武芳;王鵬波;張冬林;;3維建筑綜合中基于最小特征的面平移算法[J];測(cè)繪科學(xué)技術(shù)學(xué)報(bào);2009年02期

2 駱雯,孫延明,陳振威,陳錦昌;判斷點(diǎn)與封閉多邊形相對(duì)關(guān)系的改進(jìn)算法[J];機(jī)械;1999年03期

3 李林;盧顯良;;一種基于切割映射的規(guī)則沖突消除算法[J];電子學(xué)報(bào);2008年02期

4 劉巧玲;張紅英;林茂松;;一種簡(jiǎn)單快速的圖像去霧算法[J];計(jì)算機(jī)應(yīng)用與軟件;2013年07期

5 林亞平,楊小林;快速概率分析進(jìn)化算法及其性能研究[J];電子學(xué)報(bào);2001年02期

6 章郡鋒;吳曉紅;黃曉強(qiáng);何小海;;基于暗原色先驗(yàn)去霧的改進(jìn)算法[J];電視技術(shù);2013年23期

7 楊鐵軍;靳婷;;一種動(dòng)態(tài)整周模糊值求解算法及其仿真分析[J];系統(tǒng)工程與電子技術(shù);2007年01期

8 周秀玲;郭平;陳寶維;王靜;;幾種計(jì)算超體積算法的比較研究[J];計(jì)算機(jī)工程;2011年03期

9 吳一戎,胡東輝,彭海良;Chirp Scaling SAR成象算法及其實(shí)現(xiàn)[J];電子科學(xué)學(xué)刊;1995年03期

10 王貴竹;一種產(chǎn)生單向分解值的算法[J];安徽大學(xué)學(xué)報(bào)(自然科學(xué)版);2001年03期

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

1 尹冀鋒;;一種新的圖象自適應(yīng)增強(qiáng)算法[A];四川省通信學(xué)會(huì)一九九二年學(xué)術(shù)年會(huì)論文集[C];1992年

2 寧春平;田家瑋;郭延輝;王影;張英濤;鄭桂霞;劉研;;計(jì)算機(jī)輔助增強(qiáng)、分割算法在鑒別乳腺良、惡性腫塊中的應(yīng)用價(jià)值[A];中華醫(yī)學(xué)會(huì)第十次全國超聲醫(yī)學(xué)學(xué)術(shù)會(huì)議論文匯編[C];2009年

3 謝麗聰;;SVB查詢改寫算法的改進(jìn)[A];第二十一屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2004年

4 鄭存紅;;復(fù)雜背景下相關(guān)跟蹤算法研究及DSP實(shí)現(xiàn)[A];中國光學(xué)學(xué)會(huì)2010年光學(xué)大會(huì)論文集[C];2010年

5 楊文杰;吳軍;;RFID抗沖突算法研究[A];2008通信理論與技術(shù)新進(jìn)展——第十三屆全國青年通信學(xué)術(shù)會(huì)議論文集（上）[C];2008年

6 高山;畢篤彥;魏娜;;一種基于UPF的小目標(biāo)TBD算法[A];第十四屆全國圖象圖形學(xué)學(xué)術(shù)會(huì)議論文集[C];2008年

7 周磊;張衛(wèi)華;王曉奇;張軍;;基于流水算法的智能路障機(jī)器人設(shè)計(jì)[A];2011年全國電子信息技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2011年

8 潘巍;李戰(zhàn)懷;陳群;索博;李衛(wèi)榜;;面向MapReduce的非對(duì)稱分片復(fù)制連接算法優(yōu)化技術(shù)研究[A];第29屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（B輯）（NDBC2012）[C];2012年

9 李偉偉;蔡康穎;鄭新;王文成;;3D模型中重復(fù)結(jié)構(gòu)的多尺度快速檢測(cè)算法[A];第六屆和諧人機(jī)環(huán)境聯(lián)合學(xué)術(shù)會(huì)議（HHME2010)、第19屆全國多媒體學(xué)術(shù)會(huì)議（NCMT2010）、第6屆全國人機(jī)交互學(xué)術(shù)會(huì)議（CHCI2010）、第5屆全國普適計(jì)算學(xué)術(shù)會(huì)議（PCC2010）論文集[C];2010年

10 楊任爾;陳懇;勵(lì)金祥;;基于棱邊方向檢測(cè)的運(yùn)動(dòng)自適應(yīng)去隔行算法[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

中國重要報(bào)紙全文數(shù)據(jù)庫 前1條

1 國泰君安資產(chǎn)管理部;“算法交易”是道指暴跌罪魁禍?zhǔn)?[N];上海證券報(bào);2010年

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

1 馮輝;網(wǎng)絡(luò)化的并行與分布式優(yōu)化算法研究及應(yīng)用[D];復(fù)旦大學(xué);2013年

2 許玉杰;云計(jì)算環(huán)境下海量數(shù)據(jù)的并行聚類算法研究[D];大連海事大學(xué);2014年

3 李琰;基于貓群算法的高光譜遙感森林類型識(shí)別研究[D];東北林業(yè)大學(xué);2015年

4 陳加順;海洋環(huán)境下聚類算法的研究[D];南京航空航天大學(xué);2014年

5 王洋;基于群體智能的通信網(wǎng)絡(luò)告警關(guān)聯(lián)規(guī)則挖掘算法研究[D];太原理工大學(xué);2015年

6 雷雨;面向考試時(shí)間表問題的啟發(fā)式進(jìn)化算法研究[D];西安電子科技大學(xué);2015年

7 熊霖;大數(shù)據(jù)下的數(shù)據(jù)選擇與學(xué)習(xí)算法研究[D];西安電子科技大學(xué);2015年

8 周雷;基于圖結(jié)構(gòu)的目標(biāo)檢測(cè)與分割算法研究[D];上海交通大學(xué);2014年

9 王冰;人工蜂群算法的改進(jìn)及相關(guān)應(yīng)用的研究[D];北京理工大學(xué);2015年

10 蔣亦樟;多視角和遷移學(xué)習(xí)識(shí)別方法和智能建模研究[D];江南大學(xué);2015年

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

1 姚鑫宇;EMD去噪與MUSIC算法在DOA估計(jì)中的聯(lián)合應(yīng)用[D];昆明理工大學(xué);2015年

2 陸進(jìn);面向含噪數(shù)據(jù)聚類相關(guān)算法的研究[D];復(fù)旦大學(xué);2014年

3 李家昌;基于能量約束的超聲圖像自動(dòng)分割算法[D];華南理工大學(xué);2015年

4 陳堅(jiān);基于密度和約束的數(shù)據(jù)流聚類算法研究[D];蘭州大學(xué);2015年

5 高健;基于Zynq7000平臺(tái)的去霧算法研究及實(shí)現(xiàn)[D];南京理工大學(xué);2015年

6 顧磊;基于Hadoop的聚類算法的數(shù)據(jù)優(yōu)化及其應(yīng)用研究[D];南京信息工程大學(xué);2015年

7 楊燕霞;基于Hadoop平臺(tái)的并行關(guān)聯(lián)規(guī)則挖掘算法研究[D];四川師范大學(xué);2015年

8 王羽;基于MapReduce的社區(qū)發(fā)現(xiàn)算法的設(shè)計(jì)與實(shí)現(xiàn)[D];南京理工大學(xué);2015年

9 許振佳;流式數(shù)據(jù)的并行聚類算法研究[D];曲阜師范大學(xué);2015年

10 董琴;人工蜂群算法的改進(jìn)與應(yīng)用[D];大連海事大學(xué);2015年

，

本文編號(hào)：534448