開題報(bào)告基于半環(huán)約束的限制優(yōu)化診斷

1、 畢業(yè)設(shè)計(jì)綜合設(shè)計(jì)報(bào)告學(xué)生姓名： 學(xué) 號： 專 業(yè)： 自動(dòng)化 設(shè)計(jì)題目： 基于半環(huán)約束的限制優(yōu)化診斷 指導(dǎo)教師： 劉兆偉 基于半環(huán)約束的限制優(yōu)化診斷整體思路約束優(yōu)化在人工智能中是中心問題。針對這個(gè)課題我構(gòu)造了在點(diǎn)陣基礎(chǔ)上的作為限制優(yōu)化問題基于模型的診斷。我將展示基于軟約束的框架工作，稱之為半環(huán)約束。被良好設(shè)計(jì)的精確屬性半環(huán)約束，我將展示它如何在一個(gè)框架工作中被半環(huán)限制滿足問題所獲取,在把診斷問題分解為樹形結(jié)構(gòu)和運(yùn)用動(dòng)態(tài)程序中，被良好定義的半環(huán)限制滿足問題的精確屬性允許設(shè)計(jì)一個(gè)有效的解決方法。許多問題在人工智能中被構(gòu)造成優(yōu)化問題，任務(wù)是給一個(gè)變數(shù)組找一個(gè)最好的分配方式，如此，一套約束被滿足。形式

2、主義為軟的約束19，2目的在于更加接近的實(shí)現(xiàn)約束優(yōu)化和限制問題。這個(gè)元素可以被闡釋由于重量，成本，效用，可能性，或優(yōu)先權(quán)。一個(gè)一般骨架為軟半環(huán)約束2被基于一個(gè)半環(huán)。半環(huán)行動(dòng)各自規(guī)劃和聯(lián)合。技術(shù)示范基于模型診斷，在由點(diǎn)陣偏好結(jié)構(gòu)和強(qiáng)約束組成的普通優(yōu)化問題，能構(gòu)成半環(huán)約束，全球目標(biāo)函數(shù)和偏愛水平控制。它提高實(shí)際效用的半環(huán)約束，將領(lǐng)框架結(jié)構(gòu)，不一樣的概念的基于模型診斷（最小基本診斷，最小子集診斷，概率的診斷)能容易獲得由選擇一個(gè)合適的半環(huán)。在這個(gè)過程中，我利用基于模型診斷中的假設(shè)作為優(yōu)化問題的特殊資產(chǎn)。為傳統(tǒng)約束滿足問題，當(dāng)?shù)貐f(xié)調(diào)技術(shù)【14】提供最有效的解決問題方法。半環(huán)約束的精確屬性保證了當(dāng)?shù)貐f(xié)調(diào)

3、是適用的，除了它在樹結(jié)構(gòu)評價(jià)方案中被組織成直接協(xié)調(diào)。詳述前期工作6，7，13， 基于樹分解和即時(shí)動(dòng)態(tài)程序?yàn)榻鉀Q半環(huán)約束滿足問題我提供了一個(gè)算法，它能用于有效計(jì)算診斷問題的大量初始解。1各個(gè)模塊簡介部分1定義在點(diǎn)陣下基于模型的優(yōu)化限制診斷。部分2回顧c半環(huán)約束。部分3提出在點(diǎn)陣基礎(chǔ)上構(gòu)造優(yōu)化約束框架，以c半環(huán)作為特殊診斷，在全部目標(biāo)函數(shù)下定義條件。部分4提出基于樹分解和動(dòng)態(tài)程序的有效解決c半環(huán)的算法。部分5展示二診斷算法和三層樹結(jié)構(gòu)，這可被看做是基于c半環(huán)限制約束的特殊例子。1在點(diǎn)陣基礎(chǔ)上的優(yōu)化限制診斷定義1(約束系統(tǒng))一個(gè)約束系統(tǒng)，一個(gè)元組=x1，。，一個(gè)變數(shù)組d1，。，一套精確的定義，f為返

