경로 탐색 알고리즘 구현 및 실험

탐구 동기, 목표, 아이디어

굉장히 추상적으로 시작했다. 주제를 선정하는데 어떤 범위를 한정짓지는 않았고, 일상의 궁금증을 바탕으로 다양한 주제 후보들을 선정했다. 그러다보니 언젠가부터 생물을 모방한 기술과 아이디어에 빠져있었다. 그러다 어디선가 본 듯한 점균류가 먹이를 쫓는 과정이 자동차 네비게이션의 움직임과 비슷해보여 더 나은 경로 탐색 알고리즘을 만드는데 적용해볼 수 있지 않을까 생각했다.

그래서 목표는 더 나은 경로 탐색 알고리즘을 만드는 것이었다. 더 나은이란 보다 현실과 비슷한 상황을 모델링하여 실제로 더 나은 경로와 컴퓨터로 도출하는 예상 경로의 오차를 줄이고, 그 연산을 더 효과적으로 하는 것을 의미했다. 하지만 실제로 그것을 만들어 구현까지 하기에 기본적인 지식, 동기(지속적인 비즈니스 모델, 즉 자본) 등이 부족했기에 기존의 알고리즘과 새로 고안한 알고리즘의 특성에 대해 시뮬레이션으로 분석하고 실험하는 것을 목표로 설정했다.

몇 가지 지식

본격적인 점균류의 모델을 가져오기 전에 필요한 지식들이 있다. 기존의 것이 무엇인지 알아야한다. 가장 기본적인 경로 탐색 알고리즘인 다익스트라, 에이스타 알고리즘에 대해 살펴보겠다. 솔직히 조합론과 이산수학의 기초, 그 중에서도 그래프 이론에 대해 아무것도 모르는 상태에서 달려드는 것이 좀 아쉽다. 수학적 용어를 최대한 배제한 채 가장 간단하게 줄글로 설명해보겠다.

기본적으로 가장 좋은 해(최적해) 를 찾는 알고리즘은 단순히 경로 탐색 뿐만 아니라 많은 공학이나 경제학 설계에서 응용된다. 세상에는 그래프로 표현하고 해석하여 일반해를 찾을 수 있는 함수보다 그렇지 않은 함수들이 훨씬 더 많이 존재하기 때문에 단순히 최적해를 찾는 범용 알고리즘은 상당히 다양하다. 대표적으로 우리가 조사할 Physarum solver처럼 점균류에서 아이디어를 얻은 SMA(Slime Mould Algorithm)와 개미의 군집 활동에서 아이디어를 얻은 ACO(Ant Colony Optimization algorithm) 등이 있다. 이 알고리즘들을 보고 메타휴리스틱(Meta Heuristic) 알고리즘 이라고 한다. 이 알고리즘들은 여러 개의 후보해들을 놔두고, 확률적으로 각 후보들의 적합도를 계산한 뒤 괜찮은 후보 주위로 범위를 좁혀 가장 나은 해를 찾아간다.

쉽게 말해 이러한 메타휴리스틱은 풀어야할 문제가 확정되지 않은 상태에서 적절한 휴리스틱을 찾고, 생성하고, 조정하거나 선택하도록 만들어진 상위 수준의 절차이다. 쉽게 설명한다면서, 적절한 휴리스틱을 찾는다는 어려운 말은 썼는데, 여기서 휴리스틱 알고리즘이란 정해진 문제에서 가장 빠르고 효율적으로(최소 연산 등..) 최적해를 찾는 알고리즘이다. 휴리스틱 알고리즘은 단순히 최적해를 찾는 것을 넘어 그 가장 빠르고 효율적인 방법을 이용한다는 특징이 있다. 즉 일반적으로 어려운 문제에서 메타휴리스틱을 휴리스틱으로 넘어간 뒤 본격적으로 문제에 대한 답을 찾아나가는 것이다.

우리는 도로에서 길을 찾는 알고리즘들에 대해 알아볼 것이다. 크게 가장 대표적인 방식인 다익스트라(Dijkstra)와 에이스타(A*)에 대해 알아볼 것이며, 휴리스틱이라는 개념의 이해를 바탕으로 왜 다익스트라는 휴리스틱을 이용하지 않았고, 에이스타는 휴리스틱을 이용하였는지에 주목할 것이다. 그리고선 가장 빠르고 효율적으로 최적해를 찾고자 하지만 휴리스틱이 아닌 완전히 새로운 방법으로 최적해 찾기를 시도하는.. 알고리즘인 Physarum solver에 대해 알아볼 것이다.

다익스트라 알고리즘

