協(xié)同演化免疫算法提取水庫調度規(guī)則研究*

王小林，成金華，尹正杰，胡鐵松

(1.中國地質大學(武漢)經(jīng)濟管理學院，湖北 武漢 430074;2. 長江科學院水資源研究所，湖北 武漢 430010;3.武漢大學水資源與水電工程科學國家重點實驗室, 湖北 武漢 430072)

水資源系統(tǒng)是一個復雜適應系統(tǒng)(Complex Sdaptive System, CAS)，構成系統(tǒng)的各主體(Agent)通過協(xié)作與競爭等方式協(xié)同演化實現(xiàn)系統(tǒng)整體最優(yōu)[1-4]。水庫作為水資源系統(tǒng)一個重要組成部分，面臨的調度背景日趨復雜，其調度運行往往受經(jīng)濟、社會與生態(tài)環(huán)境等因素影響，需要不斷調整自身性能與行為(調度規(guī)則)以適應環(huán)境變化。目前數(shù)據(jù)挖掘技術(如ANN、決策樹等)已逐漸應用于水庫調度研究中，彌補了傳統(tǒng)方法在處理調度決策中的多目標、多變量與非線性等方面存在的不足[5-7]。但其思路是尋求水庫調度決策與調度影響因素之間的非線性映射關系，或是對調度決策空間的靜態(tài)劃分，還沒有將調度規(guī)則提取過程上升到復雜系統(tǒng)演化的高度來看待，因而無法洞察演化過程中調度規(guī)則自適應變化以及群體行為的涌現(xiàn)，難以適應復雜調度環(huán)境下水庫有效運行需要。

人體免疫系統(tǒng)是一高度并行、分布式的復雜適應系統(tǒng)[8-9]。文獻[10-11]研究了免疫應答中抗體種群自適應學習行為與協(xié)同演化機制，提出了協(xié)同演化人工免疫模型(Coevolution Immune System Model, CoEISM)。水庫調度規(guī)則提取過程與CoEISM相比有諸多相同之處，例如：①調度環(huán)境與調度決策之間的作用類似抗原提呈；②調度規(guī)則提取可視為抗體自適應學習；③最優(yōu)規(guī)則可視為記憶細胞。由此可見，抗體種群自適應學習以及協(xié)同演化方式應非常適用于水庫調度規(guī)則提取和水庫運行的適應性管理，盡管目前CoEISM在水庫調度研究中尚很少得到應用?；诖耍疚脑谖墨I[7]研究基礎上，以水庫供水調度為例，嘗試利用CoEISM自適應提取供水調度規(guī)則，為水庫調度研究提供新的方法與思路。

1 水庫調度規(guī)則提取的協(xié)同演化免疫算法

水庫調度環(huán)境涉及政府部門、生態(tài)以及用水戶等多個主體。不同主體對水庫蓄泄要求不同，它們與調度決策之間存在復雜非線性關系，調度過程中需要綜合考慮這些主體對調度決策的影響。水庫調度是一個不斷調整調度決策以適應環(huán)境主體變化的過程，因而調度規(guī)則提取所面臨的問題是，如何從歷史調度決策過程中挖掘出環(huán)境主體與水庫調度決策之間相互作用的非線性關系或潛在模式，以便更好地指導未來的調度決策。

對CoEISM而言，調度環(huán)境為系統(tǒng)面臨的抗原(Antigen)，其基因編碼由調度環(huán)境內不同主體的基因模塊(編碼)組合而成，而這些基因組合蘊含豐富的調度決策信息；調度規(guī)則為B細胞。由此，本文給出CoEISM自適應提取水庫調度規(guī)則系統(tǒng)結構(如圖1)，思路為：利用協(xié)同演化機制對抗原進行學習，從其基因模塊組合中獲取能適應調度環(huán)境變化的水庫調度規(guī)則。其中，B細胞由基因型與表現(xiàn)型構成(如圖2)；表現(xiàn)型稱為抗體(Antibody)，條件部分含有通配符“#”，使抗體能匹配多個抗原。調度規(guī)則提取算法主要流程如下：

Step1：抗原提呈。通過探測器將抗原轉化為B細胞能識別的二進制編碼，用“IFTHEN”形式表示，與B細胞的抗體類似但無通配符，其中為環(huán)境信息內各主體基因模塊組合；為水庫蓄泄決策(調度模式)編碼。對于供水水庫而言，這里考慮調度決策或稱供水模式(C)主要受來水、用水及管理者知識(或經(jīng)驗)的影響[6]。來水包括水庫蓄水量(S)、徑流量(I) 以及調度時段(N)三方面；用水為不同用戶的用水需求(D)；管理者知識表現(xiàn)為對中長期來水情況的預測-即對水文年型(P)的判斷。故這三個主體包含的5個影響因素構成了水庫調度特征屬性；將這5個屬性與調度決策(C)綜合考慮便形成水庫歷史調度信息，用“IF THEN”形式表示。