4、回整型值的函數(shù)=f1，。，一套約束。約束f定義了一些功能允許可控變量和不可控變量的值。例如，布爾多核線路21可以被構(gòu)造作為一個(gè)有不同變量值的約束系統(tǒng)，f為返回整型值的函數(shù)，變量從 a到z在0，1中取值，而變量o1到a2從g,b中取值，如果一個(gè)變量完好，那么它正確的形式是布爾變量。如果一個(gè)元素被破壞，那么它的行為沒有任何假設(shè)。這個(gè)“未知的模式”捕獲約束的懸掛概念，暫且，我們假設(shè)觀察值包含在一系列約束中。我們會回來研究他們?nèi)绾卧谶\(yùn)行時(shí)被加入。第1點(diǎn)。布爾多層例子由三輸入或門和二輸入與門。輸入，輸出值可以被直接觀察出。接下來，我們用t y表示子集變量y來表示元組t的坐標(biāo)。給一個(gè)約束系統(tǒng)c一個(gè)子集的變

5、量，一個(gè)解一個(gè)元組變量，這里存在一個(gè)變量的延伸。 通過一個(gè)目標(biāo)函數(shù)去定義解決方法的偏好水平，優(yōu)化擴(kuò)展了約束系統(tǒng)。定義2(目標(biāo)函數(shù))一個(gè)目標(biāo)函數(shù)u 。a中的每個(gè)子集中的元素存在最大下界和最小上界。在診斷中，z代表了模式變量。例如，在第1點(diǎn)中的布爾變量z代表一系列的變量取值o1，o2，o3，a1，a2。診斷的不一樣的概念代表不一樣的目標(biāo)函數(shù)和點(diǎn)陣。在最小取值診斷a代表一個(gè)全序的整數(shù)集價(jià)值u代表每個(gè)功能模塊中錯(cuò)誤模塊個(gè)數(shù)在概率診斷【4】中，a基于全序在【0，1】中取值u聯(lián)系著每個(gè)功能模塊的可能取值。在最小子集診斷【15，4】中，a基于特殊順序是z的子集點(diǎn)陣，每個(gè)不同的模塊設(shè)備代表不同的錯(cuò)誤模塊功能。

6、人能考慮更遠(yuǎn)的的例子，例如，聯(lián)想一個(gè)修理費(fèi)用或部分地彼此模式分配訂購用戶偏好。對于第1點(diǎn)中的多核布爾實(shí)例，如果我們假設(shè)或門有1%失敗概率，門有。5%失敗概率。2半環(huán)限制滿足問題半環(huán)約束是一個(gè)“軟”約束的構(gòu)造，約束被延伸到包括一個(gè)偏好水平。半環(huán)限制滿足問題歸入許多其他偏愛約束 ，例如模糊限制滿足問題，概率限制滿足問題，或局部限制滿足問題。定義3半環(huán)c是一個(gè)元組 。1,a是一個(gè)配置，包括0和1.2+操作是可交換的，關(guān)聯(lián)的，冪等3。操作是可交換的，4。和+遵從分配率。例如sb = (0, 1, , , 0, 1)形成一個(gè)c半環(huán)，部分序列定義了偏好水平，這樣允許挑選出半環(huán)上定義約束最好的方法。定義4(

7、基于半環(huán)的約束系統(tǒng))基于c半環(huán)的一個(gè)約束系統(tǒng)。f是分配在a中每個(gè)元組定義的函數(shù)。“傳統(tǒng)”約束14符合基于s半環(huán)的約束系統(tǒng) ，允許定義的和未定義的變量存在值。定義5(組合和投影)讓f和g為兩個(gè)獨(dú)自的被限制的變量1定義f*g表示f和g的組合，為新的約束，每個(gè)變量組都有自己的值。2。定義f y為f的投影建立在變量y上。給一個(gè)基于c半環(huán)約束系統(tǒng)，限制優(yōu)化問題是計(jì)算一個(gè)函數(shù)。3半環(huán)約束問題的診斷在這一部分，我調(diào)查在第二部分定義的基于點(diǎn)陣上的優(yōu)化問題，在特殊診斷中，它可以被構(gòu)造成半環(huán)問題。自從基于半環(huán)約束的精確屬性確保如此本地約束傳播是可行的，這些將是解決這些問題的最基本有效的方法。我首先表明那有可能“重

