全局共享因子的和聲搜索算法

劉立群，火久元，王聯(lián)國

(1.甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，蘭州 730070;2.蘭州交通大學(xué) 信息中心，蘭州 730070)

和聲搜索(harmony search，HS)算法［1-4］是通過類比音樂和最優(yōu)化問題相似性提出的啟發(fā)式智能迭代算法。HS算法是對音樂演奏中樂師憑借記憶通過反復(fù)調(diào)整樂隊中各樂器音調(diào)，最終達到一個美妙和聲狀態(tài)過程的模擬。研究表明:HS算法是單個體迭代算法，具有迭代速度緩慢、易陷入局部最優(yōu)以及求解質(zhì)量不高等缺陷［2-4］。本文針對HS算法音調(diào)微調(diào)機制中存在隨機性更新的缺陷，將全局共享因子［5］的思想引入HS算法，提出一種全局共享因子的和聲搜索算法(harmony search algorithm with global sharing factor，GSFHS)。測試函數(shù)對比實驗表明，GSF-HS算法有效改善了HS算法的優(yōu)化性能。

1 和聲搜索算法思想

隨機產(chǎn)生HMS個初始解(和聲)放入和聲記憶庫(harmony memory，HM)內(nèi)，HMS為和聲記憶庫的大小，HMCR為和聲記憶庫取值概率，PAR為音調(diào)微調(diào)概率，BW為音調(diào)微調(diào)帶寬，Tmax為算法創(chuàng)作的次數(shù)，且r1，r2，r∈[0，1]。假設(shè)問題是求最小值，其表達形式為:

隨機生成 HMS個和聲x1，x2…，xHMS放入和聲記憶庫，形式如下:

按以下規(guī)則生成一個新的和聲x'i=(x'1，x'2，…，x'N)。

新和聲的每一個音調(diào)x'i(i=1，2，…，N)通過學(xué)習(xí)和聲記憶庫產(chǎn)生。

如果 r1＜HCMR，則

通過式(3)產(chǎn)生的新和聲音調(diào)x'i還需進行音調(diào)微調(diào)。

如果 r2＜PAR，則

如果r1≥HCMR，則隨機選擇音調(diào)產(chǎn)生新和聲x'i，即

對和聲記憶庫按以下更新策略進行更新。

上述過程不斷重復(fù)，直至創(chuàng)作(迭代)次數(shù)達到Tmax為止。

2 全局共享因子的和聲搜索算法

2.1 全局共享因子思想

HS算法音調(diào)微調(diào)機制利用隨機數(shù) r∈[0 ，1]產(chǎn)生新和聲。由于這種方式具有隨機性，因此對單峰值和多峰值函數(shù)尋優(yōu)問題，HS算法易出現(xiàn)收斂速度慢、精度低等問題。

文獻［5］在共享因子［6］基礎(chǔ)上提出全局共享因子的概念。全局共享因子αG是僅隨迭代次數(shù)非線性動態(tài)變化的共享因子［5］。由于αG是由較小的初值迅速增大到一個穩(wěn)態(tài)值，故可以抑制隨機性音調(diào)微調(diào)的隨機性。

本文將HS算法中創(chuàng)作次數(shù)t∈[1，Tmax]應(yīng)用到全局共享因子中，其表達式為

根據(jù)全局共享因子理論，在HS算法初期，初始和聲隨機分布在搜索空間內(nèi)，為避免和聲音調(diào)更新步長過大跳過最優(yōu)個體，應(yīng)通過較小的全局共享因子減弱音調(diào)微調(diào)帶寬對最差和聲的音調(diào)微調(diào)能力。當?shù)螖?shù)達到一定程度時，最差和聲與通過學(xué)習(xí)和聲記憶庫產(chǎn)生的和聲的差異如果過小則會出現(xiàn)搜索停滯現(xiàn)象，此時應(yīng)通過迅速增大到一定值后的全局共享因子增強音調(diào)微調(diào)能力，實現(xiàn)全局收斂。

2.2 全局共享因子的和聲搜索算法

本文將上述全局共享因子αG引入到HS算法中，提出一種全局共享因子的和聲搜索算法(harmony search algorithm with global sharing factor，GSF-HS)。

GSF-HS算法是在HS算法基礎(chǔ)上對其音調(diào)微調(diào)機制中的隨機性更新進行改進，即GSF-HS算法中音調(diào)微調(diào)機制按式(9)進行計算，其中全局共享因子αG按式(7)、(8)計算。

GSF-HS算法步驟如下:

步驟1 隨機生成HMS個初始和聲 x1，x2，…，xHMS，第i個和聲記為xi=(x1，x2，…，xN)，其中N為和聲音調(diào)個數(shù)。

步驟2 初始化和聲記憶庫取值概率HMCR、音調(diào)微調(diào)概率PAR、音調(diào)微調(diào)帶寬BW和算法創(chuàng)作次數(shù)Tmax。

步驟3 選取目標函數(shù)f(xi)，按式(2)初始化和聲記憶庫HM。

步驟4 按式(7)、(8)計算全局共享因子αG。

步驟5 隨機生成 r1，r2，r∈[0，1]，如果 r1＜HCMR，則新和聲音調(diào)x'i按式(3)計算，且若r2＜PAR，則計算出的新和聲音調(diào)x'i再按(9)式計算;如果r1≥HCMR，則按式(5)計算新和聲。按式(6)對和聲記憶庫進行更新，如此反復(fù)迭代直至Tmax為止，輸出最優(yōu)和聲。

