开题报告----基于半环约束的限制优化诊断.doc

毕业设计综合设计报告学生姓名： 学 号： 专 业： 自动化 设计题目： 基于半环约束的限制优化诊断 指导教师： 刘兆伟 基于半环约束的限制优化诊断整体思路约束优化在人工智能中是中心问题。针对这个课题我构造了在点阵基础上的作为限制优化问题基于模型的诊断。我将展示基于软约束的框架工作，称之为半环约束。被良好设计的精确属性半环约束，我将展示它如何在一个框架工作中被半环限制满足问题所获取,在把诊断问题分解为树形结构和运用动态程序中，被良好定义的半环限制满足问题的精确属性允许设计一个有效的解决方法。许多问题在人工智能中被构造成优化问题，任务是给一个变数组找一个最好的分配方式，如此，一套约束被满足。形式主义为软的约束19，2目的在于更加接近的实现约束优化和限制问题。这个元素可以被阐释由于重量，成本，效用，可能性，或优先权。一个一般骨架为软半环约束2被基于一个半环。半环行动各自规划和联合。技术示范基于模型诊断，在由点阵偏好结构和强约束组成的普通优化问题，能构成半环约束，全球目标函数和偏爱水平控制。它提高实际效用的半环约束，将领框架结构，不一样的概念的基于模型诊断（最小基本诊断，最小子集诊断，概率的诊断)能容易获得由选择一个合适的半环。在这个过程中，我利用基于模型诊断中的假设作为优化问题的特殊资产。为传统约束满足问题，当地协调技术【14】提供最有效的解决问题方法。半环约束的精确属性保证了当地协调是适用的，除了它在树结构评价方案中被组织成直接协调。详述前期工作6，7，13， 基于树分解和即时动态程序为解决半环约束满足问题我提供了一个算法，它能用于有效计算诊断问题的大量初始解。1各个模块简介部分1定义在点阵下基于模型的优化限制诊断。部分2回顾c半环约束。部分3提出在点阵基础上构造优化约束框架，以c半环作为特殊诊断，在全部目标函数下定义条件。部分4提出基于树分解和动态程序的有效解决c半环的算法。部分5展示二诊断算法和三层树结构，这可被看做是基于c半环限制约束的特殊例子。1在点阵基础上的优化限制诊断定义1(约束系统)一个约束系统，一个元组=x1，。，一个变数组d1，。，一套精确的定义，f为返回整型值的函数=f1，。，一套约束。约束f定义了一些功能允许可控变量和不可控变量的值。例如，布尔多核线路21可以被构造作为一个有不同变量值的约束系统，f为返回整型值的函数，变量从 a到z在0，1中取值，而变量o1到a2从g,b中取值，如果一个变量完好，那么它正确的形式是布尔变量。如果一个元素被破坏，那么它的行为没有任何假设。这个“未知的模式”捕获约束的悬挂概念，暂且，我们假设观察值包含在一系列约束中。我们会回来研究他们如何在运行时被加入。第1点。布尔多层例子由三输入或门和二输入与门。输入，输出值可以被直接观察出。接下来，我们用t y表示子集变量y来表示元组t的坐标。给一个约束系统c一个子集的变量，一个解一个元组变量，这里存在一个变量的延伸。 通过一个目标函数去定义解决方法的偏好水平，优化扩展了约束系统。定义2(目标函数)一个目标函数u 。a中的每个子集中的元素存在最大下界和最小上界。在诊断中，z代表了模式变量。例如，在第1点中的布尔变量z代表一系列的变量取值o1，o2，o3，a1，a2。诊断的不一样的概念代表不一样的目标函数和点阵。在最小取值诊断a代表一个全序的整数集价值u代表每个功能模块中错误模块个数在概率诊断【4】中，a基于全序在【0，1】中取值u联系着每个功能模块的可能取值。在最小子集诊断【15，4】中，a基于特殊顺序是z的子集点阵，每个不同的模块设备代表不同的错误模块功能。人能考虑更远的的例子，例如，联想一个修理费用或部分地彼此模式分配订购用户偏好。对于第1点中的多核布尔实例，如果我们假设或门有1%失败概率，门有。5%失败概率。2半环限制满足问题半环约束是一个“软”约束的构造，约束被延伸到包括一个偏好水平。半环限制满足问题归入许多其他偏爱约束 ，例如模糊限制满足问题，概率限制满足问题，或局部限制满足问题。定义3半环c是一个元组 。1,a是一个配置，包括0和1.2+操作是可交换的，关联的，幂等3。操作是可交换的，4。和+遵从分配率。例如sb = (0, 1, , , 0, 1)形成一个c半环，部分序列定义了偏好水平，这样允许挑选出半环上定义约束最好的方法。定义4(基于半环的约束系统)基于c半环的一个约束系统。f是分配在a中每个元组定义的函数。“传统”约束14符合基于s半环的约束系统 ，允许定义的和未定义的变量存在值。定义5(组合和投影)让f和g为两个独自的被限制的变量1定义f*g表示f和g的组合，为新的约束，每个变量组都有自己的值。2。定义f y为f的投影建立在变量y上。给一个基于c半环约束系统，限制优化问题是计算一个函数。3半环约束问题的诊断在这一部分，我调查在第二部分定义的基于点阵上的优化问题，在特殊诊断中，它可以被构造成半环问题。自从基于半环约束的精确属性确保如此本地约束传播是可行的，这些将是解决这些问题的最基本有效的方法。我首先表明那有可能“重建”一个当量c半环从一个约束系统，和一个点阵中可重建一个等同的半环约束满足问题。我调查，在什么条件下有可能分解全球目标函数，定义当地偏爱水平。例如，每一个约束，那些排序的解法被保存，这建立在条件是在树状结构约束满足问题的成本优化。说明如何这些条件符合制造基于模型诊断的一般假设。定义6(撰写目标函数)一个目标函数u包括了一系列元素,定理1(半环约束满足问题的优化 )让c为一个在，上的约束系统，u为一个目标函数。定义一个约束系统(x, d, f )如下:对于每一个fj f，fj被定义为fj(t) = glb(a) 。 fj(t) = 和 fj(t) = lub(a), f =f1 . . . fm u1 . . . uk. (a, lub, , glb(a), lub(a) 是一个c半环 和 (m+ki=1fi) z = u(sol(c).每个目标函数u都初始化为0，选择a b = glb(a, b。连同定理1，这暗示，在，上每个约束系统c同目标函数u能被变成一个半环约束满足问题， a和c有相同的解决方法使他们与u相同。举例说来，在最小子集诊断中，目标函数包括一元函数，如果t代表一个正确的任务，则u为空集，如果t代表一个错误的任务，则u=z.同样的，在最小基础诊断和概率诊断中，目标函数包括一元函数 +和 ，对于基于模型的诊断，无初始化的目标函数回应在每个单独个体中错误的假设。和【2】中的结果一起，定理1在点阵偏好结构和硬约束之间建立了一对一回复方式。 到目前为止，我们有二分类型约束在c半环:功能定义在只取变量z。双重功能定义在取变量x.定义7（接触算法） 通过吸收包含在其他功能上的功能，在不改变解决方法的情况下减少一系列的变量。 定理2（吸收包含的约束）定义(x,d,f)成为基于c半环的约束系统，定义f为函数。、 对于基于模型的诊断，假设错误独立于每个单独的元素，那么u会包括至少一个f，然后，客观函数会包含在约束元素中。注意这并不包括一个元素含有多个变量的情况。例如一系列的模型变量临时代表不同的时间阶段，这也不包括客观函数与模型变量有相同值的情况（例如两个模型间可能存在的传递）。表1 可以现在总结在第二部分介绍的基于模型诊断的一样的概念的，由于特殊情况约束优化。表1展现了基于三个诊断概念的与门的结果约束。最小基础诊断：在错误元素个数的偏好准则中诊断，目标是是错误元素的个数达到最小sc = (n+0 , min, +, , 0).最小子集诊断。在错误元素系列的偏好准则中诊断，目标是错误元素系列达到最小，被包含在选择的半环s中。ss = (2z , , , z, ).最大概率诊断：在模型任务的概率中诊断偏好准则，目标是使模型任务的概率最大。sp = (0, 1, max, , 0, 1).4分解和规划程序基于c半环的精确属性（特别是联系和交换性)很好的保证当地的约束(“硬”)约束工作扩展框架。针对当地软约束的研究集中直接的协调一致，约束以一种有组织的方式跟在树结构的后面。特例是x操作没有必要是幂等的，意味着约束传播不能被应用于混沌的方式。针对延伸软约束【1，18】的当地传播概念集中在协调树主题中约束以一种有组织的方式传播。然而，随意的约束网络未必是树结构。结构分解的目标方法12，13是变成随意的约束网络到当量，树状结构(非循环的)例子，可能附近的的约束集中在一起。在硬约束中分解，但是思想自然延伸到约束优化【6】。结构分解基于约束系统假设h(x, d, f ),和每一个变量xi x,相联系，假设和每一个约束fj f相联系。第2点展示了基于布尔电路的超图形。定义8(树分解12，13)一个树分解为一个约束系统(x, d, f )，一个三重变量(t, , )，一个有根树(v, e)，f为返回整型值的函数，如此，1 对每个f，这里存在精确的v2 对于每一个x，存在相联系的子集t.第3点展示了一个的树分解布尔多层结构。为一个约束系统c定义了一个树分解当量，树状结构约束系统。注意那一个一元约束以上一个变量能增加树分解，不违反连通性条件，补充它在所有的节点当中各变量。这允许在离线时进行分解，并在树被建成后增加了变量的观察。为基于模型诊断，u从目标函数的吸收已经完备。这意味着，超图形将直接对应原设备，常常组织在一个模数的方法，对于一个任意的约束优化问题，分解和吸收目标函数的失败会导致大的限制，使问题很难被分解，导致大数量变量树型的出现。分解可理解为在直接传播技术中对约束系统的小的修补，第2点。超图形在第1点中为例子。第3点。在第2点中一个的树分解超图形 ，显示标签，对应每个节点。(动态规划)成为可适用的。解决一个基于半环约束的树结构能被免费搜索计算使用两个步骤。第一步是用即时的动态程序计算自上而下的元组的值，这一步可看做是研究的一个精确启发。在第二个步骤中，这些步骤可看做具体的解决方法。这个步骤可看做精确启发的引导，因此可以自由原路返回。以前工作约束优化以分解为依据，动态规划6，7，13关注了计算的任务最好的的价值为个人变量或一个单独对所有变量的最优分配。 我们针对诊断上下文的重要需求来扩展工作。第一，在诊断时典型的是目标解决方法的有限数字是被需要的。举例来说，解决价值在于它的可能性，则任务是寻找一系列包含大多可能密度空间的解决问题方法。我们传达这些需求，通过探索自下而上和自上而下的c半环的单调可能性，去减少寻找空间。第二，在诊断中，很多变量不是模型变量，并且它对于具体的解决方法不灵活。我们的方法避免在上下文中出现系统假设变量。在第4点的自下而上的动态程序中出现的伪代码，子集函数返回一系列子集节点。f是v的约束，f (v) f (c) var(f(v)被认为是半加入，这一步建立在节点与它的源头的直接传播上。这概括了约束满足问题【14】与软约束【18】的直接传播。程序如下：function solve(v, b)for each ci children(v)solve(child)f (v) (f (v) f (ci) var(f(v) |bif c(v) 0 thenthrow inconsistent()end ifend for第4点。由下而上通过动态规划为解决一个基于半环的树状结构。s b.。这探索了c半环的属性。就是说，对于所有的a, b a都满足(a b) s a解决问题的价值在寻求解决方法中被发现。root(t )是所有t的根节点，在计算完所有的数字后，f的最优解就是最优的解决算法。如果s 只是一个特殊序列，那么元组的最优解f是优化问题的最优解。这个问题没有持续的解决方法，只有当树结构中的节点v 满足 f (v) 0.表2展示了对于布尔变量举例的结果根数字限制。限制了单一的与门或门错误和双重的或门限制。表2。 自下而上的多层实例通过s半环第三点描述的书分解，没有列出的元组的值为0。由下而上的时间复杂度的是在一个树节点幂数的在最大变量数(称作树宽度)，它的空间复杂度是幂数的在最大的变量数那个被分享在两个节点7，13因此树分解的好处是它分解了所有变量和树元素的指数型增长。注意的是错综复杂的事物不依靠半环，这意味着从硬约束到软约束的延伸并不增加约束问题的复杂性。在第5点中解决问题的伪代码中，它列举了自下而上解决方法a s b.。举例说来，在最小基础诊断中，程序会在单限制和双重约束下执行。如果单错误存在，那么单错误只列举在自上而下的程序段中。用那种算法很容易证明上下算法。例如，具体解决方法的数目被限制。在第5点，先节点操作细举了树结构t的节点的优先节点（例如，在第3点中v0, v1, v2, v3的顺序）约束r包括了结果方法，如果x操作不是幂等的，自下而上的传播通过半结合操作fi 1 fj vars(f取消。程序如下：function extract(t, b)v preorder-node-iterator-rst(t )m r f (v) |bbegin loopfor each ci children(v)m m (v) (ci)end forr r (var(r)m)zv preorder-node-iterator-next(t )if (v = nil) thenreturn rend ifif not ( idempotent) thenr r 1 f (v) var(r)end ifr (r f (v) |bm m(parent(v) (v)end loop第5点。自上而下为枚举解一个半环约束满足问题的树状结构。解决方法只包括包含变量z的任务，其他的变量在结果中被限制。一个变量只被限制一次，它不会出现在其他的三个部分。在第5点中展示的算法中，在r和树结构中未执行的部分中共享的变量展示在多重设置m中。重新考虑在半环s中多层布尔变量的例子，继续上面的举例。假设解决方法为b=5.0e-5.最初，给v一个初始值，r在表2中被限制展示，节点v0有三个子节点，在for循环后，多重设置m为c, x, y, y, z.操作在限制变量e,f,r后的for循环后执行。假设v1在先前序列中是t的下一个节点。自从x操作对于sp不是幂等的，通过操作1 ,在r 和fa2之间执行半加入操作。表3展示了最终解。表3。枚举自上而下的多层例子的解。复杂的自上而下阶段最坏情况指数在变量z的数据类型。解枚举法如上所述在第5点，要求那操作有一个对立。这个情况是针对三个半环的。5半环约束和树结构半环约束和树结构是针对三结构系统的二诊断算法。半环约束是一个动态规划算法以“量重”分配模式变量。一个正确分配有重量0，而一个异常(故障)分配有重量1。目标是使重量的总数最小。它针对的是半环s。假设模型变量在重量课题约束中不被共享。如果用诊断模型区违反这个假设，那么半环约束会导致错误的结论。半环语文书和树分解相结合。半环约束包括三方面的分解，但是，它只精确一个最好的解决方法，并且，它不用限制手段，在【9】中，与gdb的比较中sab显示了它在基于矛盾的诊断算法的优势。正如sab-tree计算最小基本诊断一样，树结构所依据的思想是：一系列持续的分配z太小了而不能和每个元组直接联系，这时用一个单独的自上而下的程序来代替。树结构将自上而下的和自下而上的阶段折合成一个单独的阶段。任务的设置必须明确，因为减少开支费用和模型任务代表了z的子集，在树结构中，变量z不包括在约束系统中。相反，模型任务与约束问题相联系。模型任务通过u操作相联系。因为这里没有单独的解决方法，元组的值通过a b =a b | a a, b b算出。树结构通过减少开支来限制设备和诊断的传播。因为现在对细节阶段没有单独的解法，找到和元组值结合的解决树根部的解决方法。树结构单独对待约束和变量值，它是半联合和双倍价值的约束，并且更新了下一步的价值，但是注意，如果结果只是找一个更好的诊断，在z中更新的数据将呈指数形式增长。有效的数字结构，例如算法决定数字，在c半环基础上存在约束，a是确切数的子集。对于强约束和大的z集合