肖文顯， 王俊閣， 馬孝琴

(河南科技學院 網(wǎng)絡中心， 河南 新鄉(xiāng) 453003)

?

和聲蛙跳算法在復雜優(yōu)化問題中的應用研究

肖文顯*， 王俊閣， 馬孝琴

(河南科技學院 網(wǎng)絡中心， 河南 新鄉(xiāng) 453003)

和聲搜索算法在求解復雜優(yōu)化問題時，僅僅通過隨機的方式產(chǎn)生新元素，搜索過程中新個體的有效性難以持續(xù)保證，影響算法的優(yōu)化性能.針對該問題，將混合蛙跳算法的族群內部局部尋優(yōu)模塊嵌入和聲搜索的算法框架中，將和聲搜索算法的隨機性與混合蛙跳算法的導向性相耦合.定義算法自適應調整參數(shù)并以此為基礎對兩種算法進行動態(tài)調用，從而實現(xiàn)兩種算法的耦合動態(tài)搜索.將改進算法應用于標準測試函數(shù)和車輛路徑問題的優(yōu)化，模擬計算結果表明：本文提出的改進算法具有更強的全局搜索能力，得到的解更優(yōu)，適合用于求解復雜優(yōu)化問題.

優(yōu)化問題； 和聲搜索算法； 混合蛙跳算法； 耦合搜索； 動態(tài)平衡

和聲搜索算法[1](Harmony Search，HS)是由Geem于2001年根據(jù)音樂家通過調整聲調獲得和聲的原理提出的啟發(fā)式搜索算法.HS算法具有參數(shù)少、收斂快等特點，被廣泛應用于各種優(yōu)化問題[2-4].但是，由于和聲搜索算法的尋優(yōu)過程是以隨機的方式產(chǎn)生新元素，因此在求解復雜優(yōu)化問題時，算法進化后期難以保障新元素的有效性，降低了算法的尋優(yōu)性能，容易導致算法記憶庫難以更新甚至早熟收斂.

針對該問題，本文借鑒混合蛙跳算法[5-6](Shuffled Frog Leaping Algorithm，SFLA)的族群內部局部尋優(yōu)思想，將族群內部尋優(yōu)模塊作為一個子部分嵌入和聲搜索算法當中，利用混合蛙跳算法的族群導向性搜索彌補和聲搜索算法單純隨機性的缺陷.同時，定義算法自適應調整參數(shù)，并以該參數(shù)動態(tài)調用兩算法，從而實現(xiàn)搜索機制的動態(tài)調整.

1 和聲蛙跳算法

1.1 基本和聲搜索算法

和聲搜索算法是一種模仿音樂家創(chuàng)作樂曲過程的隨機搜索算法，主要有記憶選擇、局部調整、隨機生成3種進化操作.和聲搜索算法的主要參數(shù)包括：記憶庫規(guī)模NP、問題維度D、記憶選擇概率HMCR、局部調整概率PAR、調整步長BW等.

(1)

其中，xmax，j和xmin，j分別為待求解問題第j維的取值上限和下限；rand()為0～1之間隨機分布的隨機數(shù)；i=1，2，…，NP；j=1，2，…，D.

(2)

通過記憶選擇產(chǎn)生的中間試驗記憶庫再以局部調整概率PAR進行局部調整，如式(3)所示：

(3)

1.2 算法的改進策略

和聲搜索算法的尋優(yōu)過程是以隨機的方式產(chǎn)生新元素，這種尋優(yōu)搜索模式無法保證算法在進化后期產(chǎn)生新元素的有效性，容易導致算法早熟收斂.為克服和聲搜索算法這一缺陷，本文從算法的搜索機制和調整機制兩個方面對算法進行改進.

1.2 .1互補搜索機制 本文將混合蛙跳算法嵌入和聲搜索算法之中，利用混合蛙跳算法具有導向性的搜索特性，彌補和聲搜索算法的不足，從而實現(xiàn)隨機性和導向性之間的互補和平衡.

互補搜索的核心思想是將和聲搜索算法和混合蛙跳算法相結合，即當隨機因子小于選擇概率HMCR時，算法進入和聲搜索算法框架，從原記憶庫中隨機選擇現(xiàn)有音樂記憶；當隨機因子大于選擇概率HMCR時，算法進入混合蛙跳算法框架，將原種群按照個體適應值優(yōu)劣進行排序并順次分配進入不同的族群，按式(4)、(5)在每個族群內部進行局部尋優(yōu)：

