局部搜索技術(shù)在析取時序問題中的應(yīng)用.pdf

1、帶有時序信息的推理問題是人工智能領(lǐng)域的重要研究內(nèi)容。析取時序問題(Disjunctive Temporal Problem，DTP)是時序推理及調(diào)度領(lǐng)域內(nèi)更具表達(dá)能力的問題模型，由于其事件間約束的復(fù)雜性，生成問題的可行解現(xiàn)已證明是較難解決的問題。因此如何快速獲得問題的可行解引起了大量研究人員的關(guān)注:一類解決方案是將DTP轉(zhuǎn)化為約束可滿足問題(Constraint Satisfaction Problems，CSP)，使用標(biāo)準(zhǔn)的CSP求解

2、技術(shù)來求解;另一類是將DTP編碼為一個命題可滿足問題(Propositional Satisfaction Problem，SAT)，使用現(xiàn)有求解SAT的算法來求解。然而，DTP在問題轉(zhuǎn)化、啟發(fā)式策略及搜索技術(shù)的應(yīng)用等方面仍然存在改進(jìn)空間。
　　局部搜索技術(shù)一直受到人工智能界的極大關(guān)注，GSAT算法的出現(xiàn)再次證明該技術(shù)在求解可滿足問題時有著較高的效率。但是，局部搜索技術(shù)目前仍沒有成功的用于求解DTP。本文主要研究如何將局部搜索技術(shù)

3、應(yīng)用于求解DTP。為此，本文實(shí)現(xiàn)了應(yīng)用局部搜索技術(shù)并加入約束加權(quán)思想的TSAT算法，將其做部分修改，用于對DTP直接進(jìn)行求解;通過分析DTP的問題結(jié)構(gòu)，我們將TSAT算法與DPC算法結(jié)合，提出了TSAT算法的改進(jìn)算法—mTSAT，并將DTP轉(zhuǎn)化為元約束可滿足問題(meta-CSP)，用mTSAT算法在各變量的鄰域內(nèi)搜索并生成簡單時序問題，然后判斷其一致性，達(dá)到縮小搜索空間以提高DTP求解效率的目的。
　　為了評估TSAT算法的性能