基于案例推理的黃河流域水資源優(yōu)化調(diào)配

彭少明,張春生

(1.黃河勘測規(guī)劃設(shè)計有限公司,河南鄭州 450003;2.中國水利水電科學(xué)研究院水資源研究所,北京 100044)

案例推理(case-based reasoning,CBR)是一種基于知識的問題求解和學(xué)習(xí)方法,通過重用以前相似問題的方案信息來解決新問題。CBR通過舊案例的檢索、重用、匹配,再現(xiàn)案例決策,實現(xiàn)對新問題的求解,是一種有別于傳統(tǒng)人工智能的新技術(shù)。CBR將定量分析與定性分析相結(jié)合,具有動態(tài)知識庫和增量學(xué)習(xí)的特點,可以克服當(dāng)前專家系統(tǒng)所面臨的難題。

由于傳統(tǒng)的人工智能面臨知識獲取的局限,基于數(shù)據(jù)挖掘和分析的計算智能成為新的研究熱點[1]。Aamodt等[2]提出了CBR四階段循環(huán),即案例的檢索、復(fù)用、修正、保存;Gilboa等[3]將案例表示為問題描述、解描述、效果描述的三元組;Aha等[4]通過案例工程確定案例所必須包含的信息,并從數(shù)據(jù)中提取信息;Anders[5]提出了基于概率案例的PEBM模型,采用概率傳播技術(shù)評估和檢索案例。進入21世紀(jì),隨著計算機技術(shù)的快速升級,CBR已被廣泛應(yīng)用到故障診斷、商業(yè)管理、智能決策、知識提取等領(lǐng)域[2-8]。當(dāng)前CBR研究主要集中在案例的索引及檢索技術(shù)、案例修正規(guī)則的獲取方法、案例庫維護技術(shù)及其性能評價、CBR與其他方法的集成等方面[9-11]。

1 基于CBR的水資源調(diào)配

1.1 調(diào)配原理

相似性技術(shù)是一種用于分析存在于自然界和社會科學(xué)中隱含信息的技術(shù),用來探求和解決真實世界中復(fù)雜問題的工具。與以往的人工智能不同,CBR將過去處理過的問題描述成由問題特征集和解決方案組成的案例,并存儲在案例庫中,當(dāng)出現(xiàn)新的問題時,系統(tǒng)從案例庫中檢索出與新問題最相近的案例,將舊案例的解決方案作為新案例的解決方案?；贑BR的流域水資源調(diào)配原理見圖1。

在復(fù)雜水資源系統(tǒng)中,一些水文現(xiàn)象通常具有周期性特征,即一些水文要素在一定的時段內(nèi)會重復(fù)出現(xiàn),基于這一特征將CBR引入水資源調(diào)配之中。利用新舊案例要素之間的相似性,從案例庫中篩選出相似案例,重用決策信息,可避免多目標(biāo)優(yōu)化的“維數(shù)災(zāi)”問題,實現(xiàn)水資源的優(yōu)化調(diào)配。

圖1 基于CBR的流域水資源調(diào)配原理

1.2 調(diào)配流程

基于CBR的流域水資源調(diào)配采用定性與定量相結(jié)合的方法,首先根據(jù)河流主要斷面來水信息確定搜索方向,檢索出潛在的案例組,然后根據(jù)相似度大小得出最匹配的方案,其調(diào)配過程主要分為以下5個步驟。

第1步引入水文要素關(guān)系指示系數(shù)來歸納各個區(qū)間的水文特征,通過歸納水文要素的關(guān)系定性指示信息,開展定向檢索。將流域劃分為K個子區(qū)間,在搜索樹的末端尋找各子區(qū)間水文要素關(guān)系指示系數(shù)完全一致的方案,即為潛在的案例組。

第2步推理匹配。對決策問題的 n個屬性項計算潛在案例組與決策問題的相似度。

第3步案例精選。系統(tǒng)按相似度降序排列潛在案例組,選擇相似度最大的案例為精確案例,并保留這個案例。

第4步參數(shù)調(diào)整。若決策者不滿意這個案例,系統(tǒng)將啟動交互決策界面修改決策參數(shù),重復(fù)第1～3步。

第5步系統(tǒng)存儲第3步或第4步中選擇的案例。

通過上述5個步驟歸納檢索出潛在的案例組,再通過相似度確定精確案例,若該精確案例專家評價滿意,即成為最合適的案例,并更新水資源調(diào)配案例庫。

2 CBR的檢索與匹配結(jié)構(gòu)設(shè)計