8、建”一個(gè)當(dāng)量c半環(huán)從一個(gè)約束系統(tǒng)，和一個(gè)點(diǎn)陣中可重建一個(gè)等同的半環(huán)約束滿足問題。我調(diào)查，在什么條件下有可能分解全球目標(biāo)函數(shù)，定義當(dāng)?shù)仄珢鬯健＠纾恳粋€(gè)約束，那些排序的解法被保存，這建立在條件是在樹狀結(jié)構(gòu)約束滿足問題的成本優(yōu)化。說明如何這些條件符合制造基于模型診斷的一般假設(shè)。定義6(撰寫目標(biāo)函數(shù))一個(gè)目標(biāo)函數(shù)u包括了一系列元素,定理1(半環(huán)約束滿足問題的優(yōu)化 )讓c為一個(gè)在，上的約束系統(tǒng)，u為一個(gè)目標(biāo)函數(shù)。定義一個(gè)約束系統(tǒng)(x, d, f )如下:對于每一個(gè)fj f，fj被定義為fj(t) = glb(a) 。 fj(t) = 和 fj(t) = lub(a), f =f1 . . . fm

9、 u1 . . . uk. (a, lub, , glb(a), lub(a) 是一個(gè)c半環(huán) 和 (m+ki=1fi) z = u(sol(c).每個(gè)目標(biāo)函數(shù)u都初始化為0，選擇a b = glb(a, b。連同定理1，這暗示，在，上每個(gè)約束系統(tǒng)c同目標(biāo)函數(shù)u能被變成一個(gè)半環(huán)約束滿足問題， a和c有相同的解決方法使他們與u相同。舉例說來，在最小子集診斷中，目標(biāo)函數(shù)包括一元函數(shù)，如果t代表一個(gè)正確的任務(wù)，則u為空集，如果t代表一個(gè)錯(cuò)誤的任務(wù)，則u=z.同樣的，在最小基礎(chǔ)診斷和概率診斷中，目標(biāo)函數(shù)包括一元函數(shù) +和 ，對于基于模型的診斷，無初始化的目標(biāo)函數(shù)回應(yīng)在每個(gè)單獨(dú)個(gè)體中錯(cuò)誤的假設(shè)。和【2】中

10、的結(jié)果一起，定理1在點(diǎn)陣偏好結(jié)構(gòu)和硬約束之間建立了一對一回復(fù)方式。 到目前為止，我們有二分類型約束在c半環(huán):功能定義在只取變量z。雙重功能定義在取變量x.定義7（接觸算法） 通過吸收包含在其他功能上的功能，在不改變解決方法的情況下減少一系列的變量。 定理2（吸收包含的約束）定義(x,d,f)成為基于c半環(huán)的約束系統(tǒng)，定義f為函數(shù)。、 對于基于模型的診斷，假設(shè)錯(cuò)誤獨(dú)立于每個(gè)單獨(dú)的元素，那么u會包括至少一個(gè)f，然后，客觀函數(shù)會包含在約束元素中。注意這并不包括一個(gè)元素含有多個(gè)變量的情況。例如一系列的模型變量臨時(shí)代表不同的時(shí)間階段，這也不包括客觀函數(shù)與模型變量有相同值的情況（例如兩個(gè)模型間可能存在的傳

11、遞）。表1 可以現(xiàn)在總結(jié)在第二部分介紹的基于模型診斷的一樣的概念的，由于特殊情況約束優(yōu)化。表1展現(xiàn)了基于三個(gè)診斷概念的與門的結(jié)果約束。最小基礎(chǔ)診斷：在錯(cuò)誤元素個(gè)數(shù)的偏好準(zhǔn)則中診斷，目標(biāo)是是錯(cuò)誤元素的個(gè)數(shù)達(dá)到最小sc = (n+0 , min, +, , 0).最小子集診斷。在錯(cuò)誤元素系列的偏好準(zhǔn)則中診斷，目標(biāo)是錯(cuò)誤元素系列達(dá)到最小，被包含在選擇的半環(huán)s中。ss = (2z , , , z, ).最大概率診斷：在模型任務(wù)的概率中診斷偏好準(zhǔn)則，目標(biāo)是使模型任務(wù)的概率最大。sp = (0, 1, max, , 0, 1).4分解和規(guī)劃程序基于c半環(huán)的精確屬性（特別是聯(lián)系和交換性)很好的保證當(dāng)?shù)氐募s束

12、(“硬”)約束工作擴(kuò)展框架。針對當(dāng)?shù)剀浖s束的研究集中直接的協(xié)調(diào)一致，約束以一種有組織的方式跟在樹結(jié)構(gòu)的后面。特例是x操作沒有必要是冪等的，意味著約束傳播不能被應(yīng)用于混沌的方式。針對延伸軟約束【1，18】的當(dāng)?shù)貍鞑ジ拍罴性趨f(xié)調(diào)樹主題中約束以一種有組織的方式傳播。然而，隨意的約束網(wǎng)絡(luò)未必是樹結(jié)構(gòu)。結(jié)構(gòu)分解的目標(biāo)方法12，13是變成隨意的約束網(wǎng)絡(luò)到當(dāng)量，樹狀結(jié)構(gòu)(非循環(huán)的)例子，可能附近的的約束集中在一起。在硬約束中分解，但是思想自然延伸到約束優(yōu)化【6】。結(jié)構(gòu)分解基于約束系統(tǒng)假設(shè)h(x, d, f ),和每一個(gè)變量xi x,相聯(lián)系，假設(shè)和每一個(gè)約束fj f相聯(lián)系。第2點(diǎn)展示了基于布爾電路的超圖形。

