水文循環(huán)算法的改進(jìn)

何欣蕓，周朝榮,2+

(1.四川師范大學(xué) 物理與電子工程學(xué)院，四川 成都 610101；2.成都信息工程大學(xué) 氣象信息與信號(hào)處理四川省高校重點(diǎn)實(shí)驗(yàn)室，四川 成都 610225)

0 引 言

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

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

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

1 水文循環(huán)算法

1.1 流動(dòng)階段

水滴在具有數(shù)條等高線的山形圖上進(jìn)行流動(dòng)，山形圖個(gè)數(shù)由函數(shù)的維度決定，等高線條數(shù)由算法精度決定，越靠近山頂?shù)牡雀呔€所占權(quán)重越大。

水滴從山頂出發(fā)，在每層等高線上選擇移動(dòng)到某個(gè)節(jié)點(diǎn)。水滴遍歷完所有等高線后，各個(gè)維度中存儲(chǔ)著水滴在該維山形圖的等高線上所選節(jié)點(diǎn)。

流動(dòng)階段涉及到節(jié)點(diǎn)選擇與次數(shù)、速度、土壤量、溫度的更新，實(shí)現(xiàn)原理如下：

(1)節(jié)點(diǎn)選擇

水滴在山形圖上移動(dòng)時(shí)，根據(jù)下一層等高線上節(jié)點(diǎn)的選擇概率，采用輪盤賭的方法選出節(jié)點(diǎn)。水滴在節(jié)點(diǎn)i的位置選擇下一層等高線上節(jié)點(diǎn)j的概率給出如下

(1)

移動(dòng)到新的節(jié)點(diǎn)后，立即更新該段路徑被選次數(shù)、土壤量以及水滴的速度和所攜帶的土壤量。

(2)溫度更新

一次流動(dòng)階段結(jié)束時(shí)，基于此時(shí)水滴的適值差異更新溫度

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

(2)

1.2 蒸發(fā)階段

在蒸發(fā)階段，被蒸發(fā)的水滴的個(gè)數(shù)隨機(jī)生成，用輪盤賭的方法選擇出被蒸發(fā)的水滴。

1.3 凝結(jié)階段

蒸發(fā)后的水滴按如下方式進(jìn)行變異

(3)

1.4 降雨階段

在降雨階段，若達(dá)到最大迭代次數(shù)則輸出最優(yōu)解；否則，重新初始化動(dòng)態(tài)變量與參數(shù)，利用本次迭代得到的最優(yōu)解對(duì)動(dòng)態(tài)參數(shù)進(jìn)行加固處理，以指導(dǎo)下一代尋優(yōu)。參數(shù)加固計(jì)算如下

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

(4)

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

2 改進(jìn)的水文循環(huán)算法

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

2.1 混沌初始化

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

(5)

(6)

2.2 自適應(yīng)溫度更新參數(shù)

HCA在優(yōu)化某些問題時(shí)，一次流動(dòng)階段結(jié)束后的水滴適值相差較大，溫度增長(zhǎng)緩慢，算法在流動(dòng)階段多次循環(huán)，最終導(dǎo)致整個(gè)算法的運(yùn)行時(shí)間過長(zhǎng)。為此，采用自適應(yīng)溫度更新參數(shù)代替原算法中固定的溫度更新參數(shù)，由初始種群的適值來決定溫度的增長(zhǎng)速度，從而降低算法的運(yùn)行時(shí)間。

在種群初始化階段結(jié)束后，評(píng)估水滴種群的適值，根據(jù)最差適值ψmax與最優(yōu)適值ψmin計(jì)算溫度更新參數(shù)

(7)

2.3 逆水流

針對(duì)HCA容易陷入局部最優(yōu)的問題，利用已有的山形圖，設(shè)計(jì)逆水流代替原凝結(jié)階段的變異操作，以提高算法的尋優(yōu)精度。

水滴開始逆流時(shí)，首先從山腳出發(fā)，向高層等高線移動(dòng)。在此過程中，同層等高線上的節(jié)點(diǎn)間彼此連通，水滴在同層等高線上移動(dòng)后，再移向更高層的等高線。對(duì)應(yīng)的逆水流過程如圖1所示。

圖1 逆水流過程

水滴在某一層等高線上移動(dòng)時(shí)，隨機(jī)選擇一個(gè)節(jié)點(diǎn)數(shù)值比原節(jié)點(diǎn)數(shù)值小的節(jié)點(diǎn)，然后評(píng)估該節(jié)點(diǎn)。若對(duì)應(yīng)的水滴適值優(yōu)于原節(jié)點(diǎn)，則替換掉原節(jié)點(diǎn)，并繼續(xù)隨機(jī)選擇一個(gè)數(shù)值更小的節(jié)點(diǎn)，直至選擇數(shù)值更小的次數(shù)達(dá)到上限。

若所選節(jié)點(diǎn)對(duì)應(yīng)的水滴適值更差，或原節(jié)點(diǎn)的數(shù)值已是最小，或選擇數(shù)值更小的次數(shù)已達(dá)上限，則在該層隨機(jī)選擇一個(gè)節(jié)點(diǎn)數(shù)值比原節(jié)點(diǎn)數(shù)值更大的節(jié)點(diǎn)。進(jìn)一步地，評(píng)估該節(jié)點(diǎn)，若適值更優(yōu)則進(jìn)行替換，并繼續(xù)選擇數(shù)值更大的節(jié)點(diǎn)直至次數(shù)達(dá)到上限；若適值更差，或是原節(jié)點(diǎn)的數(shù)值已是最大，則水滴流入上一層等高線。

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

