周園園，胡賢德，李敬明，沈桂芳

（安徽新華學院 信息工程學院，安徽 合肥 230088）

一種改進的全局和聲搜索算法求解函數(shù)優(yōu)化問題

周園園，胡賢德，李敬明，沈桂芳

（安徽新華學院 信息工程學院，安徽 合肥 230088）

針對和聲搜索算法的早期收斂速度快，后期收斂慢，容易陷入局部最優(yōu)解的問題，本文提出了一種改進的全局和聲搜索算法.該算法對標準和聲搜索算法作了三點改進，首先在和聲記憶庫初始化時采用反向?qū)W習策略，提高初始解的質(zhì)量，提高收斂速度，其次，采用動態(tài)方式調(diào)整參數(shù)，第三，利用當前和聲記憶庫中的全局最優(yōu)解產(chǎn)生新解，提高全局搜索能力.采用該算法對6個標準的測試函數(shù)進行優(yōu)化，結(jié)果表明，該算法避免算法的早熟和增強算法的全局搜索能力，具有較好的優(yōu)化性能.

和聲搜索算法；反向?qū)W習；函數(shù)優(yōu)化

1 引言

和聲搜索算法（Harmony Search，簡稱HS）是一種較新的智能搜索算法[1].該算法結(jié)構(gòu)簡單，易于其他算法結(jié)合，已經(jīng)成功地被應用到函數(shù)優(yōu)化問題中.相關(guān)研究表明，在解決多維函數(shù)優(yōu)化問題上HS算法比較遺傳算法、模擬退火算法等具有更好的優(yōu)化性能[2-5].但該算法在迭代早期具有較快的收斂速度，后期收斂速度較慢，算法的收斂速度很大程度依賴于初始解.反向?qū)W習策略已經(jīng)被證明能產(chǎn)生高質(zhì)量的初始解[6]，提高算法的收斂速度，而且已經(jīng)被成功地應用到其他的智能算法的解空間的初始化中.為了提高和聲記憶庫中解的質(zhì)量，避免算法陷入局部最優(yōu)解，本文將反向?qū)W習方法、粒子群中全局最優(yōu)解的概念與和聲搜索算法結(jié)合起來，提出一種改進的和聲搜索算法——反向?qū)W習全局和聲搜索算法.

2 和聲搜算法

HS算法模擬音樂演奏家創(chuàng)作的過程，音樂家不斷地調(diào)整所奏樂器的音調(diào)，使真?zhèn)€演奏過程達到最美和聲狀態(tài).HS算法將音樂創(chuàng)作的元素和優(yōu)化問題中的元量進行類比，將樂器、樂器的音調(diào)、和聲、和聲效果評價與組合優(yōu)化問題中的決策變量、決策變量的值、決策變量組成的解向量、目標函數(shù)的適應度值進行類比.具體的算法步驟如下：

2.1 初始化算法參數(shù)

初始化算法參數(shù)：①決策變量的個數(shù)N，②和聲記憶庫的大小HMS，③各個決策變量的取值范圍[Li,Ui]，④和聲記憶庫考慮概率HMCR，⑤音調(diào)微調(diào)概率PAR，⑥音調(diào)微調(diào)帶寬BW，⑦算法的迭代次數(shù)NI.

2.2 初始化和聲記憶庫HM

隨機生成HMS個和聲x1，x2，……，xHMS存入和聲記憶庫HM作為優(yōu)化問題的初始解.

和聲記憶庫中的每個音調(diào)（即決策變量）按照式（1）產(chǎn)生：

其中，i=1,2,……,HMS；j=1,2,……,N；Lj和Uj分別是j分量值域的下界和上界；

2.3 產(chǎn)生一個新的和聲

初始化后，HS算法將產(chǎn)生一個新和聲x'=(x1',x2',…xN')，新和聲中任一音調(diào)xi'按照三個規(guī)則產(chǎn)生：（1）考慮和聲記憶庫，（2）隨機在值域范圍內(nèi)選擇音調(diào)，（3）微調(diào)來自和聲記憶庫的音調(diào).具體操作如下：

首先，考慮和聲記憶庫或者隨機產(chǎn)生音調(diào)，公式如（2）式：

然后，如果新和聲中的某個音調(diào)xi'來自和聲記憶庫HM，則有PAR的概率對音調(diào)xi'微調(diào)，微調(diào)的公式如（3）式：

2.4 更新和聲記憶庫HM

對步驟（3）中的新解進行評估，如果新和聲優(yōu)于HM中的最差的一個和聲，則將新解xi'替換HM中當前最差的解.

2.5 檢查算法終止條件

重復步驟（3）和步驟（4），直到創(chuàng)作(迭代)次數(shù)達到NI為止.

3 改進的全局和聲搜索算法

HS算法在解決優(yōu)化問題上，早期能快速收斂，確定最優(yōu)解搜索空間，但是會陷入局部最優(yōu)解，為了解決這個問題，需要利用全局最優(yōu)解的信息，針對HS算法后期收斂慢的問題，提高收斂速度，采用了反向?qū)W習來初始化和聲記憶庫，提出一種改進的和聲搜索算法，叫反向?qū)W習全局和聲搜索算法（OGHS）.

HS算法的具體改進方面如下：

