개미 군집 알고리즘 ( Ant Colony Optimization , ACO )

ACO

• 개미 군집 알고리즘은 실제 개미들의 경로 탐색 방식을 모방한 최적화 기법이다. ( 특히, 조합 최적화 문제를 해결하는데 효과적 )
• 영감의 기반
  • 개미들은 먹이를 찾을때 '페로몬'이라는 화학 물질을 경로에 남긴다. 개미들은 경로를 선택할때 무작위성을 가지지만, '페로몬'이 많이 쌓인 경로를 따라갈 확률이 높다.
  • 1. 처음에는 개미들이 무작위로 이동하며, 여러 경로를 탐색한다.
  • 2. 먹이를 발견한 개미가 둥지로 돌아오며 페로몬을 남긴다.
  • 3. 시간이 지나면서, 짧은 경로를 따라서 이동했던 개미들이 많아질것임. 그러면 결과적으로 짧은 경로에 페로몬이 더 많이 축적된다. ( 반대로는 짧은 경로에 쌓인 페로몬은 증발하여 점점 영향력이 줄어든다. )
  • 4. 최종적으로는 가장 짧은 경로에 페로몬이 집중되며, 군집들은 최적화된 경로를 따르게 된다.
• 장점
  • 1. 여러 개미가 동시에 탐색하여, 병렬연산을 활용이 가능하다.
  • 2. 초기에는 무작위성이 강하지만, 점진적으로 최적의 해를 찾는다.
  • 3. 다양한 최적화 문제에 사용이 가능
• 단점
  • 1. 초기에는 무작위성이 강하여 최적해를 찾는데 오래걸림
  • 2. 페로몬이 특정 경로에 집중되면, 최적해를 찾지 못할수있음
  • 3. 적절한 매개변수를 주어야 좋은 성능을 낸다
• 활용 사례
  • 1. TSP의 가장 짧은 여행경로 찾기
  • 2. 최소 비용으로 여러 지점을 방문하는 최적 경로 찾기
  • 3. 작업 스케줄링 및 자원 배분 문제 해결

 

 

 

ACO의 핵심 요소

• 1. search space : 탐색공간은 해결해야 할 문제를 그래프로 표현한것이다.
• 2. Ant colony : 개미군집은 경로를 찾기 위해서 탐색을 수행하는 에이전트(개미들)
• 3. Pheromone  : 경로에 남겨지는 신호이며, 탐색의 결과를 반영함.
  
• 4. stochastic decision : 페로몬의 양과 유발인자(휴리스틱)을 기반으로 경로 선택
• 5. evaporation : 일정 시간 후에 페로몬이 자연 감소해서, 이전의 탐색 결과를 점진적으로 무효화한다.
• 6. heuristic : 경로 선택시 추가적인 정보를 반영한다.

 

ACO의 동작과정

• 1. 그래프의 모든 edge에 초기 pheromone 값을 동일하게 설정한다. 그리고 여러 개의 개미를 초기 위치에서 출발시킨다.
• 2. 각 개미들은 현재 위치에서 이동할 수 있는 모든 노드 중에서 하나를 선택하여 이동한다. 선택하는 확률은 아래와 같다.