【摘要】：約束滿足問題在人工智能領(lǐng)域有著廣泛的應用。目前有許多求解約束滿足問題的方法,本文對常用的求解約束滿足問題的維持弧相容算法做了改進,對求解約束滿足問題的效率起到至關(guān)重要的兩個部分--弧相容和啟發(fā)式分別做了改進,從兩個方面整體地提高求解約束滿足問題的效率。本文通過分析約束滿足問題的粗粒度維持弧相容求解算法在弧相容(arc containing,AC)的執(zhí)行過程,發(fā)現(xiàn)在對弧的修正檢查算法中存在冗余的弧放回操作,并對弧的冗余放回給出了完整的證明。啟發(fā)式是約束滿足問題求解的一個重要組成部分,它通過一定的策略來選擇并確定變量和值來搜索約束滿足問題的解。目前已有許多成熟的變量啟發(fā)式能夠針對特定的問題屬性進行搜索路徑選擇,但是由于針對性極強,一旦被求解問題針對的特性并不明顯,則相應的啟發(fā)式不能發(fā)揮選擇作用,有時甚至使得問題求解效率下降極大�；诖�,考慮設(shè)計一種魯棒性強的啟發(fā)式,來避免斷崖式的求解效率波動。本文對約束滿足問題求解的改進主要體現(xiàn)在以下兩個方面:(1)在AC3算法的基礎(chǔ)上提出了一種改進算法AC_AO通過保證弧的唯一性來避免冗余弧的放回隊列的操作。這種通過維持弧的唯一性改進弧相容算法的模式可以形成框架并適用于AC系列算法,包括AC3算法、AC2001算法、AC3rm算法,本文將提出的改進算法框架AC_AO應用于AC3、AC2001、AC3rm算法與原算法做實驗對比,實驗結(jié)果表明,應用AC_AO算法框架后的AC系列算法最多可以少檢查77%的弧,最多可以減少30%的CPU求解時間,AC_AO算法通過減少弧的檢查進而減少修正函數(shù)的調(diào)用次數(shù),從而提高AC的執(zhí)行效率,縮短弧相容算法的執(zhí)行時間。將AC_AO算法應用在維持弧相容算法求解的過程中對求解效率提高是非常有意義的。(2)提出了一種基于遺傳選擇的啟發(fā)式方法,能夠針對問題屬性進行自適應地選擇合適啟發(fā)式指導變量選擇。本文對該方法進行了詳細分析與描述,將之與最新版本的Choco求解器中最常用的默認啟發(fā)式domOverWdeg啟發(fā)式、activityBased啟發(fā)式作對比,并且針對遺傳選擇的啟發(fā)式算法,分別做了兩組實驗,一組弧相容算法選擇AC3算法,另一組弧相容算法選擇AC_AO算法,分別進行約束滿足問題的求解,實驗結(jié)果表明在約束滿足問題的求解上,AC_AO算法優(yōu)于AC3算法。基于遺傳選擇的啟發(fā)式算法的求解效率最高是domOverWdeg啟發(fā)式的2.35倍,activityBased啟發(fā)式的2.26倍。在求解效率的魯棒性上也優(yōu)于其他啟發(fā)式算法。
【圖文】：

圖 2.1 原始 CSP 問題示了一個約束滿足問題示例，，此約束滿足問題涉及 3命名，其中 =( , )、 =( , ) 、 =( , )，被 、 ，變量 的論域為{0、1、2}，變量 、 、 表示支持，如 中的值 1 與 中的值 0 互為支持。，0）；對于約束 ，支持的元組為（1，0）、（2，1）；對1，0）、（2，1）。了此 CSP 問題的一組解，即變量 取 1 值，變量 取 取 0 值。

圖 2.1 原始 CSP 問題示了一個約束滿足問題示例，此約束滿足問題涉及 3 個 命名，其中 =( , )、 =( , ) 、 =( , )，被約 、 、 ，變量 的論域為{0、1、2}，變量 、 、 的線表示支持，如 中的值 1 與 中的值 0 互為支持。對1，0）；對于約束 ，支持的元組為（1，0）、（2，1）；對（1，0）、（2，1）。了此 CSP 問題的一組解，即變量 取 1 值，變量 取 量 取 0 值。
【學位授予單位】：吉林大學
【學位級別】：碩士
【學位授予年份】：2019
【分類號】：TP18

【相似文獻】

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