表1 逆流過程

當(dāng)流動(dòng)階段結(jié)束后，每顆水滴生成的解以節(jié)點(diǎn)數(shù)組的形式存儲(chǔ)在水滴中。在逆流過程中，水滴首先改變底層等高線上的節(jié)點(diǎn)，由于底層等高線所占權(quán)重小，此時(shí)可視為局部搜索；當(dāng)水滴逆移動(dòng)到較高層等高線時(shí)，可視為全局搜索。

2.4 改進(jìn)算法的流程圖

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

圖2 溫度自適應(yīng)逆水文循環(huán)算法流程

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)環(huán)境

仿真實(shí)驗(yàn)的運(yùn)行環(huán)境為Intel Core i7 CPU，主頻2.40 GHz，內(nèi)存8 GB，Windows10 64位操作系統(tǒng)，實(shí)驗(yàn)仿真軟件采用MATLAB R2016a。

3.2 測(cè)試函數(shù)與參數(shù)設(shè)置

本文選擇5組多峰基準(zhǔn)測(cè)試函數(shù)f1-f5和5組單峰基準(zhǔn)測(cè)試函數(shù)f6-f10來驗(yàn)證算法性能。表2給出了測(cè)試函數(shù)的定義、搜索空間和理論最優(yōu)解。

表2 測(cè)試函數(shù)

表2(續(xù))

所有對(duì)比算法都統(tǒng)一設(shè)置種群大小為10，最大迭代次數(shù)為500。針對(duì)上述每個(gè)函數(shù)，每種算法均獨(dú)立運(yùn)行30次。對(duì)比算法與參數(shù)設(shè)置見表3、表4。

表3 對(duì)比算法

表4 各算法參數(shù)設(shè)置

3.3 算法尋優(yōu)精度比較

所有測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果見表5、表6。

從表5可以看出，對(duì)于多峰測(cè)試函數(shù)f1-f5：在函數(shù)f1、f4中，IHCA、TIHCA與WOA得到相同的最優(yōu)值；在函數(shù)f2、f3中，IHCA與TIHCA各項(xiàng)指標(biāo)的值非常接近，且均優(yōu)于其它算法；在函數(shù)f5中，IHCA的最差值、平均值、標(biāo)準(zhǔn)差均優(yōu)于其它對(duì)比算法。

表5 多峰函數(shù)尋優(yōu)精度對(duì)比結(jié)果

表5(續(xù))

從表6可以看出，對(duì)于單峰測(cè)試函數(shù)f6-f10：就函數(shù)f6、f7、f10而言，IHCA與TIHCA準(zhǔn)確找到理論最優(yōu)值，且表現(xiàn)穩(wěn)定；在函數(shù)f8中，IHCA與TIHCA得到相同的最優(yōu)值，但I(xiàn)HCA的最差值、平均值、標(biāo)準(zhǔn)差優(yōu)于TIHCA以及其它對(duì)比算法。

表6 單峰函數(shù)尋優(yōu)精度對(duì)比結(jié)果

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

3.4 算法收斂速度比較

各個(gè)算法針對(duì)不同函數(shù)的收斂曲線如圖3-圖12所示。

圖3 函數(shù)f1的收斂曲線

圖4 函數(shù)f2的收斂曲線

圖5 函數(shù)f3的收斂曲線

圖6 函數(shù)f4的收斂曲線

圖7 函數(shù)f5的收斂曲線

圖8 函數(shù)f6的收斂曲線

圖9 函數(shù)f7的收斂曲線

圖10 函數(shù)f8的收斂曲線

圖11 函數(shù)f9的收斂曲線

圖12 函數(shù)f10的收斂曲線

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

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

3.5 算法運(yùn)行時(shí)間比較

對(duì)算法運(yùn)行30次的時(shí)間取平均值，所有對(duì)比算法的運(yùn)行時(shí)間如圖13所示。

圖13 f1-f10運(yùn)行時(shí)間對(duì)比結(jié)果

從圖13可以看出，針對(duì)10個(gè)測(cè)試函數(shù)，PSO、GA與WOA的運(yùn)行時(shí)間均為最短，這是由于HCA本身具有較多且復(fù)雜的參數(shù)與公式，即使改進(jìn)后的算法THCA、IHCA、TIHCA運(yùn)行時(shí)間仍較PSO、GA與WOA更長(zhǎng)。

與HCA相比，THCA在函數(shù)f1-f5、f7-f10上的運(yùn)行時(shí)間更短，IHCA在函數(shù)f3-f5、f9上花費(fèi)更少的時(shí)間，TIHCA在函數(shù)f3-f5、f7-f10上的運(yùn)行時(shí)間更短?？傮w而言，THCA的運(yùn)行時(shí)間最短，這體現(xiàn)了自適應(yīng)溫度更新參數(shù)策略在運(yùn)行時(shí)間上的優(yōu)越性。而TIHCA僅次于THCA，這是由于逆水流過程的引入會(huì)增加一定的計(jì)算量。

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

4 結(jié)束語

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