高級(jí)人工智能之約束推理

1、2022-1-29史忠植 高級(jí)人工智能1 第三章 約束推理 2022-1-29史忠植 高級(jí)人工智能2第三章 約束推理3.1 概述3.2 回溯法 3.3 約束傳播 3.4 回跳法 3.5 約束推理系統(tǒng)COPS 3.6 ILOG SOLVER2022-1-29史忠植 高級(jí)人工智能33.1 概述概述 最優(yōu)化問題最優(yōu)化問題經(jīng)濟(jì)學(xué)所推崇的帕累托最優(yōu)經(jīng)濟(jì)學(xué)所推崇的帕累托最優(yōu): :幾個(gè)人拎著水桶在一個(gè)水龍頭前面排隊(duì)打水，水幾個(gè)人拎著水桶在一個(gè)水龍頭前面排隊(duì)打水，水桶有大有小。他們怎樣排隊(duì)，才能使得總的排隊(duì)桶有大有小。他們怎樣排隊(duì)，才能使得總的排隊(duì)時(shí)間最短。這是一個(gè)尋求時(shí)間最短。這是一個(gè)尋求“最優(yōu)化最優(yōu)化”的

2、題目，目標(biāo)的題目，目標(biāo)是節(jié)省總的排隊(duì)時(shí)間，達(dá)到最優(yōu)。是節(jié)省總的排隊(duì)時(shí)間，達(dá)到最優(yōu)。2022-1-29史忠植 高級(jí)人工智能43.1 概述概述 優(yōu)化問題優(yōu)化問題 運(yùn)籌學(xué) 遺傳算法 神經(jīng)網(wǎng)絡(luò) 約束推理2022-1-29史忠植 高級(jí)人工智能5運(yùn)籌學(xué)的工作步驟v1）提出和形成問題，v2）建立模型，v3）求解，v4）解的檢驗(yàn)，v5）解的控制，v6）解的實(shí)施。 2022-1-29史忠植 高級(jí)人工智能6線性規(guī)劃問題 例1(廣告方式的選擇)中華家電公司推銷一種新型洗衣機(jī),有關(guān)數(shù)據(jù)見下表.銷售部第一月的廣告預(yù)算為20000元,要求至少有8電視商業(yè)節(jié)目,15家報(bào)紙廣告/電視廣告費(fèi)不得超過12000元,電臺(tái)廣播至少隔

3、日有一次.現(xiàn)問該公司銷售部應(yīng)當(dāng)采用怎樣的廣告宣傳計(jì)劃,才能取得最好的效果?2022-1-29史忠植 高級(jí)人工智能7表1廣告方式廣告費(fèi)用(元/次)可用最高次數(shù)/月期望的宣傳效果/單位電視臺(tái)a(白天,1 分鐘)5001650電視臺(tái)b(晚上,30鈔)10001080每日晨報(bào)/(半版)1002430星期日報(bào)/(半版)300440廣播電臺(tái)/(1分鐘)8025152022-1-29史忠植 高級(jí)人工智能8解:設(shè)54321,xxxxx分別是第一個(gè)月內(nèi)電視臺(tái) a,電視臺(tái)b,每日晨報(bào),星期日報(bào),廣播電臺(tái)進(jìn)行廣告宣傳的次數(shù),則其數(shù)學(xué)模型為: max 543211540308050 xxxxx s.t. . 0,25

