基于和聲退火算法的多維函數優化

摘 要:在研究和聲搜索對多維函數優化問題的基礎上，結合傳統的模擬退火算法，提出一種混合優化算法——和聲退火算法。該算法改進了和聲的搜索機制，選取合理的取值概率HMCR以及動態的微調概率PAR，在和聲記憶庫內隨機搜索，獲得較高質量的新和聲;然后對新和聲執行一次Metropolis算法，從而增強了全局探索能力，減小了陷入局部極小值的機會。仿真實驗數據表明，算法明顯優于和聲搜索和模擬退火算法，具有較高的求解質量和效率。

關鍵詞:和聲搜索;模擬退火;和聲退火;函數優化

中圖分類號:TP18 文獻標志碼:A

文章編號:1001-3695(2010)03-0853-03

doi:10.3969/j.issn.1001-3695.2010.03.012

Multi-dimensional function optimization based on global-best harmony annealing algorithm

ZHANG Feng-rong1，PAN Quan-ke1，PANG Rong-bo2，LI Huan1

(1.School of Computer Science， Liaocheng University， Liaocheng Shandong 252059， China;2.College of Dongchang， Liaocheng University， Liaocheng Shandong 252000， China)

Abstract:This paper put forward a kind of hybrid optimization algorithm:harmony annealing algorithm，which was based on harmony search and simulated annealing algorithm for multidimensional function optimization problem. Improved the algorithm the search mechanism of HS，selected the reasonable values about harmony memory considering rate(HMCR) and dynamic pitch adjusting rate(PAR). Searched the new vector randomly in the HM， then executed a Metropolis algorithm. It could improve the efficiency of the exploration and reduce the probability of trapped by local minimum value. The simulation results demonstrate the effectiveness and good quality of the proposed procedure，and better than those of harmony search and simulated annealing algorithm.

Key words:harmony search(HS); simulated annealing(SA); global harmony annealing; function optimization

和聲搜索(HS)算法是Geem等人[1]通過類比音樂和最優化問題的相似性而提出的一種現代啟發式智能進化算法。目前，該方法已在多維多極值函數優化、管道優化設計[2~4]、土坡穩定分析[5]等問題中得到了廣泛應用。有關研究表明，HS算法在解決多維函數優化問題上展示了較遺傳算法[6]、模擬退火算法[7]等更好的優化性能。最近，Mahdavi等人[8]對HS的參數進行了改進，引入動態的微調概率和音調調節率，提出了改進和聲搜索算法(improved harmony search algorithm，IHS)。 Omran等人[9]改進了和聲的搜索機制，提出了全局和聲搜索(global-best harmony search，GHS)算法，實驗結果表明該算法明顯優于基本HS。

模擬退火(SA)算法是一種概率性的全局優化算法，該算法雖然在理論上能收斂到全局最優解，但計算時間長，收斂速度慢。文獻[10，11]探討的混合優化算法為各種優化問題提供了新的思路和手段。本文針對函數優化問題，提出一種新的HS與SA相結合的混合算法，即和聲退火算法(global-best harmony annealing，GHAA)。仿真結果表明，該算法在解決多維函數優化時具有良好的求解性能及較強的跳出局部極小的能力。

1 和聲搜索算法

和聲搜索是一種新的啟發式優化算法。算法模擬了音樂創作中樂師們憑借自己的記憶，通過反復調整樂隊中各樂器的音調，最終達到一個美妙的和聲狀態的過程。將樂器聲調的和聲Ri(i=1，2，…，M)類比于優化問題的第i個解向量，評價即是各對應的目標函數值。算法引入兩個主要參數，即記憶庫取值概率(harmony memory considering rate，HMCR)和微調概率(pitch adjusting rate，PAR)。算法首先產生HMS(harmony memory size)個初始解(和聲)放入和聲記憶庫HM(harmony memory)內;然后，在和聲記憶庫內隨機搜索新解，新解的產生由HMCR決定，即隨機產生0~1的隨機數r。如果r

2 和聲退火算法

基于和聲的全局搜索以及模擬退火的局部優化的特點，可將和聲退火算法分成兩個步驟:a)先利用HS的搜索機制在和聲記憶庫內隨機搜索，得到一個較優的群體;b)運用SA的局部突跳能力對該群體進行優化。該算法改進了和聲的參數選擇，運用合理的取值概率以及動態的微調概率在和聲庫內搜索最優解，并對其進行N次抽樣以期獲得更高質量的解。以下為算法的各部分描述。

2.1 初始化算法參數

其參數包括和聲庫大小HMS、記憶庫取值概率HMCR、微調概率PAR、初始溫度t。

