基于智能優(yōu)化算法的飲用水污染源定位方法研究綜述

龔瑾玉,顏雪松,胡成玉,龔文引

(中國地質(zhì)大學(武漢)計算機學院,湖北武漢 430078)

1 引言

水資源是人類賴以生存的條件之一,飲用水的安全對居民的生活健康至關(guān)重要,供水系統(tǒng)安全在維護公共健康和工業(yè)增長方面具有重要的戰(zhàn)略地位[1].而供水系統(tǒng)因其開放性、易訪問、基礎設施易老化等原因很容易受到外界的意外侵害和故意侵害,導致飲用水被污染,使公眾健康面臨風險.2016年5月,北京飲用水供給系統(tǒng)因為管道連接失誤的問題,意外導致灰水入侵到飲用水管道中;同年5月31日,香港飲用水被檢測出鉛含量超標,且遠超世界衛(wèi)生組織的最高級別.這兩種情況都是飲用水被污染了而沒有及時被檢測到而導致的.由于污染物在供水管網(wǎng)中傳播的速度相對較快,且不可預測,因此快速識別污染源的位置和相關(guān)特性對有關(guān)部門采取措施控制和遏制污染具有十分非常重要的實際意義[2].

傳感器網(wǎng)絡技術(shù)能檢測到供水管網(wǎng)中的污染并可以獲得有用的觀測數(shù)據(jù)來識別和管理污染事件.目前常用的傳感器分為固定傳感器和移動傳感器:固定傳感器一般放置在固定的節(jié)點位置,而移動傳感器在投放到管網(wǎng)節(jié)點后會隨著水流進行移動,位置是動態(tài)變化的.目前,大部分有關(guān)供水管網(wǎng)水質(zhì)檢測的研究都是基于固定傳感器進行的.受到成本和預算的限制,不可能在供水管網(wǎng)的每個節(jié)點都布置傳感器,傳感器所在的節(jié)點位置將直接影響污染物檢測與污染源識別,有關(guān)傳感器部署的文獻已有很多[3–5].在現(xiàn)有的研究中,學者們解決水污染源定位問題時直接指定傳感器位置,并且這些傳感器能夠立即檢測到由于污染事件引起的任何水質(zhì)變化.Propato等人為了將傳感器的觀測數(shù)據(jù)與污染物可能發(fā)生的時間地點聯(lián)系起來,構(gòu)建了水質(zhì)I/O模型,該模型便于后來的學者們將污染源識別問題轉(zhuǎn)化為反演問題或參數(shù)估計問題進行求解[6].

飲用水污染源定位問題通常以固定傳感器傳回的污染物監(jiān)測數(shù)據(jù)為依據(jù),結(jié)合相應的算法,找出污染源的特征,這些特征包括:污染源位置、污染開始時間、污染持續(xù)時間、污染物濃度.目前用于解決污染源識別問題的方法大致可分為3類:粒子回溯法、機器學習法、模擬–優(yōu)化法.粒子回溯法是早期最常使用的方法,使用粒子反向追蹤,根據(jù)傳感器的檢測信息反向推斷前一時間各個節(jié)點的狀態(tài).此后,得益于機器學習算法的發(fā)展和研究,研究者們利用機器學習算法,如貝葉斯算法等,計算管網(wǎng)節(jié)點被污染的概率,其中被污染概率最大的管網(wǎng)節(jié)點就是最容易發(fā)生污染事件的節(jié)點.近年來,啟發(fā)式算法也逐漸被用于解決污染源識別問題,通過模擬–優(yōu)化的思想將飲用水污染源定位問題看作是一個根據(jù)水質(zhì)傳感器收集到的信息逆向?qū)ふ椅廴驹吹姆囱輪栴},指定時間步長與管網(wǎng)中傳感器的數(shù)量,計算管網(wǎng)中所有傳感器在每個時間步長上的估計污染濃度與觀測污染濃度之間的變化,優(yōu)化的目的是盡量減少觀測數(shù)據(jù)與所建立模型的計算數(shù)據(jù)之間的差異[7].

以上提到的3種方法中,模擬–優(yōu)化法尋找污染源位置的精確度最高,但因其需要調(diào)用仿真軟件模擬管網(wǎng)水質(zhì)和污染源事件,計算量比另外兩種方法更大.

本文主要對目前運用模擬–優(yōu)化法解決飲用水污染源定位問題的相關(guān)文獻進行綜述,歸納總結(jié)智能優(yōu)化算法在飲用水污染源定位問題中的應用.文章結(jié)構(gòu)如下:第2節(jié)介紹飲用水污染源定位問題的數(shù)學模型和運用模擬–優(yōu)化法解決污染源定位問題的優(yōu)化模型,第3節(jié)重點綜述智能優(yōu)化算法在飲用水污染源定位問題中的代表性研究成果,第4節(jié)給出智能優(yōu)化算法在解決污染源定位問題上未來的可發(fā)展方向.

2 污染源定位問題模型

如圖1所示為一個簡化的供水管網(wǎng),包含一個水源、一個水泵、一個水塔和多個節(jié)點及管道,其中黑色箭頭代表水的流向.在A點模擬一個污染事件的發(fā)生,注入污染物,污染物會隨水的流向擴散到管網(wǎng)中其他位置,并被位于E點的水質(zhì)傳感器檢測到.從圖中可以直觀地看出受污染的水主要有3個流向,第1條從A點經(jīng)B點流向水塔,第2條從A點經(jīng)D點流向G點,第3條是從A點經(jīng)D點流向E點.當水質(zhì)傳感器檢測到流過E點的水中污染物濃度超過閾值,傳感器就會示警,代表本次污染事件被檢測到了.整個污染事件從污染注入到污染被檢測的過程都可以由EPANET軟件進行模擬[8].

圖1 供水管網(wǎng)模型Fig.1 Model of water supply network