4、15, 4,24,10,16,120001000500,15, 8,20000803001001000500543215432121432154321xxxxxxxxxxxxxxxxxxxxx 2022-1-29史忠植 高級(jí)人工智能9線性規(guī)劃問題(LP)的一般形式為: min(max)2211xcxcznnxc s.t.212111xaxa11),(bxann 222121xaxa22),(bxann 2211xaxammmnmnbxa),( , 2 , 1, 0jxjn 2022-1-29史忠植 高級(jí)人工智能10線性規(guī)劃問題的標(biāo)準(zhǔn)形式為: min XCzT s.t.0XbAX(假定 b 為非

5、負(fù)) 注:任何形式的線性規(guī)劃問題均可化為標(biāo)準(zhǔn)型 2022-1-29史忠植 高級(jí)人工智能11求解-單純形法 將所給問題化為標(biāo)準(zhǔn)形 找出一個(gè)初始可行基,建立初始單純形表 檢查所有檢驗(yàn)數(shù)(若全為非負(fù),則已得到最優(yōu)解,計(jì)算停止.否則繼續(xù)下一步) 考察是否無解(若是,計(jì)算停止,否則繼續(xù)下一步) 確定入基變量,出基變量 對(duì)初始單純形表進(jìn)行單純形變換2022-1-29史忠植 高級(jí)人工智能123.1 概述概述一個(gè)約束滿足問題(Constraint Satisfaction Problem, 簡稱CSP) 包含一組變量與一組變量間的約束。 變量表示領(lǐng)域參數(shù)，每個(gè)變量都有一個(gè)固定的值域。一個(gè)變量的值域可能是有限的

6、，例如一個(gè)布爾變量的值域包含兩個(gè)值；也可能是離散無限的，如整數(shù)域；也可能是連續(xù)的，如實(shí)數(shù)域。 x1,x2,xn, D1,D2,Dn, . 4,5,6,7 red, green,blue 2022-1-29史忠植 高級(jí)人工智能133.1 概述概述 約束可用于描述領(lǐng)域?qū)ο蟮男再|(zhì)、相互關(guān)系、任務(wù)要求、目標(biāo)等。約束 滿足問題 的目標(biāo)就是找到所有變量的一個(gè)（或多個(gè)）賦值，使所有約束都得到滿足。 一元謂詞。 序關(guān)系語言，只包含偏序關(guān)系或?qū)嵶兞可系拇笮￡P(guān)系。 形如“x - y c” 的方程。 單位系數(shù)的線性方程與不等式，即所有的系數(shù)為 -1,0,1。 任意系數(shù)的線性方程與不等式。 約束的布爾組合。 代數(shù)與三

7、角方程。2022-1-29史忠植 高級(jí)人工智能143.1 概述概述約束表示易于理解、編碼及有效實(shí)現(xiàn)，它具有以下優(yōu)點(diǎn): 約束表示允許以說明性的方式來表達(dá)領(lǐng)域知識(shí)，表達(dá)能力較強(qiáng)，應(yīng)用程序只需指定問題的目標(biāo)條件及數(shù)據(jù)間的相互關(guān)系。因而具有邏輯表示的類似性質(zhì)。 約束表示允許變量的域包含任意多個(gè)值，而不像命題 只取真假二值。所以它保存了問題的一些結(jié)構(gòu)信息，如變量域的大小、變量間的相關(guān)性等，從而為問題求解提供啟發(fā)式信息。 易于并行實(shí)現(xiàn)。因?yàn)榧s束網(wǎng)絡(luò)上的信息傳播可以認(rèn)為是同時(shí)的。 適合于遞增型系統(tǒng)。約束可以遞增式地加入到約束網(wǎng)絡(luò)。 易于與領(lǐng)域相關(guān)的問題求解模型相銜接。各種數(shù)學(xué)規(guī)劃技術(shù)，方程求解技術(shù)等, 都可

8、以自然地嵌入約束系統(tǒng)。2022-1-29史忠植 高級(jí)人工智能153.1 約束推理約束推理 約束搜索約束搜索主要研究有限域上的約束滿足。對(duì)有限域而言，約束滿足問題一般情況下是 一個(gè) NP 問題。 約束語言2022-1-29史忠植 高級(jí)人工智能163.1 約束搜索約束搜索 回溯法。 約束傳播。 智能回溯與真值維護(hù)。 可變次序例示。 局部修正法。2022-1-29史忠植 高級(jí)人工智能17約束語言CONSTRAINTSCHIPCOPSILOG2022-1-29史忠植 高級(jí)人工智能18CONSTRAINTS約束語言 CONSTRAINTS是一個(gè)面向電路描述的約束表示語言。作為一個(gè)約束表示語言，它使用了符

