基于粗糙集的智能規(guī)劃算法的研究
2007-01-01 00:00:00劉日仙袁利永谷文祥
計算機(jī)應(yīng)用研究 2007年1期
摘要：提出一種新的不確定，即初始對象集合的不確定，并利用粗糙集理論來解決這種不確定性；將粗糙集理論和智能規(guī)劃相結(jié)合，提出一種新的不確定規(guī)劃——粗規(guī)劃。給出了粗規(guī)劃問題的概念、粗規(guī)劃的初始狀態(tài)、粗糙動作和粗規(guī)劃目標(biāo)等一系列相關(guān)的定義，提出了粗規(guī)劃問題的兩種求解模型，并給出基于規(guī)劃圖的粗規(guī)劃算法。
關(guān)鍵詞：智能規(guī)劃； 粗糙集； 粗規(guī)劃； 粗糙動作
中圖法分類號：TP301．6文獻(xiàn)標(biāo)識碼：A
文章編號：1001－3695(2007)01－0075－03
智能規(guī)劃是人工智能的一個重要領(lǐng)域。近年來，有關(guān)智能規(guī)劃的研究在問題描述和問題求解兩方面得到了新的突破，使得智能規(guī)劃已成為現(xiàn)在一個熱門的人工智能研究領(lǐng)域。隨著智能規(guī)劃從理論研究逐漸向應(yīng)用研究發(fā)展，人們發(fā)現(xiàn)經(jīng)典的智能規(guī)劃根本無法滿足實際應(yīng)用的要求，因為經(jīng)典規(guī)劃要求知識的完全性，即要求狀態(tài)空間確定，初始狀態(tài)、動作、動作的結(jié)果狀態(tài)、目標(biāo)狀態(tài)已知，而在實際應(yīng)用中的真實世界里具有許多不確定的因素。所以研究者們提出了不確定性規(guī)劃來求解具有不確定性的規(guī)劃問題。在不確定性規(guī)劃問題中的不確定性源主要有初始狀態(tài)的不確定和動作的不確定。
本文通過對不確定性規(guī)劃的研究，提出了一種新的不確定性：初始對象的不確定，也就是規(guī)劃問題的初始對象集根據(jù)目前已知的知識是不精確、不確定的。一個規(guī)劃問題是由問題的初始狀態(tài)、問題的操作集合、問題的對象集合和問題的目標(biāo)狀態(tài)組成的。如果說規(guī)劃問題的對象集合不確定的話，則會導(dǎo)致智能規(guī)劃的不確定。
粗規(guī)劃是一個全新的研究領(lǐng)域，雖然粗糙集和智能規(guī)劃是國內(nèi)外研究的熱點，但目前國內(nèi)外還沒有關(guān)于粗規(guī)劃的研究。所以本文的研究工作在理論上具有很大的學(xué)術(shù)價值；而且在實際的應(yīng)用中，它也有很好的應(yīng)用前景。
1初始對象集的不確定
本文要研究的是智能規(guī)劃中的另一種不確定性，即初始對象集合的不確定性。一個規(guī)劃問題是由問題的初始狀態(tài)、問題的操作集合、問題的對象集合和問題的目標(biāo)狀態(tài)組成的。若規(guī)劃問題的對象集合不確定，則會導(dǎo)致智能規(guī)劃的不確定。
初始對象集的不確定是指規(guī)劃問題的初始對象集合由于所知的知識的有限性是不確定、不精確的，從而導(dǎo)致了規(guī)劃問題的不確定性。
本文將利用粗糙集理論來處理對象集合的不確定性，主要有以下兩個優(yōu)勢：
（1）由于利用粗糙集理論處理問題時不需要提供除問題所需處理的數(shù)據(jù)集合之外的任何先驗信息，所以利用它來處理初始對象集的不確定性，不需要其他的先驗知識；
(2)粗糙集理論可以進(jìn)行知識的發(fā)現(xiàn)和知識的學(xué)習(xí)，利用它來處理初始對象集的不確定，可以使智能規(guī)劃系統(tǒng)具有一定的知識學(xué)習(xí)能力向基于知識的智能規(guī)劃系統(tǒng)發(fā)展。
2粗規(guī)劃
2．1粗規(guī)劃問題
在智能規(guī)劃中有這樣一類問題，就是對不同的規(guī)劃對象進(jìn)行不同的規(guī)劃，如對于又紅又大的蘋果，我們可能會先對其進(jìn)行包裝，然后采用海運或其他好一點的交通運輸，以保證其出口；而對于一般的蘋果，則直接采用火車進(jìn)行運輸?shù)?，也就是對于不同類別的對象采用的規(guī)劃是不一樣的。
在實際的應(yīng)用中，經(jīng)常是在運用智能規(guī)劃之前必須先識別出要處理的對象是哪個類別的，然后才能進(jìn)行規(guī)劃。例如，在一個電子郵件自動處理系統(tǒng)中，當(dāng)系統(tǒng)收到新的郵件時，必須先識別出該郵件是垃圾郵件還是正常通信的郵件，然后才能進(jìn)行規(guī)劃，求得一個規(guī)劃解；執(zhí)行這個規(guī)劃，達(dá)到我們期望的目標(biāo)，對正常通信的郵件進(jìn)行回復(fù)，對垃圾郵件進(jìn)行刪除。
定義1給定一個五元組（O，A，B，I，G），其中O是操作集合，A是對象的集合，B是關(guān)于對象集合A中對象的知識，且集合A是B的Rough集（粗糙集），I是初始狀態(tài)，G是目標(biāo)狀態(tài)，I和G均用一個邏輯公式來描述，則這個五元組就構(gòu)成一個粗規(guī)劃問題。
例如，有這樣一個五元組
表1信息表
2．2粗規(guī)劃的初始狀態(tài)
在粗規(guī)劃問題的初始狀態(tài)中，只有對初始對象集合A中對象的一些描述，但沒有對一些可能屬于集合A的對象的描述，這就產(chǎn)生了初始狀態(tài)的不確定性。例如前面的這個例子中，集合A={X1，X3，X4}，B={顏色，大小，形狀}，集合A是一個B Rough集，A的B下近似集為B_(A)={X3，X4}，A的B上近似集B-(A)={X1， X2， X3， X4}，也就是X3和X4肯定屬于集合A，而可能或肯定屬于集合A的對象有X1， X2， X3， X4，所以B-(A)/B_(A)={X1， X2}，說明X1和X2可能屬于集合A。而初始狀態(tài)I中只有對對象X1， X3， X4的描述，而沒有對對象X2的描述，也就是說缺少對對象X2初始狀態(tài)的描述，為此我們對初始狀態(tài)的定義進(jìn)行了擴(kuò)展，使初始狀態(tài)中具有對所有可能對象的狀態(tài)描述。
可能初始狀態(tài)是對原始初始狀態(tài)的一個補充，但它存在一定的不確定性，因為可能對象的初始狀態(tài)有可能與其同類對象的初始狀態(tài)并不完全相同，也就是說不能用其同類對象的狀態(tài)來替代它的狀態(tài)。但一般說來，同類對象具有很多的相似性，它們初始狀態(tài)相同的可能性比較大。
2．3粗糙動作
一個粗糙操作必須能夠根據(jù)實例化該操作的對象的粗糙隸屬度給出該操作實例的粗糙度。
下面給出粗糙動作的BNF范式：
2．4粗規(guī)劃目標(biāo)
粗規(guī)劃目標(biāo)集合G是一個確定的集合，但初始對象的不確定性，可得到一個擴(kuò)展的目標(biāo)集合G′。
定義3擴(kuò)展的目標(biāo)集合。 給定一個粗規(guī)劃問題，它是一個五元組（O，A，B，I，G），其中G是規(guī)劃問題的目標(biāo)集合，對象集合A是一個B Rough集，則可得到一個擴(kuò)展的目標(biāo)集合R(G)=G∪G′，其中G′是對可能屬于對象集A的對象的可能目標(biāo)的描述，對于每一個B-(A)/ A中的對象X，用[X]B中的對象在G中的目標(biāo)描述來作為對象X的最終目標(biāo)。
規(guī)劃問題求解時要求最終實現(xiàn)目標(biāo)集合G，并不要求完全實現(xiàn)擴(kuò)展的目標(biāo)集合，但擴(kuò)展的目標(biāo)集合可作為一個評價規(guī)劃解的標(biāo)準(zhǔn)。也就是在規(guī)劃長度相同的情況下，如果一個規(guī)劃能夠更多地實現(xiàn)擴(kuò)展目標(biāo)集合目標(biāo)的話，則這個規(guī)劃解相對來說質(zhì)量好一點。但是在求有效規(guī)劃解時，只要實現(xiàn)目標(biāo)集合G的有效規(guī)劃就是規(guī)劃問題的一個規(guī)劃解。
2．5規(guī)劃的上近似集和下近似集
一個規(guī)劃的上近似集就是將一個規(guī)劃所包含的每個動作中的對象用該對象集合的下近似集替換，這樣就得到該規(guī)劃的下近似集。
一個規(guī)劃的下近似集就是將一個規(guī)劃所包含的每個動作中的對象用該對象集合的上近似集替換，這樣就得到該規(guī)劃的上近似集。
3粗規(guī)劃問題的求解模型
模型1（圖1）的主要思想是將一個粗規(guī)劃問題P=(O， A， B， I， G)拆分成兩個一般的規(guī)劃問題P1和P2。P1=(O， B-(A)， I， G)，它的對象集是A的上近似集B-(A)；P2=(O， B_(A)， I， G)，它的對象集是A的下近似集B_(A)。
模型2（圖2）的主要思想是對規(guī)劃器的算法及操作進(jìn)行改進(jìn)，然后直接對粗規(guī)劃問題進(jìn)行求解。
4基于規(guī)劃圖的粗規(guī)劃算法
4．1粗規(guī)劃圖的構(gòu)造
粗規(guī)劃圖是一個緊湊的有向圖結(jié)構(gòu)。粗規(guī)劃圖包括兩種節(jié)點和三種邊：
（1）動作節(jié)點。用于表示一個粗糙動作或一般的動作（非粗糙動作）。
（2）命題節(jié)點。用于表示一個命題。
（3）前提邊。用于連接動作節(jié)點和表示動作前提條件的命題節(jié)點。
（4）添加效果邊。用于連接動作節(jié)點和動作節(jié)點表示的動作添加的命題節(jié)點。
（5）刪除效果邊。用于連接動作節(jié)點和動作節(jié)點表示的動作刪除的命題節(jié)點。
一個粗規(guī)劃圖按照上面的說明構(gòu)成了一個層次有向結(jié)構(gòu)，由命題節(jié)點構(gòu)成的命題層和動作節(jié)點構(gòu)成的動作層交替構(gòu)成。規(guī)劃圖從初始命題構(gòu)成的命題層開始，通過前提邊連接下層動作層，動作層則通過效果邊連接下層命題層，依此類推。
4．2粗規(guī)劃圖的搜索過程
給定一個粗規(guī)劃圖，提取一個有效的規(guī)劃是一個重要的過程。對于一個粗規(guī)劃問題，我們只需要實現(xiàn)目標(biāo)集合G，而不一定完全實現(xiàn)其擴(kuò)展目標(biāo)集合，但擴(kuò)展的目標(biāo)集合并不一定完全實現(xiàn)，而只是作為衡量規(guī)劃解的一個標(biāo)準(zhǔn)。在對粗規(guī)劃圖進(jìn)行搜索時，我們利用回溯的思想從后往前搜索，尋找一個有效規(guī)劃，它能夠?qū)崿F(xiàn)目標(biāo)集合G；然后再求取該規(guī)劃的上近似集和下近似集，看是否是規(guī)劃問題的擴(kuò)展目標(biāo)集合的一個有效規(guī)劃解（即從初始狀態(tài)出發(fā)執(zhí)行該規(guī)劃是否能實現(xiàn)擴(kuò)展目標(biāo)集合中的目標(biāo)）。
根據(jù)動作的實例化對象的粗糙度來計算動作的粗糙度，初始狀態(tài)中初始命題的粗糙度為0，精確度為1，那些在可能初始狀態(tài)中但不在初始狀態(tài)I中的命題的粗糙度根據(jù)該命題中對象的粗糙隸屬度來確定。在搜索過程中選擇動作時，選擇粗糙度低的動作，最后得到一個粗糙度最低（精確度最高）的規(guī)劃。
5總結(jié)
本文提出了智能規(guī)劃中的初始對象集的不確定性，這種不確定性不是由對象集的模糊而引起的，它是由于我們對對象的知識了解不充分而導(dǎo)致的。也就是說，相對于我們已知的知識，規(guī)劃問題的初始對象集是一個粗糙集。針對這一不確定性，本文在對智能規(guī)劃和粗糙集理論深入研究的基礎(chǔ)上給出了粗規(guī)劃問題的定義，并將粗糙集理論與智能規(guī)劃相結(jié)合，提出了粗規(guī)劃問題的求解模型。
由于規(guī)劃圖算法在規(guī)劃領(lǐng)域的特殊地位和突出的效率，我們給出了一種基于規(guī)劃圖的粗糙規(guī)劃算法，主要包括粗規(guī)劃圖的構(gòu)造和對粗規(guī)劃圖的搜索算法。由于筆者的能力有限，有些問題仍待后續(xù)研究。相信在我們的努力下，粗規(guī)劃不僅會有非常好的理論前景，也會有實際的應(yīng)用價值。
參考文獻(xiàn)：
［1］Blum A， Furst M. Fast Planning through Planning Graph Analysis[C].Proc. of the 14th Int. Joint Conf. AI，1995.16361642.
［2］Corin R Anderson， et al. Conditional Effects in Graphplan[C]. Proc. of AI Planning Systems Conference，1998.13201325.
［3］A L Blum， J C Langford. Probabilistic Planning in the Graphplan Framework[C]. AIPS’98 Workshop on Planning as Combinatorial Search， 1998.812.
［4］D Smith， D Weld. Conformant Graphplan[C]. Proc. of the 15th Nat. Conf. AI， 1998.210245.
［5］D S Weld， C R Anderson， D E Smith. Extending Graphplan to Handle Uncertainty and Sensing Actions[C]. Proc. of the 15th Nat. Conf. AI，1998.897904.
［6］J Koehler， B Nebel， J Hoffmann， et al. Extending Planning Graphs to an ADL Subset[C]. Proc. of the 4th European Conference on Planning，1997.273285.
［7］R Kambhampati， E Lambrecht， E Parker. Understanding and Extending Graphplan[C]. Proc. of the 4th European Conference on Planning，1997.635642.
［8］D Weld. An Introduction to Leastcommitment Planning[J]. AI Maga￣zine， 1994，15(4):2761.
［9］Pawlak Z. Rough Sets[J]. International Journal of Information and Computer Science， 1982，11(5)：341356.
［10］劉清.Rough集及Rough推理[M]. 北京： 科學(xué)出版社， 2001.100150.
［11］王國胤.Rough集理論與知識獲取[M]. 西安：西安交通大學(xué)出版社， 2001.200260.
作者簡介：
劉日仙（1980），女，浙江江山人，碩士，主要研究方向為智能規(guī)劃與規(guī)劃識別；袁利永（1978），男，浙江嵊州人，碩士，主要研究方向為軟件工程；谷文祥（1947），男，吉林農(nóng)安人，教授，主要研究方向為智能規(guī)劃和規(guī)劃識別、形式語言與自動機(jī)理論、模糊群等。
注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文
