目錄
Metaheuristic 爲高階的法則或啓發式演算法(經驗法則), 在有限的資訊、運算能力、資源下, 對最佳化問題(Optimization Problem)尋找足夠好的啓發式演算法。
並不保證 globally optimal
許多 Metaheuristic 帶有隨機最佳化(Stochastic Optimization)
性質:
- Metaheuristics are strategies that guide the search process.
- The goal is to efficiently explore the search space in order to find near–optimal solutions.
- Techniques which constitute metaheuristic algorithms range from simple local search procedures to complex learning processes.
- Metaheuristic algorithms are approximate and usually non-deterministic.
- Metaheuristics are not problem-specific.
不同分類方式:
- Local search vs. global search
- 基本版的爬山演算法(hill climbing)屬於 local search
- 把 local search 擴增到 global search
- simulated annealing
- tabu search
- iterated local search
- variable neighborhood search
- GRASP (Greedy Randomized Adaptive Search Procedure)
- 單純 global serach(非基於 local search 衍生),通常是 population-based
- ant colony optimization
- evolutionary computation
- particle swarm optimization
- genetic algorithm
- rider optimization algorithm
- Single-solution vs. population-based
- 單一解決方案:專注在一種候選解決方案
- simulated annealing
- iterated local search
- variable neighborhood search
- guided local search
- 多重解決方案:有多個候選解決方案在調整
- evolutionary computation
- genetic algorithms
- particle swarm optimization
- Swarm intelligence (collective behavior of decentralized, self-organized agents in a population or swarm)
- Ant colony optimization
- particle swarm optimization
- social cognitive optimization
- Hybridization and memetic algorithms
- hybrid metaheuristic:並行使用 metaheuristic 和其他最佳化演算法,兩者間可以同時進行並互相交換資訊來引導搜尋
- 可搭配 mathematical programming, constraint programming, machine learning
- memetic algorithm:傳統基因演算法的擴增
- 例如使用 local search 取代原本的變動運算,藉此減少過早收斂的機會
- Parallel metaheuristics
- 同時跑多種 metaheuristic,甚至可能是分散式到許多機器嘗試多種方案
- Nature-inspired and metaphor-based metaheuristics
- 從大自然中獲得設計想法
- simulated annealing
- evolutionary algorithms
- ant colony optimization
- particle swarm optimization
Metaheuristic Optimization Frameworks (MOFs),蒐集許多演算法實作供快速取用: