[인공지능] combinatorial optimization 정리

combinatorial optimization

• 중요한 영향을 주는 key parameter의 조합을 찾아 최적화 문제를 푸는 것

Heuristic search (->Informed search)

1. Hill-climbing
2. Best-first search
3. Beam search
4. A* search

Local search (->neighbor search)

• 일부 트리만 보는 서치 기법
• 현재 해를 기준으로 가까운 이웃 노드들만 보고 좋은 방향으로 이동함
• 시작 위치에 따라 결과가 달라지므로 local optima에 빠질 수 있음
• 가장 간단하면서도 조합 최적화에서 많이 쓰임
• 문제: local optima, flat region에서의 cycle

문제를 해결하기 위한 Metaheuristics 기법이 존재

Local search metaheuristics

1. Simulated Annealing

• Temperture T를 통해 randomness를 조절하면서 해공간을 더욱 견고하게 만듦
• 해공간이 불안정한 초기에는 randomness를 크게하고
  해공간이 안정해지면 randomness를 줄여 greedy search를 진행

2. Iterated local search(ILS)

• local search를 반복

3. multi-start local search(MLS)

• 시작 지점을 여러 개 두어 여러 곳에서 local search를 진행

4. Tabu search

• Tabu list를 관리함으로써 flat region의 cycle에서 빠져나올 수 있게 함
• Tabu list여도 심각하지 않으면 탐색을 허용해주어서 어느 정도 downhill도 가능
• 유연한 메모리 구조를 가짐

Population based metaheuristics

1. Genetic Algorithm
2. Scatter Search
3. Memetic Algorithm
4. Particle Swarm Optimization