巨集演算法之發展與應用

Development and Applications of Metaheuristics

邱裕鈞(Yu-Chiun Chiou)

《國防管理學報》 30卷2期 (2009/11) Pp. 49-67

https://doi.org/10.29496/JNDM.200911.0004

摘要

近數十年來，受到電腦設備運算能力大幅提昇之激勵，巨集演算法之發展與應用可謂一日千里。為有利於研究人員選擇、運用、改良，進而創新巨集演算法，本文乃針對10種常用的巨集演算法，包括「單點尋優」的模擬退火法、門檻值接受法、大洪水法、禁忌搜尋法、變動鄰域搜尋法，以及「多點尋優」的遺傳演算法、遺傳規劃法、微分演化法、粒子群尋優法、螞蟻演算法等加以簡介。雖然各巨集演算法之尋優邏輯與操作步驟不盡相同，但其尋優功能上均具備不同程度之多樣化及強化策略。如何平衡此兩種尋優策略之運用強度，顯為演算法求解績效之最重要關鍵。因此，本文也針對各方法如何運用此兩策略之機制加以說明與比較。

關鍵字

巨集演算法 ； 單點尋優 ； 多點尋優 ； 多樣化策略 ； 強化策略

並列摘要

In recent decades, stimulated by the dramatic increase in computational capacity, the development and applications of metaheuristics grow rapidly. To facilitate the selection, operation, improvement, and innovation of metaheuristics for interested researchers, this paper briefly introduces 10 commonly adopted metaheuristics which can be divided into two categories: single-point search method and multi-point search method. Single-point search method consists of simulated annealing, threshold accepting, great deluge algorithm, tabu search, and variable neighborhood search. Multi-point search method entails genetic algorithms, genetic programming, differential evolution, particle swarm optimization, and ant colony optimization. Although the core logic and optimization mechanism among these metaheuristics differ, all of them utilize both intensification and diversification strategies in searching the global optimum. Obviously, the right balance between intensification and diversification is the key to obtain an effective and efficient searching result. Thus, the degrees of two strategies being exercised by the metaheuristics are compared and analyzed.

並列關鍵字

Metaheuristics ； single-point search methods ； multi-point search methods intensification strategy ； diversification strategy