1 陸明;;約束滿足問題在題庫系統(tǒng)中的應用[J];民營科技;2008年04期

2 王俊潔;王俊鑫;桂林斌;;人工智能中感知問題的求解技術(shù)——約束滿足法[J];楚雄師范學院學報;2008年03期

3 郭平;侯睿;楊國洲;范麗;;方位關(guān)系約束滿足問題的推理求解[J];計算機科學;2005年08期

4 李偉,劉光復;一類基于動態(tài)約束滿足問題的產(chǎn)品配置方法[J];機械科學與技術(shù);2005年04期

5 劉洋,陳英武;動態(tài)約束滿足及其在資源調(diào)度問題中的應用[J];計算機工程與應用;2004年27期

6 郭寶龍,郭雷,戴冠中;約束滿足神經(jīng)網(wǎng)絡[J];電子學報;2000年01期

7 孫偉,馬紹漢;約束滿足問題并行弧相容算法[J];計算機工程與科學;1997年01期

8 柏淑琴;;高校排課問題的約束滿足優(yōu)化模型與算法[J];科技視界;2012年18期

9 張泉樂;袁際軍;;非二元約束滿足問題的產(chǎn)品配置建模與求解[J];武漢理工大學學報;2010年01期

10 董存祥;王文俊;楊鵬;;基于約束滿足問題的應急決策[J];計算機工程;2010年07期

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

1 張寶;方圣恩;;基于改進約束滿足問題的結(jié)構(gòu)損傷評估方法[A];第23屆全國結(jié)構(gòu)工程學術(shù)會議論文集（第Ⅲ冊）[C];2014年

2 李海晨;馮玉強;;基于模糊約束滿足問題的談判決策研究[A];第八屆中國管理科學學術(shù)年會論文集[C];2006年

3 張志強;王萬玉;王建平;李凡;袁剛;;多站多星任務調(diào)度優(yōu)化模型研究[A];第二十三屆全國空間探測學術(shù)交流會論文摘要集[C];2010年

相關(guān)博士學位論文 前9條

1 劉濤;約束滿足問題：算法和復雜性[D];中國科學院研究生院（計算技術(shù)研究所）;1994年

2 王秦輝;約束滿足及其分布式求解和應用研究[D];中國科學技術(shù)大學;2007年

3 馮欣;約束滿足技術(shù)的研究及在生產(chǎn)調(diào)度中的應用[D];東北大學;2008年

4 李宏博;約束滿足問題研究及其在蛋白質(zhì)結(jié)構(gòu)預測中的應用[D];吉林大學;2015年

5 徐周波;約束滿足問題的符號算法及其在裝配規(guī)劃中的應用研究[D];西安電子科技大學;2012年

6 韋沙;基于分布式約束滿足算法的無線信道分配研究[D];華中科技大學;2011年

7 沈靜;約束滿足問題的模型構(gòu)造和相變現(xiàn)象[D];華中師范大學;2011年

8 付宏杰;求解二元約束滿足問題的混合差分進化算法研究[D];吉林大學;2011年

9 袁際軍;大規(guī)模定制下基于約束的產(chǎn)品配置方法研究[D];湖南大學;2008年

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

1 王宇星;基于多主體建模與量詞約束滿足的產(chǎn)品質(zhì)量控制研究[D];西南科技大學;2019年

2 王希彤;基于MBO的約束滿足問題求解算法研究[D];吉林大學;2019年

3 楊罡;基于約束滿足問題求解算法的改進算法研究[D];吉林大學;2019年

4 王蓀馨;基于約束滿足技術(shù)的作業(yè)車間調(diào)度問題研究[D];西安理工大學;2007年

5 任雪亮;改進的置信傳播算法在求解最大約束滿足問題的應用[D];東北師范大學;2015年

6 趙利;基于約束滿足問題的配置解釋算法研究[D];吉林大學;2008年

7 李碧濤;基于約束滿足神經(jīng)網(wǎng)絡的作業(yè)車間調(diào)度及應用[D];吉林大學;2006年

8 馬冬梅;約束滿足問題分解算法及其在配置求解中的應用[D];吉林大學;2007年

9 王旭;交互約束滿足問題的沖突解釋算法研究[D];吉林大學;2016年

10 徐亞男;二元約束滿足問題上基于禁止模式刪變量的實現(xiàn)及其優(yōu)化研究[D];吉林大學;2016年

本文編號：2588855