융합탐구교실_탐구내용

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

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

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

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

몇 가지 지식

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

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

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

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

다익스트라 알고리즘

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

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

에이스타 알고리즘

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

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

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

피사룸 알고리즘

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

기본적인 작동 방식을 수식으로 표현하면 다음과 같다. 신기한 점은 유체의 흐름이나 전류로도 비슷한 모델링이 가능하다는 것이다.

마찬가지로 i, j를 각각의 노드라 할 때, L은 도로의 비용을 의미한다. 그리고 여기에 일정한 D(전도도)를 흘려주며 시작한다. 그리고 전도도가 일정하다는 가정 하에 이 시행을 반복하면, 두 노드 간의 압력 차이가 발생하는데, 이 압력 차에 따라 어떤 경로는 더 강화되고, 어떤 경로는 더 약화되는 피드백 구조가 만들어지는 것이다(일단 자세한 수학적 설명은 생략할게요..). 그 피드백 과정까지 예로 들어 수식으로 표현하면 다음과 같다.

어떤 경로의 전도도가 변화되는 것을 나타낸 함수이다.

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

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

시뮬레이션 프로그램 제작

어쨌거나 필요한 지식은 많지만, 우리가 하고자 하는 것은 당장 훌륭한 네비게이션 프로그램을 만드는 게 아니다. 이미 카카오맵이나 티맵에서 훌륭한 연구원 분들이 실시간 데이터를 분석하는 인공지능으로 각 도로의 가중치를 설정하여 에이스타를 기반으로 움직이는 네비게이션 프로그램을 만들어두셨다.

우리는 단지 점균류에서 착안한 새로운 아이디어를 수학적으로 모델링하고(최근이지만 사실 이미 누군가가 모델링 해두셨다.) 그것들을 실험할 프로그램만 있으면 된다. 그래서 각각 다익스트라, 에이스타, 피사룸 알고리즘을 시뮬레이션 할 수 있는 실험도구를 만들었다. 기본적으로 파이썬인데, Numpy 에서 수학적 모델링을 거쳐 Pygame으로 실행하는 구조이다. 너무 길어서 이 문서에는 첨부하지 않겠다.

실험

실험은 결국 점균류 알고리즘이 기존의 알고리즘과 어떤 차이가 있고, 활용에 있어서 어떤 가능성이 있는지 알아보기 위함이다. 이 실험의 설계는 근본적으로 각 알고리즘들의 작동원리에 기인하여 예상되는 특성을 가설로 하여 진행하였다.

실험에서 알아볼 것은 정확성, 연산 효율성, 적응성이다. 3개를 알아볼 것이므로 각 주제 당 실험 하나씩을 진행할 것이다.

실험1_정확성

가장 단순하다. 얼마나 다익스트라 알고리즘을 정답으로 설정하고, 피사룸 알고리즘이 그것에서 얼마나 벗어나는지 살펴볼 것이다.

다익스트라 알고리즘은 그것이 어떻게 최단 경로를 뽑아내는지와 별개로 노드를 찾아 모든 경로를 다 계산하기에 항상 정확하다. 반면 피사룸 알고리즘은 모든 경로에 같은 전도도를 주고 점점 어느 것을 강화시키는 방식이다.

가설은 다음과 같이 정한다. 수학적으로 피사룸 또한 정확하기에 모든 랜덤한 경우의 수에서 다익스트라와 같은 경로를 선택할 것이다.

실험2_연산 효율성

랜덤한 상황에서 연산의 수와 연산 시간을 비교한다. 여기서는 피사룸 알고리즘은 다른 방식으로 작동한다. 다른 알고리즘들은 간선들의 비용을 더하는 식으로 연산하지만, 피사룸 알고리즘은 시행과 반복이다. 즉, 계산 하는 과정 자체가 다르기에 단순히 계산 수를 비교하는 건 의미가 없고 계산 시간을 비교하는 것이 의미가 있다.

또한 이 실험에서는 다익스트라와 에이스타 알고리즘의 결과도 주목할만하다. 둘은 같은 연산을 시행하므로 연산 수에 주목할 필요가 있으며, 휴리스틱이 적용된 알고리즘과 그렇지 않을 알고리즘의 차이를 분석해보자.

가설은 다음과 같이 정한다. 피사룸은 단순 덧셈 연산보다 수학적으로 복잡한 과정을 여럿 반복하므로 다른 알고리즘보다 연산 시간이 길 것이다. 한편, 에이스타는 휴리스틱으로 인해 다익스트라보다 연산 수가 짧을 것이다.

실험3_적응성

여기서는 피사룸의 고유한 연산 특징에 주목한다. 다익스트라와 에이스타는 상황에 따라 매번 연산을 반복하여 상황이 변화했을 때도 똑같은 방식을 시행을 거듭한다. 반면 피사룸은 각각의 시행마다 노드 별로 다른 전도도의 값이 생성되고, 그걸 저장하기에 상황이 변화하였을 때 기존의 데이터 값을 이용할 수 있다.

즉 다양한 동적 상황에 대해 빠르게 대응할 수 있는지를 확인하는 것이며, 과연 피사룸이 어떻게 움직일지에 주목한다.

가설은 다음과 같이 정한다. 피사룸은 다른 알고리즘들에 비해 상황이 변화하였을 때 더 빠르게 움직일 것이다.