9、號(hào)處理技術(shù)來求解數(shù)學(xué)方程。在CONSTRAITS中，物理部件的功能及器件的結(jié)構(gòu)都用約束表示。這些約束一般是線性方程與不等式, 也包括條件表達(dá)式。約束變量一般是表示物理量的實(shí)變量。也有一些取離散值的變量。如開關(guān)的狀態(tài)、三極管的工作狀態(tài)等。系統(tǒng)采用表達(dá)式推理與值推理。并實(shí)現(xiàn)相關(guān)制導(dǎo)的回溯。 2022-1-29史忠植 高級(jí)人工智能19CONSTRAINTS約束語言 CONSTRAINTS 的一個(gè)優(yōu)點(diǎn)是在類型層次中表示約束，用約束來表示物理對(duì)象的功能與結(jié)構(gòu)。其缺點(diǎn)是該語言缺乏類似于面向?qū)ο笳Z言中的方法那樣的成分，不能定義特定于某個(gè)類的概念。同時(shí)，約束傳播方法比較單一，既缺乏實(shí)域上的區(qū)間傳播機(jī)制，也缺乏

10、有限域上的 域傳播機(jī)制。 2022-1-29史忠植 高級(jí)人工智能20約束邏輯程序設(shè)計(jì)語言CHIP CHIP(Constraint handling in Prolog) 就是這樣較有影響一個(gè)約束邏輯程序設(shè)計(jì)語言，其目的是簡便、靈活而有效地解決一大類組合問題。它通過提供幾種新的計(jì)算域而增強(qiáng)邏輯程序設(shè)計(jì)的能力；有限域、布爾項(xiàng)及有理項(xiàng)，對(duì)于每個(gè)計(jì)算域，都提供有效的約束求解技術(shù)，即有限域上的一致性技術(shù)，布爾域的布爾合一技術(shù)及有理數(shù)域上的單純型法。除此以外，CHIP還包含一個(gè)一般的延遲計(jì)算機(jī)制。 CHIP 主要應(yīng)用于兩個(gè)領(lǐng)域: 運(yùn)籌學(xué)與硬件設(shè)計(jì)。 CHIP 缺乏類型機(jī)制，而這種機(jī)制對(duì)于表達(dá)領(lǐng)域概念是極其

11、重要的。2022-1-29史忠植 高級(jí)人工智能21面向?qū)ο蠹s束語言COPS COPS系統(tǒng)利用面向?qū)ο蠹夹g(shù)，將說明性約束表達(dá)與類型層次結(jié)合起來。在形式上吸收了常規(guī)語言，主要是面向?qū)ο蟮某绦蛟O(shè)計(jì)語言的基本形式。內(nèi)部求解時(shí)采用約束推理機(jī)制，使說明性約束表達(dá)式與類型層次相結(jié)合，實(shí)現(xiàn)知識(shí)的結(jié)構(gòu)化封裝，充分發(fā)揮兩者的優(yōu)點(diǎn)，力圖實(shí)現(xiàn)一個(gè)具有較強(qiáng)表達(dá)能力和較高求解效率的約束滿足系統(tǒng)。2022-1-29史忠植 高級(jí)人工智能22面向?qū)ο蠹s束語言COPSCOPS的設(shè)計(jì)考慮了軟件工程的應(yīng)用要求，盡量將一個(gè)不確定問題確定化：它允許條件語句與循環(huán)語句，而不是單純以遞歸的形式來實(shí)現(xiàn)迭代計(jì)算； 通過類方法的重栽實(shí)現(xiàn)同一約束的

12、不同實(shí)現(xiàn)，提高了程序的執(zhí)行效率。COPS系統(tǒng)同時(shí)是一個(gè)漸增式的開放系統(tǒng)，用戶能通過類型層次定義，實(shí)現(xiàn)新的數(shù)據(jù)類型和新的約束關(guān)系。約束語言COPS具有許多人工智能程序設(shè)計(jì)語言的特點(diǎn)，如約束傳播、面向目標(biāo)和數(shù)據(jù)驅(qū)動(dòng)的問題求解、有限步的回溯、對(duì)象分層中的繼承等。 2022-1-29史忠植 高級(jí)人工智能23 在實(shí)際應(yīng)用中，算法的表現(xiàn)形式千變?nèi)f化，但是算法的情況也和數(shù)據(jù)結(jié)構(gòu)類似，許多算法的設(shè)計(jì)思想具有相似之處，我們可以對(duì)它們分類進(jìn)行學(xué)習(xí)和研究。 常用的算法大致有如下一些：貪心法分治法：如二分法檢索回溯法動(dòng)態(tài)規(guī)劃法局部搜索法分支限界法2022-1-29史忠植 高級(jí)人工智能24 算法分析 評(píng)價(jià)一個(gè)程序優(yōu)劣的

