高级人工智能之约束推理

高级人工智能第三章约束推理史忠植

中国科学院计算技术所1/17/20231第三章约束推理3.1概述3.2回溯法3.3约束传播3.4回跳法3.5约束推理系统COPS3.6ILOGSOLVER1/17/202323.1概述最优化问题经济学所推崇的帕累托最优:几个人拎着水桶在一个水龙头前面排队打水，水桶有大有小。他们怎样排队，才能使得总的排队时间最短。这是一个寻求“最优化”的题目，目标是节省总的排队时间，达到最优。1/17/202333.1概述

优化问题

运筹学

遗传算法

神经网络

约束推理1/17/20234运筹学的工作步骤1）提出和形成问题，2）建立模型，3）求解，4）解的检验，5）解的控制，6）解的实施。1/17/20235线性规划问题例1(广告方式的选择)中华家电公司推销一种新型洗衣机,有关数据见下表.销售部第一月的广告预算为20000元,要求至少有8电视商业节目,15家报纸广告/电视广告费不得超过12000元,电台广播至少隔日有一次.现问该公司销售部应当采用怎样的广告宣传计划,才能取得最好的效果?1/17/20236表1广告方式广告费用(元/次)可用最高次数/月期望的宣传效果/单位电视台a(白天,1分钟)5001650电视台b(晚上,30钞)10001080每日晨报/(半版)1002430星期日报/(半版)300440广播电台/(1分钟)8025151/17/202371/17/20238

1/17/20239