(4)

(5)

互補搜索機制如圖1所示.其中，R1、R2為0～1之間的隨機數(shù).

圖1 互補搜索機制Fig.1 Complementary search mechanism

1.2.2自適應調整機制 上述互補搜索是基于記憶選擇概率HMCR進行調整的.但是，固定的概率導致無法充分利用兩種算法之間的互補性.為進一步促進隨機搜索和導向性搜索之間的平衡，使算法在不同進化階段有不同的搜索側重，這里首先定義算法進化停滯系數(shù)ψ來衡量算法的進化能力，如式(6)所示.

ψ=n-1,

(6)

式中，n為種群最優(yōu)個體的適應值連續(xù)不變的代數(shù)，即若連續(xù)n代最優(yōu)個體的適應值f1=f2=…=fn，則種群停滯系數(shù)就等于n-1.

以算法停滯系數(shù)為參數(shù)對記憶選擇概率HMCR進行動態(tài)控制，從而根據(jù)需要動態(tài)調用和聲搜索和混合蛙跳兩種算法.修改后的記憶選擇概率HMCR計算方式如式(7)所示.

HMCR=HMCR0+ψ/50,

(7)

式中，HMCR0為初始記憶選擇概率.

算法進化前期，算法停滯系數(shù)ψ為0或者較小，則HMCR相對較小，算法能以更大的概率進行混合蛙跳搜索.當算法出現(xiàn)進化困難趨于停滯時，算法停滯系數(shù)變大，則HMCR相對變大，算法能以較大概率進行和聲搜索.即算法進化能力較強種群多樣性較優(yōu)時，通過調小HMCR促使算法側重有導向性的尋優(yōu)，更有利于種群個體向最優(yōu)解收斂.當算法種群多樣性變差進化能力下降時，通過調大HMCR促使算法側重隨機性搜索，更有利于拓展搜索空間，跳出局部最優(yōu).

1.3 和聲蛙跳算法的實施步驟

Step2： ψ←ψ+1；

Step3： 按式(7)計算記憶選擇概率HMCR；

Step4： 動態(tài)調整算法進化的側重，若rand()

Step5： 循環(huán)次iter←iter+1；

Step6： 判斷算法是否達到最大迭代次數(shù)itermax，若達到，則算法停止，輸出結果，否則繼續(xù)執(zhí)行Step7；

Step7： 判斷種群最優(yōu)個體是否變化，若無變化，則返回Step2，若有變化，則令ψ=0并返回Step2.

和聲蛙跳算法的框架如圖2所示.

圖2 和聲蛙跳算法流程圖Fig.2 Chart of harmony shuffled frog leaping algorithm

2 算例

為驗證本文提出的和聲蛙跳算法的優(yōu)化性能，將改進算法應分別用于標準測試函數(shù)的優(yōu)化問題和車輛路徑問題.

2.1 標準測試函數(shù)

本文采用式(8)～(12)等5個標準測試函數(shù)，如下所示：

1)Sphere函數(shù)：

(8)

2)Rosenbrock函數(shù)：

(9)

3)Rastrigrin函數(shù)：

(10)

4)Griewank函數(shù)：

(11)

5)Ackley函數(shù)：

(12)

分別采用和聲搜索算法、混合蛙跳算法、和聲蛙跳算法對上述5個標準測試函數(shù)進行優(yōu)化計算.算法參數(shù)設置如下：種群容量NP=200，族群個數(shù)m=5、初始記憶選擇概率HMCR0=0.35、局部調整概率PAR=0.6、調整步長BW=0.01、最大循環(huán)次數(shù)itermax=1000；

采用上述3種算法對5個標準測試函數(shù)分別進行50次計算，取其平均結果進行對比，求解結果如表1所示.

表1 結果對比

對比表1中3種算法的優(yōu)化結果可見，HS和SFLA兩種算法的計算結果相差不大，改進后的算法無論是平均值還是最優(yōu)值均優(yōu)于前兩種算法.對比不同算法優(yōu)化結果的標準差可見，改進算法的優(yōu)化結果浮動幅度小于HS和SFLA.由此可見，改進算法融合了HS和SFLA的優(yōu)點，具有更強的全局優(yōu)化能力，能夠得到更優(yōu)的優(yōu)化結果.

2.2 車輛路徑問題

