개미 군집 최적화 알고리즘

섬네일|개미 무리가 두 가지 다른 경로(한 경로가 다른 경로보다 훨씬 짧음)를 통해 먹이에 도달해야 하는 선택에 직면했을 때 그들의 선택은 완전히 무작위이다. 그러나 더 짧은 경로를 이용하는 사람들은 음식에 더 빨리 도달하므로 개미집과 음식 사이를 더 자주 오간다.
개미 군집 최적화 알고리즘(Ant colony optimization algorithms, ACO)은 컴퓨터 과학 및 운용연구에서 그래프 (그래프 이론)를 통해 좋은 경로를 찾는 것으로 축소될 수 있는 계산 문제를 해결하기 위한 확률적 기술이다. 인공 개미는 실제 개미의 행동에서 영감을 얻은 다중 에이전트 방법을 나타낸다. 생물학적 개미의 페로몬 기반 의사소통은 종종 사용되는 주요 패러다임이다. 인공 개미와 지역 탐색 알고리즘의 조합은 차량 경로 및 인터넷 경로와 같은 일종의 그래프와 관련된 수많은 최적화 작업에 선호되는 방법이 되었다.

예를 들어, 개미 군집 최적화는 개미 군체의 행동을 모델로 한 최적화 알고리즘 클래스이다. 인공 '개미'(예: 시뮬레이션 에이전트)는 가능한 모든 솔루션을 나타내는 매개변수 공간을 이동하여 최적의 솔루션을 찾는다. 실제 개미는 환경을 탐색하는 동안 서로에게 자원을 알려주기 위해 페로몬을 분비한다. 시뮬레이션된 '개미'는 유사하게 자신의 위치와 솔루션의 품질을 기록하므로 이후의 시뮬레이션 반복에서 더 많은 개미가 더 나은 솔루션을 찾을 수 있다. 이 접근법의 한 가지 변형은 또 다른 사회 곤충인 꿀벌의 수렵 패턴과 더 유사한 꿀벌 알고리즘이다.

이 알고리즘은 떼 지능 방법에서 개미 식민지 알고리즘 계열의 구성원이며 일부 메타휴리스틱 최적화를 구성한다. 1992년 마르코 도리고(Marco Dorigo)가 박사 학위 논문에서 처음 제안한 첫 번째 알고리즘은 군집과 식량 공급원 사이의 경로를 찾는 개미의 행동을 기반으로 그래프에서 최적의 경로를 찾는 것을 목표로 했다. 이후 원래 아이디어는 더 넓은 종류의 수치 문제를 해결하기 위해 다양해졌고, 그 결과 개미 행동의 다양한 측면을 활용하는 몇 가지 문제가 나타났다. 더 넓은 관점에서 ACO는 모델 기반 탐색을 수행하며 분포 알고리즘 추정과 일부 유사점을 공유한다.

 외부 링크 
 Scholarpedia Ant Colony Optimization page
 Ant Colony Optimization Home Page
 "Ant Colony Optimization" - Russian scientific and research community
 AntSim - Simulation of Ant Colony Algorithms
 MIDACO-Solver General purpose optimization software based on ant colony optimization (Matlab, Excel, VBA, C/C++, R, C#, Java, Fortran and Python)
 University of Kaiserslautern, Germany, AG Wehn: Ant Colony Optimization Applet Visualization of Traveling Salesman solved by ant system with numerous options and parameters (Java Applet)
 Ant algorithm simulation (Java Applet)
 Java Ant Colony System Framework
 Ant Colony Optimization Algorithm Implementation (Python Notebook)

분류:최적화 알고리즘 및 방법