啟發式和弦搜尋演算法之改良及應用

Abstract

啟發式演算法發展至今，已成功應用於各種領域。本研究旨在改善既有之啟發式和弦搜尋最佳化演算法（Harmony-Search Optimization Method）以提高其應用時之適用性與搜尋結果之收斂性。本研究以既有和弦搜尋演算法為基礎，針對啟發式演算法之集中強化（Intensification）與多樣化（Diversification）進行改善，以取得兩者間最佳之平衡。本研究先以參數自由設定之和弦搜尋演算法(Parameter-Setting-Free Harmony Search, 簡稱PSF-HS)結合粒子群法(Particle Swarm Harmony Search, 簡稱PS-HS)令和弦演算法中控制多樣化之參數HMCR與及控制調音率之參數PAR隨著迭代次數動態調整，使演算法於搜尋階段處於高多樣化的階段隨迭代次數增加而逐漸降低，漸次提高集中強化之比重，藉此提高和弦搜尋演算法的搜尋速度。再於驗證分析中，針對離散式例題分別加入移動平均、調音方向、粒子群法等方法以改善其搜尋所需迭代次數；針對連續式例題則於收斂階段時加入數值微分的方法以改善其收斂效果。隨後以經過修改與驗證後之演算法應用於新山壩滲漏問題之反算分析，並比較前人採用原版和弦搜尋演算法之計算結果，證明採用本研究之改良方法可得到收斂更佳的解。復以國道3號3.1k邊坡問定問題進行反算分析，比對災後調查報告與現地資料結果，展示此方法於實際反算分析應用時之適用性與有效性。

Heuristic optimization methods (HOM) have been successfully applied in various disciplines. This thesis aims to improve the existing harmony search (HS) method, as one of the HOM, in order to improve its applicability and convergence rate. The thesis attempts to seek a balance between intensification and diversification of the HOM. The improved algorithm combines the strategy of “parameter-setting-free (PSF) harmony search” (PSF-HS) with “particle swarm (PS) harmony search” (PS-HS). This algorithm enables the HMCR (which is the parameter controls diversification) and the PAR (which is the parameter controls intensification) to adjust dynamically along with iterations. It is able to emphasize diversification in the early search stage, and gradually transform to intensification in the later iterative stage to improve the search efficiency of the HS method. Several improved strategy on the HS method were tested and examined; these strategies include the usage of moving average in the PSF method, the control of tuning direction, the adding concept of the PS method, and the shift to the gradient method in the final iterative stage. These improved algorithms were verified through two examples, including one discrete variable problem and one continuous problem. Finally, the improved methods were applied to the back analyses of two practical geotechnical problems to demonstrate their applicability and usefulness.