肖文顯， 王俊閣， 馬孝琴

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

?

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

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

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

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

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

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

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

1 和聲蛙跳算法

1.1 基本和聲搜索算法

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

(1)

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

(2)

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

(3)

1.2 算法的改進(jìn)策略

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

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

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

(4)

(5)

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

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

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

ψ=n-1,

(6)

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

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

HMCR=HMCR0+ψ/50,

(7)

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

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

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

Step2： ψ←ψ+1；

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

Step4： 動態(tài)調(diào)整算法進(jìn)化的側(cè)重，若rand()

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

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

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

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

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

2 算例

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

2.1 標(biāo)準(zhǔn)測試函數(shù)

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

1)Sphere函數(shù)：

(8)

2)Rosenbrock函數(shù)：

(9)

3)Rastrigrin函數(shù)：

(10)

4)Griewank函數(shù)：

(11)

5)Ackley函數(shù)：

(12)

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

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

表1 結(jié)果對比

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

2.2 車輛路徑問題

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

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

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

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

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

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

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

3 結(jié)論

本文針對和聲搜索算法進(jìn)化中隨機生成新元素難以保證產(chǎn)生有效個體的問題，將混合蛙跳算法作為子模塊嵌入和聲搜索算法中，并以算法停滯系數(shù)為控制參數(shù)動態(tài)調(diào)整兩種算法的側(cè)重，從而將隨機搜索與導(dǎo)向性搜索結(jié)合，達(dá)到全局搜素與局部尋優(yōu)的平衡.將改進(jìn)算法應(yīng)用于標(biāo)準(zhǔn)測試函數(shù)和車輛路徑問題的優(yōu)化，模擬計算結(jié)果表明：本文提出的改進(jìn)算法具有更強的全局搜索能力，得到的解更優(yōu)，適合用于求解復(fù)雜優(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] 高立群， 依玉峰， 鄭 平. 和聲搜索算法在求解最短路徑問題中的應(yīng)用[J].東北大學(xué)學(xué)報(自然科學(xué)版)， 2011， 32(6)：769-772.

[4] 王 蕊， 夏 軍， 張文華. 和聲搜索算法在非線性馬斯京根模型參數(shù)率定中的應(yīng)用[J].水電能源科學(xué)， 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ìn)混合蛙跳算法[J].計算機工程與應(yīng)用， 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.

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

1000-1190(2016)02-0211-05

TP301.6

A

*E-mail: xwenx@yeah.net.