13、重要依據(jù)是看這個(gè)程序的執(zhí)行需要占用多少機(jī)器資源。人們最關(guān)心的就是程序所用算法運(yùn)行時(shí)所要花費(fèi)的時(shí)間代價(jià)和程序中使用的數(shù)據(jù)結(jié)構(gòu)占有的空間代價(jià)。 算法的空間代價(jià)算法的空間代價(jià)(或稱空間復(fù)雜性空間復(fù)雜性)：當(dāng)被解決問題的規(guī)模(以某種單位計(jì)算)由1增至n時(shí)，解該問題的算法所需占用的空間也以某種單位由f(1) 增至f(n)，這時(shí)我們稱該算法的空間代價(jià)是f(n)。 算法的時(shí)間代價(jià)算法的時(shí)間代價(jià)(或稱時(shí)間復(fù)雜性時(shí)間復(fù)雜性)：當(dāng)問題規(guī)模以某種單位由1增至n時(shí)，對(duì)應(yīng)算法所耗費(fèi)的時(shí)間也以某種單位由g(1)增至g(n)，這時(shí)我們稱算法的時(shí)間代價(jià)是g(n)。 2022-1-29史忠植 高級(jí)人工智能25窮盡搜索方法窮盡搜

14、索方法窮盡搜索方法 即產(chǎn)生所有可能的樹，然后根據(jù)評(píng)價(jià)標(biāo)準(zhǔn)選擇一棵最優(yōu)的樹。 Exhaustive-Search-Top(P) where P is a CSP of the form(V,D,C)1. f:= the null assignment2. return Exhaustive-Search(f,P)2022-1-29史忠植 高級(jí)人工智能26窮盡搜索方法窮盡搜索方法 Exhaustive-Search(f,P)1. if f is a total assignment of the variables in P2. if f satisfies the constraints in

15、P3. answer := f4. else 5. answer := Unsat6. else 7. v := some variable in P that is not yet assigned a value by f8. answer := Unsat9. for each value while answer = Unsat10. f(v) := 11. answer := Exhaustive-Search(f,P)12. return answer2022-1-29史忠植 高級(jí)人工智能27貪心法貪心法把構(gòu)造可行解的工作分階段來完成。在各個(gè)階段，選擇那些在某些意義下是局部最優(yōu)的方

16、案，期望各階段的局部最優(yōu)的選擇帶來整體最優(yōu)。例：Dijkstra的最短路徑算法、Kruskal的求最小生成樹算法、信號(hào)燈問題2022-1-29史忠植 高級(jí)人工智能28回溯算法回溯算法有些問題需要徹底的搜索才能解決問題，然而，徹底的搜索要以大量的運(yùn)算時(shí)間為代價(jià)，對(duì)于這種情況可以通過回溯法來去掉一些分支，從而大大減少搜索的次數(shù)。 八皇后問題 迷宮問題 深度優(yōu)先周游樹或圖2022-1-29史忠植 高級(jí)人工智能29回溯算法回溯算法 Backtracking-Top(P)1 f := the null assignment2 return Backtracking(f,P)2022-1-29史忠植 高級(jí)

17、人工智能30回溯算法回溯算法 Backtracking(f,P)1 if f is a total assignment of the variables in P2 answer := f3 else 4 v := some variable in P that is not yet assigned a value by f5 answer := Unsat6 for each value while answer = Umsat7 f(v) := x8 if f satisfies the constraints in P9 answer := Backtracking(f,P)10 r

