728x90
개미의 페로몬 경로와 네트워크 라우팅
개미는 먹이를 찾기 위해 무작위로 이동하다가 먹이를 발견하면, 돌아오는 길에 페로몬(pheromone)을 남긴다.
다른 개미들은 이 화학적 흔적을 따라가며 더욱 많은 개미가 같은 경로를 사용하게 되고, 결과적으로 가장 짧고 효율적인 경로가 자연스럽게 선택된다.
이 단순하면서도 강력한 자연의 알고리즘은 컴퓨터 네트워크 분야, 특히 안트 콜로니 최적화(Ant Colony Optimization, ACO) 알고리즘의 기반이 되었다. 이 알고리즘은 최단 경로를 찾거나 복잡한 문제를 분산적으로 해결할 때 사용되며, 인터넷 트래픽 관리, 물류 배송, 로봇 경로 탐색 등 다양한 분야에서 활용되고 있다.
실제 개미의 행동 원리
- 무작위 탐색 시작: 개미들은 처음엔 무작위로 이동해 먹이를 탐색합니다.
- 페로몬 흔적 남기기: 먹이를 찾은 개미는 돌아가는 길에 페로몬을 남깁니다.
- 다른 개미의 추종: 다른 개미들은 페로몬이 더 진한 길을 선호해서 따라가며, 그 경로에 더 많은 페로몬을 추가합니다.
- 자연스러운 최적화: 시간이 지나면서 더 짧고 빠른 경로에 페로몬이 집중되며, 가장 효율적인 경로가 선택됩니다.
이 원리가 네트워크 라우팅에 어떻게 적용되는가?
Ant Colony Optimization (ACO)은 위의 행동을 수학적 모델로 변환해 다음과 같이 작동합니다:
1. 가상 개미(agent)의 경로 탐색
- 네트워크상의 각 노드(라우터 등)는 그래프의 정점(Vertex)입니다.
- 가상 개미들은 한 노드에서 다른 노드로 이동하며 경로(Edge)를 탐색합니다.
- 각 경로에는 가상의 페로몬 값이 저장되어 있고, 이는 해당 경로가 얼마나 좋았는지를 반영합니다.
2. 경로 선택 확률 계산
- 각 가상 개미는 현재 위치에서 다음 노드를 선택할 때, 아래 요소들을 고려하여 확률적으로 선택합니다.
$$
P_{ij} = \frac{(\tau_{ij})^\alpha \cdot (\eta_{ij})^\beta}{\sum_{k \in N_i} (\tau_{ik})^\alpha \cdot (\eta_{ik})^\beta}
$$
- $\alpha, \beta $: 페로몬과 휴리스틱 정보의 중요도 가중치
- $N_i $: 현재 노드 $i$에서 갈 수 있는 노드 집합
3. 경로 평가 및 페로몬 업데이트
- 여러 개미들이 목적지에 도달한 후, 경로의 성능에 따라 페로몬을 업데이트합니다.
- 더 짧고 빠른 경로에는 더 많은 페로몬을 남기고, 비효율적인 경로의 페로몬은 증발합니다 (자연의 원리 모사).
$$
\tau_{ij} + \Delta \tau_{ij}
$$
- $\rho$: 증발 계수 (0 < ρ < 1)
- $\Delta \tau_{ij}$: 새로 남겨질 페로몬 양
4. 최적 경로 수렴
- 시간이 흐르며 더 많은 개미들이 짧고 효율적인 경로를 선택하고,
- 결국 네트워크는 최적 또는 준최적의 라우팅 경로를 형성하게 됩니다.
ACO 시뮬레이션 코드
Python 코드는 개미 군집 최적화(ACO, Ant Colony Optimization) 알고리즘을 사용하여 그래프 상에서 출발지에서 도착지까지 최적 경로(최단 거리)를 찾는 시뮬레이션을 실행하는 예제입니다.
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
import random
# 그래프 생성
G = nx.Graph()
nodes = list(range(6))
edges = [
(0, 1, 2), (0, 2, 2), (1, 2, 1), (1, 3, 1),
(2, 3, 2), (2, 4, 3), (3, 5, 1), (4, 5, 2)
]
for u, v, w in edges:
G.add_edge(u, v, weight=w)
# 초기 페로몬 값 설정
pheromones = { (u, v): 1.0 for u, v, _ in edges }
# 휴리스틱 정보 (1 / 거리)
heuristics = { (u, v): 1.0 / w for u, v, w in edges }
# 파라미터
alpha = 1 # 페로몬 영향도
beta = 2 # 휴리스틱 영향도
rho = 0.1 # 증발 계수
Q = 100 # 페로몬 총량
# 시뮬레이션 설정
num_ants = 10
num_iterations = 10
start_node = 0
end_node = 5
best_path = None
best_length = float('inf')
# 시뮬레이션 루프
for iteration in range(num_iterations):
all_paths = []
all_lengths = []
for _ in range(num_ants):
path = [start_node]
current = start_node
visited = set(path)
while current != end_node:
neighbors = [n for n in G.neighbors(current) if n not in visited]
if not neighbors:
break
probs = []
for n in neighbors:
edge = (min(current, n), max(current, n))
tau = pheromones[edge] ** alpha
eta = heuristics[edge] ** beta
probs.append(tau * eta)
probs = np.array(probs)
probs /= probs.sum()
next_node = random.choices(neighbors, weights=probs, k=1)[0]
path.append(next_node)
visited.add(next_node)
current = next_node
length = sum(G[path[i]][path[i + 1]]['weight'] for i in range(len(path) - 1))
all_paths.append(path)
all_lengths.append(length)
if current == end_node and length < best_length:
best_length = length
best_path = path
# 페로몬 증발
for key in pheromones:
pheromones[key] *= (1 - rho)
# 페로몬 업데이트
for path, length in zip(all_paths, all_lengths):
for i in range(len(path) - 1):
u, v = sorted((path[i], path[i + 1]))
pheromones[(u, v)] += Q / length
# 결과 시각화
pos = nx.spring_layout(G)
edge_labels = { (u, v): f"{G[u][v]['weight']}" for u, v in G.edges() }
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=600)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
path_edges = list(zip(best_path, best_path[1:]))
nx.draw_networkx_edges(G, pos, edgelist=path_edges, width=4, edge_color='r')
plt.title(f"Best path: {best_path} (length: {best_length})")
plt.tight_layout()
plt.show()
코드 설명
- 여러 개미(가상 에이전트)를 출발지(0번 노드)에서 도착지(5번 노드)까지 보내서,
점점 더 짧은 길로 가는 경로를 학습하게 만듭니다. - 개미는 갈 때마다 페로몬(가상의 숫자 값)을 남기고, 그걸 따라가는 다른 개미가 효율적인 길을 더 많이 선택하게 됩니다.
1. 기본 라이브러리 불러오기
import matplotlib.pyplot as plt # 결과를 그래프로 보여주기 위한 시각화 도구
import networkx as nx # 그래프를 만들기 위한 도구 (노드와 엣지 연결)
import numpy as np # 확률 계산에 필요한 수학 도구
import random # 랜덤한 선택을 위한 도구
2. 그래프 생성
G = nx.Graph()
edges = [
(0, 1, 2), (0, 2, 2), (1, 2, 1), (1, 3, 1),
(2, 3, 2), (2, 4, 3), (3, 5, 1), (4, 5, 2)
]
for u, v, w in edges:
G.add_edge(u, v, weight=w)
- 노드 0~5까지 있고, 노드들 사이에 간선(Edge)이 연결돼 있습니다.
- 각 간선에는 거리(weight)가 정해져 있어요. 예를 들어 (0, 1, 2)는 0번과 1번 사이의 거리가 2입니다.
- G.add_edge(u, v, weight=w)는 두 노드를 연결하고, 거리 정보를 추가합니다.
3. 페로몬과 휴리스틱 정보 초기화
pheromones = { (u, v): 1.0 for u, v, _ in edges }
heuristics = { (u, v): 1.0 / w for u, v, w in edges }
- pheromones: 각 경로에 초기 페로몬 양을 1.0으로 설정합니다.
- heuristics: 짧은 거리일수록 높은 값을 주기 위해, 1 / 거리로 휴리스틱 값을 계산합니다.
4. 파라미터 설정
alpha = 1 # 페로몬의 영향력 (크면 기존 경로를 따름)
beta = 2 # 거리의 영향력 (클수록 짧은 경로를 더 선호)
rho = 0.1 # 페로몬 증발율 (0.1이면 매번 10%씩 줄어듦)
Q = 100 # 한 개미가 남기는 페로몬의 총량
- 이 값들을 조절하면 알고리즘의 성능과 경로 선택 방식이 바뀝니다.
5. 반복 시뮬레이션
num_ants = 10
num_iterations = 10
start_node = 0
end_node = 5
best_path = None
best_length = float('inf')
- 개미 10마리가,
- 총 10번의 반복(iteration) 동안 최적 경로를 찾습니다.
- 최종 목적지는 5번 노드, 시작은 0번 노드입니다.
6. 각 개미가 경로를 탐색
for _ in range(num_iterations):
paths = []
lengths = []
for _ in range(num_ants):
# 한 마리 개미의 경로 시작
path = [start_node]
current = start_node
visited = set(path)
while current != end_node:
# 아직 방문하지 않은 이웃 노드 찾기
neighbors = [n for n in G.neighbors(current) if n not in visited]
if not neighbors:
break # 막히면 중단
# 확률적으로 다음 노드 선택
probs = []
for n in neighbors:
edge = tuple(sorted((current, n)))
tau = pheromones[edge] ** alpha
eta = heuristics[edge] ** beta
probs.append(tau * eta)
probs = np.array(probs)
probs /= probs.sum()
next_node = random.choices(neighbors, weights=probs)[0]
# 경로 추가
path.append(next_node)
visited.add(next_node)
current = next_node
- 개미는 주변 경로 중 페로몬이 많고, 거리가 짧은 쪽을 확률적으로 선택합니다.
- random.choices()는 가중치 기반 랜덤 선택입니다.
neighbors = [n for n in G.neighbors(current) if n not in visited]
- 이 줄에서 현재 노드(current)의 이웃 노드들 중에서 아직 방문하지 않은 노드들만 후보로 삼습니다.
- 즉, 모든 노드를 다 가보지는 않고, 현재 위치에서 한 걸음씩 나아가며 하나의 경로만 형성합니다.
next_node = random.choices(neighbors, weights=probs, k=1)[0]- 이웃 노드 중에서 페로몬 + 거리(휴리스틱)를 기반으로 확률적으로 한 곳을 선택해 이동합니다.
- 개미는 시작점부터 도착점까지 가는 동안,모든 노드를 반드시 다 가보지 않습니다.
- 매 순간, 이웃 노드들 중에서 확률적으로 하나를 선택해서 전진합니다.
- 따라서 매 개미는 하나의 독립적인 경로를 형성하고, 그 길을 평가한 뒤 페로몬을 남깁니다.
7. 경로 평가 및 페로몬 업데이트
if current == end_node:
length = sum(G[path[i]][path[i+1]]['weight'] for i in range(len(path)-1))
paths.append(path)
lengths.append(length)
if length < best_length:
best_length = length
best_path = path
- 도착지까지 간 개미의 총 거리를 계산하고,
- 가장 짧은 경로(best_path)를 저장합니다.
# 기존 페로몬 일부 증발
for edge in pheromones:
pheromones[edge] *= (1 - rho)
# 좋은 경로일수록 많은 페로몬을 추가
for path, length in zip(paths, lengths):
for i in range(len(path) - 1):
u, v = sorted((path[i], path[i + 1]))
pheromones[(u, v)] += Q / length
- 페로몬은 시간이 지나면 점점 증발합니다.
- 하지만 짧은 경로를 찾은 개미일수록 더 많은 페로몬을 남깁니다.
8. 최종 결과 시각화
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='skyblue', node_size=600)
nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): G[u][v]['weight'] for u, v in G.edges()})
if best_path:
path_edges = list(zip(best_path, best_path[1:]))
nx.draw_networkx_edges(G, pos, edgelist=path_edges, width=4, edge_color='red')
plt.title(f"Best path: {best_path} (length: {best_length})")
plt.show()
- 그래프를 그려주고,
- 개미들이 찾은 최적 경로(best_path)를 빨간색으로 강조해서 보여줍니다.
728x90
'Python for Beginners' 카테고리의 다른 글
| Flet 메모장 (1) | 2024.11.14 |
|---|---|
| Flet로 만든 별다방 키오스크(Kiosk) (0) | 2024.11.11 |
| Flet GridView로 만든 계산기 (1) | 2024.11.08 |
| Flet ListTitle (0) | 2024.11.07 |
| Flet ListView (0) | 2024.11.05 |