EPANET是美國環(huán)境保護署開發(fā)的一款水力、水質(zhì)分析軟件,其源代碼是開源的,由C語言編寫,其開發(fā)的目的是為了改善對水管網(wǎng)系統(tǒng)中物質(zhì)遷移轉(zhuǎn)化規(guī)律的理解,它可以實現(xiàn)許多不同類型的給水管網(wǎng)系統(tǒng)水力水質(zhì)分析,對管網(wǎng)水源的改變與配置,對水泵的提升,對水池注水/放水時間的調(diào)度安排,對水處理的補充措施(例如蓄水池中重新加氯)等,其中水質(zhì)模擬是獲取傳感器數(shù)據(jù)的關(guān)鍵.水質(zhì)模擬提供以下功能:模擬供水管網(wǎng)中不發(fā)生反應的示蹤劑隨時間的變化的過程;模擬供水管網(wǎng)中反應物質(zhì)的變化情況,如消毒副產(chǎn)物可以隨時間而濃度增長,而余氯隨時間濃度降低;模擬整個管網(wǎng)的水齡;模擬主流水體和管壁處的反應;在管網(wǎng)中任意節(jié)點,允許任意的濃度的污染物輸入;模擬蓄水池中不同的混合模型.利用上述的水質(zhì)模擬特性,EPANET可以實現(xiàn)以下的水質(zhì)現(xiàn)象:使來源不同的水源進行混合、模擬整個系統(tǒng)的水齡、余氯的損失、消毒副產(chǎn)物的增長、跟蹤污染事件.

EPANET為每個節(jié)點都能設置源頭水質(zhì),通過設置源頭水質(zhì)可以模擬供水管網(wǎng)污染源入侵的場景.污染物可能從管網(wǎng)的任何節(jié)點進入,向管網(wǎng)節(jié)點注射進某一質(zhì)量或者某一濃度的污染物,然后調(diào)用EPANET進行水力、水質(zhì)模擬獲取污染事件對應的水質(zhì)傳感器檢測的污染物濃度,便實現(xiàn)污染物事件入侵模擬.

污染事件中,污染物可能在任意時間在管網(wǎng)的任何節(jié)點進入,通過向管網(wǎng)中某個節(jié)點中注射一定濃度的污染物,然后通過EPANET模擬污染物入侵時管網(wǎng)數(shù)據(jù)的動態(tài)變化,通過這些數(shù)據(jù)獲取到污染事件矩陣.通過設置源頭水水質(zhì)來模擬給水管網(wǎng)的污染物入侵場景,入侵節(jié)點表示增強源頭,在不考慮節(jié)點需水量的條件下,污染物質(zhì)在該節(jié)點中直接注射到管網(wǎng).常見的污染模擬入侵方式分為:質(zhì)量注入、流量步進注入和設置點注入.

當使用模擬–優(yōu)化法解決污染源識別問題時,通常定義以下數(shù)學模型[9],以確定傳感器檢測到污染后任何時刻的污染物位置、開始時間和釋放歷史,在單節(jié)點污染源入侵事件中,污染源定位問題模型描述如下:

其中:F表示模擬污染場景與真實污染場景間的誤差,L表示污染源位置,T0表示污染事件開始時間,t0表示傳感器檢測到污染的時間,tc表示當前時間步,表示從T0到tc的污染濃度矩陣,即傳感器從T0到tc的示數(shù)矩陣,它代表從開始時間到當前時間各傳感器檢測到的污染物濃度變化,表示傳感器i在時間步t觀測到的濃度,Cit(L,,T0)表示傳感器i應當在時間步t觀測到的濃度,即真實濃度,i表示傳感器位置,t表示觀測時間步,Ns表示傳感器數(shù)目.

在給定一組傳感器網(wǎng)絡的濃度觀測值后,將水分布模擬模型結(jié)合優(yōu)化算法,可以構(gòu)造一個反問題來識別污染源位置、濃度和釋放歷史特性.該反問題的解決方案是最小化網(wǎng)絡中傳感器節(jié)點的模型濃度和真實觀測濃度之間的誤差,即滿足式(1).

模擬–優(yōu)化法在求解飲用水污染源定位問題時的基本思路如下:首先由優(yōu)化算法迭代產(chǎn)生污染事件,并用EPANET模擬器進行水力水質(zhì)模擬,得出該污染事件的污染濃度矩陣.通過比較真實觀測到的污染濃度矩陣和模擬得到的污染濃度矩陣,如果誤差小于設定閾值則視優(yōu)化算法最優(yōu)解為污染源,否則繼續(xù)迭代求解,直到程序結(jié)束.

3 基于智能優(yōu)化算法的污染源定位

智能優(yōu)化算法在解決工程優(yōu)化問題上已表現(xiàn)出明顯的優(yōu)勢,智能優(yōu)化算法作為一種啟發(fā)式算法,提供了一種全局搜索機制來有效識別大型非線性優(yōu)化問題的最優(yōu)解.目前,智能優(yōu)化算法已在飲用水污染源定位問題上取得一定進展.

在模擬–優(yōu)化法解決污染源定位問題中,是以EPANET作為模擬器,優(yōu)化算法作為優(yōu)化器進行求解,優(yōu)化的目標是在迭代的過程中逐漸最小化式(1)中的目標函數(shù).在早期運用模擬–優(yōu)化法的文獻中,Guan等人[10]提出一種仿真優(yōu)化法解決非線性污染源識別和釋放歷史定位問題,該方法以EPANET作為模擬器,通過在水管網(wǎng)中指定的任意位置的潛在污染源釋放歷史,通過仿真軟件在任意選擇的檢測位置產(chǎn)生對應的濃度,將這些信息用于連續(xù)優(yōu)化預測-校準算法中識別污染源及釋放歷史.在該研究中,假設供水管網(wǎng)在已知的水力運行模式下運行.Pries和Ostfeld[11]提出了一種結(jié)合啟發(fā)式搜索技術(shù)的污染源定位方法,通過水質(zhì)傳感器檢測到的污染物濃度狀態(tài)信息來匹配隨機污染矩陣中的污染事件,由此逆向搜索污染源的位置和注入質(zhì)量等等,這項研究能解決計算量過大的問題,但是算法假設管道內(nèi)的流量是已知的,這和實際情況不符.

之后又有學者運用遺傳算法等智能優(yōu)化算法進一步提高了定位的準確性,Yan等人[12]運用改進的遺傳算法,根據(jù)問題變量的特性提出混合編碼方案,提高了算法的收斂速度和定位精度.Leichombam等人[13]將基于梯度的局部搜索策略和遺傳算法相結(jié)合提出一種混合的優(yōu)化方法用于污染源識別,該算法主要是對遺傳算法進行了改進,以不同的方式處理位置和通量的源變量,并通過仿真實驗證明了該方法在污染源定位問題的有效性和適用性.