2.3 算法流程

GSF-HS算法流程見圖1。

圖1 GSF-HS算法流程

3 對比實驗及結(jié)果分析

實驗采用 Rastrigrin、Griewank、Ackley和Rosenbrock［7-8］4個測試函數(shù)作為HS算法的目標函數(shù)，分別對HS及GSF-HS算法進行極小值尋優(yōu)性能測試。其中:Rastrigrin、Griewank、Ackley函數(shù)為多峰值函數(shù)，Rosenbrock函數(shù)為單峰值函數(shù)，4個函數(shù)的極小值均為0［7-8］。

實驗參數(shù)設(shè)置如下:和聲記憶庫大小HMS=200，HMCR=0.9，PAR=0.3，BW=0.01，Tmax=30 000。實驗所用計算機處理器為Intel Core2，主頻為2.0 GHz，內(nèi)存為2.0 GB，測試平臺為VC++6.0。最終測試結(jié)果采用獨立運行30次后的平均值。

算法性能評價采用如下方法:①固定迭代次數(shù)，評價算法收斂精度和速度;② 固定收斂精度，評價算法達到該精度所需的迭代次數(shù)。

3.1 固定迭代次數(shù)的收斂精度和速度分析

固定迭代次數(shù)下，各算法收斂結(jié)果如表1所示。4個測試函數(shù)在固定迭代次數(shù)條件下的函數(shù)平均最優(yōu)值迭代曲線如圖2～5所示。

對多峰值 Rastrigrin和 Ackley函數(shù)，表1表明:GSF-HS算法平均最優(yōu)值結(jié)果均優(yōu)于HS算法，且GSF-HS算法標準差較HS算法更具優(yōu)勢，改進算法對這2個函數(shù)的收斂精度改善較為明顯。圖2的Rastrigrin函數(shù)和圖4的Ackley函數(shù)迭代曲線表明:GSF-HS算法收斂速度均優(yōu)于HS算法。

對多峰值 Griewank函數(shù)，表1表明:雖然GSF-HS算法平均最優(yōu)值結(jié)果遠優(yōu)于HS算法，但其標準差較HS算法高，改進算法對Griewank函數(shù)的收斂精度沒有明顯改善。圖3的Griewank函數(shù)迭代曲線顯示:在迭代次數(shù)少于10 000時，GSFHS算法的收斂速度優(yōu)于HS算法，但在之后的迭代中，GSF-HS算法收斂速度并無太大改進。

對單峰值Rosenbrock函數(shù)，表1表明:GSF-HS算法平均最優(yōu)值結(jié)果遠優(yōu)于HS算法，且GSF-HS算法標準差為0，明顯優(yōu)于HS算法，改進算法對單峰值函數(shù)的收斂精度改善較為明顯。圖5的Rosenbrock函數(shù)迭代曲線顯示:在迭代次數(shù)超過20 000之后，GSF-HS算法的收斂速度較HS算法有較大提升。

圖2 Rastrigrin函數(shù)平均最優(yōu)值迭代曲線

圖3 Griewank函數(shù)平均最優(yōu)值迭代曲線

圖4 Ackley函數(shù)平均最優(yōu)值迭代曲線

圖5 Rosenbrock函數(shù)平均最優(yōu)值迭代曲線

3.2 固定收斂精度下的迭代次數(shù)分析

4個測試函數(shù)的目標精度和各函數(shù)達到目標精度時的平均迭代次數(shù)見表2［7-8］。實驗結(jié)果表明:GSF-HS算法達到目標精度的次數(shù)明顯少于HS算法。由此可知，GSF-HS算法收斂精度、速度均優(yōu)于HS算法。

表1 固定迭代次數(shù)結(jié)果比較

表2 固定收斂精度結(jié)果比較

4 結(jié)束語

本文提出一種全局共享因子的和聲搜索算法，將全局共享因子思想和HS算法創(chuàng)作次數(shù)相結(jié)合，并將其應(yīng)用到HS算法的音調(diào)微調(diào)機制中以改進HS算法音調(diào)微調(diào)機制隨機性更新的缺陷。4個測試函數(shù)的對比實驗結(jié)果表明:GSF-HS算法收斂精度、速度均優(yōu)于HS算法，有效改善了HS算法的優(yōu)化性能。

［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］趙鵬軍，劉三陽.一種新的智能優(yōu)化及其改進研究［J］.小型微型計算機系統(tǒng)，2010，31(5):955-958.

［3］雍龍泉.和聲搜索算法研究進展［J］.計算機系統(tǒng)應(yīng)用，2011，20(7):244-248.

［4］韓紅燕，潘全科，梁靜.改進的和聲搜索算法在函數(shù)優(yōu)化中的應(yīng)用［J］.計算機工程，2010，36(13):245-247.

［5］劉立群，王聯(lián)國，韓俊英，等.基于全局共享因子的混合蛙跳算法［J］.計算機工程，2013，39(10):162-166.

［6］王輝.一種帶共享因子的人工蜂群算法［J］.計算機工程，2011，37(22):139-142.

［7］王凌.智能優(yōu)化算法及其應(yīng)用［M］.北京:清華大學(xué)出版社，2001:2-6.

［8］Andrice P，Engelbrecht.Fundamentals of Computational Swarm Intelligence［M］.譚營，譯.北京:清華大學(xué)出版社，2009:10-15.