水文循環算法的改進

何欣蕓，周朝榮,2+

(1.四川師范大學 物理與電子工程學院，四川 成都 610101；2.成都信息工程大學 氣象信息與信號處理四川省高校重點實驗室，四川 成都 610225)

0 引 言

近年來，受自然界中水運動的啟發，一些基于水的智能優化算法迅速發展起來。Hosseini基于河流中水滴間的作用與反作用，提出智能水滴算法[1]。Yang等模擬水流運動設計出類水流算法[2]。Rabanal等借鑒河流形成動力學來解決NP-Hard問題[3]。通過觀察水的循環過程以及河流、溪流的運動，Eskandar等設計出水循環算法，并應用于約束優化問題的求解[4]。Wu等受淺水波模型啟發，提出水波算法[5]。這些受水運動啟發的算法由于參數少、易調節、模型簡單等優點受到了許多學者的關注。

然而，上述算法只涉及到自然界中水運動的部分過程，未考慮到完整的水循環運動，只模擬水運動的部分過程會限制算法搜索能力，造成算法早熟收斂。為此，Wedyan等模擬水的循環再生過程提出水文循環算法(hydrological cycle algorithm，HCA)，并通過仿真實驗驗證水文循環算法在連續問題與離散問題上均優于僅模擬部分水運動的算法[6,7]。其中，水文循環是指水在自然界中的連續循環運動，包括水受重力與地勢影響從高處向低處流動、受陽光照射蒸發到大氣層以及在空中凝結成水滴重新落回地面等階段。HCA利用完整的水循環過程，為算法設計提供新的思路。

然而，HCA仍存在收斂速度慢、尋優精度不高以及運行時間較長等問題。為此，本文首先在HCA的種群初始化階段采用混沌的方法，強化全局搜索能力、加快收斂速度；其次，自適應產生溫度更新參數，以減少算法的運行時間；最后，在凝結階段引入逆水流過程，以提高算法的尋優精度。為驗證改進后的算法性能，在10個經典函數上進行仿真測試，并與粒子群算法[8]、遺傳算法[9]與鯨魚算法[10]進行比較。測試結果表明，改進后的算法在尋優精度、收斂速度以及運行時間上較HCA表現更優，且總體性能優于粒子群算法、遺傳算法與鯨魚算法。

1 水文循環算法

1.1 流動階段

水滴在具有數條等高線的山形圖上進行流動，山形圖個數由函數的維度決定，等高線條數由算法精度決定，越靠近山頂的等高線所占權重越大。

水滴從山頂出發，在每層等高線上選擇移動到某個節點。水滴遍歷完所有等高線后，各個維度中存儲著水滴在該維山形圖的等高線上所選節點。

流動階段涉及到節點選擇與次數、速度、土壤量、溫度的更新，實現原理如下：

(1)節點選擇

水滴在山形圖上移動時，根據下一層等高線上節點的選擇概率，采用輪盤賭的方法選出節點。水滴在節點i的位置選擇下一層等高線上節點j的概率給出如下

(1)

移動到新的節點后，立即更新該段路徑被選次數、土壤量以及水滴的速度和所攜帶的土壤量。

(2)溫度更新

一次流動階段結束時，基于此時水滴的適值差異更新溫度

Temp(T+1)=Temp(T)+ΔTemp

(2)

1.2 蒸發階段

在蒸發階段，被蒸發的水滴的個數隨機生成，用輪盤賭的方法選擇出被蒸發的水滴。

1.3 凝結階段

蒸發后的水滴按如下方式進行變異

(3)

1.4 降雨階段

在降雨階段，若達到最大迭代次數則輸出最優解；否則，重新初始化動態變量與參數，利用本次迭代得到的最優解對動態參數進行加固處理，以指導下一代尋優。參數加固計算如下

Soil(i,j)=0.9×Soil(i,j) ?(i,j)∈BestWD

(4)

其中，BestWD表示本次迭代得到的最優解，?(i,j)∈BestWD表示該最優解在流動階段所選路徑。

2 改進的水文循環算法

