一種自適應參數調整的水波優(yōu)化算法

杜兆宏，夏培淞， 邱飛岳，朱會杰

(浙江工業(yè)大學 教育科學與技術學院，杭州 310023) E-mail：476876541@qq.com

1 引 言

為了尋求解決工程優(yōu)化問題更好的方法，國內外許多學者從自然、物理和社會等現象中受到啟發(fā)，相繼提出了如粒子群優(yōu)化算法[1]、蟻群優(yōu)化算法[2]、蝙蝠算法[3]、布谷鳥算法[4]等眾多群體智能啟發(fā)式算法.相較傳統(tǒng)算法而言，由于群體智能啟發(fā)式算法在解決優(yōu)化問題時采用了特有的全局和局部搜索機制，所以其性能更為優(yōu)越.近年來，群體智能算法得到了人們極大的關注，許多研究者已將其應用到生產調度、組合優(yōu)化等許多領域中.例如，學者Rahmani M等[5]把蝙蝠算法應用到機器人自適應控制中，研究表明利用蝙蝠算法對機器人進行控制具有較好的性能；Mirjalili S[6]已將蜻蜓算法應用到潛艇螺旋槳優(yōu)化中，結果表明蜻蜓算法在潛艇螺旋槳優(yōu)化方面具有很好的效果；Liao W等[7]將人工螢火蟲算法應用到無線傳感器部署中，研究表明基于人工螢火蟲算法的無線傳感器部署具有較好的魯棒性.

水波優(yōu)化算法(Water Wave Optimization，WWO)是由國內學者鄭宇軍[8]于2015年所提出的一種新興群體智能啟發(fā)式算法，該算法通過模擬淺水波運動的方式，在高維空間進行高效的搜索尋優(yōu).WWO具有控制參數少、種群規(guī)模小、實現簡單和計算開銷量小等優(yōu)點.目前，WWO已在TSP求解[9]和高鐵調度[8]等優(yōu)化問題中得到了應用，并且取得了較好的效果.

WWO自提出以來，由于其在求解優(yōu)化問題中不俗的表現而得到許多研究人員的關注.張蓓等[10]最初從執(zhí)行傳播和折射操作兩方面對水波優(yōu)化算法的收斂性條件進行了分析，并用具體實驗驗證了兩種收斂條件的正確性.Zheng接著又提出了一種種群規(guī)?？勺兊乃▋?yōu)化算法[11]，在這種改進的水波優(yōu)化算法中，在折射操作中引入了學習機制，從而更好地提升了算法的性能.之后，鄭宇軍等[12]在對軟件形式化開發(fā)關鍵部位選取問題研究中，通過建立該問題的0-1規(guī)劃約束模型，并設計了離散水波優(yōu)化算法來對大型軟件系統(tǒng)應用的實例，研究結果表明，離散水波優(yōu)化算法解決該問題是可行的，并且其優(yōu)化效果明顯要優(yōu)于BPSO、IBPSO、GA和BDE等算法.

盡管水波優(yōu)化算法在許多優(yōu)化問題上表現出優(yōu)越的性能，但由于其還處于發(fā)展階段，所以仍然還存在一些不足.正如文獻[8]所述，水波算法在理論分析和性能方面還有很大改進的空間，比如其收斂速度較慢、收斂精度較低等不足.

為了進一步提升水波優(yōu)化算法的性能，已有研究者從不同視角提出了一些有效改進水波優(yōu)化算法的策略.例如，張杰峰等[13]提出了另一種種群規(guī)?？勺兊乃▋?yōu)化算法，在該改進的水波算法中，通過將原水波算法固定種群規(guī)模改為線性遞減的種群規(guī)模，使算法在早期更好地支持全局搜索，并在后期更多的支持局部搜索開發(fā)，這種改進策略在一定程度上提升了算法的性能.吳秀麗等[14]針對水波優(yōu)化算法在局部搜索方面存在的局限，提出了將局部搜索能力較強的單純形法融入到水波算法中，同時在種群初始化中采用混沌種群初始化，在迭代過程中對種群進行混沌擾動等一系列策略來改進水波算法，從而有效提升了水波優(yōu)化算法的收斂速度和搜索精度.