以上方法都是將污染源定位問題轉(zhuǎn)化成一個優(yōu)化問題,再運用優(yōu)化算法進行問題求解.而供水管網(wǎng)的真實情況的復雜性使飲用水污染源定位問題具有3個復雜的特性:1)解的非唯一性.考慮到經(jīng)濟等因素,一般在城市給水管網(wǎng)中放置的水質(zhì)傳感器的數(shù)量遠少于管網(wǎng)節(jié)點數(shù)目,因此利用有限的水質(zhì)傳感器的檢測信息預測整個管網(wǎng)污染物注入狀態(tài),可能會得到多個污染物注入場景,但是,真實的污染物注入事件往往只在一個或兩個節(jié)點發(fā)生.該問題是一個典型的多模函數(shù)優(yōu)化問題,即雖然是單目標優(yōu)化問題,但適應值空間卻存在一個或多個全局極值點.2)計算代價昂貴性.飲用水供水管網(wǎng)節(jié)點規(guī)模巨大,并且污染源頭可能不止一個,造成了決策空間巨大,一般算法難以求解.該問題具有數(shù)據(jù)密集和計算密集的特點,利用優(yōu)化算法求解該問題時,需要較多的計算和存儲資源,是一個典型的昂貴優(yōu)化問題.3)解的不確定性.在實際的飲用水供水管網(wǎng)中,水流的方向和速度會隨著居民的需水量而動態(tài)變化,如果考慮到污染物為非保守物質(zhì),有可能與水體、管壁發(fā)生化學反應,則實際的污染源位置則更難預測,該問題是一個典型的動態(tài)優(yōu)化問題.針對問題的這些特性,學者們將污染源定位問題分別轉(zhuǎn)化成相應的優(yōu)化問題進行研究,得到了一系列新的研究成果.

3.1 多模優(yōu)化

前文列舉的研究成果都是將污染源定位問題看作是一個單目標優(yōu)化問題,通過對該問題進行深入的研究和分析,該問題還可被看作是一個多模優(yōu)化問題.

現(xiàn)實生活中很多問題并不是只有一個全局最優(yōu),它需要找到所有的全局最優(yōu)和局部最優(yōu),這一類問題被稱為多模問題,例如機器學習中的聚類問題和地震波的反演問題[14].優(yōu)化算法需要找到搜索空間中的多個最優(yōu)解,這么做有兩大好處:通過定位多個最優(yōu)解,提高尋找全局最優(yōu)的可能性;面對工程問題時,有時受限于時間或預算,算法并不需要找到全局最優(yōu),滿足條件的次優(yōu)解也可作為最后采納的解[15].

多模優(yōu)化是智能計算中最具挑戰(zhàn)性的任務之一.近年來,發(fā)展了許多進化多模態(tài)優(yōu)化算法.要想成功地解決多模態(tài)問題,就必須解決以下兩個問題:如何識別多個全局/局部最優(yōu)解以及如何將已識別的最優(yōu)解保持到搜索結(jié)束.

在進化算法的基礎,學者們將小生境方法融入其中來定位多個最優(yōu)解.小生境是將每一代種群中的個體根據(jù)相似性分成若干子種群,在每個子種群中找出適應值比較好的個體作為這一子種群的優(yōu)秀代表組成一個群,再在群內(nèi)和各子種群間進行選擇操作、交叉操作和突變操作產(chǎn)生下一代種群.小生境優(yōu)化技術(shù)[16]的本質(zhì)是通過在一次運行中保持種群的多樣性來尋找并保持盡可能多的全局最優(yōu)和局部最優(yōu).與傳統(tǒng)的優(yōu)化算法相比,小生境優(yōu)化算法在提高種群多樣性的同時,降低了陷入局部最優(yōu)的概率.其優(yōu)勢在于能搜索和定位多個全局/局部峰值,缺點在于要找到全局最優(yōu)通常需要更多的函數(shù)評估.小生境技術(shù)具有相對簡單、有效和通用的特性,因此可以作為進化算法強有力的組成部分.它可促使群體內(nèi)個體間協(xié)同合作,使算法易于找出優(yōu)化問題的所有局部最優(yōu)解和全局最優(yōu)解.小生境已經(jīng)被證明能夠非常有效的解決多解問題[17].

近年來,多模多目標優(yōu)化成為多模優(yōu)化研究領域的熱點問題.Yue等人[18]基于指數(shù)的環(huán)形拓撲結(jié)構(gòu)產(chǎn)生穩(wěn)定的小生境,從而能夠識別更多的帕累托最優(yōu)解,并在決策空間和目標空間中采用特殊擁擠距離的概念作為密度度量,提出了一種新的粒子群優(yōu)化算法,用于求解具有多個帕累托最優(yōu)解的多模多目標優(yōu)化問題.該算法不僅能定位和保持大量的帕累托最優(yōu)解,而且在決策空間和目標空間都能得到良好的分布.Liu等人[19]提出了一種新的多模態(tài)多目標進化算法,采用雙存檔和重組策略.該算法首先分析了決策變量的性質(zhì)和它們之間的關(guān)系,以指導進化搜索.然后采用融合檔案和多樣性檔案兩個檔案的總體框架來協(xié)同解決這些問題.同時采用聚類策略保證目標空間的多樣性,采用基于小生境的清除策略提高決策空間的多樣性,在進化過程結(jié)束時,對收斂性和多樣性檔案中的解進行重組,得到大量的多重帕累托最優(yōu)解.Liang等人[20]提出了一種多模態(tài)多目標差分進化優(yōu)化算法用于求解帕累托多模問題.該算法的主要貢獻是制定了一個決策變量預選方案,在決策空間和目標空間促進了解決方案的多樣性.同時還引入了一種新的突變結(jié)合過程,作為差分進化方法中經(jīng)典突變方案的補充,該方案給予搜索邊界之外的后代第2次突變機會,從而減少了搜索空間邊界上的個體密度.Qu等人[21]提出了一種基于自組織物種形成的多目標粒子群優(yōu)化算法,用于求解多模態(tài)多目標問題的多帕累托最優(yōu)解.該方法利用物種形成策略形成穩(wěn)定的生態(tài)位,并對這些生態(tài)位/亞種群進行優(yōu)化,以并行地搜索和保持帕累托最優(yōu)解.在此基礎上,提出了一種自組織機制,以提高物種形成的效率和算法的性能,為了保持決策空間和目標空間解的多樣性,將非支配排序方案和特殊擁擠距離技術(shù)相結(jié)合.Lin等人[22]提出了一種在決策空間和目標空間中具有對偶聚類的多模態(tài)多目標進化算法.在決策空間中運行一個聚類來聚集鄰近的解,將解劃分為多個局部聚類.首先選擇每個局部聚類內(nèi)的非支配解以保持局部帕累托集,然后選擇在目標空間內(nèi)具有較好的收斂性的非支配解,形成一個有N個以上解的臨時種群(N為種群規(guī)模).然后,對該臨時種群在目標空間進行第2次聚類,最終得到目標空間中具有良好多樣性的N個聚類.最后,在上述聚類上反復運行一個剪枝過程,直到每個聚類只有一個解決方案,每次都從目標空間最擁擠的聚類中刪除決策空間中最擁擠的解決方案.這樣,決策空間的聚類可以區(qū)分所有的帕累托集,避免局部帕累托集的損失,而目標空間的聚類則可以保持目標空間的多樣性.Liang等人[23]設計了基于聚類的特殊擁擠距離方法來計算決策空間和目標空間的綜合擁擠程度.同時引入基于距離的精英選擇機制來確定不同個體的學習范例.在樣本周圍生成新的個體,從而在決策空間和客觀空間中獲得均勻分布的種群.在此基礎上提出了一種基于聚類技術(shù)和精英選擇機制的差分進化算法來解決多模態(tài)多目標問題.

