本文關(guān)鍵詞：基于啟發(fā)式搜索的靈活規(guī)劃的算法研究，由筆耕文化傳播整理發(fā)布。

《吉林大學(xué)》 2013年

基于圖規(guī)劃和啟發(fā)式搜索的一致性規(guī)劃求解

李大為  

【摘要】：智能規(guī)劃是人工智能研究領(lǐng)域的一個(gè)非常重要的分支，是人工智能領(lǐng)域內(nèi)較早的研究方向之一。智能規(guī)劃依據(jù)對(duì)領(lǐng)域內(nèi)知識(shí)的和所給目標(biāo)的分析，對(duì)資源約束和可供選擇的操作進(jìn)行推理，最終得出到達(dá)目標(biāo)的動(dòng)作序列。智能規(guī)劃的研究早期，為了簡(jiǎn)化問(wèn)題和加強(qiáng)對(duì)規(guī)劃問(wèn)題的針對(duì)性，對(duì)智能規(guī)劃的問(wèn)題做出了若干假設(shè)，即所謂經(jīng)典規(guī)劃。不過(guò)這些假設(shè)對(duì)于現(xiàn)實(shí)世界的問(wèn)題過(guò)于嚴(yán)格，為了使智能規(guī)劃能夠得到更為廣泛的應(yīng)用，破除這些限制的諸多類(lèi)型的規(guī)劃，如：一致性規(guī)劃，，概率規(guī)劃，靈活規(guī)劃等便隨之產(chǎn)生。 一致性規(guī)劃任務(wù)是指在初始狀態(tài)和動(dòng)作效果存在不確定性條件下，并且在規(guī)劃執(zhí)行過(guò)程中智能體沒(méi)有任何感知能力的規(guī)劃任務(wù)。生成的規(guī)劃解應(yīng)該在任何可能的初始狀態(tài)下都能達(dá)到規(guī)劃目標(biāo)。一致性規(guī)劃可以轉(zhuǎn)化成信念狀態(tài)空間下的搜索問(wèn)題。其中信念狀態(tài)空間包含的元素包含任何可能的真實(shí)世界狀態(tài)。 在經(jīng)典規(guī)劃中，應(yīng)用松弛規(guī)劃圖作為啟發(fā)式的方法的FF經(jīng)典規(guī)劃器被證明是成功的，這里的松弛指的是忽略動(dòng)作的刪除效果，即刪除表為空。然后對(duì)初始狀態(tài)和沒(méi)有刪除效果的動(dòng)作，進(jìn)行正向搜索，得到一個(gè)松弛規(guī)劃解，解的長(zhǎng)度即我們要得到的啟發(fā)值。對(duì)于一致性規(guī)劃，由于不確定性的存在和規(guī)劃復(fù)雜度的提高，Conformant-FF規(guī)劃器對(duì)于FF規(guī)劃器中的“松弛”做了進(jìn)一步的擴(kuò)展，對(duì)于每個(gè)規(guī)劃動(dòng)作的CNF范式只保留2個(gè)命題，即2-CNF，雖然這種表示忽略了松弛的正確性，不過(guò)最終的整個(gè)的規(guī)劃算法是完備且健全的。這種松弛雖然保證了基于圖規(guī)劃的啟發(fā)式的產(chǎn)生的時(shí)間效率，不過(guò)由于范式中命題選擇的盲目性和命題數(shù)量的大幅度減少，導(dǎo)致啟發(fā)式的產(chǎn)生質(zhì)量存在很大的問(wèn)題。 根據(jù)A*算法的性質(zhì)，我們知道如果一個(gè)可采納的啟發(fā)式方法得到的啟發(fā)解越接近最優(yōu)解，則含有的信息的啟發(fā)能力越強(qiáng)，反之則啟發(fā)能力越弱。本文通過(guò)對(duì)Conformant-FF中松弛規(guī)劃圖啟發(fā)式的分析，提出了求解一致性規(guī)劃問(wèn)題的一種新的解決辦法，通過(guò)降低conformant-FF中對(duì)動(dòng)作的松弛程度，將對(duì)動(dòng)作的松弛改進(jìn)成3-CNF,4-CNF來(lái)提高啟發(fā)式的質(zhì)量，并將這種啟發(fā)式應(yīng)用于信念狀態(tài)空間的搜索過(guò)程當(dāng)中，通過(guò)實(shí)驗(yàn)對(duì)這種啟發(fā)式的啟發(fā)值的準(zhǔn)確程度和搜索效率與C-FF規(guī)劃器相比較,并對(duì)這種基于松弛規(guī)劃圖的啟發(fā)式方法的一些建議。實(shí)驗(yàn)結(jié)果表明采用3-CNF,4-CNF的動(dòng)作松弛方法得到的啟發(fā)值更接近真實(shí)解，說(shuō)明這兩種啟發(fā)式得到啟發(fā)值的啟發(fā)能力要強(qiáng)于conformant-FF中的2-CNF動(dòng)作松弛方法。

