免疫優化算法在農村供水管線布置中的應用研究

王 超，蘇明娟，付少波

（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 自然村供水管線布置方案

本研究在自然村供水管線布局模型建立的基礎上，利用免疫優化算法快速求得最優解，可為農村供水管線布局設計提供參考。由于免疫機理復雜、系統龐大，目前人工免疫系統可借鑒的成果不多，在今后的研究中還需不斷完善和優化。