選擇合適的檢索和定位方法可以提高CBR系統(tǒng)的檢索速度和匹配精度。考慮到黃河流域水資源調(diào)配具有多目標(biāo)、多屬性、高維度的復(fù)雜特征,CBR采用K-D樹[12-17]檢索算法和相似度匹配方法。檢索過程中每選定一個檢索方向可以看成是進行一次統(tǒng)計推斷,首先判斷較粗粒度空間中哪個部分最可能包含目標(biāo),然后在被選出的較細(xì)粒度空間上進一步判斷被選出的較細(xì)粒度空間中哪個細(xì)粒度空間最有可能包含目標(biāo),這樣逐層下降直到所有空間均包含搜索信息,確定出潛在案例組,然后計算相似度,尋找出精確案例。

2.1 K-D樹檢索技術(shù)

CBR搜索結(jié)構(gòu)設(shè)計采用K-D樹建立多維索引,K-D樹是一種K維空間點二叉索引樹[14],具有數(shù)據(jù)結(jié)構(gòu)簡單、存取效率高等優(yōu)點,是一種適用于高維數(shù)據(jù)結(jié)構(gòu)的快速搜索結(jié)構(gòu)。K-D樹內(nèi)部節(jié)點與某一空間維xi(1≤i≤K)對應(yīng),且每個內(nèi)部節(jié)點都用1個正交于其空間維xi的超平面xi=c(c為常數(shù))將該節(jié)點所表示的K維空間分成兩部分,這些超平面在K個方向上交替出現(xiàn),并且每個超平面至少包括1個點數(shù)據(jù)。K-D樹將數(shù)據(jù)分散存儲在每個節(jié)點上,K-D樹算法中,每個節(jié)點是1個二選結(jié)構(gòu),2個子節(jié)點代表將空間劃分為2個子區(qū)。K-D樹的內(nèi)部節(jié)點有1個相關(guān)聯(lián)的屬性 a和一個值V,它將數(shù)據(jù)點分成2個部分:a的取值小于V的部分和a的取值大于或等于V的部分。由于所有維的屬性在層間循環(huán),所以樹的不同層上的屬性是不同的。為獲得塊模式,對K-D樹結(jié)構(gòu)進行以下2處修改:①內(nèi)部節(jié)點只有1個屬性,該屬性的每個值確定地指向左、右分支;②子節(jié)點是塊,塊空間中存放著盡可能多的記錄。

2.2 K-D樹結(jié)構(gòu)的定性推理

按照黃河流域主要斷面(花園口、三門峽、河口鎮(zhèn)、蘭州、龍羊峽)將流域分為6層(級),5個斷面分別對應(yīng)于K-D樹的5個節(jié)點,而5個流域區(qū)間則設(shè)計為K-D樹的5級子系。圖2為系統(tǒng)搜索的K-D樹路徑結(jié)構(gòu)設(shè)計。

圖2 基于CBR的黃河流域水資源調(diào)配系統(tǒng)K-D樹路徑結(jié)構(gòu)設(shè)計

K-D樹定性搜索的方向是根據(jù)每一層級的來水特征進行判別,按照主要斷面的水文信息(包括河道來水量和降水量)與多年平均水量(由斷面來水和區(qū)間降水量綜合確定)的關(guān)系將區(qū)間的水文年份定性分為多水年和少水年。

K-D樹的案例檢索規(guī)則是:首先采取歸納法抽取各節(jié)點來水量和降水量信息,按照水文要素的特征劃分為不同水文年份,為決定檢索分支方向提供依據(jù);采用歸納法搜索,逐層遞進,沿決策樹越過節(jié)點的路徑取各節(jié)點所包含信息的交集,在決策樹的末端定位識別出與決策方案各區(qū)間水文年份均相同的潛在案例組。

2.3 基于水文要素相似度的案例匹配

基于CBR的黃河流域水資源調(diào)配方法從決策方案的降雨、徑流預(yù)測入手,根據(jù)關(guān)鍵水文要素的相似程度,按照案例推理法則選擇相似度最大(最接近)的案例為目標(biāo)案例。案例相似度是水文要素(降雨量、徑流量)的貼近程度。

a.計算變量屬性偏離度。對于數(shù)字型優(yōu)化變量,采用偏離度作為屬性差別的度量,設(shè)新案例的數(shù)字型優(yōu)化變量的屬性值為Aj,與其相對應(yīng)的舊案例的數(shù)字型優(yōu)化變量為,其屬性值為 A*j,定義新案例中與的偏離度為

可以得到

