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

肖文顯， 王俊閣， 馬孝琴

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

?

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

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

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

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

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

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

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

1 和聲蛙跳算法

1.1 基本和聲搜索算法

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

(1)

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

(2)

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

(3)

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

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

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

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

(4)

(5)

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

圖1 互補(bǔ)搜索機(jī)制Fig.1 Complementary search mechanism

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

ψ=n-1,

(6)

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

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

HMCR=HMCR0+ψ/50,

(7)

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

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

1.3 和聲蛙跳算法的實(shí)施步驟

Step2： ψ←ψ+1；

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

Step4： 動(dòng)態(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)個(gè)體是否變化，若無(wú)變化，則返回Step2，若有變化，則令ψ=0并返回Step2.

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

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

2 算例

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

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

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

1)Sphere函數(shù)：

(8)

2)Rosenbrock函數(shù)：

(9)

3)Rastrigrin函數(shù)：

(10)

4)Griewank函數(shù)：

(11)

5)Ackley函數(shù)：

(12)

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

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

表1 結(jié)果對(duì)比

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

2.2 車(chē)輛路徑問(wèn)題

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

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

表2 分庫(kù)需求及各庫(kù)之間距離

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

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

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

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

3 結(jié)論

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

[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] 高立群， 依玉峰， 鄭 平. 和聲搜索算法在求解最短路徑問(wèn)題中的應(yīng)用[J].東北大學(xué)學(xué)報(bào)(自然科學(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].計(jì)算機(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.

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

1000-1190(2016)02-0211-05

TP301.6

A

*E-mail: xwenx@yeah.net.