利用反演思想求解污染源定位問題時存在著潛在的解的非唯一性問題,主要的原因在于由于經(jīng)濟因素,一般在管網(wǎng)中布置的傳感器數(shù)量遠少于管網(wǎng)節(jié)點數(shù)目,不同來源的污染物排放特性顯著不同,但可能預測誤差相似,因此該問題具有多個全局極值,這導致所得解的精度大大下降.對于該類優(yōu)化問題,算法的目標是在一次執(zhí)行中搜索到所有的極值點.污染源定位問題已經(jīng)被證明是一個多模函數(shù)優(yōu)化問題[24].

針對污染源定位問題解的非唯一性的特征,Yan等人[25]將該問題轉(zhuǎn)化為一個多模優(yōu)化問題,在式(1)的基礎上對問題模型進行了改進,描述如下:

其中:N是管網(wǎng)的節(jié)點總數(shù),Ns表示傳感器的數(shù)目,Ts表示仿真周期,M表示污染物注入向量,n表示污染源注入的管網(wǎng)節(jié)點序號,tI表示注入污染物的初始時間,cj(t)表示在時間t時傳感器j的污染物濃度,它是(M,n,tI)的函數(shù),表示在時間t時傳感器j的實際檢測的污染物濃度.EPANET模擬個體對應的污染事件,當水質(zhì)傳感器檢測不到任何污染物時,此時f當污染事件偏離真實污染事件時,水質(zhì)傳感器檢測的濃度與真實傳感器濃度相差更大,致使個體適應度值f當污染事件接近真實污染事件時,水質(zhì)傳感器檢測的濃度與真實濃度更相近,個體適應度值f <隨著優(yōu)化算法的逐漸收斂,個體的適應度值不斷減小,通過實驗觀察,當適應度f <時,表示算法足夠收斂,即該污染事件可以當作滿足條件的污染事件.在改進的問題模型下,迭代條件由取得更小的適應度值變?yōu)槿〉脻M足閾值條件的適應度值.

文章采用動態(tài)小生境遺傳算法,通過算法的一次執(zhí)行計算出多個潛在的污染源,為篩選真實污染源提供了可能性,該研究認為,當污染事件在傳感器處的累積模擬濃度和實際累積檢測濃度最小方差小于閾值ε時,則認為該污染事件的注入節(jié)點為實際的污染源,最終的實驗結(jié)果表明小生境遺傳算法在解決污染源定位這個多模問題時是有效的.然而,文章并未在大規(guī)模管網(wǎng)中進行實驗,也沒有考慮管網(wǎng)中各種動態(tài)因素,如變化的用戶水需求等,因此該算法在求解大規(guī)模污染源定位問題時的有效性還有待驗證.

3.2 昂貴優(yōu)化

在實際工程問題中,許多目標函數(shù)不能用解析式表達出來,優(yōu)化模型也十分復雜,這時就需要運用仿真模型來模擬或評價目標函數(shù),而這種仿真模型調(diào)用一次計算量往往大于簡單函數(shù)計算,甚至一些特殊問題的仿真模型本身造價就高,多次使用仿真模型將耗費高昂的時間代價和經(jīng)濟代價,這類問題被稱為昂貴優(yōu)化問題.

在模擬–優(yōu)化法求解污染源定位問題的模型中,需要使用EPANET模擬器模擬污染事件,進而計算預測誤差.而調(diào)用EPANET需要消耗一定時間成本,當使用優(yōu)化算法求解時,作為一種靠迭代尋優(yōu)的方法,無疑會消耗大量的計算時間和資源.以管網(wǎng)BWSN2[26]為例(該管網(wǎng)包含12527個節(jié)點、2個水庫、2個池塘和20個傳感器),模擬一個污染事件,計算適應度值大約需要3 s.當使用種群規(guī)模100的遺傳算法運行100代求解時,需要花費329 min,接近5.5 h.在目前的研究中,小型管網(wǎng)如Rossman2000(92個節(jié)點)所需計算時間較少,EPANET模擬時間也較少,然而現(xiàn)實情況中的供水管網(wǎng)節(jié)點數(shù)量通常比較大,必然會消耗更多的時間,這在實際應用中是不被允許的.因此,污染源定位問題是一個昂貴優(yōu)化問題.

普通的優(yōu)化問題可以通過迭代計算得出最優(yōu)解,然而昂貴優(yōu)化問題受限于高昂成本,不能簡單地依靠大量迭代計算解決,優(yōu)化的主要目的變成了如何盡可能少地使用仿真模型同時不損失解得精度.為了克服這些障礙,基于代理的智能優(yōu)化算法已經(jīng)被廣泛使用.該方法使用一個計算花費小的近似模型去替代部分昂貴的適應度函數(shù)評價,近似模型也被稱作為元模型或者代理模型.