本文對水波優(yōu)化算法搜索過程中各個階段控制參數變化進行分析的基礎上，提出了一種自適應參數調整的水波優(yōu)化算法(LOGWWO)，即在算法執(zhí)行前期以較大的參數來支持算法進行全局搜索尋優(yōu)，在算法執(zhí)行后期則以較小的參數變化以支持算法進行局部精細化探索開發(fā)，更好的平衡算法的搜索機制，從而進一步提升算法的整體性能.

2 水波優(yōu)化算法概述

2.1 基本原理

水波優(yōu)化算法(Water Wave Optimization，WWO)是從淺水波運動模型解決優(yōu)化問題中得到啟發(fā)發(fā)展而來的一種群體智能啟發(fā)式算法.在對優(yōu)化問題進行求解時，WWO將要優(yōu)化問題的搜索空間看作海床，其中每個解在水波優(yōu)化算法中看作一個“水波”對象，每一個水波都具有一個波高h和波長λ，每個水波的適應度值與其距海床的垂直距離成反比.因此，水波如果離海床的距離越近，其適應度值也就越大，對應的水波的能量也越高，波高h越大，波長λ則越小(如圖1所示)，這樣就使得算法能夠在全局和局部搜索較優(yōu)解和較差解，從而不斷使水波朝著更優(yōu)的解靠近，從而保證水波算法能夠搜索到最優(yōu)解.WWO是通過執(zhí)行傳播、碎浪和折射等3個操作來對所優(yōu)化的問題進行全局搜索的，在種群初始化時，水波的波高一般設定為hmax，波長一般設為λ=0.5.

圖1 深水區(qū)和淺水區(qū)不同波形示意圖Fig.1 Deep and shallow water different waveform diagram

2.2 傳播

水波能量的積聚是由每個水波在運動過程中不斷執(zhí)行傳播操作來完成的.傳播前后的水波分別表示為x、x′，原始水波x是通過公式(1)來執(zhí)行傳播操作產生x′的.

xd=xd+rand(-1,1)*λLd,d=1,2,…n

(1)

式(1)中，rand(-1,1)為[-1，1]之間分布的均勻隨機數，λ表示水波長度；Ld為搜索空間第d維的長度，且d∈D.在執(zhí)行傳播操作過程中，如果Ld超出了所求問題搜索空間的范圍，則將其按公式(2)隨機重新設置為搜索空間中的一個新位置.

Ld=lbd+randO*(ubd-lbd)

(2)

式(2)中，lbd為搜索范圍第d維的下界，ubd為搜索范圍第d維的上界，randO為[0，1]內的隨機數.

執(zhí)行傳播操作并得到x′后，需要判斷f(x)是否大于f(x′)，如果f(x)

每次迭代結束時，水波算法都會按公式(3)更新每個水波x的波長.

λ=λ·a-(f(x)-fmin+ε)/(fmax-fmin+ε)

(3)

式(3)中fmax、fmin分別表示當前水波種群中最大適應度值和最小適應度值，a是波長的衰減系數，ε是為了避免分母為0而設置的一個很小的正數.

2.3 碎浪

隨著水波運動過程中能量不斷的增加，水波的波峰會變得越來越陡峭，當其速度超過水波傳播的速度時會破碎成一連串孤立的水波.當WWO在傳播后搜索到最優(yōu)的解x時，會執(zhí)行碎浪操作來生成一連串的孤立波來擴充水波種群的多樣性.碎浪操作的方式如下：首先隨機選擇k=[1,kmax]，選擇的每一維按公式(4)進行搜索得到一個孤立的波x.

(4)

式(4)中，β表示碎浪系數，如果在執(zhí)行碎浪操作之后k個孤立波的適應度值都小于原水波x，則保留x，否則用種群中孤立波的最優(yōu)解來替代x.

2.4 折射

水波在經過若干次傳播操作后仍然沒有得到改善的情況下，為了模擬其在這一過程中能量的消耗，每次傳播過后都會對波高進行減1操作，當波高減為h=0時，為了避免算法搜索的停滯，水波算法會按公式(5)對其進行折射操作：

(5)

式(5)中，x*表示當前種群中的最優(yōu)值，N(μ,σ)均值為μ，標準差為σ的高斯隨機數.

折射操作結束之后，其波高重置為h=hmax，并且對水波的波長按公式(6)進行更新：

λ=λf(x)/f(x′)

(6)

3 自適應參數調整的水波優(yōu)化算法