【關(guān)鍵詞】：
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類(lèi)號(hào)】：TP18;O221
【目錄】：

下載全文 更多同類(lèi)文獻(xiàn)

CAJ全文下載

(如何獲取全文？ 歡迎：購(gòu)買(mǎi)知網(wǎng)充值卡、在線充值、在線咨詢)

CAJViewer閱讀器支持CAJ、PDF文件格式

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前1條

1 丁德路;姜云飛;;智能規(guī)劃及其應(yīng)用的研究[J];計(jì)算機(jī)科學(xué);2002年02期

【共引文獻(xiàn)】

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

1 孫偉;;智能規(guī)劃與規(guī)劃識(shí)別在網(wǎng)絡(luò)教學(xué)技術(shù)中的應(yīng)用研究芻議[J];長(zhǎng)春大學(xué)學(xué)報(bào);2010年02期

2 谷文祥,孫鐵利,呂英華;智能規(guī)劃中互斥動(dòng)作延遲算法[J];東北師大學(xué)報(bào)(自然科學(xué)版);2003年03期

3 谷文祥;劉科成;;帶有規(guī)劃庫(kù)的規(guī)劃器設(shè)計(jì)模型研究[J];東北師大學(xué)報(bào)(自然科學(xué)版);2007年04期

4 劉日仙;袁利永;谷文祥;;智能規(guī)劃學(xué)習(xí)和學(xué)習(xí)型智能規(guī)劃系統(tǒng)架構(gòu)研究[J];東北師大學(xué)報(bào)(自然科學(xué)版);2010年02期

5 李楊;宋克非;;用智能規(guī)劃解空間樹(shù)法生成測(cè)試數(shù)據(jù)[J];光學(xué)精密工程;2011年07期

6 黃平;李暉;韓豐;馮建雷;;電網(wǎng)智能規(guī)劃系統(tǒng)技術(shù)[J];華東電力;2012年01期

7 李麗;沈湘衡;魏穎;任佳閱;王大勇;;一種改進(jìn)的規(guī)劃器算法在軍用軟件GUI測(cè)試用例自動(dòng)生成中的應(yīng)用[J];解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年03期

8 李楊;陳佳豫;韓誠(chéng)山;孫焱;谷文祥;;基于啟發(fā)式搜索的靈活規(guī)劃的算法研究與系統(tǒng)實(shí)現(xiàn)[J];計(jì)算機(jī)科學(xué);2008年04期

9 史晶晶;劉大有;蔡敦波;呂帥;江鴻;;基于多值表示的并行規(guī)劃方法[J];計(jì)算機(jī)科學(xué);2009年09期

10 江鴻;劉大有;呂帥;蔡敦波;史晶晶;;命題編碼中公理的組合與設(shè)計(jì)[J];計(jì)算機(jī)科學(xué);2009年10期

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

1 劉偉;對(duì)地觀測(cè)衛(wèi)星任務(wù)規(guī)劃模型與算法研究[D];中國(guó)科學(xué)院研究生院（空間科學(xué)與應(yīng)用研究中心）;2008年

2 李麗;航天相機(jī)主控軟件測(cè)試用例自動(dòng)生成技術(shù)的研究[D];中國(guó)科學(xué)院研究生院（長(zhǎng)春光學(xué)精密機(jī)械與物理研究所）;2010年

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

1 劉鴻亮;基于啟發(fā)值的圖規(guī)劃算法[D];吉林大學(xué);2011年

2 程爽;聯(lián)合啟發(fā)式求解優(yōu)先約束問(wèn)題[D];東北師范大學(xué);2011年

3 高志升;基于多Agent的語(yǔ)義Web服務(wù)自動(dòng)組合方法的研究[D];西華大學(xué);2006年

4 蔡增玉;圖規(guī)劃框架下創(chuàng)建/刪除對(duì)象規(guī)劃的研究及實(shí)現(xiàn)[D];東北師范大學(xué);2006年

5 董軼群;一種基于目標(biāo)驅(qū)動(dòng)理論的應(yīng)對(duì)規(guī)劃方法[D];東北師范大學(xué);2007年

6 王艷;帶有并行動(dòng)作的概率規(guī)劃算法的研究[D];東北師范大學(xué);2007年