代理模型的種類有很多,選擇合適的代理模型對算法非常重要.常用的代理模型[27]大致有以下幾類:

1) 多項式響應曲面法(polynomial response surface,PRS).響應面方法(response surface methodology,RSM)[28]采用統(tǒng)計技術(shù)進行回歸和方差分析,以獲得響應的最小方差,多項式的簡單性使它們成為近似大多數(shù)多項式響應曲面的好方法.

2) 克里金法(Kriging),也稱高斯代理模型.高斯隨機過程[29]是隨機變量的集合,其中任意數(shù)量的樣本點具有聯(lián)合高斯分布.高斯隨機過程能模擬出函數(shù)的分布情況,它不僅能進行回歸預測,而且還能計算未知區(qū)域的不確定性.一般的回歸模型,僅僅能夠進行預測,無法判斷該預測是否正確,而高斯隨機過程能夠通過不確定性反映預測值的可信度.由于這一特性使得高斯隨機過程在很多領域得到了發(fā)展,也成為代理模型中最為廣泛的模型之一.

3) 徑向基函數(shù)(radical basis function,RBF).徑向基函數(shù)方法由Hardy[30]在1971年提出,RBF是一個實值函數(shù),其值僅取決于從輸入到神經(jīng)元中心的距離,只要符合一定條件的函數(shù),包括線性、立方、多元二次或高斯函數(shù)都可以作為核函數(shù).

4) 支持向量機(support vector machine,SVM).支持向量機[31]從統(tǒng)計學習理論中汲取靈感,是一種相關(guān)的監(jiān)督學習方法,用于分析數(shù)據(jù)和識別模式.SVM在高維中構(gòu)造超平面或一組超平面空間,可用于分類和回歸.

5) 人工神經(jīng)網(wǎng)(artificial neutral network,ANN).人工神經(jīng)網(wǎng)絡是大量神經(jīng)元互連而成的復雜網(wǎng)絡.網(wǎng)絡中的每個神經(jīng)元都能夠接收輸入信號,處理它們并發(fā)送輸出信號.它由一組加權(quán)的突觸、一個加法器和一個激活函數(shù)組成.加法器用于計算輸入信號經(jīng)神經(jīng)元相應突觸加權(quán)的和,激活函數(shù)用于限制神經(jīng)元輸出的幅度.網(wǎng)絡架構(gòu)有兩種不同的神經(jīng)網(wǎng)絡,包括多層前饋網(wǎng)絡和循環(huán)網(wǎng)絡.Komogorov定理表明,具有3層的多層感知器可以準確的模擬任何線性和非線性函數(shù).人工神經(jīng)網(wǎng)絡也經(jīng)常用于近似復雜、耗時的目標函數(shù),或者耗時的仿真實驗.

在優(yōu)化算法框架中嵌入代理模型,根據(jù)不同的情況選擇使用代理模型還是真實昂貴函數(shù)的策略稱為模型管理.模型管理同樣會影響算法的性能,管理方式分為離線與在線.離線模型在訓練好模型后就不再更新模型,如果數(shù)據(jù)量足夠多,那么問題變成了如何自適應地選擇數(shù)據(jù)子集來減少計算時間[32],如果數(shù)據(jù)量很少且有噪聲,就需要相應的策略來建立精準的模型;在線模型可以通過獲得的新數(shù)據(jù)不斷更新代理模型,這種模型管理方式會讓模型更精確,但同時更新模型也會消耗計算資源.代理模型的應用可以根據(jù)在優(yōu)化過程中是否更新大致分為兩種:一種是代理模型建立之后在優(yōu)化過程中保持不變,一直使用已建立的模型;另一種是在優(yōu)化過程中代理模型不斷更新,每次迭代就再次建立代理模型.面對不同的實際問題,選擇不同的應用方式:當樣本量較少時,就需要優(yōu)化過程中的數(shù)據(jù)來更新模型,以提高模型精確度;而樣本量比較大時,如果采用以上方式就會耗費大量的計算時間,因此根據(jù)大量樣本建立高精度模型,并在優(yōu)化過程中使用已建立的高精度模型.近年來,代理模型相關(guān)的算法和應用越來越受到關(guān)注,許多研究人員獲得了豐碩的成果.Chugh等人[33]使用Kriging來近似目標函數(shù)來降低計算成本.利用Kriging模型得到預測點的不確定性,平衡算法的多樣性與收斂性,并且他們還提出了模型樣本點選取策略.Yang等人[34]在高維優(yōu)化問題中,采用分而治之的解決方案,提出子問題的搜索應被視為昂貴優(yōu)化問題,并通過代理模型解決.Chen等人[35]將代理模型應用在運輸網(wǎng)的最優(yōu)收費方案中,建立近似的反應曲面,減少求解時間,從結(jié)果表明:代理模型的使用,使得預測的最優(yōu)收費可以讓社會受益.Pan等人[36]將代理模型引入到高維多目標優(yōu)化問題中,算法使用人工神經(jīng)網(wǎng)絡預測候選解與參考解之間的支配關(guān)系,既考慮個體的優(yōu)勢關(guān)系,也考慮模型的精確度.Yu等人[37]提出一個基于代理模型的分層粒子群優(yōu)化器來求解高維問題,該算法是標準粒子群優(yōu)化算法和社會學習粒子群優(yōu)化算法的結(jié)合,使用這兩種算法在搜索空間中一起來進行搜索,同時增強代理模型全局和局部的搜索性能.Wang等人[38]提出了一種綜合考慮全局勘探和局部開采兩種能力的演化抽樣輔助優(yōu)化方法.利用變異算子和交叉算子,采用差分進化方法產(chǎn)生后代.建立了全局徑向基函數(shù)代理模型,對后代的目標函數(shù)值進行預篩選,并篩選出最優(yōu)的目標函數(shù)值,用真函數(shù)對目標函數(shù)值進行評價.當其函數(shù)值小于親本時,其最佳后代將取代親本在種群中的位置.然后使用選定的當前最佳解決方案構(gòu)建局部代理模型.Li等人[39]提出了一種求解高維計算昂貴問題的代理輔助多種群優(yōu)化算法,該算法包括兩個種群:第1個是使用基于教學優(yōu)化的學習者階段來增強探索,第2個是使用粒子群優(yōu)化來加快收斂速度,這兩個種群可以互相學習.同時提出了一種動態(tài)種群大小調(diào)整方案來控制進化過程.為了進一步提高粒子群算法在不同功能場景下的搜索效率,采用了兩個坐標系統(tǒng)來生成粒子群算法的理想位置.此外,提出了一種新的預篩選準則來選擇有潛力的個體進行精確的功能評估.Cai 等人[40]提出了一種代理引導的差分進化算法.與其他代理輔助的元啟發(fā)式算法不同的是,該算法實現(xiàn)了差分進化算法與代理算法之間的融合,而不僅僅是作為加速元啟發(fā)式算法收斂的額外工具.具體而言,該算法將全局和局部代理預測的最優(yōu)值與變異算子相結(jié)合,使變異算子引導差分進化算法的變異方向,從而使差分進化算法快速收斂.Cai等人[41]還提出了一種高效的代理輔助的粒子群優(yōu)化算法,該算法有時需要進行昂貴的仿真分析.與其他幾種代理輔助的元啟發(fā)式算法不同之處在于該算法在優(yōu)化過程中能夠有效平衡代理模型的預測能力和粒子群優(yōu)化的全局搜索能力.該算法利用建立在整個設計空間的全局代理模型和建立在個人歷史最佳粒子周圍的鄰近區(qū)域的局部代理模型來更新粒子的速度.需要強調(diào)的是,用于獲得最優(yōu)局部代理模型的鄰域劃分策略是該算法的一個重要方面,該策略有助于獲得鄰域局部代理的預測最優(yōu)解,以指導優(yōu)化過程中粒子群優(yōu)化的搜索.

