高級人工智能之約束推理

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

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

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

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

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

6、，例如一個布爾變量的值域包含兩個值；也可能是離散無限的，如整數域；也可能是連續(xù)的，如實數域。 x1,x2,xn, D1,D2,Dn, . 4,5,6,7 red, green,blue 2022-1-29史忠植 高級人工智能133.1 概述概述 約束可用于描述領域對象的性質、相互關系、任務要求、目標等。約束 滿足問題 的目標就是找到所有變量的一個（或多個）賦值，使所有約束都得到滿足。 一元謂詞。 序關系語言，只包含偏序關系或實變量上的大小關系。 形如“x - y c” 的方程。 單位系數的線性方程與不等式，即所有的系數為 -1,0,1。 任意系數的線性方程與不等式。 約束的布爾組合。 代數與三

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

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

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

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

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

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

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

14、索方法窮盡搜索方法 即產生所有可能的樹，然后根據評價標準選擇一棵最優(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史忠植 高級人工智能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史忠植 高級人工智能27貪心法貪心法把構造可行解的工作分階段來完成。在各個階段，選擇那些在某些意義下是局部最優(yōu)的方

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

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

19、)(red,blue)(red, green,blue) 弧一致性弧一致性Arc consistency 2022-1-29史忠植 高級人工智能33弧一致性弧一致性 Arc consistency 如果對vi 的當前域中的所有值x，存在vj的當前域中的某值y使得 vi=x和vj=y是vi與vj之間的約束所允許的，則弧(vi, vj)是弧一致的。 弧一致性的概念是有向的。即(vi, vj)是弧一致的并不自動地意味著(vj, vi)是一致的。2022-1-29史忠植 高級人工智能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史忠植 高級人工智能35CONSTRAINT PROPAGATIONCONSTRAINT PROPAGATIONMackworth 1977Mackworth 1977 AC-1 AC-1 AC-2AC-2 AC-3 AC-3

22、2022-1-29史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能39BackjumpingBackjumping-Top(P)1 f := the null assignment2 := Backjumping(f,P)3 return answer2022-1-29史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人工智能55 ILOG Schedule 1.0Schedule CtSchedule class Global object: time original -tineMin time horizon -timeMax 2022-1-29史忠植 高級人工智能56 ILOG Schedule 1.0Resources CtResource CtDiscreteResource CtUnaryResource CtDiscreteEnergy CtSt

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

38、$20000, Day 15: +$90002022-1-29史忠植 高級人工智能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史忠植 高級人工智能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史忠植 高級人