基于粗糙集的智能規(guī)劃算法的研究

摘要：提出一種新的不確定，即初始對(duì)象集合的不確定，并利用粗糙集理論來解決這種不確定性；將粗糙集理論和智能規(guī)劃相結(jié)合，提出一種新的不確定規(guī)劃——粗規(guī)劃。給出了粗規(guī)劃問題的概念、粗規(guī)劃的初始狀態(tài)、粗糙動(dòng)作和粗規(guī)劃目標(biāo)等一系列相關(guān)的定義，提出了粗規(guī)劃問題的兩種求解模型，并給出基于規(guī)劃圖的粗規(guī)劃算法。

關(guān)鍵詞：智能規(guī)劃； 粗糙集； 粗規(guī)劃； 粗糙動(dòng)作

中圖法分類號(hào)：TP301．6文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001－3695(2007)01－0075－03

智能規(guī)劃是人工智能的一個(gè)重要領(lǐng)域。近年來，有關(guān)智能規(guī)劃的研究在問題描述和問題求解兩方面得到了新的突破，使得智能規(guī)劃已成為現(xiàn)在一個(gè)熱門的人工智能研究領(lǐng)域。隨著智能規(guī)劃從理論研究逐漸向應(yīng)用研究發(fā)展，人們發(fā)現(xiàn)經(jīng)典的智能規(guī)劃根本無法滿足實(shí)際應(yīng)用的要求，因?yàn)榻?jīng)典規(guī)劃要求知識(shí)的完全性，即要求狀態(tài)空間確定，初始狀態(tài)、動(dòng)作、動(dòng)作的結(jié)果狀態(tài)、目標(biāo)狀態(tài)已知，而在實(shí)際應(yīng)用中的真實(shí)世界里具有許多不確定的因素。所以研究者們提出了不確定性規(guī)劃來求解具有不確定性的規(guī)劃問題。在不確定性規(guī)劃問題中的不確定性源主要有初始狀態(tài)的不確定和動(dòng)作的不確定。

本文通過對(duì)不確定性規(guī)劃的研究，提出了一種新的不確定性：初始對(duì)象的不確定，也就是規(guī)劃問題的初始對(duì)象集根據(jù)目前已知的知識(shí)是不精確、不確定的。一個(gè)規(guī)劃問題是由問題的初始狀態(tài)、問題的操作集合、問題的對(duì)象集合和問題的目標(biāo)狀態(tài)組成的。如果說規(guī)劃問題的對(duì)象集合不確定的話，則會(huì)導(dǎo)致智能規(guī)劃的不確定。

粗規(guī)劃是一個(gè)全新的研究領(lǐng)域，雖然粗糙集和智能規(guī)劃是國內(nèi)外研究的熱點(diǎn)，但目前國內(nèi)外還沒有關(guān)于粗規(guī)劃的研究。所以本文的研究工作在理論上具有很大的學(xué)術(shù)價(jià)值；而且在實(shí)際的應(yīng)用中，它也有很好的應(yīng)用前景。

1初始對(duì)象集的不確定

本文要研究的是智能規(guī)劃中的另一種不確定性，即初始對(duì)象集合的不確定性。一個(gè)規(guī)劃問題是由問題的初始狀態(tài)、問題的操作集合、問題的對(duì)象集合和問題的目標(biāo)狀態(tài)組成的。若規(guī)劃問題的對(duì)象集合不確定，則會(huì)導(dǎo)致智能規(guī)劃的不確定。

初始對(duì)象集的不確定是指規(guī)劃問題的初始對(duì)象集合由于所知的知識(shí)的有限性是不確定、不精確的，從而導(dǎo)致了規(guī)劃問題的不確定性。

本文將利用粗糙集理論來處理對(duì)象集合的不確定性，主要有以下兩個(gè)優(yōu)勢(shì)：

（1）由于利用粗糙集理論處理問題時(shí)不需要提供除問題所需處理的數(shù)據(jù)集合之外的任何先驗(yàn)信息，所以利用它來處理初始對(duì)象集的不確定性，不需要其他的先驗(yàn)知識(shí)；