13、定義8(樹分解12，13)一個(gè)樹分解為一個(gè)約束系統(tǒng)(x, d, f )，一個(gè)三重變量(t, , )，一個(gè)有根樹(v, e)，f為返回整型值的函數(shù)，如此，1 對每個(gè)f，這里存在精確的v2 對于每一個(gè)x，存在相聯(lián)系的子集t.第3點(diǎn)展示了一個(gè)的樹分解布爾多層結(jié)構(gòu)。為一個(gè)約束系統(tǒng)c定義了一個(gè)樹分解當(dāng)量，樹狀結(jié)構(gòu)約束系統(tǒng)。注意那一個(gè)一元約束以上一個(gè)變量能增加樹分解，不違反連通性條件，補(bǔ)充它在所有的節(jié)點(diǎn)當(dāng)中各變量。這允許在離線時(shí)進(jìn)行分解，并在樹被建成后增加了變量的觀察。為基于模型診斷，u從目標(biāo)函數(shù)的吸收已經(jīng)完備。這意味著，超圖形將直接對應(yīng)原設(shè)備，常常組織在一個(gè)模數(shù)的方法，對于一個(gè)任意的約束優(yōu)化問題，分解和

14、吸收目標(biāo)函數(shù)的失敗會導(dǎo)致大的限制，使問題很難被分解，導(dǎo)致大數(shù)量變量樹型的出現(xiàn)。分解可理解為在直接傳播技術(shù)中對約束系統(tǒng)的小的修補(bǔ)，第2點(diǎn)。超圖形在第1點(diǎn)中為例子。第3點(diǎn)。在第2點(diǎn)中一個(gè)的樹分解超圖形 ，顯示標(biāo)簽，對應(yīng)每個(gè)節(jié)點(diǎn)。(動(dòng)態(tài)規(guī)劃)成為可適用的。解決一個(gè)基于半環(huán)約束的樹結(jié)構(gòu)能被免費(fèi)搜索計(jì)算使用兩個(gè)步驟。第一步是用即時(shí)的動(dòng)態(tài)程序計(jì)算自上而下的元組的值，這一步可看做是研究的一個(gè)精確啟發(fā)。在第二個(gè)步驟中，這些步驟可看做具體的解決方法。這個(gè)步驟可看做精確啟發(fā)的引導(dǎo)，因此可以自由原路返回。以前工作約束優(yōu)化以分解為依據(jù)，動(dòng)態(tài)規(guī)劃6，7，13關(guān)注了計(jì)算的任務(wù)最好的的價(jià)值為個(gè)人變量或一個(gè)單獨(dú)對所有變量的最