和聲庫的規模是影響優化結果的一個重要因素，受人類記憶能力在短時間內最優的啟發，和聲庫的規模越小，在解空間中搜索最優解的效率越高。借鑒文獻[9]的相關數據，本文選取HMS=5。

HMCR的大小決定算法的優化性能，對多維函數而言，其值越大，越有利于算法的局部收斂;值越小，越有利于群體的多樣性。根據實驗數據，本文選取HMCR=0.98。

微調概率PAR:在算法搜索初期，較小的PAR參數有利于算法快速地搜尋較好區域，然而在算法搜索的后期，采用較大的PAR有利于算法跳出局部極值，故本文選取動態的PAR∈[0.1，0.5]，其線性變化圖像如圖2所示 。最初PAR參數為最小值，隨著迭代次數的增加，PAR的值逐漸線性增大;當迭代次數t達到23×NI時PAR達到最大值，此后一直保持不變，直到算法結束。

PAR(k)=PARmin+(PARmax-PARmin)×k23NI k≤23NI

PARmaxk>23NI(1)

初始化溫度t:初溫的選取影響獲得高質量解的幾率。溫度越大，求解質量越高，但計算時間增加，因此初溫的確定應折中考慮優化質量和優化效率。初溫設為700。

2.2 初始化和聲庫HM

為了使初始種群具有一定的分散性以及優化結果具有普遍性，初始種群在函數的定義域內均勻產生如下:

xi(j)=LBi+r×(UBi-LBi)(2)

其中:xi(j)為庫中第i維的變量;r為(0，1)的隨機數;xi(j)∈[LBi，UBi]。和聲庫結構如下:

HM=x1x2xHMS=x1(1)x1(2)…x1(n)x2(1)x2(2)…x2(n)



xHMS(1)xHMS(2)…xHMS(n)(3)

2.3 新解向量的產生

與基本和聲搜索產生新解的機制不同，GHAA采用GHS的產生機制:在取值概率HMCR的影響下，生成隨機數r1∈(0，1)，若r1

for(i=1 to n) do

if rand(0，1)

begin

x′i=xji//在和聲庫中隨機選取

if rand(0，1)

begin

x′i=xbestj//j為和聲庫中最優值隨機解向量

end if

else

x′i=LBi+r×(UBi-LBi)

//向量在變量允許的范圍內隨機選取

end if

end for

2.4 對新解執行一次Metropolis算法

在當前溫度t下，對產生的新解進行多次抽樣搜索最優解，狀態產生函數決定了算法在解空間中的移動方式和優化質量。本文采用的狀態產生函數為

x′=x+η×v(4)

其中:η為尺度參數;ν為隨機撓動。本文采用均勻分布對算法進行仿真研究。

尺度參數η:尺度參數大，則算法產生大步長移動的概率加大，有利于大范圍內的粗搜索，并克服局部極小;反之，尺度參數小，則算法產生局部小撓動的概率加大，有利于進行局部鄰域趨化性細搜索。故本文選取動態η，其線性變化圖像如圖3所示。最初η參數為最大值，隨著迭代次數的增加，η的值逐漸線性減小，當迭代次數k達到23×NI時，η達到最小值。此后一直保持不變，直到算法結束。

η(k)=ηmax-(ηmax-ηmin)×k23NI k≤23NI

ηmink>23NI(5)

狀態接受概率:在較高的溫度下算法產生概率突跳的本質，本文選取:

p(si→si+1)=exp(-Δ/t) Δ>0

1Δ≤0(6)

其中:Δ為新舊狀態的目標值差;t是當前溫度。

2.5 溫度更新

為提高優化效率，采用指數降溫方式。其中退溫速率λ=0.99。

tk+1=λtk，0<λ<1(7)

2.6 判斷算法是否收斂

為了兼顧算法的搜索性能和時間性能，采用溫度閾值法使算法終止，若滿足收斂條件，則算法終止并輸出最優值;否則執行2.3節。算法流程如圖4所示。

3 數值仿真與分析

3.1 算法性能測試函數

算法性能的比較，一般基于一些Benchmark問題展開。本文采用的Benchmark函數如下:

a)Sphere function

f(x)=Ndi=1x2i(8)

最優解為x*=0， f(x*)=0，|xi|≤100。

b)Schwefel’s problem 2.22

f(x)=Ni=1|xi|+Ni=1|xi|(9)

最優解為x*=0，f(x*)=0，|xi|≤10。

c)Step function

f(x)=∑Ndi=1(xi+0.5」)2(10)

最優解為x*=0，f(x*)=0，|xi|≤100。

d)Rosenbrock function