將污染源定位問題看作是一個昂貴優(yōu)化問題后,在原有的模擬–優(yōu)化算法基礎上就是以代理模型來代替部分EPANET軟件計算誤差的過程,即用簡單的數(shù)學模型替代復雜的仿真軟件,達到節(jié)約計算資源的目的.基本的思路如下:首先建立一個與目標函數(shù)相近的模型,使用樣本集建立一個誤差較低的代理模型.代理模型的目的是代替真實的評價函數(shù)對個體進行適應度評價,在保證算法精確度的情況下,盡可能的減少時間成本較大的真實目標函數(shù)的使用.與普通的優(yōu)化算法不同,昂貴優(yōu)化算法的模型中,在種群產(chǎn)生新的后代后,可以選擇代理模型代替EPANET模擬器評價新的個體,或者仍然使用原始目標函數(shù).如何平衡高斯代理模型和EPANET模擬器間使用對算法的優(yōu)化過程有著直接的影響.如果使用代理模型的次數(shù)過多,模擬評價個體適應度的誤差較大,直接影響算法的收斂方向;如果使用EPANET模擬器次數(shù)過多,又不能達到減少計算代價的目的.因此,在優(yōu)化算法求解污染源定位問題中,不僅需要根據(jù)問題特性建立代理模型,而且需要對代理模型使用進行設計.

此時問題轉(zhuǎn)化為如何平衡EPANET和代理模型之間的使用,在不影響求解精度的同時盡可能減少計算時間.Gong等人[42]通過實驗得出使用高斯代理模型和不使用高斯代理模型分別調(diào)用EPANET的次數(shù),前者約為后者的

Preis和Ostfeld[43]在2006年首次提出了一種利用耦合模型樹–線性規(guī)劃算法進行供水系統(tǒng)污染源識別的方法,模型樹取代了EPANET模擬器,線性規(guī)劃算法用模型樹來識別污染源,對于一個給定的網(wǎng)絡,模型樹結(jié)構(gòu)模擬網(wǎng)絡對不同隨機污染事件的響應,該方法提供了對時間、位置和污染注入濃度的估計.Gong等人[42]提出了一種基于協(xié)同的昂貴優(yōu)化算法,該算法根據(jù)供水管網(wǎng)的特點,針對不同的變量分別提出不同策略來指導算法的搜索方向,算法盡可能采用高斯代理模型,以保證識別精度,最后通過仿真實驗,驗證了所提算法的有效性和穩(wěn)定性.Yan等人[44]根據(jù)供水管網(wǎng)的特性,建立了管網(wǎng)中每個節(jié)點的高斯代理模型,提出了一種基于高斯代理模型的昂貴優(yōu)化算法來解決供水管網(wǎng)中的污染源定位問題,并通過仿真實驗證明了算法的有效性和高效性.

代理模型雖然代替部分EPANET,減少了算法運行時間,但代理模型與真實評估函數(shù)間仍存在差距,可能會引導算法向錯誤的方向收斂,導致算法陷入局部最優(yōu),代理模型使用比例越高,誤導率也會越高.因此在基于代理的優(yōu)化算法需要平衡代理模型與EPANET仿真軟件之間的使用,既不損失解精度,保證算法朝正確的方向收斂,又能盡可能減少計算時間.

3.3 不確定性

現(xiàn)實生活中很多實例都存在不確定性,例如不斷有新任務到達的調(diào)度問題.不確定性使優(yōu)化問題的復雜性大幅度提升,傳統(tǒng)的靜態(tài)優(yōu)化算法已不能滿足問題需求.常見的不確定性因素包括適應度值發(fā)生變化、問題實例變化和約束條件變化,這些因素都使問題轉(zhuǎn)化為一個動態(tài)優(yōu)化問題(dynamic optimization problems,DOPs)[45],其定義如下:

其中:S ∈Rn,S是搜索空間,t是時間,S×T →R是目標函數(shù),x是可行解,X(t)是在t時間內(nèi)可行解集合.對一個最小化問題,DOPs 的目標是尋找一系列隨時間變化的最優(yōu)個體集合X?t ∈T滿足t)≤f(x,t),?x ∈X(t).

