출처 : http://opt-lab.tistory.com/14
개미는 페로몬으로 길을 찾는다. 처음 가보는 길이더라도 동료들이 남긴 페로몬을 따라 먹이가 있는 곳까지 찾아간다. 뿐만 아니라 시간의 흐름에 따라 효율적으로 짧은 길을 찾아낸다. 개미가 지름길을 찾아낼 수 있는 것은 먼 거리의 경로 보다 짧은 거리의 경로에 상대적으로 같은 시간 안에 통과하는 개미가 더 많게되고, 더 많은 페로몬이 누적되기 때문이다. 아래는 시간의 흐름에 따라 개미가 짧은 길을 찾아내는 과정을 나타낸 그림이다.
장애물이 처음 나타났을 때 장애물을 돌아가는 양쪽 길 중 하나를 같은 확률로 선택한다면 더 짧은 경로에 더 많은 개미가 통과하게 되고 따라서 더 많은 페로몬이 누적되게된다. 시간의 흐름에 따라 긴 경로의 페로몬이 증발량이 누적량보다 많아지게 되면 점점 긴 경로를 선택하는 개미는 줄어들게 될 것이고 결국 짧은 경로만 선택되게 된다. 개미의 입장에서 보면 TSP문제가 아무것도 아닌 문제일 수도 있다.
Ant Colony Optimization은 이러한 개미의 습성을 모방한 Meta-Heuristic이다. Meta-Heuristic이란 Optimal에 근사한 답을 찾아낼 수 있는 Heuristic을 말한다. 보통 Optimal의 1~2%내외의 답을 찾아낼 수 있을 때 Meta-Heuristic이라고 할 수있다. 대표적인 Meta-Heuristic은 Genetic Algorithm, Simulated Anealing이 있다. 재미있는 것은 훌륭한 Meta-Heuristic은 대부분 자연을 모방해서 만들어졌다는 것이다.
Ant Colony Optimization을 얘기하려면 Ant Colony Optimization의 역사를 먼저 이야기 해야 하는데 Ant Colony System의 기원은 Ant System이다. Ant System은 1992년 Marco Dorigo가 창안해냈다. 그 후 Ant System을 몇 가지 개선시킨 Ant Colony System이 1997년(Gambardella Dorigo) 발표되었다. 그럼 먼저 Ant System을 알아보자.
Ant System은 간단하게 3단계로 나눌 수 있다.
Ant System
1. 개미들을 탐색시킨다.
2. 모든 개미가 탐색이 끝나면 각 arc의 페로몬을 업데이트 한다.
3. 개미가 찾은 해를 비교해서 현재의 best solution보다 더 나은 해일경우 best solution 업데이트.
종료 조건이 충족될 때 까지 1~3반복
Heristic의 특성상 Optimal을 찾았더라도 그 답이 Optimal인지 확인 할 수 없기 때문에 보통 종료 조건은 일정한 시간 혹은 iteration 동안 더 나은 해를 찾지 못하면 종료하도록 하거나 평균적인 solution의 값이 어떤 값으로 수렴하게되면 종료한다.
Ant System에서 가장 중요한 것은 개미가 탐색할 때 다음 노드를 선택하는 기준이다. 개미의 습성을 구현하는 방법은 많겠지만 Ant System은 다음과 같은 확를 분포를 이용했다.
pi,j : 개미가 node i에서 node j로 이동할 확률
τi,j : arc i,j의 페로몬 양
ηi,j : arc i,j의 중요도. 보통 1/ci,j
S : 개미가 방문한 node
α, β : 파라미터
그러니까 arc의 페로몬의 양이 클 수록, arc의 cost가 작을 수록 그 arc를 선택할 확률이 높아지고 α, β의 값으로 각각 페로몬의 양에 비례할 강도와 arc cost에 반비례할 강도를 조절할 수 있다. 논문에서는 α=1, β=2를 사용했지만 꼭 정수일 필요는 없다. 개미가 방문한 노드들은 선택에서 제외시킴으로써 개미가 집으로 돌아오지 못하고 무한루프에 빠지는 경우를 막는다.
그리고 Ant System의 페로몬 Update 방법은 다음과 같은 공식을 사용해 이루어 진다.
ρ : 파라미터. 페로몬의 증발비율. 0~1 사이의 값을 가진다.
ck : 개미k가 찾은 solution의 cost
Iteration마다 모든 arc의 페로몬을 일정비율 증가시키고, 개미가 이동한 arc에는 페로몬을 누적시키는 것이다. 주의깊게 보아야 할 부분은 페로몬의 양이 Iteration마다 ρ만큼씩 증발한다는 것이다. 즉, 개미가 그 arc를 지나가지 않으면 그 arc의 페로몬 값은 Iteration 횟수가 증가할 수록 0으로 수렴한다. 그리고 개미가 지나간 arc에 추가되는 페로몬의 양은 그 개미가 찾은 답의 비용에 반비례한다. 즉, 좋은 답을 찾은 개미일수록 더 많은 양의 페로몬을 남긴다.
Ant System의 특징은 각각의 개미가 arc를 선택하는 것이 다른 개미의 arc 선택에 영향을 주지 않는다는 것이다. 한번의 Iteration이 끝나야 페로몬이 업데이트 되기 때문이다. 또한 개미의 arc선택이 페로몬의 양과 arc의 cost에 영향을 받기는 하지만 기본적으로 Random한 선택이기 때문에 Iteration이 진행되어도 개미가 이전보다 더 나은 선택을 한다는 보장이 없다.
이런점을 보완한 것이 Ant Colony System이다. 아마도 Colony를 붙인 것은 개미간의 상호 작용을 반영했기 때문인 것 같다. 먼저 Ant System과 구분되는 Ant Colony System의 특징을 알아보자.
Ant Colony System
1. 개미가 다음 노드를 선택할 때, 확률적으로 Deterministic한 선택을 한다.
2. 개미가 arc를 선택해서 이동할 때 마다 페로몬의 값을 업데이트한다.
3. 개미들 중 제일 좋은 solution을 찾은 개미가 선택한 arc에 추가적인 페로몬을 누적시킨다.
자연의 개미가 길을 선택할 때 페로몬이 많은 길을 선택할 것은 자명한 일이다. 1번은 이점을 표현한 것이다. 그러니까 개미가 arc를 선택할 때 단순히 페로몬의 가장 많은 arc를 선택할 확률이 있다는 것이다. 이러한 선택은 다음과 같이 나타낼 수 있다.
q0 : 파라미터. 개미가 Deterministic한 선택을 할 확률. 0~1 사이의 값을 가진다.
q : 0~1사이의 확률변수
※ q ≥ q0라면 Ant System의 확률분포를 이용한 arc선택을 한다.
즉 q0확률로 개미는 주사위를 던지지 않고 본능에 충실하게 페로몬이 많은 길을 선택하는 것이다.
2번이 추가됨으로써 개미가 한 노드에서 다른 노드로 움직일 때 마다 페로몬을 업데이트(Local Step Update) 시키고 그 영향을 탐색중인 모든 개미들이 받게된다. 다음의 식을 이용해서 업데이트 한다.
τ0 : 파라미터. 페로몬의 초기값. 보통 1/(N x Nearest Neighbor의 값)
φ : 파라미터. 페로몬의 Local Step 증발비율.
3번은 한 번의 Iteration이 끝난 후에 이루어진다.(Global Update) 다음과 같은 식을 이용해서 업데이트 한다.
3번을 보면 Neural Net의 신경망 학습과정과 매우 유사하다. 아무튼 전체 개미 중에서 가장 좋은 solution을 찾은 개미에게 자신의 tour에 페로몬을 남길 기회를 준다. 이렇게 함으로써 다음 Iteration에서 더 좋은 arc를 선택할 확률이 늘어나게되고 결과적으로 개미들에게 더 좋은 solution을 찾도록 유도한다.
지금까지 설명한 Ant Colony System을 정리하면 다음과 같다.
1. 개미들을 탐색시킨다.
1-1. 0~1사이의 난수를 발생시켜 q0보다 작으면 Deterministic한 선택을 한다.(1번 식)
1-2. 난수가 q0보다 크거나 같으면 Ant System과 같은 확를분포를 사용한 아크선택을 한다.
1-3. 개미들이 아크를 이동할 때마다 그 아크의 페로몬을 Local Step Update 시킨다. (2번 식)
2. 한 번의 Iteration이 끝나면 제일 좋은 solution을 찾은 개미의 tour에 페로몬을 Global Update한다. (3번 식)
3. 개미가 찾은 해를 비교해서 현재의 best solution보다 더 나은 해일경우 best solution 업데이트.
종료 조건이 충족될 때 까지 1~3반복
Ant Colony Optimization 알고리듬의 단점은 우선 파라미터 값들이 너무 많고 알고리듬이 파라미터에 너무 민감하게 반응한다는 것이다. 또 문제의 크기에 따라 파라미터 값들을 적절히 바꿔줘야 Optimal에 근사한 답을 찾아낸다. 파라미터를 고정시켜놓고 다양한 크기의 문제에 적용하면 solution의 질이 천차만별이다. 하지만 파라미터를 적절히 설정했을 때 optimal +1% 안밖의 답을 찾아냈다.
유의해야할 파라미터는 φ와 ρ이다. φ와 ρ는 페로몬 값이 0으로 수렴하는 속도를 결정한다. 너무 크게하면 좋은 경로를 놓치게 될 확률이 크고 너무 작게하면 더 좋은 답을 찾지 못하고 엉뚱한 방향으로 페로몬이 수렴하는 경향이 있다. 50 node의 문제에서 φ=0.02, ρ= 0.05로 했을 때 가장 좋은 결과를 얻었다.
다음은 50개의 랜덤하게 생성한 node의 문제에서 페로몬의 값과 best solution의 변화를 보여준다.
페로몬의 색깔은 상대적인 페로몬의 크기를 나타낸다.
'Algorithm' 카테고리의 다른 글
| FDM vs FVM vs FEM (0) | 2021.01.04 |
|---|---|
| kmeans - hadoop map-reduce 프로그래밍 (0) | 2018.11.20 |
| ML flow (0) | 2018.11.19 |
nssm-2.24.zip