(2)粗糙集理論可以進(jìn)行知識(shí)的發(fā)現(xiàn)和知識(shí)的學(xué)習(xí)，利用它來處理初始對(duì)象集的不確定，可以使智能規(guī)劃系統(tǒng)具有一定的知識(shí)學(xué)習(xí)能力向基于知識(shí)的智能規(guī)劃系統(tǒng)發(fā)展。

2粗規(guī)劃

2．1粗規(guī)劃問題

在智能規(guī)劃中有這樣一類問題，就是對(duì)不同的規(guī)劃對(duì)象進(jìn)行不同的規(guī)劃，如對(duì)于又紅又大的蘋果，我們可能會(huì)先對(duì)其進(jìn)行包裝，然后采用海運(yùn)或其他好一點(diǎn)的交通運(yùn)輸，以保證其出口；而對(duì)于一般的蘋果，則直接采用火車進(jìn)行運(yùn)輸?shù)龋簿褪菍?duì)于不同類別的對(duì)象采用的規(guī)劃是不一樣的。

在實(shí)際的應(yīng)用中，經(jīng)常是在運(yùn)用智能規(guī)劃之前必須先識(shí)別出要處理的對(duì)象是哪個(gè)類別的，然后才能進(jìn)行規(guī)劃。例如，在一個(gè)電子郵件自動(dòng)處理系統(tǒng)中，當(dāng)系統(tǒng)收到新的郵件時(shí)，必須先識(shí)別出該郵件是垃圾郵件還是正常通信的郵件，然后才能進(jìn)行規(guī)劃，求得一個(gè)規(guī)劃解；執(zhí)行這個(gè)規(guī)劃，達(dá)到我們期望的目標(biāo)，對(duì)正常通信的郵件進(jìn)行回復(fù)，對(duì)垃圾郵件進(jìn)行刪除。

定義1給定一個(gè)五元組（O，A，B，I，G），其中O是操作集合，A是對(duì)象的集合，B是關(guān)于對(duì)象集合A中對(duì)象的知識(shí)，且集合A是B的Rough集（粗糙集），I是初始狀態(tài)，G是目標(biāo)狀態(tài)，I和G均用一個(gè)邏輯公式來描述，則這個(gè)五元組就構(gòu)成一個(gè)粗規(guī)劃問題。

例如，有這樣一個(gè)五元組，其中操作集合O中有這樣幾個(gè)操作：包裝(Package)、出口(Export)、海運(yùn)、陸運(yùn)等，對(duì)象集合A={X1，X3，X4}，B={顏色，大小，形狀}，集合A關(guān)于B的知識(shí)可以用如表1所示的信息表來描述。

表1信息表

2．2粗規(guī)劃的初始狀態(tài)

在粗規(guī)劃問題的初始狀態(tài)中，只有對(duì)初始對(duì)象集合A中對(duì)象的一些描述，但沒有對(duì)一些可能屬于集合A的對(duì)象的描述，這就產(chǎn)生了初始狀態(tài)的不確定性。例如前面的這個(gè)例子中，集合A={X1，X3，X4}，B={顏色，大小，形狀}，集合A是一個(gè)B Rough集，A的B下近似集為B_(A)={X3，X4}，A的B上近似集B-(A)={X1， X2， X3， X4}，也就是X3和X4肯定屬于集合A，而可能或肯定屬于集合A的對(duì)象有X1， X2， X3， X4，所以B-(A)/B_(A)={X1， X2}，說明X1和X2可能屬于集合A。而初始狀態(tài)I中只有對(duì)對(duì)象X1， X3， X4的描述，而沒有對(duì)對(duì)象X2的描述，也就是說缺少對(duì)對(duì)象X2初始狀態(tài)的描述，為此我們對(duì)初始狀態(tài)的定義進(jìn)行了擴(kuò)展，使初始狀態(tài)中具有對(duì)所有可能對(duì)象的狀態(tài)描述。

可能初始狀態(tài)是對(duì)原始初始狀態(tài)的一個(gè)補(bǔ)充，但它存在一定的不確定性，因?yàn)榭赡軐?duì)象的初始狀態(tài)有可能與其同類對(duì)象的初始狀態(tài)并不完全相同，也就是說不能用其同類對(duì)象的狀態(tài)來替代它的狀態(tài)。但一般說來，同類對(duì)象具有很多的相似性，它們初始狀態(tài)相同的可能性比較大。

2．3粗糙動(dòng)作

