王 超，蘇明娟，付少波

（1.廣東省水利水電科學(xué)研究院，廣東 廣州 510635；2.廣東省水動力學(xué)應(yīng)用研究重點實驗室，廣東 廣州510635）

2019年3月，廣東省水利廳下發(fā)了《關(guān)于做好全域自然村集中供水工作的通知》（粵水農(nóng)水農(nóng)電〔2019〕8號）[1]，確定在2025年底前，實現(xiàn)全域自然村集中供水100%覆蓋的目標(biāo)。由于廣東自然村分布較分散，所以如何合理布局供水管線，最大限度地減少管線長度，節(jié)省投資，具有重要意義。本研究以廣東北部某鎮(zhèn)轄內(nèi)自然村為例，探討利用生物免疫系統(tǒng)算法尋找供水管線最優(yōu)布局的方法。

1 工程實例

本研究選取廣東北部某鎮(zhèn)轄內(nèi)自然村，利用生物免疫系統(tǒng)算法尋找供水管線最優(yōu)布局。轄內(nèi)共38個自然村，各村位置采用西安1980坐標(biāo)系標(biāo)注，用水需求根據(jù)各村人口情況計算，按60L/人/天計算（統(tǒng)計結(jié)果見表1）。

2 免疫優(yōu)化算法解題分析

2.1 免疫優(yōu)化算法的特點

免疫優(yōu)化算法是一種高度并行、分布、自適應(yīng)和自組織的系統(tǒng)算法，具有較強(qiáng)的學(xué)習(xí)、識別和記憶能力，是一種新興的智能計算方法。它利用免疫系統(tǒng)的多樣性產(chǎn)生和維持機(jī)制來保持群體的多樣性，克服了一般尋優(yōu)過程尤其是多峰函數(shù)尋優(yōu)過程中難處理的“早熟”問題，最終求得全局最優(yōu)解[2]。

2.2 模型建立

自然村供水管線呈樹狀分布，在滿足距離上限的情況下，從自然村中找出輸水節(jié)點并向各自然村供水。目標(biāo)函數(shù)是各自然村到輸水節(jié)點自然村的用水量和距離值乘積之和的最小值。目標(biāo)函數(shù)見式（1）[3，4]。

約束條件為

表1 各自然村位置及用水需求統(tǒng)計

其中，N=｛1，2，…n｝是所有自然村的序號集合；Mi為到自然村i的距離小于s的備選供水節(jié)點自然村集合，i∈N，MiN；ωi表示自然村的用水量；dij表示從自然村i到離它最近的供水節(jié)點自然村j的距離；Zij為0-1變量，表示自然村和供水節(jié)點自然村的供水分配關(guān)系，當(dāng)其為1時，表示供水，否則表示不供水；hj是0-1變量，當(dāng)其為1時，表示點j被選為供水節(jié)點；s為供水節(jié)點自然村到由它供水的自然村的距離上限。

式（2）保證每個自然村只能由一個供水節(jié)點服務(wù)；式（3）確保自然村的用水量只能被設(shè)為供水節(jié)點的自然村供水；式（4）規(guī)定了被選為供水節(jié)點自然村的數(shù)量為p；式（5）表示變量Zij和hj是0-1變量；式（6）保證了自然村在可供水范圍內(nèi)。

2.3 解題步驟

2.3.1 算法流程

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

圖1 免疫算法流程

2.3.2 初始抗體產(chǎn)生

如果記憶庫非空，則初始抗體群從記憶庫中選擇生成。否則，在可行解空間隨機(jī)產(chǎn)生初始抗體群，需滿足約束條件式（4）和式（5）。

2.3.3 解的多樣性評價

（1）抗體與抗原的親和力

抗體與抗原之間的親和力用于表示抗體對抗原的識別程度，采用式（7）表示。

（2）抗體與抗體間的親和力

抗體與抗體之間的親和力反映了抗體之間的相似程度。采用R位連續(xù)方法計算抗體與抗體間的親和力。采用式（8）表示。

其中，kv,s為抗體v與抗體s中相同的位數(shù)；L為抗體的長度。

（3）抗體濃度

抗體的濃度Cv即群體中相似抗體所占的比例，即：

其中，N為抗體總數(shù)；Sv,s為0-1值。

（4）期望繁殖概率

在群體中，每個個體的期望繁殖概率由抗體與抗原間親和力Av和抗體濃度Cv兩部分共同決定，即：

其中，α為常數(shù)。

2.3.4 免疫操作

（1）選擇：按照輪船賭選擇機(jī)制進(jìn)行選擇操作，個體被選擇的概率即為式（10）計算出的期望繁殖概率。

（2）交叉：采用閃單點交叉法進(jìn)行交叉操作。

（3）變異：采用隨機(jī)選擇變異位進(jìn)行變異。

3 計算結(jié)果

3.1 第一供水節(jié)點自然村選擇

以本研究所選38個自然村及其用水量情況為例，計算得出6個第一供水節(jié)點自然村及供水量（見表 2）。

表2 計算結(jié)果

首次計算免疫算法收斂曲線如圖2所示。得到的供水管線初次布局如圖3所示。

圖2 首次計算免疫算法收斂曲線

圖3 供水管線初次布局

3.2 第二供水節(jié)點自然村選擇

以表2所示第一供水節(jié)點自然村及其供水量為數(shù)據(jù)集合，再次利用免疫優(yōu)化算法，求得2個第二供水節(jié)點自然村及管線布局。

第二次計算免疫算法收斂曲線如圖4所示。得到的第二供水管線布局如圖5所示。

3.3 供水管線優(yōu)化輸出

整合上述兩次計算結(jié)果并優(yōu)化距離較近的自然村，獲得供水管線最終布局方案（見圖6）。

4 結(jié)論

圖4 第二次計算免疫算法收斂曲線

圖5 第二供水管線初次布局

圖6 自然村供水管線布置方案

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