18、eturn answer2022-1-29史忠植 高級(jí)人工智能31回溯算法回溯算法 盡管回溯法好于生成測試法，但對(duì)于非平凡問題仍然是低效的。其原因在于搜索空間中不同路徑的搜索重復(fù)相同的失敗子路徑。一些研究者認(rèn)為，造成這種反復(fù)的原因是所謂的局部不一致性。最簡單的情形是所謂的結(jié)點(diǎn)不一致性。對(duì)一個(gè)變量vi的一個(gè)一元約束。存在域中一個(gè)值vi不滿足該約束。這樣，每當(dāng)vi取到 a 時(shí)就會(huì)出現(xiàn)不一致性。 另一種重復(fù)的情形 是所謂的弧不一致性。2022-1-29史忠植 高級(jí)人工智能323.3 約束傳播CONSTRAINT PROPAGATIONCONSTRAINT PROPAGATION(red, green

19、)(red,blue)(red, green,blue) 弧一致性弧一致性Arc consistency 2022-1-29史忠植 高級(jí)人工智能33弧一致性弧一致性 Arc consistency 如果對(duì)vi 的當(dāng)前域中的所有值x，存在vj的當(dāng)前域中的某值y使得 vi=x和vj=y是vi與vj之間的約束所允許的，則弧(vi, vj)是弧一致的。 弧一致性的概念是有向的。即(vi, vj)是弧一致的并不自動(dòng)地意味著(vj, vi)是一致的。2022-1-29史忠植 高級(jí)人工智能343.3 CONSTRAINT PROPAGATION3.3 CONSTRAINT PROPAGATIONAll of

20、 the Mackworth algorithms make use All of the Mackworth algorithms make use of a Revise procedure.of a Revise procedure. Let Dv be the current domain of v, Let Dv be the current domain of v, Let Dw be the current domain of w, Let Dw be the current domain of w, Let P be the constraint predicate that

21、Let P be the constraint predicate that holds between v and w, then Revise updates holds between v and w, then Revise updates Dv as followsDv as follows: :yxPDDxDwyvv,such that : 2022-1-29史忠植 高級(jí)人工智能35CONSTRAINT PROPAGATIONCONSTRAINT PROPAGATIONMackworth 1977Mackworth 1977 AC-1 AC-1 AC-2AC-2 AC-3 AC-3