圖1 CoEISM自適應提取水庫調度規(guī)則系統(tǒng)結構

圖2 B細胞結構及基因型與表現(xiàn)型關系

Step3：B細胞種群生滅。每隔固定演化代數(shù)K，利用式(1)檢查系統(tǒng)演化是否停滯；當演化停滯時，則產生新調度規(guī)則子集；如果種群Sl(t)的代表rl的適應度小于消亡閥值(Extinction threshold,ET)，則種群Sl(t)被清除或該調度規(guī)則子集自動消亡。f(t)為種群代表構成的合作體(r1(t),…,ri(t),…,rm(t))的適應度，C為系統(tǒng)演化壓力，為一設定值。

f(t)-f(t-K)

(1)

Step4：調度規(guī)則生成。不斷重復Step2-Step3，當演化一定代數(shù)后，從各B細胞種群中找出適應度最大的調度規(guī)則，形成水庫調度規(guī)則庫，用于未來調度決策。

2 實例研究

2.1 實例背景

以某供水水庫為例，主要考慮3個供水目標：農業(yè)灌溉用水D1,t；工業(yè)及市政用水D2,t；居民生活用水D3,t。3個供水目標優(yōu)先級依次從低到高，其中t為時段序號。依文獻[12]，水庫在任一時段有4種可能調度模式分別為，模式①：正常供水；模式②：限制農業(yè)供水；模式③：限制農業(yè)和工業(yè)供水；模式④：限制所有用水戶供水。根據(jù)水庫長系列(1956-2000年)來用水資料，以缺水指數(shù)Z(供需缺水平方和)最小作為目標，建立動態(tài)規(guī)劃模型，獲得全運行期水庫供水逐時段調度模式(C)的最優(yōu)決策序列[7]。將調度模式(C)與相應時段的結合起來，則形成了該供水水庫歷史調度環(huán)境信息。

為減小水庫特征屬性S、I、D的隨機性以及水文年型判斷(P)的主觀不確定性對規(guī)則提取效果的影響，采用基于信息熵的FUSINTER算法[13]將其離散為幾個區(qū)間(見表1，2)；調度決策是在年內不同時段做出的，故N直接采用二進制編碼，按月分為12個時段(見表2)。4種供水調度模式編碼為模式①：“00”；模式②：“01”；模式③：“10”；模式④：“11”。

2.2 計算結果與分析

本文用30a數(shù)據(jù)(1956-1985年，共360條)提取調度規(guī)則(如圖3所示)，后15a數(shù)據(jù)(共180條)用于檢驗。初始種群數(shù)為4，對應4種供水模式，種群內個體popsize=100。模型中遺傳算法參數(shù)采用經(jīng)驗取值：交叉率Pc=0.4，變異率Pm=0.06。經(jīng)多次試驗，種群動態(tài)變化控制參數(shù)ET=2，K=10；而C的取值對提取效果影響不顯著(試驗過程不贅述)。規(guī)則提取過程如圖3所示，識別率從初始的68.6%逐漸上升，經(jīng)500代演化，最終接近92.5%，獲得24條調度規(guī)則(如表3)。

表1 蓄水量(S)，來水量(I)，需水量(D)離散區(qū)間與編碼

表2 水文年型P與調度時段N編碼

表3 水庫供水調度規(guī)則

對所獲規(guī)則進行檢驗，得到識別率為84.4%，缺水指數(shù)為2.23×1014m6，與RBF提取結果相當(識別率為84%, 缺水指數(shù)為2.36×1014m6)[7]。

圖3 調度規(guī)則提取自適應學習過程

演化過程中大約每隔10代識別率會產生跳躍，其因源于調度環(huán)境壓力使得規(guī)則在演化過程中發(fā)生分化(如圖4)，即新規(guī)則不斷產生(如種群8、15、18)，原有規(guī)則因適應度較小而消亡。例如種群(**)在410～420代因適應度小于ET=2，故該種群被清除。這一過程清晰表明，調度規(guī)則通過協(xié)同演化的方式自適應調整，產生多樣性，以應對復雜調度環(huán)境；因而，在實際調度中調度人員可以通過觀察規(guī)則動態(tài)調整與演變軌跡，做出合理決策以適應調度環(huán)境的變化。

圖4 部分供水調度規(guī)則動態(tài)產生與消亡演化過程

所獲24條調度規(guī)則編碼含有大量通配符“#”，如將其與表1、2對應，則每一規(guī)則具有明確物理意義，能涵蓋不同基因模塊組合而形成的調度環(huán)境。例如，規(guī)則12包含213種對3個用水戶限制性供水的決策信息，可解釋為：

