採用失敗後跳躍的策略以改良爬山演算法

An Improvement of Hill Climbing Algorithm with Jumping Strategy

林伯陽(Bo-Yang Lin) ； 陳鍾誠(Chung-Chen Chen)

《國立金門技術學院學報》 4期 (2010/01) Pp. 105-116

https://doi.org/10.7057/JNKIT.201001.0105

摘要

爬山演算法（Hill-Climbing, HC）是廣為人知的一種基礎性演算法，具有簡單且快速的優點，但此方法落入區域最佳解後，就無法跳出，因而難以找到更好的解。有鑑於此，我們設計出一種隨失敗次數遞增的跳躍策略，這使得爬山演算法有機會脫離區域最佳解，以尋找更好的解答，此種方法我們稱為爬山跳躍演算法（Hill-Climbing with Jumping Strategies, HCJ）。本文採用近來經常被使用到的三個非線性規劃（Nonlinear Programming）問題－G1、G7、G9，來測試HCJ演算法的效果。結果顯示HCJ的表現在G1、G9上相當優秀，但在G7上則無法趨近最佳解，經過分析顯示，G7可能是一個具有狹長滑道型的問題，這是HCJ目前所難以處理的問題，也是未來HCJ有待改進之處。然而HCJ與其它同為單一粒子的演算法，像是HC跟SA相比，HCJ在效能與求解的準確度相當多的改進；且在經過與多粒子型演算法的文獻比較後，可以發現HCJ的求解結果，雖然尚不及改良過後的PSO及GA，但還是比原始的PSO及GA來的好，這是因為HCJ跳躍策略所導致的改良，也代表HCJ的潛力值得進一步的探索。

關鍵字

最佳化 ； 爬山演算法 ； 模擬退火法 ； 粒子群演算法 ； 非線性規劃

並列摘要

Hill-Climbing (HC) is an optimization algorithm that is widely known. It's simple and fast. However, HC will be trapped when it fall into local optima, and cannot find global optimal solution. In this paper, we design a jumping strategy to help HC escape from local optima. The new algorithm is called Hill-Climbing with Jumping Strategies (HCJ).This text adopts three popular Nonlinear Programming problems - G1, G7, G9, to test the effect of HCJ algorithm. The result showed that HCJ had excellent performances on G1, G9, but HCJ couldn't work well on G7. Through analyzing the experiment, we realized that G7 may contain a problem itself, this is a problem which HCJ cannot solve at the moment, but it is also an area which HCJ could be improved in the future.However, when comparing HCJ with other single-particle algorithm, such as HC and SA, HC shows much improvement in its accuracy with its performance and solutions; when compared with multi-particle algorithm, we have found out that when HCJ is obtaining a solution, although it is not as good as the modified PSO and GA, but it is better than the original PSO and GA. This is resulted from the modification of the HCJ jumping strategy, it also shows the improvement in the potential of the HCJ jumping strategy.

並列關鍵字

Optimization ； Hill Climbing ； Simulated Annealing ； Particle Swarm Optimization ； Nonlinear programming