和聲搜尋算法

和聲搜尋算法是新近問世的一種啟發式全局搜尋算法，在許多組合最佳化問題中得到了成功套用。在有關問題上展示了較遺傳算法、模擬退火算法和禁忌搜尋更好的性能。

基本介紹

• 中文名：和聲搜尋算法
• 時間：新近問世
• 性質：啟發式全局搜尋算法
• 範圍：組合最佳化問題

來源

在音樂演奏中，樂師們憑藉自己的記憶，通過反覆調整樂隊中各樂器的音調，最終達到一個美妙的和聲狀態。Z.W.Geem等受這一現象啟發，提出了和聲搜尋算法（HS:Harmony Search）。

參考：雍龍泉.和聲搜尋算法研究進展.計算機系統套用,2011,20(7):244-249

算法原理

HS算法將樂器i（i=1，2，……，m）類比於最佳化問題中的第i個設計變數，各樂器聲調的和聲Rj（j=1，2，……，M）相當於最佳化問題的第j個解向量，評價類比於目標函式。算法首先產生M個初始解（和聲）放入和聲記憶庫HM（harmony memory)內，以機率HMCR在HM內搜尋新解，以機率1-HMCR在HM外變數可能值域中搜尋。然後算法以機率PAR對新解產生局部擾動。判斷新解目標函式值是否優於HM內的最差解，若是，則替換之；然後不斷疊代，直至達到預定疊代次數Tmax為止。

設定規則

算法通過引入HR和PR兩個參數，以期望達到算法對解空間開發、探索能力的平衡，但是如何取值，並沒有理論基礎。Z.W.Geem等人認為HR應該取較大值，PR取較小值，這與遺傳算法中的交叉機率與變異機率的取值規律類似。