3.1 自適應碎浪系數調整策略

在WWO中，碎浪系數β是用來控制在找到的最優(yōu)水波附近進行密集搜索孤立波范圍的一個重要參數，β越大，則搜索范圍越大，反之，搜索范圍越小.目前，原始水波算法通常采用碎浪系數β隨著迭代次數線性遞減的策略，即在算法執(zhí)行過程中，碎浪系數隨著迭代次數的增加而線性遞減，雖然這種策略在一定程度上有利于算法搜索精度的提高.但碎浪系數的初始值、最終值和迭代次數一定的情況下，碎浪系數的變化幅度是固定的.因而碎浪系數線性遞減策略無法滿足算法在前期和后期兩個不同時段搜索尋優(yōu)的需要，無法很好的平衡算法全局和局部探索開發(fā)，不利于算法搜索精度的提高.

與原始WWO碎浪系數線性遞減策略不同，本文提出的改進水波優(yōu)化算法的碎浪系數采用對數遞減策略，即在WWO執(zhí)行的前期，以較大的碎浪系數支持算法進行全局搜索，從而獲得更加優(yōu)越的水波；而在算法執(zhí)行的后期，則以較小的碎浪系數來支持算法進行局部精細化探索開發(fā).以下為碎浪系數對數遞減公式：

βk=βmax-α(βmax-βmin)×logiterMaxk

(7)

式(7)中，α為對數調整因子，0<α<1稱其為對數壓縮因子，α>1稱其為對數膨脹因子.

圖2 碎浪系數遞減曲線Fig.2 Breaker coefficient decline curve

圖3 不同值碎浪系數遞減曲線Fig.3 Different values of a breaker coefficient decline curve

圖2為對數調整因子α=1，iterMax=200，時碎浪系數β對數遞減和線性遞減的對比曲線.從圖中可以看出，按公式(7)對算法的碎浪系數進行對數遞減策略相較線性遞減策略而言，前期以較大碎浪系數支持算法進行全局搜索取得最優(yōu)水波后，隨著迭代次數的增加，碎浪系數以較快的迅速下降并進入局部探索；而在算法迭代后期，碎浪系數遞減速度逐漸緩慢，這一階段則以較小的碎浪系數支持算法在局部進行精細開發(fā).上述策略更好的平衡了算法的全局和局部探索能力，從而有利于算法整體性能的提升.

圖3為不同對數調整因子下碎浪系數遞減曲線，其中，當0<α<1時，碎浪系數β的最終值大于設定的最小值，此時算法進行精細搜索的范圍相對上移，即在α=1的初期進行精細化的搜素；而當α>1，β終值小于設定的最小值，算法精細搜索的范圍則相對下移，即在α=1時進行相對更加精細的搜索.由此可見，α不同的取值在一定程度上保證了碎浪系數對數遞減策略可以使得算法在不同的搜索空間中進行更好的尋優(yōu)，進一步提高了算法的收斂速度和搜索精度.

綜上所述，α值越小，碎浪系數β遞減的速度就越慢，從而能更好地適應算法在迭代后期進行精細化局部開發(fā)，有利于算法整體性能的提升.

3.2 衰減系數范圍選擇

在WWO中，每次迭代結束后，算法會按公式(3)對每個水波的波長進行更新.由公式(3)可知，如果水波所得的適應度值越高，其波長也就越短，相應的其搜索范圍就越小，反之則搜索范圍越大.由此可知，適應度值較大的水波能更好地進行局部探索，衰減系數a作為水波優(yōu)化算法波長更新中的一個重要參數，其范圍的合理選擇對于算法的整體性能具有重要影響.關于怎樣合理的設置衰減系數a的范圍，文獻[8]研究表明，當衰減系數a的范圍設為[1.001，1.01]時，水波優(yōu)化算法所取得的優(yōu)化效果更好.

LOGWWO具體執(zhí)行步驟如下：

Step1.初始化具有n個水波的種群p，并分別計算每個水波的適應度值f(x)，找到最優(yōu)的水波x*.

Step2.如果沒有滿足終止條件，則轉到Step 3；否則算法結束，并返回.

Step3.對種群中的每個水波x執(zhí)行以下操作：

Step3.1.根據公式(1)進行傳播操作；

Step3.2.得到一個新的水波x′，如果f(x′)>f(x)，轉Step 3.2.1；否則轉Step 3.3.