15、優(yōu)分配。 我們針對診斷上下文的重要需求來擴(kuò)展工作。第一，在診斷時(shí)典型的是目標(biāo)解決方法的有限數(shù)字是被需要的。舉例來說，解決價(jià)值在于它的可能性，則任務(wù)是尋找一系列包含大多可能密度空間的解決問題方法。我們傳達(dá)這些需求，通過探索自下而上和自上而下的c半環(huán)的單調(diào)可能性，去減少尋找空間。第二，在診斷中，很多變量不是模型變量，并且它對于具體的解決方法不靈活。我們的方法避免在上下文中出現(xiàn)系統(tǒng)假設(shè)變量。在第4點(diǎn)的自下而上的動(dòng)態(tài)程序中出現(xiàn)的偽代碼，子集函數(shù)返回一系列子集節(jié)點(diǎn)。f是v的約束，f (v) f (c) var(f(v)被認(rèn)為是半加入，這一步建立在節(jié)點(diǎn)與它的源頭的直接傳播上。這概括了約束滿足問題【14】與

16、軟約束【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點(diǎn)。由下而上通過動(dòng)態(tài)規(guī)劃為解決一個(gè)基于半環(huán)的樹狀結(jié)構(gòu)。s b.。這探索了c半環(huán)的屬性。就是說，對于所有的a, b a都滿足(a b) s a解決問題的價(jià)值在尋求解決方法中被發(fā)現(xiàn)。root(t )是所有t的根節(jié)點(diǎn)，在計(jì)算完所有的數(shù)字后，f的最優(yōu)解就是最優(yōu)的解決算法。如果s 只是一個(gè)特殊序列，那么

17、元組的最優(yōu)解f是優(yōu)化問題的最優(yōu)解。這個(gè)問題沒有持續(xù)的解決方法，只有當(dāng)樹結(jié)構(gòu)中的節(jié)點(diǎn)v 滿足 f (v) 0.表2展示了對于布爾變量舉例的結(jié)果根數(shù)字限制。限制了單一的與門或門錯(cuò)誤和雙重的或門限制。表2。 自下而上的多層實(shí)例通過s半環(huán)第三點(diǎn)描述的書分解，沒有列出的元組的值為0。由下而上的時(shí)間復(fù)雜度的是在一個(gè)樹節(jié)點(diǎn)冪數(shù)的在最大變量數(shù)(稱作樹寬度)，它的空間復(fù)雜度是冪數(shù)的在最大的變量數(shù)那個(gè)被分享在兩個(gè)節(jié)點(diǎn)7，13因此樹分解的好處是它分解了所有變量和樹元素的指數(shù)型增長。注意的是錯(cuò)綜復(fù)雜的事物不依靠半環(huán)，這意味著從硬約束到軟約束的延伸并不增加約束問題的復(fù)雜性。在第5點(diǎn)中解決問題的偽代碼中，它列舉了自下而上

18、解決方法a s b.。舉例說來，在最小基礎(chǔ)診斷中，程序會在單限制和雙重約束下執(zhí)行。如果單錯(cuò)誤存在，那么單錯(cuò)誤只列舉在自上而下的程序段中。用那種算法很容易證明上下算法。例如，具體解決方法的數(shù)目被限制。在第5點(diǎn)，先節(jié)點(diǎn)操作細(xì)舉了樹結(jié)構(gòu)t的節(jié)點(diǎn)的優(yōu)先節(jié)點(diǎn)（例如，在第3點(diǎn)中v0, v1, v2, v3的順序）約束r包括了結(jié)果方法，如果x操作不是冪等的，自下而上的傳播通過半結(jié)合操作fi 1 fj vars(f取消。程序如下：function extract(t, b)v preorder-node-iterator-rst(t )m r f (v) |bbegin loopfor each ci chi

19、ldren(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點(diǎn)。自上而下為枚舉解一個(gè)半環(huán)約束滿足問題的樹狀結(jié)構(gòu)。解決方法只包括包含變量z的任務(wù)，其他的變量在結(jié)果中被限制。一個(gè)變量只被限制一次，它不會出現(xiàn)在其他的三個(gè)部分。在第5點(diǎn)中展示的算法中，在r和樹結(jié)構(gòu)中未執(zhí)行的部分中

20、共享的變量展示在多重設(shè)置m中。重新考慮在半環(huán)s中多層布爾變量的例子，繼續(xù)上面的舉例。假設(shè)解決方法為b=5.0e-5.最初，給v一個(gè)初始值，r在表2中被限制展示，節(jié)點(diǎn)v0有三個(gè)子節(jié)點(diǎn)，在for循環(huán)后，多重設(shè)置m為c, x, y, y, z.操作在限制變量e,f,r后的for循環(huán)后執(zhí)行。假設(shè)v1在先前序列中是t的下一個(gè)節(jié)點(diǎn)。自從x操作對于sp不是冪等的，通過操作1 ,在r 和fa2之間執(zhí)行半加入操作。表3展示了最終解。表3。枚舉自上而下的多層例子的解。復(fù)雜的自上而下階段最壞情況指數(shù)在變量z的數(shù)據(jù)類型。解枚舉法如上所述在第5點(diǎn)，要求那操作有一個(gè)對立。這個(gè)情況是針對三個(gè)半環(huán)的。5半環(huán)約束和樹結(jié)構(gòu)半環(huán)約

21、束和樹結(jié)構(gòu)是針對三結(jié)構(gòu)系統(tǒng)的二診斷算法。半環(huán)約束是一個(gè)動(dòng)態(tài)規(guī)劃算法以“量重”分配模式變量。一個(gè)正確分配有重量0，而一個(gè)異常(故障)分配有重量1。目標(biāo)是使重量的總數(shù)最小。它針對的是半環(huán)s。假設(shè)模型變量在重量課題約束中不被共享。如果用診斷模型區(qū)違反這個(gè)假設(shè)，那么半環(huán)約束會導(dǎo)致錯(cuò)誤的結(jié)論。半環(huán)語文書和樹分解相結(jié)合。半環(huán)約束包括三方面的分解，但是，它只精確一個(gè)最好的解決方法，并且，它不用限制手段，在【9】中，與gdb的比較中sab顯示了它在基于矛盾的診斷算法的優(yōu)勢。正如sab-tree計(jì)算最小基本診斷一樣，樹結(jié)構(gòu)所依據(jù)的思想是：一系列持續(xù)的分配z太小了而不能和每個(gè)元組直接聯(lián)系，這時(shí)用一個(gè)單獨(dú)的自上而下

22、的程序來代替。樹結(jié)構(gòu)將自上而下的和自下而上的階段折合成一個(gè)單獨(dú)的階段。任務(wù)的設(shè)置必須明確，因?yàn)闇p少開支費(fèi)用和模型任務(wù)代表了z的子集，在樹結(jié)構(gòu)中，變量z不包括在約束系統(tǒng)中。相反，模型任務(wù)與約束問題相聯(lián)系。模型任務(wù)通過u操作相聯(lián)系。因?yàn)檫@里沒有單獨(dú)的解決方法，元組的值通過a b =a b | a a, b b算出。樹結(jié)構(gòu)通過減少開支來限制設(shè)備和診斷的傳播。因?yàn)楝F(xiàn)在對細(xì)節(jié)階段沒有單獨(dú)的解法，找到和元組值結(jié)合的解決樹根部的解決方法。樹結(jié)構(gòu)單獨(dú)對待約束和變量值，它是半聯(lián)合和雙倍價(jià)值的約束，并且更新了下一步的價(jià)值，但是注意，如果結(jié)果只是找一個(gè)更好的診斷，在z中更新的數(shù)據(jù)將呈指數(shù)形式增長。有效的數(shù)字結(jié)構(gòu)，例如算法決定數(shù)字，在c半環(huán)基礎(chǔ)上存在約束，a是確切數(shù)的子集。對于強(qiáng)約束和大的z集合