22、2022-1-29史忠植 高級(jí)人工智能36約束傳播修改算法約束傳播修改算法REVISE(Vi,Vj)1 DELETE false;2 for each x Di do 3 if there is no such yj Dj4such that(x,yj) is consistent,5 then 6 delete x from Di;7 DELETE true;8 endif 9 endfor 10 return DELETE; 11 end REVISE2022-1-29史忠植 高級(jí)人工智能37AC-11 Q ;2 repeat 3 CHANGE false;4 for each (Vi,

23、Vj) Q do5 CHANGE REVISE(Vi, Vj) CHANGE;6 endfor;7 until not(CHANGE);8 end AC-1 V VGijij, arcs 2022-1-29史忠植 高級(jí)人工智能38AC-31 Q ;2 While Q not empty 3 Select and delete any arc(Vk,Vm) from Q;4 If (REVISE(Vk,Vm) Then Q (Vi,Vk) such that (Vi,Vk)arcs(G), ik, im;6 endfor;7 endwhile;8 end AC-3 V VGijij, arcs

24、2022-1-29史忠植 高級(jí)人工智能39BackjumpingBackjumping-Top(P)1 f := the null assignment2 := Backjumping(f,P)3 return answer2022-1-29史忠植 高級(jí)人工智能40BackjumpingBackjumping(f,P)1 if f is a total assignment of the variables in P2 answer := 3 else 4 v := some variable in P that is not yet assigned a value by f5 answer

25、 := Unsat6 conflict-set := 7 for each value 8 f(v) := x9 if f satisfies the constraints in P10 := Backjumping(f,P)2022-1-29史忠植 高級(jí)人工智能41Backjumping11 else12 new-conflicts := the set of variables in a violated constraint13 if answer Unsat14 return 15 else if v new-conflicts16 return 17 else 18 conflic

26、t-set := conflict-set (new-conflicts v)19 return 2022-1-29史忠植 高級(jí)人工智能42COPS Constraint : predicate expression P(t1, ., tn) where P is built in function, such as sum times eq(equal) neq(not equal) ge(great than or equal to) gt(great than) also can be defined by users2022-1-29史忠植 高級(jí)人工智能43COPS Condition

27、al constraint condition1: constraint1; . . conditionn: constraintn where condition1, ., conditionn are boolean expressions. constraint1,. constraintn are constraints or contraints table. 2022-1-29史忠植 高級(jí)人工智能44COPS RULE Rule is used to define new function, method, predicate, or add new constraint into

28、 object. RULE class: predicate(varibles) (boolean expression)constraint_1;-constraint_n; CASEboolean expression_1: constraint_1; -boolean expression_m: constraint_m; 2022-1-29史忠植 高級(jí)人工智能45COPS For example: RULE multiple(INTEGER: *x, INTEGER: y, INTEGER: z) (neq(y, 0) equal(x, divide(z, y); z = x * y2

29、022-1-29史忠植 高級(jí)人工智能46COPS CLASS class_name:superclass_name / attributes definition date type: attribute_name; . / rule definition rule_name; . /function definition function_name; . / method definition method_name; . 2022-1-29史忠植 高級(jí)人工智能47COPS Implementation Program written by COPS consists of classes

30、and rules. COPS constraint programming language is a declarative language, providing classes, methods which are exist in object oriented language. It is similar with C+ . COPS has the features: constraint object oriented logic programming production system 2022-1-29史忠植 高級(jí)人工智能48COPS COPS_Compiler1 2

31、Call yacc to parse the program and 3 to generate internal structures.4 Initializatiion5 Create Cops Constant trueNode;6 Allocate memories for global variables. 2022-1-29史忠植 高級(jí)人工智能49COPS7 Interprte the program with the internal structures.8 Constraint networks are built up for Unsolved 9 constraints

32、and variables.10 while some constraints in the constraint networks are triggered,11 inteprete the triggered constraints.12 2022-1-29史忠植 高級(jí)人工智能50COPSInterpreter: 1 2 switch (constraint type)3 case Constant:4 return Constant:5 case global variable:6 interprete global variable:7 case local variable or

33、argument:8 interprete local variable or argument:9 case object-attribute pair;10 interprete object-attribute pair:11 case function call:2022-1-29史忠植 高級(jí)人工智能51COPS12 interprete function call:13 case method call:14 interprete method call:15 case CASE expression:16 interprete CASE expression:17 .18 defa

34、ult:20 report error21 2022-1-29史忠植 高級(jí)人工智能52ILOG SOLVERCombines object oriented programming with constraint logic programming, containing logic variables, incremental constraint satisfaction and backtracking. variables : C+ object integer variable CtIntVar floating variable CtFloatVar boolean variabl

35、e CtBoolVarMemory Management new: delete:2022-1-29史忠植 高級(jí)人工智能53ILOG SOLVERConstraints CtTell(x = (y + z); Basic constraints: =, , , , +, -, *, /, subset, superset, union, intersection, member, boolean or, boolean and, boolean not, boolean xor, CtTell(x=0) | (y=0); CtIfThen (x chooseValue(); CtOr(Cons

36、traint(x = a), CtAnd(Constraint(x != a), CtInstantiate(x); 2022-1-29史忠植 高級(jí)人工智能55 ILOG Schedule 1.0Schedule CtSchedule class Global object: time original -tineMin time horizon -timeMax 2022-1-29史忠植 高級(jí)人工智能56 ILOG Schedule 1.0Resources CtResource CtDiscreteResource CtUnaryResource CtDiscreteEnergy CtSt

37、ateResource 2022-1-29史忠植 高級(jí)人工智能57 ILOG Schedule 1.0ActivitiesCtActivityclassCtIntervalActivityAnactivityisdefinedbyitsstarttime,endtimeanddurationActivitiesrequire,provide,consumeandproduceresources2022-1-29史忠植 高級(jí)人工智能58 Scheduling Problem Prices paid as tasks begin $1000 per day Availability: Day 0:

38、$20000, Day 15: +$90002022-1-29史忠植 高級(jí)人工智能59Constraints / To create a schedule with origin 0 and given horizon.CtSchedule* schedule = new CtSchedule(0, horizon); / To create an activity with the given duration.CtIntervalActivity* act = new CtIntervalActivity(schedule, duration); /To post a precedence

39、 constraint between act1 and act2.act2-startsAfterEnd(act1,0); 2022-1-29史忠植 高級(jí)人工智能60Constraints/To create a total budget of limited capacity (here 29000).CtDiscreteResource* res = new CtDiscreteResource(schedule, CtRequiredResource, capacity); / To state that only cap (here 20000) is available prior to a / given date (here 15).res-setCapacityMax(0,date,cap); / To state that an activity act consumes c units of res.act-consumes(res, c);2022-1-29史忠植 高級(jí)人