Step3.2.1.用新的水波x′替代原水波x；

Step3.2.2.如果f(x′)>f(x*)，根據公式(3)執(zhí)行碎浪操作，用x′替代x*.

Step3.3.將水波的h進行減1操作；如果h=0依據公式(5)、(6)對x進行折射操作.

Step3.4.根據公式(3)對所有的水波的波長都進行更新.

Step4.對每個水波的適應度f(x)計算，并對最優(yōu)的水波進行更新，轉Step 2.

4 仿真實驗與結果分析

4.1 測試函數

為了進一步驗證LOGWWO的優(yōu)化效果和穩(wěn)定性，將LOGWWO、蜻蜓算法(Dragonfly Algorithm，DA)、正余弦算法(Sine Cosine Algorithm，SCA)和原始WWO等四種算法在10個標準測試函數上進行求解函數最優(yōu)值的對比實驗.表1列出了實驗中所用到的10個標準測試函數的信息.

4.2 實驗參數設置與實驗環(huán)境

在進行算法仿真實驗時，參數的合理設置至關重要，算法參數的細微變化都會對其整體性能都會產生一定影響.為了使實驗更加公平和客觀，本實驗將LOGWWO、WWO、DA、SCA的種群規(guī)模統(tǒng)一設置為30，各個算法評價次數也都統(tǒng)一設置為1000次；在實驗中，每個算法在每個測試函數上獨立運行30次.各算法的其它參數設置如下：

LOGWWO的波高hmax=12，波長設置為λ=0.5，衰減系數α=1.0026，碎浪系數β最大值設為β=0.25，最小值設為β=0.001.

WWO的波長λ=0.5，波高設置為hmax=12，波長衰減系α=1.0026，碎浪系數最大值設為β=0.25，最小值設為β=0.001[8].

DA的慣性權重最大值設為ω=0.9，最小值設為ω=0.4，常數β=0.5[6].

仿真實驗環(huán)境如下：處理器為Intel(R)Xeorn3.5GHz，內存為8GB，操作系統(tǒng)為Windows10；所采用的仿真軟件為Matlab2012a.

4.3 實驗結果

表2列出了LOGWWO以及WWO、DA、SCA等四種算法在10個標準測試函數上經過30次獨立運行后所得的實驗結果.其中“Max”表示運行30次后所得的函數最大值，“Min”表示尋找到的函數最小值，“Ave”和“Std”分別表示函數經過30次迭代后得到的平均值和標準方差.其中最優(yōu)的平均值(Ave)和標準差(Std)用粗體顯示.

圖4～圖7為LOGWWO、WWO、DA、SCA等四種算法在標準測試函數f1、f3、f5、f7上搜索函數最優(yōu)值過程中隨迭代次數增加的收斂曲線.

表1 標準測試函數f1-f10Table 1 Standard test functions f1-f10

4.4 實驗結果分析

從表2的實驗結果可知，相較其他三種啟發(fā)式算法，基于自適應參數調整的水波優(yōu)化算法(LOGWWO)在所測試的10個標準測試函數上對其性能的測試結果具有相對優(yōu)勢.在f1～f5這5個30維的函數測試中，經過30次獨立運行后，LOGWWO所獲得的函數平均值和標準差在4種算法中都取得了最小值，這充分說明其在函數搜索最優(yōu)值方面表現出較強的性能.

在進行單峰函數f1測試中，經過30次運行后，LOGWWO在平均值和標準差上都要明顯好于DA、SCA和WWO等3種算法，說明LOGWWO具有較高的搜索精度和較好的穩(wěn)定性能.在對于單峰函數f2進行的測試中，LOGWWO同樣也獲得了最優(yōu)的精度值，其獲得的平均值和標準差相較其他3種算法同樣也為最優(yōu).