1/17/202310求解--单纯纯形法将所给问题化化为标准形找出一个初始始可行基,建建立初始单纯纯形表检查所有检验验数(若全为为非负,则已已得到最优解解,计算停止止.否则继续续下一步)考察是否无解解(若是,计计算停止,否否则继续下一一步)确定入基变量量,出基变量量对初始单纯形形表进行单纯纯形变换12/31/2022113.1概述一个约束满足足问题(ConstraintSatisfactionProblem,简称CSP)包含一组组变量与一组组变量间的约约束。▪变量表示领领域参数，每每个变量都有有一个固定的的值域。一个变变量的的值域域可能能是有有限的的，例例如一一个布布尔变变量的的值域包含含两个个值；；也可可能是是离散散无限限的，，如整整数域域；也也可能是连连续的的，如如实数数域。。{x1,x2,…xn},{D1,D2,…Dn},.{4,5,6,7}red,green,blue}12/31/2022123.1概述▪约束束可用用于描描述领领域对对象的的性质质、相相互关关系、、任务务要求、、目标标等。。约束束满满足问问题的的目目标就就是找找到所所有变量的的一个个（或或多个个）赋赋值，，使所所有约约束都都得到到满足足。一元谓谓词。。序关系系语言言，只只包含含偏序序关系系或实实变量量上的的大小小关系系。形如““x-y>c””的的方程程。单位系系数的的线性性方程程与不不等式式，即即所有有的系系数为为-1,0,1。。任意系系数的的线性性方程程与不不等式式。约束的的布尔尔组合合。代数与与三角角方程程。12/31/2022133.1概述约束表示示易于理理解、编编码及有有效实现现，它具具有以下下优点:约束表示示允许以以说明性性的方式式来表达达领域知知识，表表达能力较强强，应用用程序只只需指定定问题的的目标条条件及数数据间的相互关关系。因因而具有有逻辑表表示的类类似性质质。约束表示示允许变变量的域域包含任任意多个个值，而而不像命命题只取真假假二值。。所以它它保存了了问题的的一些结结构信息息，如变量域的的大小、、变量间间的相关关性等，，从而为为问题求求解提供供启发式信信息。易于并行行实现。。因为约约束网络络上的信信息传播播可以认认为是同时的。。适合于递递增型系系统。约约束可以以递增式式地加入入到约束束网络。。易于与领领域相关关的问题题求解模模型相衔衔接。各各种数学学规划技技术，方程程求解技技术等,都可可以自然然地嵌入入约束系系统。12/31/2022143.1约束推理理约束搜索索约束搜索索主要研研究有限限域上的的约束满满足。对对有限域域而言，，约束满足足问题一一般情况况下是一个个NP问题题。约束语言言12/31/2022153.1约束搜索回溯法。约束传播。。智能回溯与与真值维护护。可变次序例例示。局部修正法法。12/31/202216约束语言CONSTRAINTSCHIPCOPSILOG12/31/202217CONSTRAINTS约束束语言CONSTRAINTS是一一个面向电电路描述的的约束表示示语言。作为一个约约束表示语语言，它它使用了符符号处理技技术来求解解数学方程程。在CONSTRAITS中，，物理部件件的功能及及器件的结结构都用约约束表示。。这些约束一一般是线性性方程与不不等式,也也包括条条件表达式式。约束变变量一般是表示示物理量的的实变量。。也有一些些取离散值值的变量。。如开关的的状态、三极管管的工作状状态等。系系统采用表表达式推理理与值推理理。并实现现相关制导的的回溯。12/31/202218CONSTRAINTS约束束语言CONSTRAINTS的的一个优点点是在类型型层次中表表示约束，，用约束来表示物理理对象的功功能与结构构。其缺点点是该语言言缺乏类似似于面向对象语言中中的方法那那样的成分分，不能定定义特定于于某个类的的概念。同时，约束束传播方法法比较单一一，既缺乏乏实域上的的区间传播播机制，也缺乏有限限域上的域域传播机机制。12/31/202219约束逻辑程程序设计语语言CHIPCHIP(ConstrainthandlinginProlog)就就是这样较较有影响一个约束逻逻辑程序设设计语言，，其目的是是简便、灵灵活而有效效地解决一大类组合合问题。它它通过提供供几种新的的计算域而而增强逻辑辑程序设计的能力；；有限域、、布尔项及及有理项，，对于每个个计算域，，都提供有效的约束束求解技术术，即有限限域上的一一致性技术术，布尔域域的布尔合一技术及及有理数域域上的单纯纯型法。除除此以外，，CHIP还包含一一个一般的延迟迟计算机制制。CHIP主主要应用用于两个领领域:运运筹学与硬硬件设计。。CHIP缺缺乏类型型机制，而而这种机制制对于表达达领域概念念是极其重重要的。12/31/202220面向对象约束束语言COPSCOPS系统统利用面向对对象技术，将将说明性约束束表达与类型型层次结合起来。在在形式上吸收收了常规语言言，主要是面面向对象的程程序设计语言的基本本形式。内部部求解时采用用约束推理机机制，使说明明性约束表达式与类类型层次相结结合，实现知知识的结构化化封装，充分分发挥两者的优点，，力图实现一一个具有较强强表达能力和和较高求解效效率的约束满足系统统。12/31/202221面向对象约束束语言COPSCOPS的设设计考虑了软软件工程的应应用要求，尽尽量将一个不不确定问题确定化：它它允许条件语语句与循环语语句，而不是是单纯以递归的形形式来实现迭迭代计算；通通过类方法法的重栽实现现同一约束的不同实实现，提高了了程序的执行行效率。COPS系统同同时是一个渐增式的开放放系统，用户户能通过类型型层次定义，，实现新的数数据类型和新的约束束关系。约束束语言COPS具有许多多人工智能程程序设计语言的特点，如如约束传播、、面向目标和和数据驱动的的问题求解、、有限步的回溯、对对象分层中的的继承等。12/31/202222在实际应用中中，算法的表表现形式千变变万化，但是是算法的情况况也和数据结结构类似，许许多算法的设设计思想具有有相似之处，，我们可以对对它们分类进进行学习和研研究。常用的算法大大致有如下一一些：贪心法分治法：如二二分法检索回溯法动态规划法局部搜索法分支限界法12/31/202223算法法分分析析评价价一一个个程程序序优优劣劣的的重重要要依依据据是是看看这这个个程程序序的的执执行行需需要要占占用用多多少少机机器器资资源源。。人人们们最最关关心心的的就就是是程程序序所所用用算算法法运运行行时时所所要要花花费费的的时间间代代价价和程程序序中中使使用用的的数数据据结结构构占占有有的的空间间代代价价。算法法的的空空间间代代价价(或或称称空间间复复杂杂性性)：：当当被被解解决决问问题题的的规规模模(以以某某种种单单位位计计算算)由由1增增至至n时，，解解该该问问题题的的算算法法所所需需占占用用的的空空间间也也以以某某种种单单位位由由f(1)增增至至f(n)，，这这时时我我们们称称该该算算法法的的空空间间代代价价是是f(n)。。算法法的的时时间间代代价价(或或称称时间间复复杂杂性性)：：当当问问题题规规模模以以某某种种单单位位由由1增增至至n时，，对对应应算算法法所所耗耗费费的的时时间间也也以以某某种种单单位位由由g(1)增增至至g(n)，，这这时时我我们们称称算算法法的的时时间间代代价价是是g(n)。。12/31/202224穷尽搜索索方法穷尽搜索索方法即产生所所有可能能的树，，然后根根据评价价标准选选择一棵棵最优的的树。Exhaustive-Search-Top(P){wherePisaCSPoftheform(V,D,C)}1.f:=thenullassignment2.returnExhaustive-Search(f,P)12/31/202225穷尽搜索索方法Exhaustive-Search(f,P)1.iffisatotalassignmentofthevariablesinP2.iffsatisfiestheconstraintsinP3.answer:=f4.else5.answer:=Unsat6.else7.v:=somevariableinPthatisnotyetassignedavaluebyf8.answer:=Unsat9.foreachvaluewhileanswer=Unsat10.f(v):=11.answer:=Exhaustive-Search(f,P)12.returnanswer12/31/202226贪心法贪心法把构造造可行解的工工作分阶段来来完成。在各各个阶段，选选择那些在某某些意义下是是局部最优的的方案，期望望各阶段的局局部最优的选选择带来整体体最优。例：Dijkstra的最短短路径算法、、Kruskal的求最最小生成树算算法、信号灯灯问题12/31/202227回溯算法有些问题需要要彻底的搜索索才能解决问问题，然而，，彻底的搜索索要以大量的的运算时间为为代价，对于于这种情况可可以通过回溯溯法来去掉一一些分支，从从而大大减少少搜索的次数数。八皇后问题迷宫问题深度优先周游游树或图12/31/202228回溯算法Backtracking-Top(P)1f:=thenullassignment2returnBacktracking(f,P)12/31/202229回溯溯算算法法Backtracking(f,P)1iffisatotalassignmentofthevariablesinP2answer:=f3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6foreachvaluewhileanswer=Umsat7f(v):=x8iffsatisfiestheconstraintsinP9answer:=Backtracking(f,P)10returnanswer12/31/202230回溯溯算算法法尽管管回回溯溯法法好好于于生生成成测测试试法法，，但但对对于于非非平平凡凡问问题题仍仍然然是是低低效效的的。。其其原原因因在在于于搜搜索索空空间间中中不不同同路路径径的的搜搜索索重重复复相相同同的的失失败败子子路路径径。。一一些些研研究究者者认认为为，，造造成成这这种种反反复复的的原原因因是是所所谓谓的的局局部部不不一一致致性性。。最最简简单单的的情情形形是是所所谓谓的的结结点点不不一一致致性性。。对对一一个个变变量量vi的的一一个个一一元元约约束束。。存存在在域域中中一一个个值值vi不不满满足足该该约约束束。。这这样样，，每每当当vi取取到到a时时就就会会出出现现不一致性。另一种重复的的情形是所所谓的弧不一一致性。12/31/2022313.3约约束传播CONSTRAINTPROPAGATION弧一致性Arcconsistency12/31/202232弧一致性Arcconsistency如果对vi的当前前域中的所所有值x，，存在vj的当前域域中的某值值y使得vi=x和vj=y是vi与vj之之间的约束束所允许的的，则弧(vi,vj)是是弧一致的的。弧一致性的的概念是有有向的。即即(vi,vj)是弧一致的的并不自动动地意味着着(vj,vi)是一致的的。12/31/2022333.3CONSTRAINTPROPAGATIONAlloftheMackworthalgorithmsmakeuseofaReviseprocedure.LetDvbethecurrentdomainofv,LetDwbethecurrentdomainofw,LetPbetheconstraintpredicatethatholdsbetweenvandw,thenReviseupdatesDvasfollows:12/31/202234CONSTRAINTPROPAGATIONMackworth1977AC-1AC-2AC-312/31/202235约束传播播修改算算法REVISE(Vi,Vj)1DELETEfalse;2foreachxDido3ifthereisnosuchyjDj4 suchthat(x,yj)isconsistent,5then6deletexfromDi;7DELETEtrue;8endif9endfor10returnDELETE;11endREVISE12/31/202236AC-11Q;2repeat3CHANGEfalse;4foreach(Vi,Vj)Qdo5CHANGEREVISE(Vi,Vj)CHANGE;6endfor;7untilnot(CHANGE);8endAC-112/31/202237AC-31Q;2WhileQnotempty3Selectanddeleteanyarc(Vk,Vm)fromQ;4If(REVISE(Vk,Vm))ThenQ{(Vi,Vk)suchthat(Vi,Vk)arcs(G),ik,im};6endfor;7endwhile;8endAC-312/31/202238BackjumpingBackjumping-Top(P)1f:=thenullassignment2<answer,conflict-set>:=Backjumping(f,P)3returnanswer12/31/202239BackjumpingBackjumping(f,P)1iffisatotalassignmentofthevariablesinP2answer:=<f,>3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6conflict-set:=7foreachvalue8f(v):=x9iffsatisfiestheconstraintsinP10<answer,new-conflicts>:=Backjumping(f,P)12/31/202240Backjumping11else12new-conflicts:=thesetofvariablesinaviolatedconstraint13ifanswerUnsat14return<answer,>15elseifvnew-conflicts16return<Unsat,new-conflicts>17else18conflict-set:=conflict-set(new-conflicts{v})19return<Unsat,conflict-set>12/31/202241COPSConstraint:predicateexpressionP(t1,...,tn)wherePisbuiltinfunction,suchassumtimeseq(equal)neq(notequal)ge(greatthanorequalto)gt(greatthan)alsocanbedefinedbyusers12/31/202242COPSConditionalconstraintcondition1:constraint1;..conditionn:constraintnwherecondition1,...,conditionnarebooleanexpressions.constraint1,...constraintnareconstraintsorcontraintstable.12/31/202243COPSRULERuleisusedtodefinenewfunction,method,predicate,oraddnewconstraintintoobject.RULE[class::]predicate(varibles)(booleanexpression){constraint_1;­constraint_n;CASEbooleanexpression_1:constraint_1;­booleanexpression_m:constraint_m;}12/31/202244COPSForexample:RULEmultiple(INTEGER:*x,INTEGER:y,INTEGER:z)(neq(y,0)){equal(x,divide(z,y));}z=x*y12/31/202245COPSCLASS[class_name][:superclass_name]{//attributesdefinitiondatetype:attribute_name;...//ruledefinitionrule_name;...//functiondefinitionfunction_name;...//methoddefinitionmethod_name;...}12/31/202246COPSImplementationProgramwrittenbyCOPSconsistsofclassesandrules.COPSconstraintprogramminglanguageisadeclarativelanguage,providingclasses,methodswhichareexistinobjectorientedlanguage.ItissimilarwithC++.COPShasthefeatures:constraintobjectorientedlogicprogrammingproductionsystem12/31/202247COPSCOPS_Compiler1{2Callyacctoparsetheprogramand3togenerateinternalstructures.4Initializatiion5CreateCopsConstanttrueNode;6Allocatememoriesforglobalvariables.12/31/202248COPS7Interprtetheprogramwiththeinternalstructures.8ConstraintnetworksarebuiltupforUnsolved9constraintsandvariables.10whilesomeconstraintsintheconstraintnetworksaretriggered,11intepretethetriggeredconstraints.12}12/31/202249COPSInterpreter:1{2switch(constrainttype)3caseConstant:4returnConstant:5caseglobalvariable:6interpreteglobalvariable:7caselocalvariableorargument:8interpretelocalvariableorargument:9caseobject-attributepair;10interpreteobject-attributepair:11casefunctioncall:12/31/202250COPS12interpretefunctioncall:13casemethodcall:14interpretemethodcall:15caseCASEexpression:16interpreteCASEexpression:17...18default:20reporterror21}12/31/202251ILOGSOLVERCombinesobjectorientedprogrammingwithconstraintlogicprogramming,containinglogicvariables,incrementalconstraintsatisfactionandbacktracking.variables:C++objectintegervariableCtIntVarfloatingvariableCtFloatVarbooleanvariableCtBoolVarMemoryManagementnew:delete:12/31/202252ILOGSOLVERConstraintsCtTell(x==(y+z));Basicconstraints:=,,,<,>,+,-,*,/,subset,superset,union,intersection,member,booleanor,booleanand,booleannot,booleanxor,CtTell((x==0)||(y==0));CtIfThen(x<100,x=x+1);Search12/31/202253ILOGSOLVERCTGOALn:howtoexecuteCTGOAL1(CtInstantiate,CtIntVar*x){CtInta=x->chooseValue();CtOr(Constraint(x==a),CtAnd(Constraint(x!=a),CtInstantiate(x)));}12/31/202254ILOGSchedule1.0ScheduleCtScheduleclassGlobalobject:timeoriginal---tineMintimehorizon---timeMax12/31/202255ILOGSchedule1.0ResourcesCtResourceCtDiscreteResourceCtUnaryResourceCtDiscreteEnergyCtStateResource12/31/202256ILOGSchedule1.0ActivitiesCtActivityclassCtIntervalActivityAnactivityisdefinedbyitsstarttime,endtimeanddurationActivitiesrequire,provide,consumeandproduceresources12/31/202257SchedulingProblemPricespaidastasksbegin$1000perdayAvailability:Day0:$20000,Day15:+$900012/31/202258Constraints//Tocreateaschedulewithorigin0andgivenhorizon.CtSchedule*schedule=newCtSchedule(0,horizon);//Tocreateanactivitywiththegivenduration.CtIntervalActivity*act=newCtIntervalActivity(schedule,duration);//Topostaprecedenceconstraintbetweenact1andact2.act2->startsAfterEnd(act1,0);12/31/202259Constraints//Tocreateatotalbudgetoflimitedcapacity(here29000).CtDiscreteResource*res=newCtDiscreteResource(schedule,CtRequiredResource,capacity);//Tostatethatonlycap(here20