协同演化免疫算法提取水库调度规则研究*

王小林，成金华，尹正杰，胡铁松

(1.中国地质大学(武汉)经济管理学院，湖北 武汉 430074;2. 长江科学院水资源研究所，湖北 武汉 430010;3.武汉大学水资源与水电工程科学国家重点实验室, 湖北 武汉 430072)

水资源系统是一个复杂适应系统(Complex Sdaptive System, CAS)，构成系统的各主体(Agent)通过协作与竞争等方式协同演化实现系统整体最优[1-4]。水库作为水资源系统一个重要组成部分，面临的调度背景日趋复杂，其调度运行往往受经济、社会与生态环境等因素影响，需要不断调整自身性能与行为(调度规则)以适应环境变化。目前数据挖掘技术(如ANN、决策树等)已逐渐应用于水库调度研究中，弥补了传统方法在处理调度决策中的多目标、多变量与非线性等方面存在的不足[5-7]。但其思路是寻求水库调度决策与调度影响因素之间的非线性映射关系，或是对调度决策空间的静态划分，还没有将调度规则提取过程上升到复杂系统演化的高度来看待，因而无法洞察演化过程中调度规则自适应变化以及群体行为的涌现，难以适应复杂调度环境下水库有效运行需要。

人体免疫系统是一高度并行、分布式的复杂适应系统[8-9]。文献[10-11]研究了免疫应答中抗体种群自适应学习行为与协同演化机制，提出了协同演化人工免疫模型(Coevolution Immune System Model, CoEISM)。水库调度规则提取过程与CoEISM相比有诸多相同之处，例如：①调度环境与调度决策之间的作用类似抗原提呈；②调度规则提取可视为抗体自适应学习；③最优规则可视为记忆细胞。由此可见，抗体种群自适应学习以及协同演化方式应非常适用于水库调度规则提取和水库运行的适应性管理，尽管目前CoEISM在水库调度研究中尚很少得到应用。基于此，本文在文献[7]研究基础上，以水库供水调度为例，尝试利用CoEISM自适应提取供水调度规则，为水库调度研究提供新的方法与思路。

1 水库调度规则提取的协同演化免疫算法

水库调度环境涉及政府部门、生态以及用水户等多个主体。不同主体对水库蓄泄要求不同，它们与调度决策之间存在复杂非线性关系，调度过程中需要综合考虑这些主体对调度决策的影响。水库调度是一个不断调整调度决策以适应环境主体变化的过程，因而调度规则提取所面临的问题是，如何从历史调度决策过程中挖掘出环境主体与水库调度决策之间相互作用的非线性关系或潜在模式，以便更好地指导未来的调度决策。

对CoEISM而言，调度环境为系统面临的抗原(Antigen)，其基因编码由调度环境内不同主体的基因模块(编码)组合而成，而这些基因组合蕴含丰富的调度决策信息；调度规则为B细胞。由此，本文给出CoEISM自适应提取水库调度规则系统结构(如图1)，思路为：利用协同演化机制对抗原进行学习，从其基因模块组合中获取能适应调度环境变化的水库调度规则。其中，B细胞由基因型与表现型构成(如图2)；表现型称为抗体(Antibody)，条件部分含有通配符“#”，使抗体能匹配多个抗原。调度规则提取算法主要流程如下：

Step1：抗原提呈。通过探测器将抗原转化为B细胞能识别的二进制编码，用“IFTHEN”形式表示，与B细胞的抗体类似但无通配符，其中为环境信息内各主体基因模块组合；为水库蓄泄决策(调度模式)编码。对于供水水库而言，这里考虑调度决策或称供水模式(C)主要受来水、用水及管理者知识(或经验)的影响[6]。来水包括水库蓄水量(S)、径流量(I) 以及调度时段(N)三方面；用水为不同用户的用水需求(D)；管理者知识表现为对中长期来水情况的预测-即对水文年型(P)的判断。故这三个主体包含的5个影响因素构成了水库调度特征属性；将这5个属性与调度决策(C)综合考虑便形成水库历史调度信息，用“IF THEN”形式表示。

图1 CoEISM自适应提取水库调度规则系统结构

图2 B细胞结构及基因型与表现型关系

Step3：B细胞种群生灭。每隔固定演化代数K，利用式(1)检查系统演化是否停滞；当演化停滞时，则产生新调度规则子集；如果种群Sl(t)的代表rl的适应度小于消亡阀值(Extinction threshold,ET)，则种群Sl(t)被清除或该调度规则子集自动消亡。f(t)为种群代表构成的合作体(r1(t),…,ri(t),…,rm(t))的适应度，C为系统演化压力，为一设定值。

f(t)-f(t-K)

(1)

Step4：调度规则生成。不断重复Step2-Step3，当演化一定代数后，从各B细胞种群中找出适应度最大的调度规则，形成水库调度规则库，用于未来调度决策。

2 实例研究

2.1 实例背景