다익스트라 알고리즘은 쉽게 말해 노드를 설정한 뒤 각 노드를 경로로 잇고, 경로별로 비용함수를 설정한다. 그리고 출발 지점에서 각 노드까지 도달하는 최소 비용 경로를 선택하고, 해당 노드로부터 다른 노드로 까지 최소 비용을 모두 계산하는 과정을 반복한다. 이 과정에서 출발 지점으로부터 각 노드까지 도달하는 최소비용 리스트를 계속 업데이트 하여 해를 구해낸다.

$$ d(v) = \min\left(d(v),\ d(u) + w(u,v)\right) $$ 이 알고리즘을 수식화 하면 위와 같다. 여기서 d(v)는 출발 노드에서 v까지 현재까지 구한 최단거리를 의미하는데, 만약 d(u) + w(u, v), 즉 u라는 노드를 거쳐 v로 가는 비용까지 계산해서 고려하는 것이다. 그리고 현재 v까지 가는 비용과 u를 경유해서 v까지 가는 비용 중 더 저렴한 비용을 골라 해를 구해내는 것이다.

에이스타 알고리즘

에이스타 알고리즘은 기본적으로 다익스트라 알고리즘과 구조가 같다. 하지만, 한가지를 더 고려하여 결과(최소 비용 루트)는 다익스트라와 같게 하되, 연산 수를 획기적으로 줄인다. $$ f(n) = g(n) + h(n) $$

f(n)을 다음 노드 탐색을 결정하는 평가 값, g(n)을 출발점부터 현재 노드까지 실제 비용, 그리고 h(n)을 현재 노드부터 목적지까지 추정 비용이라고 할 때 단순히 g(n)만 고려하여 모든 길을 일일히 뒤졌던 다익스으라와 달리 에이스타는 h(n)이라는 목적지까지 추정비용, 즉 하나의 힌트를 더 제공함으로써 목적지와 멀어지는 루트는 가차없이 버려버린다. 그래서 에이스타의 연산 수가 다익스트라보다 훨씬 적은 것이다.

여기서 h(n)을 제공한 것이 바로 휴리스틱을 적용한 것이다. 단순히 어느 경로가 최적일까를 고민했던 다익스트라와는 달리 에이스타는 최적 경로를 가장 적은 연산의 수로 구하기 위해 h(n)을 의도적으로 첨가했다. 이것이 두 알고리즘의 가장 큰 차이라 할 수 있다. 실제로 현재 우리가 사용하는 지도 앱이나 네비게이션에는 이 에이스타 알고리즘이 이용된다.

피사룸 알고리즘

피사룸 알고리즘은 점균류가 최적 경로를 찾는 알고리즘을 수학적으로 단순화한 것으로, 앞의 두 알고리즘과는 접근 방식이 아얘 다르다. 에이스타처럼 최적해를 가장 빠르게 구하려고 하지만, 특정한 힌트를 제공하는 전통적인 휴리스틱과 다르게 본인이 네트워크를 변화시킨다는 점이 가장 큰 특징이다.

기본적인 작동 방식을 수식으로 표현하면 다음과 같다. 신기한 점은 유체의 흐름이나 전류로도 비슷한 모델링이 가능하다는 것이다. $$ Q_{ij} = \frac{D_{ij}}{L_{ij}}\left(p_i-p_j\right) $$ 마찬가지로 i, j를 각각의 노드라 할 때, L은 도로의 비용을 의미한다. 그리고 여기에 일정한 D(전도도)를 흘려주며 시작한다. 그리고 전도도가 일정하다는 가정 하에 이 시행을 반복하면, 두 노드 간의 압력 차이가 발생하는데, 이 압력 차에 따라 어떤 경로는 더 강화되고, 어떤 경로는 더 약화되는 피드백 구조가 만들어지는 것이다(일단 자세한 수학적 설명은 생략할게요..). 그 피드백 과정까지 예로 들어 수식으로 표현하면 다음과 같다.

$$ \frac{dD_{ij}}{dt}

f\left(\left|Q_{ij}\right|\right)

\mu D_{ij} $$ 어떤 경로의 전도도가 변화되는 것을 나타낸 함수이다.

이 알고리즘은 매우 최근은 2020년 쯤부터 고안되었으며, 아직 그렇게 일반적으로 알려지진 않았다. 하지만, 실제로 위의 두 알고리즘과 그 특성을 비교하고, 실제 경로 최적화 모델에 적용하면 어떨까 싶어서 가져왔다.

여기까지가 아주 기본적인 이론이다. 이것들을 컴퓨터를 통해 시뮬레이션 하고, 연산 수, 결과, 연산 시간들을 비교하는 게 실험이다.