HCA的初始水滴種群隨機產生，多樣性難以保證，會對算法的性能造成顯著影響，初始種群分布越均勻的算法具有更高的收斂速度與尋優精度[11]。為此，考慮混沌方法豐富初始種群的多樣性。其次，HCA將溫度更新參數設置為固定值，個別優化函數在流動階段內循環多次，以致算法運行時間過長。因此，針對不同的優化函數設置不同的溫度更新參數。最后，為解決尋優精度低的問題，基于原算法中的山形圖，提出水滴逆向運動模型，即“逆水流”過程。該過程舍棄原算法流動階段中的復雜參數與公式，不僅模型更為簡單，且有效地提高了算法的尋優精度。

2.1 混沌初始化

混沌是具有遍歷性、半隨機性以及初始條件依賴性的一種非線性系統[12]。與隨機初始化相比，利用混沌進行初始化可以產生分布更均勻的初始種群[13]。Skew Tent混沌映射模型簡單、具有較好的遍歷性，且初始條件的依賴性低。本文采用Skew Tent混沌映射對水滴種群進行初始化[14]

(5)

(6)

2.2 自適應溫度更新參數

HCA在優化某些問題時，一次流動階段結束后的水滴適值相差較大，溫度增長緩慢，算法在流動階段多次循環，最終導致整個算法的運行時間過長。為此，采用自適應溫度更新參數代替原算法中固定的溫度更新參數，由初始種群的適值來決定溫度的增長速度，從而降低算法的運行時間。

在種群初始化階段結束后，評估水滴種群的適值，根據最差適值ψmax與最優適值ψmin計算溫度更新參數

(7)

2.3 逆水流

針對HCA容易陷入局部最優的問題，利用已有的山形圖，設計逆水流代替原凝結階段的變異操作，以提高算法的尋優精度。

水滴開始逆流時，首先從山腳出發，向高層等高線移動。在此過程中，同層等高線上的節點間彼此連通，水滴在同層等高線上移動后，再移向更高層的等高線。對應的逆水流過程如圖1所示。

圖1 逆水流過程

水滴在某一層等高線上移動時，隨機選擇一個節點數值比原節點數值小的節點，然后評估該節點。若對應的水滴適值優于原節點，則替換掉原節點，并繼續隨機選擇一個數值更小的節點，直至選擇數值更小的次數達到上限。

若所選節點對應的水滴適值更差，或原節點的數值已是最小，或選擇數值更小的次數已達上限，則在該層隨機選擇一個節點數值比原節點數值更大的節點。進一步地，評估該節點，若適值更優則進行替換，并繼續選擇數值更大的節點直至次數達到上限；若適值更差，或是原節點的數值已是最大，則水滴流入上一層等高線。

水滴逆流的完整過程見表1。

表1 逆流過程

當流動階段結束后，每顆水滴生成的解以節點數組的形式存儲在水滴中。在逆流過程中，水滴首先改變底層等高線上的節點，由于底層等高線所占權重小，此時可視為局部搜索；當水滴逆移動到較高層等高線時，可視為全局搜索。

2.4 改進算法的流程圖

HCA結合上述混沌初始化與自適應溫度更新參數策略，得到溫度自適應水文循環算法(THCA)；HCA結合上述混沌初始化與逆水流策略，得到逆水文循環算法(IHCA)；HCA同時結合上述混沌初始化、自適應溫度更新參數以及逆水流策略，得到溫度自適應逆水文循環算法(TIHCA)。其中，TIHCA的流程如圖2所示。

圖2 溫度自適應逆水文循環算法流程

3 實驗結果及分析

3.1 實驗環境

仿真實驗的運行環境為Intel Core i7 CPU，主頻2.40 GHz，內存8 GB，Windows10 64位操作系統，實驗仿真軟件采用MATLAB R2016a。

3.2 測試函數與參數設置

本文選擇5組多峰基準測試函數f1-f5和5組單峰基準測試函數f6-f10來驗證算法性能。表2給出了測試函數的定義、搜索空間和理論最優解。

表2 測試函數

表2(續)

所有對比算法都統一設置種群大小為10，最大迭代次數為500。針對上述每個函數，每種算法均獨立運行30次。對比算法與參數設置見表3、表4。

表3 對比算法

表4 各算法參數設置

3.3 算法尋優精度比較

所有測試函數的實驗結果見表5、表6。

從表5可以看出，對于多峰測試函數f1-f5：在函數f1、f4中，IHCA、TIHCA與WOA得到相同的最優值；在函數f2、f3中，IHCA與TIHCA各項指標的值非常接近，且均優于其它算法；在函數f5中，IHCA的最差值、平均值、標準差均優于其它對比算法。