以某供水水库为例，主要考虑3个供水目标：农业灌溉用水D1,t；工业及市政用水D2,t；居民生活用水D3,t。3个供水目标优先级依次从低到高，其中t为时段序号。依文献[12]，水库在任一时段有4种可能调度模式分别为，模式①：正常供水；模式②：限制农业供水；模式③：限制农业和工业供水；模式④：限制所有用水户供水。根据水库长系列(1956-2000年)来用水资料，以缺水指数Z(供需缺水平方和)最小作为目标，建立动态规划模型，获得全运行期水库供水逐时段调度模式(C)的最优决策序列[7]。将调度模式(C)与相应时段的结合起来，则形成了该供水水库历史调度环境信息。

为减小水库特征属性S、I、D的随机性以及水文年型判断(P)的主观不确定性对规则提取效果的影响，采用基于信息熵的FUSINTER算法[13]将其离散为几个区间(见表1，2)；调度决策是在年内不同时段做出的，故N直接采用二进制编码，按月分为12个时段(见表2)。4种供水调度模式编码为模式①：“00”；模式②：“01”；模式③：“10”；模式④：“11”。

2.2 计算结果与分析

本文用30a数据(1956-1985年，共360条)提取调度规则(如图3所示)，后15a数据(共180条)用于检验。初始种群数为4，对应4种供水模式，种群内个体popsize=100。模型中遗传算法参数采用经验取值：交叉率Pc=0.4，变异率Pm=0.06。经多次试验，种群动态变化控制参数ET=2，K=10；而C的取值对提取效果影响不显著(试验过程不赘述)。规则提取过程如图3所示，识别率从初始的68.6%逐渐上升，经500代演化，最终接近92.5%，获得24条调度规则(如表3)。

表1 蓄水量(S)，来水量(I)，需水量(D)离散区间与编码

表2 水文年型P与调度时段N编码

表3 水库供水调度规则

对所获规则进行检验，得到识别率为84.4%，缺水指数为2.23×1014m6，与RBF提取结果相当(识别率为84%, 缺水指数为2.36×1014m6)[7]。

图3 调度规则提取自适应学习过程

演化过程中大约每隔10代识别率会产生跳跃，其因源于调度环境压力使得规则在演化过程中发生分化(如图4)，即新规则不断产生(如种群8、15、18)，原有规则因适应度较小而消亡。例如种群(**)在410～420代因适应度小于ET=2，故该种群被清除。这一过程清晰表明，调度规则通过协同演化的方式自适应调整，产生多样性，以应对复杂调度环境；因而，在实际调度中调度人员可以通过观察规则动态调整与演变轨迹，做出合理决策以适应调度环境的变化。

图4 部分供水调度规则动态产生与消亡演化过程

所获24条调度规则编码含有大量通配符“#”，如将其与表1、2对应，则每一规则具有明确物理意义，能涵盖不同基因模块组合而形成的调度环境。例如，规则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∈{调度模式④}。

仅就该规则给出的解释来看似乎不合理，因为如果遇到连续丰水年份，由于水库蓄水较大，可正常供水。但调度规则对调度信息识别，不仅取决于自身基因结构(模式)，而且更取决于同其他规则竞争和协作。例如，1990年6月样本编码为“0000 0010 101 0110 101:11”，能同时被多条规则匹配(如表3)，但规则3，4，12的匹配值最大(值均为1.0)，然而规则12所含通配符数最少，其物理意义更明确，故调度模式由规则12给出，即为供水模式④。由此可见，所获调度规则不仅合理，而且具有可解释性，能为水库调度管理提供更为丰富的决策信息。

尽管所获24条规则对检验样本识别率与RBF的识别率相当，但分别从4种调度模式识别结果来看(见文献[7])，前者对模式①②④的识别率高于RBF(如表4，5)，模式③则相反。可见，CoEISM对样本的非线性划分能力总体上高于RBF，所获调度规则同样能表示水库调度特征属性之间的高维非线性关系。不仅如此，前者在实际调度中可输出与调度环境信息匹配的所有规则，并结合已有调度知识与经验做出决策；而后者提取的规则隐含于网络中，其结果不易为调度人员理解。

表4 CoEISM识别结果

表5 RBF识别结果[7]

3 结 论

1) CoEISM模型用于用于水库调度规则提取，可微观洞察水库调度规则自适应演变轨迹与动态调整，有利于调度决策者做出合理蓄泄决策，以适应调度环境变化；

2)所获调度规则不仅具有高维非线性识别能力，而且具有明确的物理意义，易于理解，为水库调度管理提供更为丰富的决策信息。

参考文献：

[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] 赵建世, 王忠静, 翁文斌. 水资源复杂适应配置系统的理论与模型[J].地理学报, 2002, 7(6):639-647.

[3] 王慧敏, 伶金萍, 马小平，等. 基于CAS范式的流域水资源配置与管理及建模仿真[J].系统工程理论与实践, 2005, 23(5):34-36.

[4] 陈洋波, 曾碧球. 基于水库调蓄的流域可供水量优化模型研究与应用[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] 尹正杰,王小林,胡铁松，等. 基于数据挖掘的水库供水调度规则提取[J]. 系统工程理论与实践,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] 尹正杰,胡铁松,崔远来,等. 水库多目标供水调度规则研究[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.