3.1 和聲記憶庫初始化

為了提高初始解的質(zhì)量，本算法采用反向?qū)W習的策略產(chǎn)生初始解.不再按照標準的HS算法采用均勻分布的策略，而是采用均勻分布與反向?qū)W習相結(jié)合的策略對和聲記憶庫初始化.和聲記憶庫中一半的解按照均勻分布策略產(chǎn)生如式（1），剩余的一半解采用反向?qū)W習策略產(chǎn)生如式（4）和（5）

3.2 BW和PAR參數(shù)的動態(tài)調(diào)整

文獻[7]中的測試結(jié)果表明，和聲搜索算法按照式（6）與（7）比Mahdavi等[8]提出IHS算法中的公式對PAR和BW進行動態(tài)調(diào)整的尋找的最優(yōu)解更好，因此，本算法采用式（6）和式（7）對PAR和BW進行動態(tài)調(diào)整比.

3.3 新解產(chǎn)生方式

為了提高算法的全局搜索能力，避免算法陷入局部最優(yōu)解，在產(chǎn)生新解的步驟中，保留當前和聲記憶庫中的最優(yōu)解，對標準HS算法中的式（3）做了改進，若新解來自于和聲記憶庫，有一半的概率是來自最優(yōu)解，新解不再按照式（3）產(chǎn)生，而是按照式（8）產(chǎn)生：

其中，i=1,2,……,n；k=1,2,……,HMS

即將當前和聲記憶庫中最優(yōu)解的第j維變量賦值給新解的第j維變量.

3.4 解的邊界值處理

當新解超過值域范圍，對新解按照式（9）[9]進行處理.

本算法與HS算法的流程整體相同，但對HS算法的初始解的產(chǎn)生和產(chǎn)生新解的核心部分進行了修正.

4 仿真實驗及結(jié)果分析

為了驗證OGHS算法的性能，采用典型的Benchmark測試函數(shù)對HS算法、IHS算法、GHS算法、IGHS算法和本文提出的OGHS算法進行測試比較.測試函數(shù)如表1所示.函數(shù)分別采用30維和100維進行測試.表2是實驗中各算法參數(shù)設(shè)置.

表1 測試函數(shù)

表2 不同算法的參數(shù)設(shè)置

本文中用最優(yōu)解平均值和標準方差來衡量算法的性能，最優(yōu)解平均值（MB）的大小能衡量算法的平均搜索能力，標準方差（SD）能說明算法的收斂速度.

表3記錄了30維和100維的6個測試函數(shù)在各個算法獨立運行20次的結(jié)果.表中GHS的測試結(jié)果來自文獻[10].

從表3的測試結(jié)果可以看出，在所有的測試函數(shù)中IGHS的最優(yōu)解平均值明顯比HS，HIS,GHS的要小，還可以看出GHS在一些單峰函數(shù)優(yōu)化問題上，結(jié)果并不優(yōu)于HS和IHS算法.

5 結(jié)論

本文提出一種反向?qū)W習全局和聲搜索算法（OGHS），該算法首先通過反向?qū)W習策略產(chǎn)生和聲記憶庫初始解，利用動態(tài)方式調(diào)整PAR和BW參數(shù)，然后利用全局信息改變新解產(chǎn)生.仿真實驗結(jié)果表明，該算法整體上表現(xiàn)出良好的性能，可以用于復雜優(yōu)化問題的求解.

表3 四種HS算法運算結(jié)果比較(運行程序20次)

〔1〕Geem Z W,Kim J H,Loganathan G V.A new heuristic optimization algorithm:harmony search[J].Simulation,2001,76(2):60-68.

〔2〕Geem ZW,Lee KS,Park Y.Application of harmony search to vehicle routing.American Journal of Applied Sciences,2005,2(12):1552?1557.

〔3〕Geem ZW.Optimal cost design of water distribution networks using harmony search.Eng Optimiz,2006,38(3): 259-280.

〔4〕Pan Q K,Suganthan P N,Tasgetiren M F,et al.A self-adaptive global best harmony search algorithm for continuous optimization problems[J].Applied Mathematics and Computation,2010,216(3):830-848.

〔5〕Ashrafi,S.M.,&Dariane,A.B.(2013).Performance evaluation of an improved harmony search algorithm for numerical optimization:melody search(MS).Engineering Applications of Artificial Intelligence,26(4),1301–1321.

〔6〕Wang H,Wu Z,Rahnamayan S,et al.Enhancing particle swarm optimization using generalized oppositionbased learning [J].Information Sciences,2011,181(20): 4699-4714.

〔7〕韓紅燕,潘全科,梁靜.改進的和聲搜索算法在函數(shù)優(yōu)化中的應用[J].計算機工程,2010,36(13):245-247.

〔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〕Gong,W.,Cai,Z.,&Ling,C.X.(2010).DE/BBO:a hybrid differential evolution withbiogeography-based optimization for global numerical optimization.SoftComputing,15(4),645–665.

〔10〕Omran M G H,Mahdavi M.Global-best harmony search [J].Applied Mathematics and Computation, 2008,198(2):643-656.

TP393

A

1673-260X（2016）11-0015-03

2016-06-22

安徽省教育廳自然科學基金重點項目（KJ2016A308)