f(x)=∑Ndi=1(100(xi-x2i-1)2)+(xi-1-1)2

(11)

最優解為x*=0，f(x*)=0，|xi|≤30。

e)Generalized Swefel’s problem 2.26

f(x)=-∑Ndi=1(xi sin(|xi|))(12)

最優解為x*=(420.9687，420.9687，…，420.9687)，f(x*)=-12569.5，|xi|≤500。

f)Ackley’s function

f(x)=-20 exp(-0.2130∑Ni=1x2i)-exp(130∑Ni=1cos(2πxi))+20+e(13)

最優解為x*=0，f(x*)=0，|xi|≤32。

g)Griewank function

f(x)=14000∑Ndi=1x2i-∏Ndi=1cos(xii)+1(14)

最優解為x*=0，f(x*)=0，|xi|≤600。

h)Rastrigin function

f(x)=∑Ndi=1(x2i-10cos(2∏xi)+10)(15)

最優解為x*=0，f(x*=0)，|xi|≤5.12。

3.2 算法性能分析

為了考察GHAA算法的優化性能，以VC++6.0為仿真環境，采用處理器為AMD 4200+2.21 GHz、內存為1 GB的PC機，對每一個測試函數進行30次仿真，所有的函數都是30維的。表1給出了算法HS、GHS、SA、GHAA所得的均值與均方差，以及GHAA與其他三種算法的T測試結果。圖5(a)~(h)描述了優化過程中被求解函數的調用次數(迭代次數)與相應的優化值之間的變化關系。圖中所取25個點為各種算法在執行中每迭代2 000次的優化值，除step和generalized函數外，縱坐標均采用優化值的對數，橫坐標為迭代次數。最大調用次數為50 000次。

由表1和圖5可以看出:

a)GHAA有六個函數的均值明顯優于HS，其余兩個函數GHAA均達到了函數的最優值。從進化曲線上看，HS進化緩慢，并較早地陷入局部極小。b)GHAA有五個函數的均值明顯優于GHS，對函數3和5，兩種算法均達到了最優值。從進化曲線上看，在搜索前期，GHS的進化速度和效率明顯優于GHAA算法，但隨著迭代的不斷增加，GHS較早地陷入局部極小。

 c)GHAA有六個函數的均值明顯優于SA，對函數3，兩種算法均達到了最優值。 從進化曲線上看，SA算法收斂的速度很慢，并且優化效果不好。

 d)比較以上實驗結果可知，GHAA的優化性能和效率明顯優于其他三種算法，收斂速度雖不及和聲搜索算法，但其進化穩定，跳出局部極小的能力增強。

4 結束語

本文將和聲搜索與模擬退火算法相結合，提出了和聲退火優化算法。為提高算法的優化性能，運用了動態微調概率PAR以及尺度參數η，并給出了合理的分段標準。由仿真數據和圖5表明，該算法具有較高的求解質量、穩定的優化速度和較強的跳出局部極小的能力。

參考文獻:

[1]GEEM Z W， KIMJ H， LOGANA T G V. A new heurstic optimization algorithm: harmony search[J]. Simulation， 2001，76(2):60-68.

[2]GEEM Z W. Optimal cost design of water distribution networks using harmony search[J]. Eng Optimiz， 2006，38(3):259-280.

[3]GEEM Z W， KIMJ H， LOGANA T G V. Harmony search optimization: application to pipe network design[J].International Journal of Model Simulation， 2002，22(2):125-133.

[4]LEE K S， GEEM Z W. A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice[J]. Computer and Methods in Applied Mechanics and Engineering， 2005，194(36-38):3902-3933.

[5]李亮，遲世春. 新型和聲搜索算法在土坡穩定分析中的應用[J]. 水利與建筑工程學報，2007，5(3):1-6.

[6]玄光男，程潤偉.遺傳算法與工程優化[M].北京:清華大學出版社，2004.

[7]王凌.智能優化算法及其應用[M].北京:清華大學出版社，2001.

[8]MAHDAVI M， FESANGHARY M， DAMANGIR E. An improved harmony search algorithm for solving optimization problems[J]. Applied Mathematics and Computation， 2007，188(2):1567-1579.

[9]OMRAN M G H， MAHDAVI M. Global-best harmony search[J]. Applied Mathematics and Computation， 2008，198(2):643-656.

[10]潘全科，王文宏，朱劍英. 一類解決車間調度問題的遺傳退火算法[J].機械科學與技術 ，2006，25(3):317-321.

[11]潘全科，朱劍英. 基于進化算法和模擬退火的混合調度算法[J].機械工程學報， 2005，41(6):224-227.