IF:S∈(4644, 2400]∩I∈[13, 121]∪(165, 309]∪ (342, 417]∪(502, 637]∩D∈[416, 1480]∩N∈{1月, 2月, ... , 7月}∩P∈{豐, 偏豐, 平, 偏枯} THEN :C∈{調度模式④}。

僅就該規(guī)則給出的解釋來看似乎不合理，因為如果遇到連續(xù)豐水年份，由于水庫蓄水較大，可正常供水。但調度規(guī)則對調度信息識別，不僅取決于自身基因結構(模式)，而且更取決于同其他規(guī)則競爭和協(xié)作。例如，1990年6月樣本編碼為“0000 0010 101 0110 101:11”，能同時被多條規(guī)則匹配(如表3)，但規(guī)則3，4，12的匹配值最大(值均為1.0)，然而規(guī)則12所含通配符數(shù)最少，其物理意義更明確，故調度模式由規(guī)則12給出，即為供水模式④。由此可見，所獲調度規(guī)則不僅合理，而且具有可解釋性，能為水庫調度管理提供更為豐富的決策信息。

盡管所獲24條規(guī)則對檢驗樣本識別率與RBF的識別率相當，但分別從4種調度模式識別結果來看(見文獻[7])，前者對模式①②④的識別率高于RBF(如表4，5)，模式③則相反?？梢?，CoEISM對樣本的非線性劃分能力總體上高于RBF，所獲調度規(guī)則同樣能表示水庫調度特征屬性之間的高維非線性關系。不僅如此，前者在實際調度中可輸出與調度環(huán)境信息匹配的所有規(guī)則，并結合已有調度知識與經(jīng)驗做出決策；而后者提取的規(guī)則隱含于網(wǎng)絡中，其結果不易為調度人員理解。

表4 CoEISM識別結果

表5 RBF識別結果[7]

3 結 論

1) CoEISM模型用于用于水庫調度規(guī)則提取，可微觀洞察水庫調度規(guī)則自適應演變軌跡與動態(tài)調整，有利于調度決策者做出合理蓄泄決策，以適應調度環(huán)境變化；

2)所獲調度規(guī)則不僅具有高維非線性識別能力，而且具有明確的物理意義，易于理解，為水庫調度管理提供更為豐富的決策信息。

參考文獻：

[1] JEFFERY R., SEATON R. Evaluation methods for the design of adaptive water supply systems in urban environments[J].Water Science and Technology, 1997, 35(9):45-51.

[2] 趙建世, 王忠靜, 翁文斌. 水資源復雜適應配置系統(tǒng)的理論與模型[J].地理學報, 2002, 7(6):639-647.

[3] 王慧敏, 伶金萍, 馬小平，等. 基于CAS范式的流域水資源配置與管理及建模仿真[J].系統(tǒng)工程理論與實踐, 2005, 23(5):34-36.

[4] 陳洋波, 曾碧球. 基于水庫調蓄的流域可供水量優(yōu)化模型研究與應用[J]. 中山大學學報：自然科學版, 2005,44(2):94-97.

[5] BESSLER T, FLORIAN S, DRAGAN A & GODFREY A. Water reservoir control with data mining [J]. Journal of Water Resources Planning and Management, 2003, 129(1): 26-34.

[6] NEELAKANTAN T. R., PUNDARIKANTHAN N. Neural network-based simulation optimization model for reservoir operation [J]. Journal of Water Resources Planning and Management, 2000, 126(2):57- 64.

[7] 尹正杰,王小林,胡鐵松，等. 基于數(shù)據(jù)挖掘的水庫供水調度規(guī)則提取[J]. 系統(tǒng)工程理論與實踐,2006, 26(8):129-135.

[8] DASGUPTA D. An artificial immune system as a multi-agent decision support sytem[C]∥Proceeding of the SMC98, IEEE International Conference on Systems, Man, and Cybernetics, Sandiego California,1998,4: 3816-3820.

[9] 張靈, 陳曉宏, 翁毅,等. 人工免疫算法在洪水分類中的應用[J]. 中山大學學報：自然科學版, 2008,47(5):110-114.

[10] POTTER M A, DE JONG K A. The coevolution of antibodies for concept learning[C]∥Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature,Springer-Verlag,1998:530-539.

[11] POTTER M A, DE JONG K A. Cooperative coevolution: An architecture for evolving coadapted subcomponents [J]. Evolutionary Computation, 2000, 8(1):1-29.

[12] 尹正杰,胡鐵松,崔遠來,等. 水庫多目標供水調度規(guī)則研究[J]. 水科學進展, 2005, 16(6) :875 - 880.

[13] ZIGHED D A, RABASEDA S, RAKOTOMALA R. FUSINTER: A method for discretization of continuous attributes [J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 1998, 6(3): 307-326.