表5 多峰函數尋優精度對比結果

表5(續)

從表6可以看出，對于單峰測試函數f6-f10：就函數f6、f7、f10而言，IHCA與TIHCA準確找到理論最優值，且表現穩定；在函數f8中，IHCA與TIHCA得到相同的最優值，但IHCA的最差值、平均值、標準差優于TIHCA以及其它對比算法。

表6 單峰函數尋優精度對比結果

與HCA相比，THCA有3個函數的平均值更優，其余函數的平均結果相差不大；IHCA在10個函數中的尋優均值均優于HCA；TIHCA在9個函數中具有更好的平均值?？傮w而言，IHCA在尋優精度方面表現最好，而 TIHCA 僅次于IHCA。這表明逆水流策略在尋優精度上具有明顯優勢，而自適應溫度更新參數策略雖未能有效地改善HCA的尋優精度，但減少流動階段的循環次數未對算法的尋優精度造成不利影響。

3.4 算法收斂速度比較

各個算法針對不同函數的收斂曲線如圖3-圖12所示。

圖3 函數f1的收斂曲線

圖4 函數f2的收斂曲線

圖5 函數f3的收斂曲線

圖6 函數f4的收斂曲線

圖7 函數f5的收斂曲線

圖8 函數f6的收斂曲線

圖9 函數f7的收斂曲線

圖10 函數f8的收斂曲線

圖11 函數f9的收斂曲線

圖12 函數f10的收斂曲線

從圖中可以看出，在絕大多數時候，所有改進的HCA都比HCA更快收斂。在函數f1-f3、f6中，THCA的收斂速度最快。雖然在函數f1、f2、f6中，PSO與THCA具有相同的收斂速度，但PSO的尋優精度較差。在函數f7、f8、f10中，IHCA具有最快的收斂速度。雖然在函數f8中，GA與IHCA的收斂速度相同，但GA的尋優精度遠低于IHCA。在函數f9中，TIHCA的收斂速度最快。

與HCA相比，THCA在函數f1-f3、f5-f7、f9中具有更快的收斂速度，IHCA在函數f1、f3、f5-f8、f10中的收斂速度更快，TIHCA在函數f1、f2、f5、f6、f9中收斂更快?？傮w而言，THCA與IHCA的收斂速度最快。這表明各個策略對算法的收斂速度均有不同程度的提升，而混沌初始化與自適應溫度更新參數的結合，以及混沌初始化與逆水流的結合在收斂速度上均有更好的改進效果。

3.5 算法運行時間比較

對算法運行30次的時間取平均值，所有對比算法的運行時間如圖13所示。

圖13 f1-f10運行時間對比結果

從圖13可以看出，針對10個測試函數，PSO、GA與WOA的運行時間均為最短，這是由于HCA本身具有較多且復雜的參數與公式，即使改進后的算法THCA、IHCA、TIHCA運行時間仍較PSO、GA與WOA更長。

與HCA相比，THCA在函數f1-f5、f7-f10上的運行時間更短，IHCA在函數f3-f5、f9上花費更少的時間，TIHCA在函數f3-f5、f7-f10上的運行時間更短?？傮w而言，THCA的運行時間最短，這體現了自適應溫度更新參數策略在運行時間上的優越性。而TIHCA僅次于THCA，這是由于逆水流過程的引入會增加一定的計算量。

綜合上述實驗結果可以看出：THCA的運行時間最短、收斂速度最快，IHCA具有最好的尋優精度與收斂速度，而TIHCA折中了尋優精度與運行時間兩方面的性能指標，算法性能介于THCA與IHCA之間。在求解實際優化問題時，可以根據實際需要選擇合適的策略。

4 結束語

針對水文循環算法的不足，本文采用混沌的方法初始化水滴種群，增強算法的全局搜索能力、提升算法的收斂速度；引入自適應溫度更新參數策略，減少算法的運行時間；提出逆水流過程代替原凝結階段中的變異操作，以提高算法的尋優精度。實驗結果表明，改進的算法在收斂速度、尋優精度與運行時間等方面均有較大的性能提升。然而，水文循環算法自身也存在局限性：算法中包含大量參數與動態變量，以致水文循環算法以及本文中的改進算法在運行時間方面依然不如粒子群算法、遺傳算法與鯨魚算法，且求解高維函數較為困難。如何改進這些缺點，將是下一步的研究工作。