메타휴리스틱스(Metaheuristics)

[Site Map] [자료구조, 알고리즘 목차]

 

연관토픽

 

 

기출문제

회차	문제
관리126-1	2. 메타휴리스틱스(Metaheuristics)

 

 

 

개념

• 특정 문제에 한정되지 않고, 어떤 문제에 대해서도 범용적으로 대응할 수 있도록 설계된 알고리즘의 기본적 뼈대(범용적인 휴리스틱스^[각주:1])
• 특정 문제에 종속되지 않고, 다양한 문제에 적용이 가능한 Framework가 되는 알고리즘

• Heuristic Algorithm과 같은 good solution을 구하는 Algorithm이지만, problem-independent한다는 차이가 있음

 

 

 

메타휴리스틱의 분류

 

 

 

메타휴리스틱 알고리즘 기법

• 대표적으로 Simulated Annealing, Genetic Algorithm, Particle Swarm Optimization, Ant Colony Optimization 등이 있음

기법	설명
유전 알고리즘 (GA, genetic algorithms)	- 자연세계의 진화현상인 유전학의 원리에 근거하여, 세대를 거치면서 적자생존을 통해 점진적으로 최적해를 탐색해가는 최적화 문제 해결 알고리즘
시뮬레이티드 어닐링 (SA, simulated annealing)	- 전역 최적화 문제에 대한 일반적인 확률적 메타휴리스틱스 알고리즘
터부탐색 (TS, tabu search)	- 유전알고리즘, 시뮬레이티드 어닐링의 빈번하게 지역 최적적(local optimum)에 수렴하는 문제를 해결하기 위해, 지역 최적점에 대한 정보를 저장하여 이 정보를 기반으로 지역 최적점을 회피하여 전체 최적점을 찾는 알고리즘

 

 

 

Reference

---

1. META-HEURISTIC ALGORITHM이란?
2. 메타 휴리스틱스(Metaheuristics)의 소개(1)
3. 메타휴리스틱 기법과 탐색 방법, Metaheuristics and Search Technique
4. Meta-heuristic 정의 및 Ant colony optimization 개념, job shop scheduling 적용예

 

 

 

 

 

 

 

1. 휴리스틱스(heuristics) : '발견적 기법' 또는 '발견법'이라고도 부르며, 언제나 올바른 답을 얻을 수 있는 건 아니지만 경험적으로 어느 정도 좋을 것으로 생각되는 해답을 유추하는 기법 [본문으로]