有關(guān)動態(tài)優(yōu)化問題的研究已經(jīng)成為優(yōu)化算法研究領域的一個熱點,傳統(tǒng)的進化算法(evolutionary algorithms,EA)在解決動態(tài)優(yōu)化問題時,一旦收斂,失去了探索新區(qū)域的多樣性,當新的環(huán)境到來時,就不能跟蹤到新環(huán)境里繼續(xù)搜索了.為了解決DOPs,靜態(tài)優(yōu)化算法需要在演化過程中對變化的環(huán)境做出及時的反應并跟蹤最優(yōu)值.2005年后有大量動態(tài)環(huán)境進化算法被提出,學者們關(guān)注的問題主要在于兩個方面:環(huán)境監(jiān)測;保持群體多樣性.檢測通常是通過重新評估解的適應度值來判斷環(huán)境是否變化的,除了在環(huán)境發(fā)生變化后增加群體多樣性,一些學者還通過在算法運行過程中維持多樣性、設置記憶機制、預測機制、多種群機制等方法設計進化算法[46].

前面提到的污染源定位問題研究都假設供水管網(wǎng)系統(tǒng)的水力特性是已知的,例如壓力、流量、消耗、水箱水位等,而實際情況是只有部分信息能被獲取.當污染事件發(fā)生時,供水運營商需要在不確定的環(huán)境下做出決策,他們只能利用有限的信息,并且水管網(wǎng)的水力因素也會因消費者的反應動態(tài)變化,這些都使得管網(wǎng)系統(tǒng)的動態(tài)性更加復雜,導致優(yōu)化目標函數(shù)可能隨著時間改變,問題的最優(yōu)解也在隨時改變.Ostfeld在文獻[47]中總結(jié)了供水系統(tǒng)中包括的不確定性和風險,并提出了這些問題帶來的相應挑戰(zhàn).Preis等人[48]提出一種量化不確定性的方法,在先前開發(fā)的污染源模型的基礎上,將水需求和傳感器傳輸?shù)臄?shù)據(jù)中的不確定性納入其中.

考慮不確定性的污染源定位問題具有兩個復雜的特性:

1) 不確定的用水需求數(shù)據(jù).供水管網(wǎng)污染源定位系統(tǒng)的不確定性包括3個方面:由于抽樣的偏差和檢測的錯誤導致的觀測誤差和傳感器測量誤差;由于水利水質(zhì)模型中的簡化和不正確的假設導致的模型誤差;由于未知的即時水需求的波動導致的不確定的用水需求,用水消費水平的固有變化,消費者節(jié)點水需求是不確定的主要來源.由以上存在的不確定性,給水管網(wǎng)污染源定位問題不能使用確定性方法(假設系統(tǒng)在完全已知的條件下運行)解決.

2) 突發(fā)性污染源的實時特性.在采用模擬–優(yōu)化的方法求解污染源定位問題時,為了盡量減小污染物對公共健康的危害,需要在發(fā)生突發(fā)性事件時能夠?qū)崟r定位污染源位置,即當水質(zhì)傳感器開始檢測到污染獲取了水質(zhì)信息后開始模擬,需要盡可能快的定位污染源位置.

Liu等人[49]提出一種基于多種群的動態(tài)優(yōu)化算法,該方法利用流數(shù)據(jù)可用來自適應估計源的特性,在檢測到污染事件后,源特性的估計值會隨著新的觀測數(shù)據(jù)不斷更新,從而動態(tài)更新預測誤差函數(shù),改變優(yōu)化模型中的目標函數(shù).隨著更多觀測數(shù)據(jù)的添加,多種群方案會逐漸尋找到更好地解決方案,同時減少解的非唯一性程度.Laird等人[50]提出了一種基于子域的動態(tài)優(yōu)化方法,以減少過多的計算時間,研究表明子域方法減少了用于優(yōu)化的可用信息數(shù)量,因此減少了計算時間,同時提高了解的質(zhì)量.Vankayala等人[51]采用高斯模型和自回歸模型綜合生成隨機水需求,將隨機遺傳算法和噪聲遺傳算法應用于同一問題進行比較.結(jié)果表明噪聲遺傳算法比隨機遺傳算法具有更好的魯棒性和更小的計算開銷,自回歸模型比高斯模型更能代表污染源識別過程中的不確定性.

Yan等人分別采用高斯模型[52]、自回歸模型[53]和齊次泊松模型[54]來模擬用戶的需水量,然后提出一種改進的遺傳算法來解決不確定需水量條件下的飲用水污染源定位問題,并在不同規(guī)模的供水管網(wǎng)上進行仿真實驗對比.

1) 高斯模型是一個加入簡單白噪聲干擾的完全不相關(guān)模型,被應用在缺少先驗概率的情形下,也就是在沒有大量的觀測到的用水需求數(shù)據(jù)下使用,在高斯模型中,在每個節(jié)點每個時間步長下的用水需求被加入一個簡單的高斯擾動.

2) 自回歸模型是一種隨機的、線性的需求變化模型,是用自身做回歸變量的過程,即利用前期若干時刻的隨機變量的線性組合來描述以后某時刻隨機變量的線性回歸模型[55],當已知大量的用水需求數(shù)據(jù)時,適合使用自回歸模型建立水需求變化模型.

3) 泊松分布模型是一種統(tǒng)計與概率學里常見到的離散機率分布,與前兩種模型不同,泊松分布可以給出管網(wǎng)中任意節(jié)點的瞬時水需求數(shù)據(jù).

文章分別用上述3種模型產(chǎn)生的若干組用水需求數(shù)據(jù),與基礎用水需求數(shù)據(jù)的曲線作對比,結(jié)果顯示:高斯模型具有很大的隨機性,自回歸模型更貼近真實的用水需求,泊松的隨機性居中;但是3種不同的水需求變化模型產(chǎn)生的水需求符合居民每日用水變化規(guī)律.作者將不確定的用水數(shù)據(jù)作為模擬–優(yōu)化模型的輸入,在式(1)的基礎上加入不確定的居民用水需求以及模擬時間,采用最小最大化準則求解不確定水需求的污染源定位問題.不確定水需求污染源定位模型如下:

其中:L表示污染源位置節(jié)點,C0表示在已知的污染注射時間內(nèi)源污染物濃度,t表示當前的時間步長,需要求解得到注入污染的污染源位置節(jié)點和注入污染物的質(zhì)量;F表示預測誤差,目標函數(shù)是最小化預測誤差,Ns表示傳感器的數(shù)量,Ts表示仿真周期,表示在時間t時傳感器k處的觀測污染物濃度,它是(M,n,tI)的函數(shù),(L,C0,t)表示在時間t時傳感器k處的實際污染物濃度;M表示污染物注入向量,n表示污染源注入的管網(wǎng)節(jié)點序號,tI表示注入污染物的初始時間.