b.計算案例的相似度。采用案例相似度判斷2個案例之間綜合水文要素的趨同或差異程度。設(shè)由m個屬性組成的案例,其相似度可以定義為偏離度的集成,表達(dá)式如下:

式中:sim(i,m)為舊案例 i與目標(biāo)案例m的相似度;ωj為各屬性的權(quán)重。

為了利用相似度中包含的信息,將獲取的相似度按從大到小的順序排序,相似度最大的案例即為精確案例。

為了保證推理的質(zhì)量,精確案例必須滿足屬性偏離度和案例相似度的臨界閾值約束,即

式中:D0和λ0分別為目標(biāo)案例屬性偏離度和相似度閾值,其值由專家確定。

同時滿足相似度最大和臨界閾值約束的案例為優(yōu)選案例。若不存在同時滿足相似度最大和臨界閾值約束的案例則修改參數(shù),重復(fù)執(zhí)行檢索過程直至得到?jīng)Q策者滿意的目標(biāo)方案。

3 基于CBR的黃河流域水資源調(diào)配

3.1 案例的定向搜索

系統(tǒng)在接收到水文預(yù)報數(shù)據(jù)后,分析水文信息,對來水年份定性辨識歸類,確定K-D樹結(jié)構(gòu)的搜索方向?；贑BR的黃河流域水資源調(diào)配系統(tǒng)K-D樹設(shè)計為6個層級(含流域級),對6個層級水文要素進行辨識,確定搜索方向。根據(jù)K-D樹結(jié)構(gòu),每個層級節(jié)點設(shè)有多水及少水2個方向,通過6層級的定性推理識別,確定1組與決策信息完全相同的案例。表1為基于CBR的黃河流域水資源調(diào)配定性搜索結(jié)果,表中V1～V6為流域K-D樹自下而上的6個層級,A1和A2分別為斷面來水量及降水量。系統(tǒng)通過專家信息對決策方案進行定性辨識,例如對四級子系(蘭州以上)進行水文要素辨識,若判斷結(jié)果為少水年,則向右側(cè)分支搜索(圖2)。決策方案的6個層級屬性定性表達(dá)值為(多水,多水,少水,少水,少水,少水)。系統(tǒng)接收水文信息后通過K-D樹搜索快速定位一組具有“龍羊峽、蘭州兩斷面多水,河口鎮(zhèn)、三門峽、花園口及全流域少水”特征的潛在案例。

3.2 案例的定量匹配

系統(tǒng)完成搜索后,鎖定了一組潛在案例,案例組的表達(dá)包括案例編號及6個層級的定性值。CBR的目標(biāo)是搜索與決策信息相似度最大的案例,即精確案例,根據(jù)專家信息得出目標(biāo)案例屬性偏離度和相似度閾值為D0＜5%和λ0＞0.95。

采用式(2)～(4)計算潛在案例組所有案例與目標(biāo)案例的相似度,并按照相似度大小進行排序。選擇相似度最大的案例作為精確案例,其水文特征及各屬性偏離度見表2,案例編號為BC99,sim(i,m)=0.976＞0.95,各屬性偏離度均小于5%。流域水資源調(diào)配成果見表3。將水資源調(diào)配結(jié)果與國務(wù)院1987年頒布的黃河可供水量分配方案(簡稱“87分水方案”,“87分水方案”根據(jù)黃河來水量進行折扣分配)進行對比,可以看出農(nóng)業(yè)灌溉用水量減少,發(fā)達(dá)地區(qū)用水量得到有效保障,體現(xiàn)了高效用水的原則。

表1 基于CBR的黃河流域水資源調(diào)配定性搜索結(jié)果

表2 精確案例的水文特征及各屬性偏離度

表3 基于案例推理的黃河流域水資源調(diào)配結(jié)果 億m3

3.3 案例的評價與輸出

系統(tǒng)鎖定的精確案例將由專家從經(jīng)濟效益、社會效益和生態(tài)環(huán)境效益3個方面進行綜合評價,評價滿意的方案方可作為最終推薦方案。首先分析生態(tài)效益,6個斷面的下泄水量(203.12億m3,296.41億m3,192.92億m3,272.51億m3,299.15億m3,206.85億m3)滿足生態(tài)環(huán)境需水量(140億m3,160億m3,197億m3,205億m3,200億m3,200億m3)要求,流域生態(tài)環(huán)境需水可得到滿足;其次分析經(jīng)濟效益,與黃河流域長期實行的“87分水方案”比較,寧夏、陜西、內(nèi)蒙古及山東等新興工業(yè)區(qū)用水適度增加,而青海、甘肅及山西由于長期用水量不足,分配水量適度減少,這樣既可保證能源化工產(chǎn)業(yè)區(qū)的用水需求,又可刺激農(nóng)業(yè)節(jié)水發(fā)展,支持經(jīng)濟社會的快速發(fā)展;最后分析社會效益,青海、甘肅、寧夏、內(nèi)蒙古的民生用水得到了保障。因此,綜合評價該精確案例為滿意方案,推薦實施。

