개미 집단 최적화 알고리즘
개미집단최적화알고리즘(ACO)는 컴퓨터를 이용해 연결그래프의 최적의 길을 찾는 방법을 줄일 수 있는 알고리즘이다.
이 알고리즘은 개미집단 알고리즘(ant colony algorithm)의 일부이다.
1992년 Marco Dorigo 박사의 논문에서 제안되었는데 그래프에서 최적의 길을 찾는 것을 목적으로 했다. 이 알고리즘은 먹이를 찾는 개미의 행동을 보고 만들어졌다.
첫 번째 개미가 (a) 방향으로 어느 길이든 경유해 먹이(F)를 찾아낸다. 그러면 개미는 (b)방향으로 페로몬을 남기며 집(N)으로 돌아온다. 개미는 집에서 음식까지 4가지의 이동경로를 가질 수 있다. 하지만 시간이 지나면 개미들은 가장 짧은 길을 선택한다. 결국 페로몬이 증발하면서 긴 길은 사라지게 된다.
개미들은 다음과 같은 과정을 따른다.
1. 개미들은 무작정 개미집 주변을 돌아다닌다.
2. 만약 음식을 찾아내면 개미는 페로몬을 뿌리며 집으로 돌아온다.
3. 페로몬은 매우 매력적이어서 개미가 따라가고 싶게 만든다.
4. 개미가 집으로 돌아오는 횟수가 많을수록 그 경로는 더 견고해진다.
5. 긴 경로와 짧은 경로가 있으면 같은 시간에 짧은 경로로 이동할 수 있는 횟수가 많다.
6. 짧은 경로는 갈수록 더 많은 페로몬이 뿌려지면서 더욱 견고해진다.
7. 페로몬은 휘발성이기 때문에 시간이 지나면서 긴 경로는 사라진다.
8. 결국 모든 개미가 짧은 경로를 선택한다.
An example pseudo-code and formulae
procedure ACO_MetaHeuristic
while(not_termination)
generateSolutions()
daemonActions()
pheromoneUpdate()
end while
end procedure
Edge Selection
개미가 노드 i에서 j로 이동할 확률은 다음과 같다.
τi,j 는 edge i,j에 있는 페로몬의 양이다.
α 는 τi,j 의 영향력을 조절하기 위한 변수.
ηi,j 는 edge i,j 에 대한 만족도이다(초기에 주어지는 값, 보통 1 / di,j, 이며 d는 거리이다.).
β 는 of ηi,j 의 영향력을 조절하기 위한 변수.
Pheromone Update
τi,j = (1 − ρ)τi,j + Δτi,j
τi,j edge i,j 에 남아있는 페로몬의 양.
ρ 페로몬의 증발률.
Δτi,j 는 초기에 주어지는 값이며, 보통 다음과 같이 정한다.
Lk 는 K번째 개미가 여행하는데 드는 비용(보통 길이).
From Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Ant_colony_optimization#Summary
From Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Ant_colony_optimization#Summary
출처 : http://antalgo.cafe24.com/
----------------------------------------본----인----작----성----------------------------------------