7 馮宇軒;基于分層規(guī)劃的柔性和一致性規(guī)劃求解[D];吉林大學(xué);2008年

8 溫立紅;前向狀態(tài)空間搜索中并行規(guī)劃算法的研究及實(shí)現(xiàn)[D];東北師范大學(xué);2008年

9 蘇衛(wèi)華;增量式動(dòng)態(tài)概率規(guī)劃的研究[D];東北師范大學(xué);2008年

10 尹吉麗;基于完全目標(biāo)圖的對(duì)手規(guī)劃識(shí)別方法[D];東北師范大學(xué);2008年

【相似文獻(xiàn)】

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

1 李德仁,肖平;利用人工智能方法進(jìn)行粗差的啟發(fā)式搜索[J];測(cè)繪學(xué)報(bào);1990年04期

2 張志明,王越,陶然,閻飛,周思永;基于時(shí)間Petri網(wǎng)和啟發(fā)式搜索的資源分配(英文)[J];Journal of Beijing Institute of Technology;2000年02期

3 吉艷霞;;一種基于遺傳算法的北京公共交通選乘問(wèn)題的啟發(fā)式算法[J];運(yùn)城學(xué)院學(xué)報(bào);2008年05期

4 張偉;基于多項(xiàng)式逼近的學(xué)習(xí)式搜索[J];遼寧大學(xué)學(xué)報(bào)(自然科學(xué)版);1995年S1期

5 楊勇;劉弘;楊峰;;一種優(yōu)化排料方法及其數(shù)學(xué)描述[J];山東科學(xué);2006年04期

6 張偉;洪聲貴;;學(xué)習(xí)式搜索:一種新的搜索策略[J];遼寧大學(xué)學(xué)報(bào)(自然科學(xué)版);1992年04期

7 張燕,袁書(shū)卿,魯漢榕;一種使用啟發(fā)式搜索優(yōu)化的模糊規(guī)則分類(lèi)方法[J];計(jì)算機(jī)工程與應(yīng)用;2004年01期

8 王德忠,劉紅,王魯川;一種啟發(fā)式的自適應(yīng)圖像邊緣檢測(cè)方法[J];遼寧大學(xué)學(xué)報(bào)(自然科學(xué)版);1999年03期

9 許福永,梅中磊;基于現(xiàn)代超啟發(fā)式搜索方法的計(jì)算機(jī)通信網(wǎng)絡(luò)中路由選擇優(yōu)化的研究[J];蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版);2001年02期

10 劉潤(rùn),戎建剛;自動(dòng)布線中的一種有效的搜索算法[J];哈爾濱工業(yè)大學(xué)學(xué)報(bào);1987年02期

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

1 趙慶杞;楊東升;張化光;;基于地理信息系統(tǒng)的配電檢修最優(yōu)路徑的算法研究[A];2004中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];2004年

2 黃宇純;王樹(shù)青;王驥程;;間歇生產(chǎn)過(guò)程規(guī)劃問(wèn)題的智能優(yōu)化模型[A];1995年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議暨智能自動(dòng)化專(zhuān)業(yè)委員會(huì)成立大會(huì)論文集（下冊(cè)）[C];1995年

3 蔡陽(yáng)波;鄧一貴;王康;;并發(fā)啟發(fā)式搜索蛙跳算法[A];2008'中國(guó)信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（一）[C];2008年

4 王家廞;;生產(chǎn)調(diào)度的沖突對(duì)排序方法[A];1995年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議暨智能自動(dòng)化專(zhuān)業(yè)委員會(huì)成立大會(huì)論文集（下冊(cè)）[C];1995年

5 盛穎璞;毛衛(wèi)寧;;基于啟發(fā)式搜索的線譜跟蹤技術(shù)[A];水下聲系統(tǒng)會(huì)議論文集[C];2006年

6 董銀文;王航宇;李鵬;;噪聲圖象中提取邊緣的邊緣分段自增強(qiáng)算法[A];第十三屆全國(guó)圖象圖形學(xué)學(xué)術(shù)會(huì)議論文集[C];2006年

7 陳媛媛;施鵬飛;;基于啟發(fā)式搜索的運(yùn)動(dòng)圖像匹配[A];第十一屆中國(guó)體視學(xué)與圖像分析學(xué)術(shù)會(huì)議論文集[C];2006年

8 馬春紅;葉繼昌;王小平;楊兵;;前視紅外圖像中機(jī)場(chǎng)的自動(dòng)識(shí)別[A];2006年全國(guó)光電技術(shù)學(xué)術(shù)交流會(huì)會(huì)議文集（D 光電信息處理技術(shù)專(zhuān)題）[C];2006年

