외판원 순회 문제를 해결하는 모습
Problems
외판원 순회 문제(TSP, Traveling Salesman Problem)는 컴퓨터 과학 분야에서 중요한 문제로 취급되어 왔습니다.
완전 탐색으로 이 문제를 해결한다면, 도시의 수가 N개일 때, N!이라는 경우의 수를 모두 탐색해야지 답을 도출해낼 수 있었습니다. 만약 도시의 수가 20개라면 2,432,902,008,176,640,000이라는 매우 큰 경우의 수가 되고, 컴퓨터가 해결할 수 없게 됩니다.
그래서 다항 시간 내에 답을 "근사"할 수 있는 메타 휴리스틱(Meta-Heuristic) 기법을 활용해 이 문제를 해결해보려고 했습니다.
담금질 기법 - Simulated Annealing
전역 최적화 문제에 대한 메타 휴리스틱 기법 중 하나입니다.
광대한 탐색 범위 내에서 전역 최저점(Global Minimum)을 찾는 것을 목표로 동작합니다. 즉, 전역 최적해에 대한 근사치를 구해 냅니다.
담금질 기법의 동작 방법은 금속 공학의 담금질에서 파생되어 왔습니다. 금속재료를 가열한 뒤 조금씩 냉각하며 결함을 줄이는 것처럼, SA 알고리즘은 해를 반복적으로 개선시키며 현재의 해 근방에 있는 해를 임의로 찾습니다.
지역 최저점과 전역 최저점
유전 알고리즘 - Genetic Algorithm
생명과학의 유전 현상에서 영감을 얻어 개발된 알고리즘입니다. 전역 최적화 문제에 대한 메타 휴리스틱 기법입니다.
다윈의 진화론을 지탱하는 가장 중요한 개념 중 하나인 "자연 선택"을 기반으로 동작합니다. 또한, 생물의 진화를 모방한 진화 연산의 대표적인 기법으로써, 실제 세대의 진화 과정에서 많은 부분을 따라합니다.
유전 알고리즘
적용 및 결과
담금질 기법과 유전 알고리즘을 외판원 순회 문제에 적용시켜 봤습니다.
(아래 소개해드리는 코드는 모두 Python으로 구현되었습니다.)
담금질 기법
self.cities = TSP.generates_cities(30) # 초기 상태를 정의
t = 100000.0 # 초기 온도
delta = 0.9999 # 온도 감률
k = 1 # 볼츠만 상수
lim = 0.005 # 임계 온도
n = len(self.cities)
best_e = TSP.tour_length(self.cities) # 현재 상태를 평가
best_cities = cities = self.cities
while t > lim:
e1 = TSP.tour_length(cities)
# 현재 상태를 변이시킴
e2 = TSP.tour_length(new_cities) # 인접 상태의 평가 함수 값
p = np.exp((e2 - e1) / (k * t)) # 인접 상태로 전이할 확률
if p < random.random(): # 1 - p의 확률로 인접 상태로 전이
e1 = e2
cities = new_cities
if e1 < best_e: # 결과 값 갱신
best_e = e1
best_cities = cities
t *= delta # 현재 온도를 조금씩 낮춤유전 알고리즘
self.cities = TSP.generates_cities(20) # 초기 상태를 정의
best_cities = self.cities
best_e = TSP.tour_length(best_cities)
population = [self.Gene_Generation() for _ in range(100)] # 한 세대당 100명
for g in range(100): # 100세대 동안 진행
population_sorted = self.Compute_Performance(population) # 현재 세대를 평가하고 정렬
if best_e > population_sorted[0][1]: # 결과 값 갱신
best_cities = population_sorted[0][0]
best_e = population_sorted[0][1]
children = self.Create_Children(population_sorted) # 현재 세대를 기반으로 새로운 세대 생성
new_generation = self.Mutate_Population(children) # 새로운 세대를 일정 확률로 변이
population = new_generation더 자세한 코드는 깃허브에서 확인하실 수 있습니다.