一個(gè)粗糙操作必須能夠根據(jù)實(shí)例化該操作的對(duì)象的粗糙隸屬度給出該操作實(shí)例的粗糙度。

下面給出粗糙動(dòng)作的BNF范式：

2．4粗規(guī)劃目標(biāo)

粗規(guī)劃目標(biāo)集合G是一個(gè)確定的集合，但初始對(duì)象的不確定性，可得到一個(gè)擴(kuò)展的目標(biāo)集合G′。 

定義3擴(kuò)展的目標(biāo)集合。 給定一個(gè)粗規(guī)劃問題，它是一個(gè)五元組（O，A，B，I，G），其中G是規(guī)劃問題的目標(biāo)集合，對(duì)象集合A是一個(gè)B Rough集，則可得到一個(gè)擴(kuò)展的目標(biāo)集合R(G)=G∪G′，其中G′是對(duì)可能屬于對(duì)象集A的對(duì)象的可能目標(biāo)的描述，對(duì)于每一個(gè)B-(A)/ A中的對(duì)象X，用[X]B中的對(duì)象在G中的目標(biāo)描述來作為對(duì)象X的最終目標(biāo)。

規(guī)劃問題求解時(shí)要求最終實(shí)現(xiàn)目標(biāo)集合G，并不要求完全實(shí)現(xiàn)擴(kuò)展的目標(biāo)集合，但擴(kuò)展的目標(biāo)集合可作為一個(gè)評(píng)價(jià)規(guī)劃解的標(biāo)準(zhǔn)。也就是在規(guī)劃長度相同的情況下，如果一個(gè)規(guī)劃能夠更多地實(shí)現(xiàn)擴(kuò)展目標(biāo)集合目標(biāo)的話，則這個(gè)規(guī)劃解相對(duì)來說質(zhì)量好一點(diǎn)。但是在求有效規(guī)劃解時(shí)，只要實(shí)現(xiàn)目標(biāo)集合G的有效規(guī)劃就是規(guī)劃問題的一個(gè)規(guī)劃解。

2．5規(guī)劃的上近似集和下近似集

一個(gè)規(guī)劃的上近似集就是將一個(gè)規(guī)劃所包含的每個(gè)動(dòng)作中的對(duì)象用該對(duì)象集合的下近似集替換，這樣就得到該規(guī)劃的下近似集。

一個(gè)規(guī)劃的下近似集就是將一個(gè)規(guī)劃所包含的每個(gè)動(dòng)作中的對(duì)象用該對(duì)象集合的上近似集替換，這樣就得到該規(guī)劃的上近似集。

3粗規(guī)劃問題的求解模型

模型1（圖1）的主要思想是將一個(gè)粗規(guī)劃問題P=(O， A， B， I， G)拆分成兩個(gè)一般的規(guī)劃問題P1和P2。P1=(O， B-(A)， I， G)，它的對(duì)象集是A的上近似集B-(A)；P2=(O， B_(A)， I， G)，它的對(duì)象集是A的下近似集B_(A)。

模型2（圖2）的主要思想是對(duì)規(guī)劃器的算法及操作進(jìn)行改進(jìn)，然后直接對(duì)粗規(guī)劃問題進(jìn)行求解。

4基于規(guī)劃圖的粗規(guī)劃算法

4．1粗規(guī)劃圖的構(gòu)造

粗規(guī)劃圖是一個(gè)緊湊的有向圖結(jié)構(gòu)。粗規(guī)劃圖包括兩種節(jié)點(diǎn)和三種邊：

（1）動(dòng)作節(jié)點(diǎn)。用于表示一個(gè)粗糙動(dòng)作或一般的動(dòng)作（非粗糙動(dòng)作）。

（2）命題節(jié)點(diǎn)。用于表示一個(gè)命題。

（3）前提邊。用于連接動(dòng)作節(jié)點(diǎn)和表示動(dòng)作前提條件的命題節(jié)點(diǎn)。

（4）添加效果邊。用于連接動(dòng)作節(jié)點(diǎn)和動(dòng)作節(jié)點(diǎn)表示的動(dòng)作添加的命題節(jié)點(diǎn)。

（5）刪除效果邊。用于連接動(dòng)作節(jié)點(diǎn)和動(dòng)作節(jié)點(diǎn)表示的動(dòng)作刪除的命題節(jié)點(diǎn)。

