메타휴리스틱 (Metaheuristic)

메타휴리스틱 (Metaheuristic)

최적해를 보장하지는 않지만 합리적 시간 내에 충분히 좋은 근사해를 찾는 범용 탐색 전략으로, NP-hard 문제에 적용

목적: 조합 최적화, NP-hard 문제 근사해, 탐색 공간이 너무 큰 문제 해결

특징: 문제 독립적, 확률적, 탐색(Exploration)과 활용(Exploitation) 균형

분류

• •집단 기반: GA(유전 알고리즘), PSO(입자 군집), ACO(개미 군집)
• •단일 해 기반: SA(시뮬레이티드 어닐링), 타부 서치

PSO(Particle Swarm Optimization): 군집 행동 모방, 개인 최적(pBest)과 전체 최적(gBest) 방향 이동

ACO(Ant Colony Optimization): 개미 페로몬 모방, 좋은 경로 강화, 나쁜 경로 증발

타부 서치(Tabu Search): 최근 방문 해를 타부 리스트 저장하여 재방문 금지, 지역 최적해 탈출

No Free Lunch 정리: 모든 문제에 최적인 메타휴리스틱은 없음, 문제 특성에 맞게 선택

장점: 범용성, NP-hard 적용 가능, 구현 용이, 좋은 근사해

단점: 최적해 미보장, 파라미터 튜닝, 수렴 속도 불확실

적용사례: TSP, 스케줄링, VLSI 설계, 물류 최적화, 하이퍼파라미터 튜닝

비교: GA(집단/진화) vs SA(단일/담금질) vs PSO(집단/군집) vs ACO(집단/페로몬) vs 타부(단일/메모리)

연관: 조합 최적화, NP-hard, 근사 알고리즘, 최적화