高级人工智能3约束推理

1、2022/7/151高级人工智能 第三章 约束推理 2022/7/152第三章 约束推理3.1 概述3.2 回溯法 3.3 约束传播 3.4 回跳法 3.5 约束推理系统COPS 3.6 ILOG SOLVER2022/7/1533.1 概述 最优化问题经济学所推崇的帕累托最优:几个人拎着水桶在一个水龙头前面排队打水，水桶有大有小。他们怎样排队，才能使得总的排队时间最短。这是一个寻求“最优化”的题目，目标是节省总的排队时间，达到最优。2022/7/1543.1 概述 优化问题 运筹学 遗传算法 神经网络 约束推理2022/7/155运筹学的工作步骤1）提出和形成问题，2）建立模型，3）求解，4

2、）解的检验，5）解的控制，6）解的实施。 2022/7/156线性规划问题例1(广告方式的选择)中华家电公司推销一种新型洗衣机,有关数据见下表.销售部第一月的广告预算为20000元,要求至少有8个电视商业节目,15家报纸广告/电视广告费不得超过12000元,电台广播至少隔日有一次.现问该公司销售部应当采用怎样的广告宣传计划,才能取得最好的效果?2022/7/157表1广告方式广告费用(元/次)可用最高次数/月期望的宣传效果/单位电视台a(白天,1 分钟)5001650电视台b(晚上,30钞)10001080每日晨报/(半版)1002430星期日报/(半版)300440广播电台/(1分钟)802

3、5152022/7/1582022/7/1592022/7/15102022/7/1511求解-单纯形法将所给问题化为标准形找出一个初始可行基,建立初始单纯形表检查所有检验数(若全为非负,则已得到最优解,计算停止.否则继续下一步)考察是否无解(若是,计算停止,否则继续下一步)确定入基变量,出基变量对初始单纯形表进行单纯形变换2022/7/15123.1 概述一个约束满足问题(Constraint Satisfaction Problem, 简称CSP) 包含一组变量与一组变量间的约束。 变量表示领域参数，每个变量都有一个固定的值域。一个变量的值域可能是有限的，例如一个布尔变量的值域包含两个值；

4、也可能是离散无限的，如整数域；也可能是连续的，如实数域。 x1,x2,xn, D1,D2,Dn, . 4,5,6,7 red, green,blue 2022/7/15133.1 概述 约束可用于描述领域对象的性质、相互关系、任务要求、目标等。约束 满足问题 的目标就是找到所有变量的一个（或多个）赋值，使所有约束都得到满足。 一元谓词。 序关系语言，只包含偏序关系或实变量上的大小关系。 形如“x - y c” 的方程。 单位系数的线性方程与不等式，即所有的系数为 -1,0,1。 任意系数的线性方程与不等式。 约束的布尔组合。 代数与三角方程。2022/7/15143.1 概述约束表示易于理解、

5、编码及有效实现，它具有以下优点: 约束表示允许以说明性的方式来表达领域知识，表达能力较强，应用程序只需指定问题的目标条件及数据间的相互关系。因而具有逻辑表示的类似性质。 约束表示允许变量的域包含任意多个值，而不像命题 只取真假二值。所以它保存了问题的一些结构信息，如变量域的大小、变量间的相关性等，从而为问题求解提供启发式信息。 易于并行实现。因为约束网络上的信息传播可以认为是同时的。 适合于递增型系统。约束可以递增式地加入到约束网络。 易于与领域相关的问题求解模型相衔接。各种数学规划技术，方程求解技术等, 都可以自然地嵌入约束系统。2022/7/15153.1 约束推理 约束搜索约束搜索主要研

6、究有限域上的约束满足。对有限域而言，约束满足问题一般情况下是 一个 NP 问题。 约束语言2022/7/15163.1 约束搜索 回溯法。 约束传播。 智能回溯与真值维护。 可变次序例示。 局部修正法。2022/7/1517约束语言CONSTRAINTSCHIPCOPSILOG2022/7/1518CONSTRAINTS约束语言 CONSTRAINTS是一个面向电路描述的约束表示语言。作为一个约束表示语言，它使用了符号处理技术来求解数学方程。在CONSTRAITS中，物理部件的功能及器件的结构都用约束表示。这些约束一般是线性方程与不等式, 也包括条件表达式。约束变量一般是表示物理量的实变量。也

7、有一些取离散值的变量。如开关的状态、三极管的工作状态等。系统采用表达式推理与值推理。并实现相关制导的回溯。 2022/7/1519CONSTRAINTS约束语言 CONSTRAINTS 的一个优点是在类型层次中表示约束，用约束来表示物理对象的功能与结构。其缺点是该语言缺乏类似于面向对象语言中的方法那样的成分，不能定义特定于某个类的概念。同时，约束传播方法比较单一，既缺乏实域上的区间传播机制，也缺乏有限域上的 域传播机制。 2022/7/1520约束逻辑程序设计语言CHIP CHIP(Constraint handling in Prolog) 就是这样较有影响一个约束逻辑程序设计语言，其目的是

