Hengki's archive

Ant Colony Algorithm(ACO)

개미 알고리즘(Ant algorithm)은 실제 개미들이 먹이까지 가장 짧은 경로를 찾는 것을 모방한 알고리즘입니다. 이 알고리은 1992년 Dorigo에 의해 처음 제안되었습니다. 개미들은 어떻게 가장 짧은 경로를 찾게 되는 것일까요? 다음과 같은 예제를 통해 살펴보겠습니다.
 

1. 어떤 개미가 (a) 라는 길을 열심히 돌아다니다가 음식 (F)를 찾게 됩니다. 그 후 <그림1>과 같이 둥지로 돌아오는 경로 (b)에다가 페로몬으로 흔적을 남기면서 돌아옵니다.
2. 이 어떤 개미는 한 마리가 아니었고 4마리 정도가 동시에 둥지에 도착해서 <그림2> 번과 같이 여러 개의 길을 찾게 되었습니다. 이중에는 먹이까지 긴 길도 있고 짧은 길도 있게 됩니다.. 그러나 페로몬의 특성상 길에 남겨진 페로몬은 시간이 지날수록 그 향이 희미해진다. 
3. 경로가 길게 되면 개미들이 흔적을 남기는 시간도 길어지게 되며 자연적으로 긴 경로에는 상대적으로 페로몬 향이 옅어 지게 됩니다.
4. 개미들은 여러 경로 중 페로몬 향이 강한 길을 선택해서 움직입니다.
5. 짧은 길일 수록 개미들의 왕래가 잦아지면서 페로몬 향기는 짙어집니다.
6. 결국 <그림3>과 같이 개미들은 가장 짧은 경로로 먹이를 운반하게 됩니다.

Ant 알고리즘은 최적의 경로를 선택합니다. 우리는 이 경로를 Edge 로 정의하고 Edge 끝은 Node 로 정의 합니다. 정리하면 다음과 같습니다.
 

Ant 알고리즘은 페로몬의 향기 정도를 다음과 같은 확률계산식으로 계산합니다.

이 식에서 τ_i,j  는 edge_i,j  의 페로몬의 양을 나타냅니다. α는 τi,j 의 값을 컨트롤 하는 파라미터 값입니다.

η_i,j  는 edge_i,j  에 대한 가중치를 나타내며 보통 노드 사이의 거리에 반비례하는 값입니다.

β는 η_i,j  의 값을 컨트롤 하는 파라미터 값입니다.

Ant 알고리즘에서 개미는 이 확률 값을 통해 경로를 선택하게 됩니다.

다음은 페로몬 업데이트 공식을 살펴 보겠습니다.

τ_i,j = (1 − ρ)τ_i,j + Δτ_i,j

 ρ 값은 페로몬의 증발 비율을 나타냅니다. Δτ_i,j  는 새로이 추가되는 양을 나타내며 다음과 같이 정의됩니다.
 

L_k  는 노드 사이의 거리로 볼 수 있습니다.

Ant 알고리즘은 TSP 문제에 적용시킬 때 좋은 예가 됩니다.
 

TSP는 판매원이 집에서 출발하여 모든 고개들의 도시에 방문하고 다시 집에 돌아오는 최단 경로를 찾는 문제 입니다.

이 문제에는 다음과 같은 전제 조건이 있다.

1. 매판원의 집도 도시로 취급한다.
2. 모든 도시들은 서로 연결되어 있다.
3. 모든 도시들은 한번씩만 거쳐야 한다.
4. 모든 도시들을 거친뒤 다시 매판원의 집으로 돌아와야 한다.

이 전제 조건을 고려하여 TSP를 구하는 Pseudocode 를 작성하면 다음과 같습니다.

Start Node : Each ant is initially put on a ramdomly chosen start city
While(all ants don’t pass by every nodes)
 while(an ant don’t pass by every nodes)
  ant←getNextMovableNode()
  ant←chooseNextNode()
 end-while
 Arc←updatePheromone(ant’s path)
End-while

개미는 처음에 랜덤하게 시작 노드를 정해 위치시킵니다.

페로몬을 업데이트 할 때는 짧은 경로일수록 가중치를 주기 위해서 경로의 길이가 짧을수록 페로몬이 증발량을 작게 합니다.

모든 개미가 모든 노드를 거치게 되면 프로그램이 종료하게 됩니다.

TSP의 결과는 프로그램이 종료된 후 그래프의 각 arc(경로)에 남아있는 페로몬의 수치가 높은 순으로 선택하면 앞의 그림처럼 하나의 루프가 형성된다.

이것은 곧 TSP의 최적의 해가 됩니다.