9 楊淮清;閔亞?wèn)|;張琳琳;;一種基于橡皮筋拉緊的全國(guó)公路網(wǎng)行車(chē)分層規(guī)劃研究[A];中國(guó)電子學(xué)會(huì)第十六屆信息論學(xué)術(shù)年會(huì)論文集[C];2009年

10 耿沿鋒;康凱;王宏;;基于啟發(fā)式搜索的半導(dǎo)體集束設(shè)備調(diào)度[A];2007'儀表，自動(dòng)化及先進(jìn)集成技術(shù)大會(huì)論文集（一）[C];2007年

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

1 程鴻興 張宇;[N];中國(guó)計(jì)算機(jī)報(bào);2008年

2 內(nèi)蒙古建設(shè)銀行包頭分行 薛志強(qiáng);[N];網(wǎng)絡(luò)世界;2002年

3 ;[N];計(jì)算機(jī)世界;2001年

4 本報(bào)記者 筱林;[N];中國(guó)信息報(bào);2000年

5 陳翔;[N];中國(guó)計(jì)算機(jī)報(bào);2007年

6 ;[N];中國(guó)計(jì)算機(jī)報(bào);2001年

7 本報(bào)記者 汪挺;[N];中國(guó)商報(bào);2009年

8 金紅;[N];國(guó)際商報(bào);2009年

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

1 劉洋;成像偵察衛(wèi)星動(dòng)態(tài)重調(diào)度模型、算法及應(yīng)用研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2004年

2 孫小猛;基于模態(tài)觀測(cè)的結(jié)構(gòu)健康監(jiān)測(cè)的傳感器優(yōu)化布置方法研究[D];大連理工大學(xué);2009年

3 蔡敦波;基于啟發(fā)式搜索的智能規(guī)劃方法研究[D];吉林大學(xué);2009年

4 雍愛(ài)霞;仿人機(jī)器人關(guān)節(jié)用永磁球形步進(jìn)電機(jī)的轉(zhuǎn)子位置檢測(cè)及控制策略[D];合肥工業(yè)大學(xué);2007年

5 殷明浩;自動(dòng)推理和智能規(guī)劃中若干問(wèn)題研究[D];吉林大學(xué);2008年

6 廖勝利;面向省級(jí)電網(wǎng)的跨流域水電群優(yōu)化建模與應(yīng)用研究[D];大連理工大學(xué);2009年

7 朱永宣;基于模式識(shí)別的入侵檢測(cè)關(guān)鍵技術(shù)研究[D];北京郵電大學(xué);2006年

8 任小龍;基于Petri網(wǎng)的FMS調(diào)度問(wèn)題研究[D];西安電子科技大學(xué);2010年

9 龍?jiān)评?天基紅外監(jiān)視系統(tǒng)目標(biāo)檢測(cè)與跟蹤技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2012年

10 Okafor Ekene Gabriel;復(fù)雜系統(tǒng)失效率評(píng)估與多目標(biāo)優(yōu)化方法研究[D];南京航空航天大學(xué);2012年

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

1 王改革;一種基于啟發(fā)式搜索的感知圖規(guī)劃算法的研究與實(shí)現(xiàn)[D];東北師范大學(xué);2010年

2 李大為;基于圖規(guī)劃和啟發(fā)式搜索的一致性規(guī)劃求解[D];吉林大學(xué);2013年

3 解瑞飛;基于啟發(fā)式搜索的生物特征辨識(shí)算法研究[D];杭州電子科技大學(xué);2012年

4 董程玲;遺傳連鎖群中分子標(biāo)記排序研究[D];南京林業(yè)大學(xué);2011年

5 王宗原;基于電子地圖的路徑規(guī)劃的設(shè)計(jì)與實(shí)現(xiàn)[D];哈爾濱工程大學(xué);2005年

6 李楊;基于啟發(fā)式搜索的靈活規(guī)劃的算法研究[D];東北師范大學(xué);2006年

7 蔡敦波;基于延遲部分推理的快速前向規(guī)劃系統(tǒng)[D];東北師范大學(xué);2006年

8 韓軍偉;景物邊緣提取技術(shù)的研究與應(yīng)用[D];西北工業(yè)大學(xué);2001年

9 鄭朝明;配電網(wǎng)故障恢復(fù)系統(tǒng)的研究[D];華北電力（北京）大學(xué);2002年

10 高彥明;蟻群算法并行化研究[D];蘇州大學(xué);2005年

  本文關(guān)鍵詞：基于啟發(fā)式搜索的靈活規(guī)劃的算法研究，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：124864