8、简便、灵活而有效地解决一大类组合问题。它通过提供几种新的计算域而增强逻辑程序设计的能力；有限域、布尔项及有理项，对于每个计算域，都提供有效的约束求解技术，即有限域上的一致性技术，布尔域的布尔合一技术及有理数域上的单纯型法。除此以外，CHIP还包含一个一般的延迟计算机制。 CHIP 主要应用于两个领域: 运筹学与硬件设计。 CHIP 缺乏类型机制，而这种机制对于表达领域概念是极其重要的。2022/7/1521面向对象约束语言COPS COPS系统利用面向对象技术，将说明性约束表达与类型层次结合起来。在形式上吸收了常规语言，主要是面向对象的程序设计语言的基本形式。内部求解时采用约束推理机制，使说明

9、性约束表达式与类型层次相结合，实现知识的结构化封装，充分发挥两者的优点，力图实现一个具有较强表达能力和较高求解效率的约束满足系统。2022/7/1522面向对象约束语言COPSCOPS的设计考虑了软件工程的应用要求，尽量将一个不确定问题确定化：它允许条件语句与循环语句，而不是单纯以递归的形式来实现迭代计算； 通过类方法的重栽实现同一约束的不同实现，提高了程序的执行效率。COPS系统同时是一个渐增式的开放系统，用户能通过类型层次定义，实现新的数据类型和新的约束关系。约束语言COPS具有许多人工智能程序设计语言的特点，如约束传播、面向目标和数据驱动的问题求解、有限步的回溯、对象分层中的继承等。 2

10、022/7/1523 在实际应用中，算法的表现形式千变万化，但是算法的情况也和数据结构类似，许多算法的设计思想具有相似之处，我们可以对它们分类进行学习和研究。 常用的算法大致有如下一些：贪心法分治法：如二分法检索回溯法动态规划法局部搜索法分支限界法2022/7/1524 算法分析 评价一个程序优劣的重要依据是看这个程序的执行需要占用多少机器资源。人们最关心的就是程序所用算法运行时所要花费的时间代价和程序中使用的数据结构占有的空间代价。 算法的空间代价(或称空间复杂性)：当被解决问题的规模(以某种单位计算)由1增至n时，解该问题的算法所需占用的空间也以某种单位由f(1) 增至f(n)，这时我们称

11、该算法的空间代价是f(n)。 算法的时间代价(或称时间复杂性)：当问题规模以某种单位由1增至n时，对应算法所耗费的时间也以某种单位由g(1)增至g(n)，这时我们称算法的时间代价是g(n)。 2022/7/1525穷尽搜索方法穷尽搜索方法 即产生所有可能的树，然后根据评价标准选择一棵最优的树。 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/7/1526穷尽搜索方法 Exhaustive-Searc

12、h(f,P)1. if f is a total assignment of the variables in P2. if f satisfies the constraints in 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-

13、Search(f,P)12. return answer2022/7/1527贪心法贪心法把构造可行解的工作分阶段来完成。在各个阶段，选择那些在某些意义下是局部最优的方案，期望各阶段的局部最优的选择带来整体最优。例：Dijkstra的最短路径算法、Kruskal的求最小生成树算法、信号灯问题2022/7/1528回溯算法有些问题需要彻底的搜索才能解决问题，然而，彻底的搜索要以大量的运算时间为代价，对于这种情况可以通过回溯法来去掉一些分支，从而大大减少搜索的次数。八皇后问题迷宫问题深度优先周游树或图2022/7/1529回溯算法 Backtracking-Top(P)1 f := the nul

14、l assignment2 return Backtracking(f,P)2022/7/1530回溯算法 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 constraint

15、s in P9 answer := Backtracking(f,P)10 return answer2022/7/1531回溯算法 尽管回溯法好于生成测试法，但对于非平凡问题仍然是低效的。其原因在于搜索空间中不同路径的搜索重复相同的失败子路径。一些研究者认为，造成这种反复的原因是所谓的局部不一致性。最简单的情形是所谓的结点不一致性。对一个变量vi的一个一元约束。存在域中一个值vi不满足该约束。这样，每当vi取到 a 时就会出现不一致性。 另一种重复的情形 是所谓的弧不一致性。2022/7/15323.3 约束传播CONSTRAINT PROPAGATION弧一致性Arc consistenc

16、y 2022/7/1533弧一致性 Arc consistency 如果对vi 的当前域中的所有值x，存在vj的当前域中的某值y使得 vi=x和vj=y是vi与vj之间的约束所允许的，则弧(vi, vj)是弧一致的。 弧一致性的概念是有向的。即(vi, vj)是弧一致的并不自动地意味着(vj, vi)是一致的。2022/7/15343.3 CONSTRAINT PROPAGATIONAll of the Mackworth algorithms make use of a Revise procedure. Let Dv be the current domain of v, Let Dw b

