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

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

2、主義為軟的約束19，2目的在于更加接近的實現(xiàn)約束優(yōu)化和限制問題。這個元素可以被闡釋由于重量，成本，效用，可能性，或優(yōu)先權(quán)。一個一般骨架為軟半環(huán)約束2被基于一個半環(huán)。半環(huán)行動各自規(guī)劃和聯(lián)合。技術(shù)示范基于模型診斷，在由點陣偏好結(jié)構(gòu)和強約束組成的普通優(yōu)化問題，能構(gòu)成半環(huán)約束，全球目標(biāo)函數(shù)和偏愛水平控制。它提高實際效用的半環(huán)約束，將領(lǐng)框架結(jié)構(gòu)，不一樣的概念的基于模型診斷（最小基本診斷，最小子集診斷，概率的診斷)能容易獲得由選擇一個合適的半環(huán)。在這個過程中，我利用基于模型診斷中的假設(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)評價方案中被組織成直接協(xié)調(diào)。詳述前期工作6，7，13， 基于樹分解和即時動態(tài)程序為解決半環(huán)約束滿足問題我提供了一個算法，它能用于有效計算診斷問題的大量初始解。1各個模塊簡介部分1定義在點陣下基于模型的優(yōu)化限制診斷。部分2回顧c半環(huán)約束。部分3提出在點陣基礎(chǔ)上構(gòu)造優(yōu)化約束框架，以c半環(huán)作為特殊診斷，在全部目標(biāo)函數(shù)下定義條件。部分4提出基于樹分解和動態(tài)程序的有效解決c半環(huán)的算法。部分5展示二診斷算法和三層樹結(jié)構(gòu)，這可被看做是基于c半環(huán)限制約束的特殊例子。1在點陣基礎(chǔ)上的優(yōu)化限制診斷定義1(約束系統(tǒng))一個約束系統(tǒng)，一個元組=x1，。，一個變數(shù)組d1，。，一套精確的定義，f為返

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

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

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

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

8、建”一個當(dāng)量c半環(huán)從一個約束系統(tǒng)，和一個點陣中可重建一個等同的半環(huán)約束滿足問題。我調(diào)查，在什么條件下有可能分解全球目標(biāo)函數(shù)，定義當(dāng)?shù)仄珢鬯健＠?，每一個約束，那些排序的解法被保存，這建立在條件是在樹狀結(jié)構(gòu)約束滿足問題的成本優(yōu)化。說明如何這些條件符合制造基于模型診斷的一般假設(shè)。定義6(撰寫目標(biāo)函數(shù))一個目標(biāo)函數(shù)u包括了一系列元素,定理1(半環(huán)約束滿足問題的優(yōu)化 )讓c為一個在，上的約束系統(tǒng)，u為一個目標(biāo)函數(shù)。定義一個約束系統(tǒng)(x, d, f )如下:對于每一個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) 是一個c半環(huán) 和 (m+ki=1fi) z = u(sol(c).每個目標(biāo)函數(shù)u都初始化為0，選擇a b = glb(a, b。連同定理1，這暗示，在，上每個約束系統(tǒng)c同目標(biāo)函數(shù)u能被變成一個半環(huán)約束滿足問題， a和c有相同的解決方法使他們與u相同。舉例說來，在最小子集診斷中，目標(biāo)函數(shù)包括一元函數(shù)，如果t代表一個正確的任務(wù)，則u為空集，如果t代表一個錯誤的任務(wù)，則u=z.同樣的，在最小基礎(chǔ)診斷和概率診斷中，目標(biāo)函數(shù)包括一元函數(shù) +和 ，對于基于模型的診斷，無初始化的目標(biāo)函數(shù)回應(yīng)在每個單獨個體中錯誤的假設(shè)。和【2】中

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

11、遞）。表1 可以現(xiàn)在總結(jié)在第二部分介紹的基于模型診斷的一樣的概念的，由于特殊情況約束優(yōu)化。表1展現(xiàn)了基于三個診斷概念的與門的結(jié)果約束。最小基礎(chǔ)診斷：在錯誤元素個數(shù)的偏好準(zhǔn)則中診斷，目標(biāo)是是錯誤元素的個數(shù)達到最小sc = (n+0 , min, +, , 0).最小子集診斷。在錯誤元素系列的偏好準(zhǔn)則中診斷，目標(biāo)是錯誤元素系列達到最小，被包含在選擇的半環(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、(“硬”)約束工作擴展框架。針對當(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 ),和每一個變量xi x,相聯(lián)系，假設(shè)和每一個約束fj f相聯(lián)系。第2點展示了基于布爾電路的超圖形。

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

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

15、優(yōu)分配。 我們針對診斷上下文的重要需求來擴展工作。第一，在診斷時典型的是目標(biāo)解決方法的有限數(shù)字是被需要的。舉例來說，解決價值在于它的可能性，則任務(wù)是尋找一系列包含大多可能密度空間的解決問題方法。我們傳達這些需求，通過探索自下而上和自上而下的c半環(huán)的單調(diào)可能性，去減少尋找空間。第二，在診斷中，很多變量不是模型變量，并且它對于具體的解決方法不靈活。我們的方法避免在上下文中出現(xiàn)系統(tǒng)假設(shè)變量。在第4點的自下而上的動態(tài)程序中出現(xiàn)的偽代碼，子集函數(shù)返回一系列子集節(jié)點。f是v的約束，f (v) f (c) var(f(v)被認為是半加入，這一步建立在節(jié)點與它的源頭的直接傳播上。這概括了約束滿足問題【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點。由下而上通過動態(tài)規(guī)劃為解決一個基于半環(huán)的樹狀結(jié)構(gòu)。s b.。這探索了c半環(huán)的屬性。就是說，對于所有的a, b a都滿足(a b) s a解決問題的價值在尋求解決方法中被發(fā)現(xiàn)。root(t )是所有t的根節(jié)點，在計算完所有的數(shù)字后，f的最優(yōu)解就是最優(yōu)的解決算法。如果s 只是一個特殊序列，那么

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

18、解決方法a s b.。舉例說來，在最小基礎(chǔ)診斷中，程序會在單限制和雙重約束下執(zhí)行。如果單錯誤存在，那么單錯誤只列舉在自上而下的程序段中。用那種算法很容易證明上下算法。例如，具體解決方法的數(shù)目被限制。在第5點，先節(jié)點操作細舉了樹結(jié)構(gòu)t的節(jié)點的優(yōu)先節(jié)點（例如，在第3點中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點。自上而下為枚舉解一個半環(huán)約束滿足問題的樹狀結(jié)構(gòu)。解決方法只包括包含變量z的任務(wù)，其他的變量在結(jié)果中被限制。一個變量只被限制一次，它不會出現(xiàn)在其他的三個部分。在第5點中展示的算法中，在r和樹結(jié)構(gòu)中未執(zhí)行的部分中

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

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

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