免疫优化算法在农村供水管线布置中的应用研究

王 超，苏明娟，付少波

（1.广东省水利水电科学研究院，广东 广州 510635；2.广东省水动力学应用研究重点实验室，广东 广州510635）

2019年3月，广东省水利厅下发了《关于做好全域自然村集中供水工作的通知》（粤水农水农电〔2019〕8号）[1]，确定在2025年底前，实现全域自然村集中供水100%覆盖的目标。由于广东自然村分布较分散，所以如何合理布局供水管线，最大限度地减少管线长度，节省投资，具有重要意义。本研究以广东北部某镇辖内自然村为例，探讨利用生物免疫系统算法寻找供水管线最优布局的方法。

1 工程实例

本研究选取广东北部某镇辖内自然村，利用生物免疫系统算法寻找供水管线最优布局。辖内共38个自然村，各村位置采用西安1980坐标系标注，用水需求根据各村人口情况计算，按60L/人/天计算（统计结果见表1）。

2 免疫优化算法解题分析

2.1 免疫优化算法的特点

免疫优化算法是一种高度并行、分布、自适应和自组织的系统算法，具有较强的学习、识别和记忆能力，是一种新兴的智能计算方法。它利用免疫系统的多样性产生和维持机制来保持群体的多样性，克服了一般寻优过程尤其是多峰函数寻优过程中难处理的“早熟”问题，最终求得全局最优解[2]。

2.2 模型建立

自然村供水管线呈树状分布，在满足距离上限的情况下，从自然村中找出输水节点并向各自然村供水。目标函数是各自然村到输水节点自然村的用水量和距离值乘积之和的最小值。目标函数见式（1）[3，4]。

约束条件为

表1 各自然村位置及用水需求统计

其中，N=｛1，2，…n｝是所有自然村的序号集合；Mi为到自然村i的距离小于s的备选供水节点自然村集合，i∈N，MiN；ωi表示自然村的用水量；dij表示从自然村i到离它最近的供水节点自然村j的距离；Zij为0-1变量，表示自然村和供水节点自然村的供水分配关系，当其为1时，表示供水，否则表示不供水；hj是0-1变量，当其为1时，表示点j被选为供水节点；s为供水节点自然村到由它供水的自然村的距离上限。

式（2）保证每个自然村只能由一个供水节点服务；式（3）确保自然村的用水量只能被设为供水节点的自然村供水；式（4）规定了被选为供水节点自然村的数量为p；式（5）表示变量Zij和hj是0-1变量；式（6）保证了自然村在可供水范围内。

2.3 解题步骤

2.3.1 算法流程

免疫算法流程如图1所示[5]。

图1 免疫算法流程

2.3.2 初始抗体产生

如果记忆库非空，则初始抗体群从记忆库中选择生成。否则，在可行解空间随机产生初始抗体群，需满足约束条件式（4）和式（5）。

2.3.3 解的多样性评价

（1）抗体与抗原的亲和力

抗体与抗原之间的亲和力用于表示抗体对抗原的识别程度，采用式（7）表示。

（2）抗体与抗体间的亲和力

抗体与抗体之间的亲和力反映了抗体之间的相似程度。采用R位连续方法计算抗体与抗体间的亲和力。采用式（8）表示。

其中，kv,s为抗体v与抗体s中相同的位数；L为抗体的长度。

（3）抗体浓度

抗体的浓度Cv即群体中相似抗体所占的比例，即：

其中，N为抗体总数；Sv,s为0-1值。

（4）期望繁殖概率

在群体中，每个个体的期望繁殖概率由抗体与抗原间亲和力Av和抗体浓度Cv两部分共同决定，即：

其中，α为常数。

2.3.4 免疫操作

（1）选择：按照轮船赌选择机制进行选择操作，个体被选择的概率即为式（10）计算出的期望繁殖概率。

（2）交叉：采用闪单点交叉法进行交叉操作。

（3）变异：采用随机选择变异位进行变异。

3 计算结果

3.1 第一供水节点自然村选择

以本研究所选38个自然村及其用水量情况为例，计算得出6个第一供水节点自然村及供水量（见表 2）。

表2 计算结果

首次计算免疫算法收敛曲线如图2所示。得到的供水管线初次布局如图3所示。

图2 首次计算免疫算法收敛曲线

图3 供水管线初次布局

3.2 第二供水节点自然村选择

以表2所示第一供水节点自然村及其供水量为数据集合，再次利用免疫优化算法，求得2个第二供水节点自然村及管线布局。

第二次计算免疫算法收敛曲线如图4所示。得到的第二供水管线布局如图5所示。

3.3 供水管线优化输出

整合上述两次计算结果并优化距离较近的自然村，获得供水管线最终布局方案（见图6）。

4 结论

图4 第二次计算免疫算法收敛曲线

图5 第二供水管线初次布局

图6 自然村供水管线布置方案

本研究在自然村供水管线布局模型建立的基础上，利用免疫优化算法快速求得最优解，可为农村供水管线布局设计提供参考。由于免疫机理复杂、系统庞大，目前人工免疫系统可借鉴的成果不多，在今后的研究中还需不断完善和优化。