17、e the current domain of w, Let P be the constraint predicate that holds between v and w, then Revise updates Dv as follows:2022/7/1535CONSTRAINT PROPAGATIONMackworth 1977 AC-1 AC-2 AC-32022/7/1536约束传播修改算法REVISE(Vi,Vj)1 DELETE false;2 for each x Di do 3 if there is no such yj Dj4such that(x,yj) is co

18、nsistent,5 then 6 delete x from Di;7 DELETE true;8 endif 9 endfor 10 return DELETE; 11 end REVISE2022/7/1537AC-11 Q ;2 repeat 3 CHANGE false;4 for each (Vi, Vj) Q do5 CHANGE REVISE(Vi, Vj) CHANGE;6 endfor;7 until not(CHANGE);8 end AC-12022/7/1538AC-31 Q ;2 While Q not empty 3 Select and delete any a

19、rc(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-32022/7/1539BackjumpingBackjumping-Top(P)1 f := the null assignment2 := Backjumping(f,P)3 return answer2022/7/1540BackjumpingBackjumping(f,P)1 if f is a total assignment of the variables

20、 in P2 answer := 3 else 4 v := some variable in P that is not yet assigned a value by f5 answer := Unsat6 conflict-set := 7 for each value 8 f(v) := x9 if f satisfies the constraints in P10 := Backjumping(f,P)2022/7/1541Backjumping11 else12 new-conflicts := the set of variables in a violated constra

21、int13 if answer Unsat14 return 15 else if v new-conflicts16 return 17 else 18 conflict-set := conflict-set (new-conflicts v)19 return 2022/7/1542COPS Constraint : predicate expressionP(t1, ., tn) where P is built in function, such as sum times eq(equal) neq(not equal) ge(great than or equal to) gt(g

22、reat than) also can be defined by users2022/7/1543COPS Conditional constraint condition1: constraint1; . . conditionn: constraintn where condition1, ., conditionn are boolean expressions. constraint1,. constraintn are constraints or contraints table. 2022/7/1544COPS RULE Rule is used to define new f

23、unction, method, predicate, or add new constraint into object.RULE class: predicate(varibles) (boolean expression)constraint_1;constraint_n; CASEboolean expression_1: constraint_1; boolean expression_m: constraint_m;2022/7/1545COPS For example: RULE multiple(INTEGER: *x, INTEGER: y, INTEGER: z) (neq

24、(y, 0) equal(x, divide(z, y); z = x * y2022/7/1546COPS CLASS class_name:superclass_name / attributes definition date type: attribute_name; . / rule definition rule_name; . /function definition function_name; . / method definition method_name; . 2022/7/1547COPS Implementation Program written by COPS

25、consists of classes 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/7/1548COPS piler1

26、2 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/7/1549COPS7 Interprte the program with the internal structures.8 Constraint networks are built up for Unsolved 9 constraints and vari

27、ables.10 while some constraints in the constraint networks are triggered,11 inteprete the triggered constraints.12 2022/7/1550COPSInterpreter:1 2 switch (constraint type)3 case Constant:4 return Constant:5 case global variable:6 interprete global variable:7 case local variable or argument:8 interpre

28、te local variable or argument:9 case object-attribute pair;10 interprete object-attribute pair:11 case function call:2022/7/1551COPS12 interprete function call:13 case method call:14 interprete method call:15 case CASE expression:16 interprete CASE expression:17 .18 default:20 report error21 2022/7/

29、1552ILOG 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 variable CtBoolVarMemory Management new: delet

30、e:2022/7/1553ILOG 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(Constraint(x = a), CtAnd(Constraint(x != a), CtInstan

31、tiate(x); 2022/7/1555 ILOG Schedule 1.0Schedule CtSchedule class Global object: time original -tineMin time horizon -timeMax 2022/7/1556 ILOG Schedule 1.0Resources CtResource CtDiscreteResource CtUnaryResource CtDiscreteEnergy CtStateResource 2022/7/1557 ILOG Schedule 1.0Activities CtActivity class

32、CtIntervalActivity An activity is defined by its start time, end time and duration Activities require, provide, consume and produce resources2022/7/1558 Scheduling Problem Prices paid as tasks begin $1000 per day Availability: Day 0:$20000, Day 15: +$90002022/7/1559Constraints / To create a schedule

33、 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 constraint between act1 and act2.act2-startsAfterEnd(act1,0);2022/7/1560Constr

34、aints/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/7/1561Algorithm ProgramCtBoolean IsUnScheduled(CtActivity* act) / Return true if act does not have a fixed start time. if