車輛路徑問題(Vehicle Routing Problem，VRP)是在滿足車輛最大負載和客戶需求的前提下，優(yōu)化車輛的行駛路徑使得運輸成本最低、時間最短等目標得以實現(xiàn).VRP問題的相關概念和數(shù)學模型可參考文獻[7]，本文在此不再贅述.

假定有8個分庫和1個總庫，總庫有2輛車輛用于配送貨物，每輛車的最大容量均為8t.要求合理安排車輛的配送路線，使得總的運輸距離最短.各分庫對總庫的貨物需求量以及各庫之間的距離如表1所示(其中0表示總庫).

表2 分庫需求及各庫之間距離

按2.1節(jié)相同的參數(shù)設置，分別采用HS、SFLA、改進算法對上述車輛路徑問題進行20次優(yōu)化，取各算法優(yōu)化結果的平均值作對比，優(yōu)化結果如表3所示.

表3 優(yōu)化結果對比

對比3種算法求解上述VRP問題的計算結果可見，改進后的和聲蛙跳算法的計算結果在多次求解的平均值、最優(yōu)值和標準差3個方面均優(yōu)于HS和SFLA.3種算法20次優(yōu)化結果的分布如圖3所示.結合表3中標準差的對比可知，和聲蛙跳算法在求解車輛路徑問題優(yōu)化方面比HS和SFLA更具全局尋優(yōu)能力，可以避免算法陷入局部最優(yōu)解.

圖3 優(yōu)化結果分布情況Fig.3 Distribution of optimal results

3 結論

本文針對和聲搜索算法進化中隨機生成新元素難以保證產(chǎn)生有效個體的問題，將混合蛙跳算法作為子模塊嵌入和聲搜索算法中，并以算法停滯系數(shù)為控制參數(shù)動態(tài)調整兩種算法的側重，從而將隨機搜索與導向性搜索結合，達到全局搜素與局部尋優(yōu)的平衡.將改進算法應用于標準測試函數(shù)和車輛路徑問題的優(yōu)化，模擬計算結果表明：本文提出的改進算法具有更強的全局搜索能力，得到的解更優(yōu)，適合用于求解復雜優(yōu)化問題.

[1] ZONG W G， JOONG H K， LOGANATHAN G V. A new heuristic optimization algorithm: harmony search[J]. Simulation， 2001， 76(2):60-68．

[2] LEE K S， GEEM Z W. A new structural optimization method based on the harmony search algorithm[J]. Computers & Structures， 2004， 82(9):781-798．

[3] 高立群， 依玉峰， 鄭 平. 和聲搜索算法在求解最短路徑問題中的應用[J].東北大學學報(自然科學版)， 2011， 32(6)：769-772.

[4] 王 蕊， 夏 軍， 張文華. 和聲搜索算法在非線性馬斯京根模型參數(shù)率定中的應用[J].水電能源科學， 2008， 26(4)：36-39．

[5] EUSUFF M M， LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. Journal of Water Resources Planning and Management， 2003， 129(3)：210-225．

[6] 李英海， 周建中， 楊俊杰. 一種基于閾值選擇策略的改進混合蛙跳算法[J].計算機工程與應用， 2007， 43(35)：19-21．

[7] LENSTRA J K， RINNOOY K. Complexity of vehicle routing and scheduling problems[J]. Networks， 1981， 11(2)：221-227．

Harmony frog leaping algorithm and its application to complex optimization problems

XIAO Wenxian， WANG Junge， MA Xiaoqin

(Henan Institute of Science and Technology， Xinxiang, Henan 453003)

When harmony search algorithm is used in solving complex optimization problems, it creates new elements via a random manner. This evolutionary strategy will affect the performance of the algorithm because the search process is difficult to ensure an effective individual. In response to these problems, shuffled frog leaping algorithm will be embedded in harmony search algorithm as a sub-part. The randomness of harmony search and the guidance of shuffled frog leaping algorithm are coupled. Adaptive factor is defined in this paper, and algorithms are invocated dynamically based on the factor so as to realize the coupling dynamic search. The improved algorithm is applied to the standard test functions and the optimization of VRP, the simulation results show that the improved algorithm has better global searching ability. Meanwhile it gets better solution and is suitable for solving complex optimization problems.

optimization problems； harmony search algorithm； shuffled frog leaping algorithm； coupling search； dynamic balance

2015-03-02.

國家自然科學基金項目(71171151)；河南省教育廳自然科學研究計劃項目(13B520011).

1000-1190(2016)02-0211-05

TP301.6

A

*E-mail: xwenx@yeah.net.