LOGWWO在處理多峰函數優(yōu)化中同樣也表現出了優(yōu)越的性能，在函數f3測試中，LOGWWO經過30次測試后，相較于其他3種算法，其在函數最小值和平均值兩項指標中均獲得了最優(yōu)值，在4種算法中表現出較為明顯的優(yōu)勢.由圖5可知，LOGWWO在函數f3上尋找最小值過程中具有較快的收斂速度.在多峰函數f4測試中，LOGWWO和WWO在平均值和標準差上相同，但較DA、SCA兩種算法，仍然在30次迭代后在函數平均值、標準方差等指標上具有較為明顯的優(yōu)勢.函數f5是一個多峰、多局部函數，其在搜索全局最優(yōu)解時具有一定困難，但LOGWWO在f5測試上經過30次獨立運行后所獲得的標準方差和平均值相較DA、SCA和WWO等其他三種算法都得到了最優(yōu)值.由此可知，LOGWWO在多峰、多局部函數上的尋優(yōu)能力具有一定優(yōu)勢，同時在函數尋優(yōu)過程中表現出較高的搜索精度和穩(wěn)定性能.

圖4 函數收斂曲線Fig.4 Convergence curve of f1

圖5 函數收斂曲線Fig.5 Convergence curve of f3

圖6 函數收斂曲線Fig.6 Convergence curve of f5

圖7 函數收斂曲線Fig.7 Convergence curve of f7

在f6、f7、f8、f9和f10這5個固定維度多峰函數測試中，相較其他3種算法，LOGWWO也同樣表現不俗.其中函數f6是一個固定維度為2的多峰函數，四種算法在f6上運行30次后，在函數標準方差指標上LOGWWO獲得了最優(yōu)值，在平均值指標上，LOGWWO和WWO獲得了同樣的值，但在平均值和標準差上所得的值比DA、SCA兩種算法優(yōu).其中函數f7、f10都為固定維度為4維的多峰函數，四種算法在這兩個函數上經過30次運行后的結果可以看出，在f7、f10這兩個函數上，WWO的優(yōu)化效果要比LOGWWO略勝一籌，但與SCA、DA兩種算法比起來，LOGWWO仍然具有一定的優(yōu)勢.函數f9是維度為6的多峰函數，在函數f9上對四種算法的性能進行測試，實驗結果顯示，與WWO、DA和SCA等三個算法相比，LOGWWO在30次評價之后所獲得的平均值在四種算法中為最優(yōu)，說明其在收斂精度上要比其它三種算法具有優(yōu)勢；而在標準方差指標上，DA獲得最優(yōu)值，LOGWWO次之.函數f8同樣為固定維度為2的多峰函數，LOGWWO、WWO和SCA這三種算法30次運行的平均值相同，在標準方差方面，SCA獲得最優(yōu)值.以上分析結果印證了NFL(NO Free Lunch)定理，并不存在某一種算法是萬能的，也不存在一種算法在所有問題優(yōu)化上都表現出優(yōu)越的性能這一論斷.

通過以上分析可知，在大部分函數優(yōu)化問題中，改進的自適應參數調整的水波優(yōu)化算法(LOGWWO)的求解精度和穩(wěn)定性方面整體優(yōu)于DA、SCA、WWO等算法.除了在f7和f10兩個函數測試上，WWO要略好于LOGWWO；f9函數測試中，DA在標準差上獲得最優(yōu)，LOGWWO次之.LOGWWO在其他測試函數上尋優(yōu)的標準差都取得了最小值，并且在幾個多極值、多局部多峰函數上，LOGWWO依然尋找到了最優(yōu)的精度值，從而說明LOGWWO具有較好的全局和局部探索尋優(yōu)性能，并且在函數優(yōu)化問題上具有較好的魯棒性.

5 總結與展望

針對水波優(yōu)化算法在求解精度方面表現出的不足，本文在對水波優(yōu)化算法在解決優(yōu)化問題過程中對控制參數變化進行分析的基礎上，提出了一種自適應參數調整的改進策略，即在算法執(zhí)行的前期以較大的碎浪系數支持算法進行全局搜索，以得到較優(yōu)的水波；在算法的后期，則以較小的碎浪系數支持算法進行局部精細化探索.改進的水波優(yōu)化算法通過碎浪系數對數遞減策略更好的平衡了算法的全局和局部搜索，從而在整體上提升了算法的搜索精度和收斂速度.水波優(yōu)化算法作為一種新興的啟發(fā)式群體智能算法，盡管已研究證明其在很多優(yōu)化問題上要比其他幾個新型智能算法優(yōu)越，但其仍然存在一些不足，比如其在局部搜索方面較弱，收斂速度較慢等.所以，如何考慮將其他局部搜索能力強的算法融入到水波優(yōu)化算法中，來全面提升水波優(yōu)化算法的性能的研究將是下一步研究的重點.