一個(gè)粗規(guī)劃圖按照上面的說明構(gòu)成了一個(gè)層次有向結(jié)構(gòu)，由命題節(jié)點(diǎn)構(gòu)成的命題層和動(dòng)作節(jié)點(diǎn)構(gòu)成的動(dòng)作層交替構(gòu)成。規(guī)劃圖從初始命題構(gòu)成的命題層開始，通過前提邊連接下層動(dòng)作層，動(dòng)作層則通過效果邊連接下層命題層，依此類推。

4．2粗規(guī)劃圖的搜索過程

給定一個(gè)粗規(guī)劃圖，提取一個(gè)有效的規(guī)劃是一個(gè)重要的過程。對(duì)于一個(gè)粗規(guī)劃問題，我們只需要實(shí)現(xiàn)目標(biāo)集合G，而不一定完全實(shí)現(xiàn)其擴(kuò)展目標(biāo)集合，但擴(kuò)展的目標(biāo)集合并不一定完全實(shí)現(xiàn)，而只是作為衡量規(guī)劃解的一個(gè)標(biāo)準(zhǔn)。在對(duì)粗規(guī)劃圖進(jìn)行搜索時(shí)，我們利用回溯的思想從后往前搜索，尋找一個(gè)有效規(guī)劃，它能夠?qū)崿F(xiàn)目標(biāo)集合G；然后再求取該規(guī)劃的上近似集和下近似集，看是否是規(guī)劃問題的擴(kuò)展目標(biāo)集合的一個(gè)有效規(guī)劃解（即從初始狀態(tài)出發(fā)執(zhí)行該規(guī)劃是否能實(shí)現(xiàn)擴(kuò)展目標(biāo)集合中的目標(biāo)）。

根據(jù)動(dòng)作的實(shí)例化對(duì)象的粗糙度來計(jì)算動(dòng)作的粗糙度，初始狀態(tài)中初始命題的粗糙度為0，精確度為1，那些在可能初始狀態(tài)中但不在初始狀態(tài)I中的命題的粗糙度根據(jù)該命題中對(duì)象的粗糙隸屬度來確定。在搜索過程中選擇動(dòng)作時(shí)，選擇粗糙度低的動(dòng)作，最后得到一個(gè)粗糙度最低（精確度最高）的規(guī)劃。

5總結(jié)

本文提出了智能規(guī)劃中的初始對(duì)象集的不確定性，這種不確定性不是由對(duì)象集的模糊而引起的，它是由于我們對(duì)對(duì)象的知識(shí)了解不充分而導(dǎo)致的。也就是說，相對(duì)于我們已知的知識(shí)，規(guī)劃問題的初始對(duì)象集是一個(gè)粗糙集。針對(duì)這一不確定性，本文在對(duì)智能規(guī)劃和粗糙集理論深入研究的基礎(chǔ)上給出了粗規(guī)劃問題的定義，并將粗糙集理論與智能規(guī)劃相結(jié)合，提出了粗規(guī)劃問題的求解模型。

由于規(guī)劃圖算法在規(guī)劃領(lǐng)域的特殊地位和突出的效率，我們給出了一種基于規(guī)劃圖的粗糙規(guī)劃算法，主要包括粗規(guī)劃圖的構(gòu)造和對(duì)粗規(guī)劃圖的搜索算法。由于筆者的能力有限，有些問題仍待后續(xù)研究。相信在我們的努力下，粗規(guī)劃不僅會(huì)有非常好的理論前景，也會(huì)有實(shí)際的應(yīng)用價(jià)值。

參考文獻(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集理論與知識(shí)獲取[M]. 西安：西安交通大學(xué)出版社， 2001.200260.

作者簡介：

劉日仙（1980），女，浙江江山人，碩士，主要研究方向?yàn)橹悄芤?guī)劃與規(guī)劃識(shí)別；袁利永（1978），男，浙江嵊州人，碩士，主要研究方向?yàn)檐浖こ蹋还任南椋?947），男，吉林農(nóng)安人，教授，主要研究方向?yàn)橹悄芤?guī)劃和規(guī)劃識(shí)別、形式語言與自動(dòng)機(jī)理論、模糊群等。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文