文章改進基礎遺傳算法求解該模型,實驗結(jié)果證明了提出改進的遺傳算法具有更高的準確性和更好的魯棒性,最后給出了對供水管網(wǎng)突發(fā)性污染源實時定位問題的有效求解方法.但文章只展現(xiàn)了兩個管網(wǎng)中的實驗數(shù)據(jù),且并未在大規(guī)模管網(wǎng)中進行研究,在建立自回歸模型時并未使用真實的居民用水需求數(shù)據(jù),而使用由高斯模型產(chǎn)生的與基準居民用水曲線具有相同規(guī)律的不確定居民用水數(shù)據(jù),因此文中的工作還可基于真實用水數(shù)據(jù)進行驗證,并嘗試運用在大規(guī)模管網(wǎng)中以貼近現(xiàn)實城鎮(zhèn)管網(wǎng)情況.

除了需水量不確定,突發(fā)性污染也是管網(wǎng)中的不確定性因素.Yan等人[56]完善了這方面的研究,他們在研究需水量不確定的情況下,突發(fā)污染源的實時定位問題,當污染源被檢測到后,用提出的實時定位算法對污染源進行跟蹤,實驗結(jié)果表明,與傳統(tǒng)的污染源定位方法相比,文章提出的方法能夠以較少的傳感器數(shù)據(jù)在較短時間內(nèi)找到真實的污染事件.

4 展望

在環(huán)境問題日益突出的今天,研究飲用水污染源定位問題對環(huán)境保護有重要意義.飲用水污染源定位問題與居民生活安全息息相關(guān),一直以來都是亟需解決的熱點問題,隨著智能優(yōu)化算法的發(fā)展,目前將模擬–優(yōu)化方法用于污染源定位問題的研究成果已有許多,但仍有許多工作需要研究與拓展,下面就問題、算法和應用等層面給予展望.

1) 問題層面.

一方面,目前的基于模擬–優(yōu)化方法的污染源定位研究通常對問題假設過多,與實際環(huán)境差距較大.許多研究都假設污染物為非衰減類,且不與水中其他物質(zhì)發(fā)生化學生物等反應.但在實際供水管網(wǎng)中的真實情況并不是這樣的,因此,研究污染物具有衰減性,且與水中其他物質(zhì)發(fā)生化學生物反應的飲用水污染源定位問題更具有現(xiàn)實意義.同時,對于供水管網(wǎng)入侵污染物流量問題,現(xiàn)有的研究是假定了污染物入侵流量的多少并不影響該管網(wǎng)的水力工況,然而供水管網(wǎng)實際突發(fā)污染事故的情況是不可預測的,污染源的個數(shù)、污染物濃度、侵入方式、持續(xù)時間等均不可預知.因此,研究不確定環(huán)境下的污染源定位問題更具挑戰(zhàn)性.研究應考慮供水管網(wǎng)的真實情況和規(guī)模,充分研究不確定性對問題帶來的影響.對問題的建?？煽紤]加入約束條件以模擬現(xiàn)實因素,使研究成果更具現(xiàn)實意義.另一方面,目前針對污染源定位的理論研究很少,而且大多針對單污染源定位問題.圍繞污染源定位問題,分析問題的特性,剖析解空間的特征,研究高效的編碼和解碼策略、快速性能評價機制、定位過程中的有效調(diào)整策略,無疑將有助于推動污染源定位的理論與方法的發(fā)展.

2) 算法層面.

污染源定位問題的求解復雜性隨著管網(wǎng)規(guī)模的增大將急劇增加,目前的算法大多局限于機器學習方法和智能優(yōu)化方法,而基于數(shù)學模型和仿真軟件的方法只適于小規(guī)模問題.對于智能優(yōu)化方法而言,目前的方法主要是遺傳算法和演化策略.一方面,針對污染源定位問題的特征提出特定的智能優(yōu)化算法,包括基于人工智能的方法;另一方面,將目前流行的群體智能算法、差分進化、多模優(yōu)化、昂貴優(yōu)化算法等推廣應用于污染源定位,均是很有意義的研究工作.智能優(yōu)化算法的關(guān)鍵在于遺傳操作的設計、參數(shù)的設定以及全局搜索與局部搜索的均衡.因此,研究的重點在于合理的搜索策略、對問題特征的知識挖掘、基于問題特征的高效的編碼和解碼策略、參數(shù)的自適應機制、有效的遺傳操作的混合智能優(yōu)化算法以及協(xié)同智能優(yōu)化算法.另外,求解精度仍需進一步提高,其中污染源位置是最主要的評判指標,后續(xù)研究在保證位置準確的情況下可進一步提高時間與污染物濃度求解的精確程度.每種智能優(yōu)化算法都有其缺陷,使用單一算法無法避免,可以考慮使用集成算法.當然,智能優(yōu)化算法的計算復雜性、收斂性、下界等理論問題也值得關(guān)注.

3) 應用層面.

開展理論研究主要是為了能指導實際應用,同時應用研究也對理論研究有促進作用.雖然污染源定位問題的相關(guān)理論和方法在某些實際問題中得到了初步應用,但離實際應用還有不小的差距.一方面,要加強對實際問題的理解和深入研究,問題特征分析、模型構(gòu)建、算法設計等工作均要跟實際問題緊密結(jié)合;另一方面,要對現(xiàn)有應用研究的范圍進行拓展,比如:充分考慮到公眾健康的需求,污染源定位的時間仍需要進一步縮短,盡可能快地為政府部門提供污染源信息以便及時制定應對措施.可在保證求解精度的同時盡量縮短算法求解的時間;針對污染源定位問題的3個特性:多模性、昂貴性和不確定性,現(xiàn)有的研究都是側(cè)重解決某一類問題,后續(xù)研究可以將其兩個特性同時考慮,或3個特性同時考慮,完善問題的數(shù)學模型,使之更符合實際情況;現(xiàn)有的研究中求解污染源定位問題時都是假設傳感器已經(jīng)部署在設定點上,沒有考慮傳感器位置的最優(yōu)布置,后續(xù)研究可以結(jié)合傳感器部署問題進行,以更優(yōu)化的傳感器位置改善污染源定位問題的求解精度和求解時間.