4 結(jié) 語

將專家智慧和人工智能技術(shù)相結(jié)合,引入水文要素的相似度作為推理檢索指標(biāo),針對水文過程的周期性和相似特征,建立基于CBR的黃河流域水資源調(diào)配決策模型,通過水文要素的檢索與匹配,再現(xiàn)案例決策,避免了人為因素的干擾。與以往傳統(tǒng)的水資源調(diào)配決策相比,具備以下優(yōu)點:①水量調(diào)度快捷、高效,據(jù)檢測基于CBR完成一個案例調(diào)度決策的時間在3min以內(nèi),而傳統(tǒng)的調(diào)配、會商決策均在數(shù)天以上;②保障決策方案有效,方案庫中存儲的方案均為已實施或?qū)＜彝扑]實施的方案,可行性已在實踐中得到檢驗;③推薦的案例為優(yōu)化方案,通過搜索與匹配環(huán)節(jié)的篩選,使目標(biāo)案例與推薦案例的水文要素高度接近(相似度95%以上),且經(jīng)過了專家的綜合評價,因此可保證推薦案例為優(yōu)化方案。

[1]姜麗紅.智能化預(yù)測支持系統(tǒng)(IFSS)的理論與方法的研究[D].天津:天津大學(xué),1996.

[2]AAMODT A,PLAZA E.Case-based reasoning:foundational issue,methodological variation,and system approaches[J].AI Communications,1994,7(1):39-59.

[3]GILBOA I,SCHMEIDLER D.Case-based decision theory[J].Quarterly Journal of Economics,1995,110:605-639.

[4]AHA D,BRESLOW L.Refining conversational case libraries[C]Proc of Second International Conference on Case-Based Reasoning.Berlin:Springer Verlag,1997:267-278.

[5]ANDERS F M R.A probabilistic exemplar based model[D].Salford:Oniversity of Salford,1998.

[6]田喜平,趙紅丹.基于案例推理的重復(fù)談判研究[J].新鄉(xiāng)學(xué)院學(xué)報:自然科學(xué)版,2010,27(1):9079-9080.

[7]鄭國寧,馬力.基于案例推理技術(shù)在故障案例中的應(yīng)用[J].電腦知識與技術(shù),2010,6(32):50.

[8]梁昌勇,顧東曉.面向不確定多屬性決策問題的范例檢索算法研究[J].中國管理科學(xué),2009,17(1):131-137.

[9]李鋒剛.基于案例推理的優(yōu)化型智能決策技術(shù)的研究[J].淮北煤炭師范學(xué)院學(xué)報,2006,27(2):58-61.

[10]楊瑾,尤建新,蔡依平.基于案例推理的供應(yīng)商選擇決策支持系統(tǒng)研究[J].計算機工程與應(yīng)用,2006,3(6):17-28.

[11]蔡芝蔚.基于知識密集型的CBR構(gòu)件檢索方法研究與實現(xiàn)[J].牡丹江教育學(xué)院學(xué)報,2009,26(9):37-39.

[12]高煒,梁立.基于貼近度的本體概念屬性相似度計算[J].長春大學(xué)學(xué)報,2009,19(8):12-14.

[13]吳涵,楊克儉.基于K-D樹的多維索引在數(shù)據(jù)庫中的運用[J].自動化技術(shù)與應(yīng)用,2007,26(9):37-39.

[14]邱永紅,曾永年,鄒濱.K-D樹:一種多維空間數(shù)據(jù)索引結(jié)構(gòu)[J].自動化技術(shù)與應(yīng)用,2009,45(8):29-31.

[15]朱明.案例推理的數(shù)據(jù)挖掘算法搜索策略研究[J].光盤技術(shù),2010,31(3):10-11.

[16]張松達(dá),蘇飛,夏夢河.考慮水質(zhì)的水資源配置模型及其解法[J].河海大學(xué)學(xué)報:自然科學(xué)版,2010,38(6):620-624.

[17]龔曉燕,王強民,陳金水.水雨情信息空間分布技術(shù)的研究與實現(xiàn)[J].河海大學(xué)常州分校學(xué)報,2006,20(2):26-28.