📌 개요
평소 즐겨보는 유튜브 채널 '과학을 보다' EP.100 편에 개미 군집 최적화가 실렸다.
검색해보니 개미들의 생물학적 먹이 활동이자 생존 방식이었다. (똑똑한 녀석들..)
내용이 재밌어서 이것 저것 찾아보게 되었고, 해당 알고리즘의 수학적 공식화, 코드 구현 내용을 기록한다.
📌 개미 군집 최적화란 무엇인가
✨ 개미 군집 최적화란
개미 군집 최적화(Ant Colony Optimization, ACO)는 개미가 먹이를 찾는 행동을 모방한 알고리즘으로 아래 순서와 같이 동작한다.
- 먹이(도착지)의 위치를 인지한 개미가 발생한다.
- 먹이(도착지)까지 도달할 수 있는 수많은 경로 중 하나를 확률에 기반하여 선택한다.
- 페로몬을 뿌리며 먹이(도착지)까지 도달한다.
- 페로몬을 뿌리며 먹이를 갖고 출발지로 복귀한다.
- 이후의 개미들이 먹이(도착지)까지 도달하는 경로를 선택할 때, 확률에 페로몬의 농도가 가중된다.
✨ 개미의 페로몬
이러한 동작이 가능한 것은 개미가 남긴 페로몬이 시간에 따라 증발하기 때문이다.
긴 경로의 길보다 짧은 길에 남은 페로몬의 농도가 짙고, 짧은 길은 개미들이 선택할 확률이 증가하기 때문에 점차 페로몬이 누적된다.
또한 확률에 의한 무작위성이 포함되어 새로운 경로를 탐색할 기회를 제공한다.
이를 통해 최적화 과정에서 지역 최적해에 빠질 위험을 배제한다.
📌 개미 군집 최적화의 수학적 공식화
개미 군집 최적화를 알고리즘으로 작성하기 전에 수학적 공식화 과정을 이해해야 한다.
✨ 특정 경로 왕복 시 페로몬의 농도 구하기
🍀 페로몬 농도
T ij 는 개미가 특정 경로 T를 왕복했을 때 남는 페로몬의 농도이다.
경로 T에 대한 출발지 i와 도착지 j를 의미한다.
🍀 페로몬 증발 속도
(1 - p) 는 경로 T의 페로몬 증발 속도이다.
0 < p < 1 이고, p가 1에 가까울수록 증발 속도가 빠르다.
이는 개미의 종류나 환경에 따라 달라질 수 있고, 알고리즘 작성 시 조절 가능한 수치이다.
🍀 페로몬 수치
△T ij는 개미가 경로를 지나며 남기는 페로몬의 수치이다.
이 때 모든 개미가 동일한 페로몬의 총량 Q를 가지며, 경로의 길이 L에 영향을 받는다.
✨ 페로몬에 기반한 경로 선택 확률 구하기
(수식이 갑자기 험악해졌는데 하나씩 살펴보자,,)
🍀 경로 선택 확률
P ij 는 개미가 경로 ij를 선택할 확률이다.
현재 경로의 수치를 모든 경로의 합산 수치에 나눈 값이다.
🍀 이동 가능한 모든 경로
∑ kj 는 개미가 선택할 수 있는 모든 경로이다.
각각의 경로가 가지는 수치를 합산한다.
🍀 페로몬의 농도와 경로의 유용성
T ik 는 앞서 말했듯이 개미가 경로 ik를 왕복한 이후 남게 되는 페로몬의 농도이다.
η ik 는 개미 입장에서 경로 ik를 왕복하는 것이 얼마나 유용한지의 수치이다.
실제 환경에서는 경로의 거리, 품질(매끄러움, 경사도), 안전성, 날씨(습도, 온도) 등의 영향을 받는다고 한다.
🍀 지수 α, β의 의미
페로몬의 농도와 경로의 유용성을 구하는 수식을 보면, 지수로 각각 α와 β를 설정한다.
α, β는 실제 개미들에게는 적용되지 않는 값으로 알고리즘의 성능 조절을 위한 값이다.
α, β의 값을 조절하여 페로몬 증발 속도를 가속하거나, 경로의 유용성 수치를 극대화하여 시뮬레이션 가능하다.
📌 Java GUI로 ACO 구현(예정)
시간적 여유가 되면 작성해보겠습니다,,,
