劉立群，火久元，王聯國

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

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

1 和聲搜索算法思想

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

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

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

新和聲的每一個音調x'i(i=1，2，…，N)通過學習和聲記憶庫產生。

如果 r1＜HCMR，則

通過式(3)產生的新和聲音調x'i還需進行音調微調。

如果 r2＜PAR，則

如果r1≥HCMR，則隨機選擇音調產生新和聲x'i，即

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

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

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

2.1 全局共享因子思想

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

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

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

根據全局共享因子理論，在HS算法初期，初始和聲隨機分布在搜索空間內，為避免和聲音調更新步長過大跳過最優(yōu)個體，應通過較小的全局共享因子減弱音調微調帶寬對最差和聲的音調微調能力。當迭代次數達到一定程度時，最差和聲與通過學習和聲記憶庫產生的和聲的差異如果過小則會出現搜索停滯現象，此時應通過迅速增大到一定值后的全局共享因子增強音調微調能力，實現全局收斂。

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

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

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

GSF-HS算法步驟如下:

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

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

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

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

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

2.3 算法流程

GSF-HS算法流程見圖1。

圖1 GSF-HS算法流程

3 對比實驗及結果分析

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

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

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

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

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

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

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

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

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

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

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

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

3.2 固定收斂精度下的迭代次數分析

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

表1 固定迭代次數結果比較

表2 固定收斂精度結果比較

4 結束語

本文提出一種全局共享因子的和聲搜索算法，將全局共享因子思想和HS算法創(chuàng)作次數相結合，并將其應用到HS算法的音調微調機制中以改進HS算法音調微調機制隨機性更新的缺陷。4個測試函數的對比實驗結果表明: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)應用，2011，20(7):244-248.

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

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

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

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

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