당신이 오래되고 약간 찢어진 지도 더미를 비교하며 미스터리를 풀려는 탐정이라고 상상해 보십시오. 각 지도는 동일한 일반 영역을 보여주지만, 어떤 지도는 도로가 누락되어 있고, 다른 지도는 추가적인 우회로가 있으며, 어떤 곳은 잉크가 서로 다른 위치에서 번져 있습니다. 당신의 임 р는 비록 누락되거나 번진 부분을 건너뛰어야 하더라도, 모든 지도에 존재하는 가장 긴 경로를 찾는 것입니다. 이것이 바로 컴퓨터 과학에서 유명한 퍼즐인 "최장 공통 부분 수열(Longest Common Subsequence)" 문제의 본질입니다. 이는 두 사람 사이의 공유된 DNA를 찾거나, 서로 다른 버전의 노래 속에 숨겨진 동일한 멜로디를 포착하는 것의 디지털 버전입니다.

하지만 현실 세계는 무질서합니다. 때로는 지도의 "누락된 부분"이 단순히 무작위적인 것이 아니라, 특정한 규칙을 따르기도 합니다. 예를 들어, 어떤 도로는 짧은 우회로일 경우에만 건너뛸 수 있거나, 누락된 다리는 너무 멀리 뻗어나가지 않는 경로로 대체되어야 한다는 식의 규칙 말입니다. 이러한 복잡성은 "간격 제약(gap constraints)"이라는 층위를 더합니다. 단 두 개의 지도만 있다면 컴퓨터는 이를 해결하는 데 능숙합니다. 하지만 만약 열 개, 스무 개, 혹은 백 개의 지도가 있고, 부분을 건너뛰는 규칙이 지도상의 위치에 따라 달라진다면 어떻게 될까요? 갑자기 이 퍼즐은 악몽이 됩니다. 전통적인 컴퓨터들은 길을 잃고 혼란에 빠지며, 종종 최선의 답을 찾는 것을 포기해 버립니다. 이것이 바로 이 논문이 탐구하는 구체적인 과학적 영역입니다. 즉, 컴퓨터가 길을 잃지 않고 이러한 무질서하고 규칙이 많은 퍼즐을 헤쳐 나갈 수 있도록 돕는 방법입니다.

---

논문의 이야기: 컴퓨터에게 최선의 경로를 "느끼는" 법 가르치기

이 논문의 저자인 마르코 주카노비치(Marko Djukanović)와 그의 팀은 **가변 간격 최장 공통 부분 수열 문제(Variable Gapped Longest Common Subsequence Problem, VGLCSP)**라고 불리는 특히 까다로운 버전의 퍼즐을 다루었습니다. 간단히 말해, 엉킨 실타래 더미 속에서 가장 긴 공통 실을 찾으려고 노력한다고 상상해 보십시오. 규칙에 따르면 일부 매듭(간격)은 건너뛸 수 있지만, 그 건너뛰는 크기는 바로 그 지점의 실의 색상과 질감에 따라 달라집니다. 실이 굵으면 큰 간격을 건너뛸 수 있고, 실이 가늘면 아주 조금만 건너뛸 수 있는 식입니다.

오랫동안 이 문제를 해결하는 가장 좋은 방법은 **빔 서치(Beam Search)**라고 불리는 방법을 사용하는 것이었습니다. 빔 서치를 거대한 안개 낀 숲을 탐험하는 등산객 그룹이라고 생각해 보십시오. 모든 경로에 한 명의 등산객을 모두 보내는 대신(그것은 시간이 너무 오래 걸릴 것입니다), 그룹은 고정된 수의 팀(즉, "빔")으로 나뉩니다. 길의 갈림길마다 그들은 어떤 경로가 가장 유망해 보이는지를 결정하기 위해 "수작업으로 제작된" 규칙책을 사용합니다. 기존의 규칙책은 인간 전문가들에 의해 작성되었습니다. 그것은 꽤 괜찮았지만, 숲이 더 커지고 규칙이 더 복잡해짐에 따라 등산객들은 잘못된 선택을 하기 시작했고, 종종 끝에 있는 보물을 놓치곤 했습니다.

이 논문은 이러한 인간이 작성한 규칙책이 너무 경직되어 있다고 주장합니다. 즉, 문제가 정말 어려워지면 무너지는 "강건성(robustness)" 결여를 겪습니다. 이를 해결하기 위해 팀은 단순히 규칙책을 수정하는 것에 그치지 않고, 컴퓨터가 스스로 규칙을 쓰는 법을 가르치기로 결정했습니다.

"신경 진화된" 코치

인간이 규칙을 쓰는 대신, 저자들은 신경망(인간의 뇌에서 영감을 얻은 유형의 컴퓨터 뇌)을 사용하여 등산객들을 위한 코치 역할을 하게 했습니다. 하지만 여기에는 반전이 있습니다. 그들은 정답을 보여줌으로써 이 코치를 가르친 것이 아닙니다(왜냐하면 아직 이 어려운 문제들에 대한 정답을 아무도 모르기 때문입니다). 대신, 그들은 유전 알고리즘을 사용했는데, 이는 디지털 버전의 진화와 같습니다.

20개의 서로 다른 코치로 구성된 인구 집단을 상상해 보십시오. 각 코치는 약간씩 다른 "뇌"(신경망의 서로 다른 가중치 세트)를 가지고 있습니다.

1. 테스트: 각 코치는 등산객들을 숲으로 보냅니다(컴퓨터가 그 코치의 조언을 사용하여 빔 서치를 실행합니다).
2. 점수: 가장 긴 공통 실을 찾아낸 코치가 높은 점수를 받습니다.
3. 진화: 가장 뛰어난 코치들은 서로 "교배"하여 새로운 코치를 "번식"시키며, 서로의 뇌를 섞습니다. 가장 못한 코치들은 버려집니다. 흥미를 유지하기 위해 몇몇 무작위 "돌연변이"들도 투입됩니다.
4. 루프: 이 과정은 계속 반복됩니다. 코치들은 숲을 암기해서가 아니라, 주변 숲의 형태를 바탕으로 어떤 경로가 유망해 보이는지를 학습함으로써, 등산객들을 안내하는 데 점점 더 능숙해집니다.

그 결과물은 **신경 진화된 휴리스틱(neuro-evolved heuristic)**입니다. 이것은 "항상 작은 간격을 건너뛰어라"와 같은 정적인 규칙을 따르는 가이드가 아닙니다. 대신, 전체적인 그림—등산객들이 얼마나 진행되었는지, 지도가 몇 장 남았는지, 그리고 현재 규칙이 얼마나 유연한지—을 살펴보고 다음에 취할 경로에 대해 똑똑하고 직관적인 추측을 내놓습니다.

팀워크의 힘

연구진은 AI 코치가 훌륭하긴 했지만 완벽하지는 않다는 것을 발견했습니다. 때때로, 기존의 인간 규칙책이 특히 단순한 퍼즐에서는 실제로 더 나았습니다. 그래서 그들은 하이브리드 팀을 만들었습니다. 그들은 AI 코치의 직관과 인간 규칙책의 논리를 결과적으로 결합했습니다. 그들은 단순히 점수를 더한 것이 아니라, 두 의견을 바탕으로 경로의 순위를 매기고 가장 높은 순위를 받은 경로가 승리하도록 했습니다. 이 "앙상블(ensemble)" 접근 방식은 안전망 역할을 하여, 한 가이드가 실수하더라도 다른 가이드가 이를 잡아낼 수 있도록 했습니다.

연구 결과

팀은 두 가지 유형의 도전 과제를 통해 새로운 방법을 테스트했습니다:

1. 합성 숲(Synthetic Forests): 다양한 수의 지도(2개에서 10개까지)와 다양한 규칙 복잡성을 가진 컴퓨터 생성 퍼즐.
2. 실제 세계의 숲(Real-World Forests): 실제 생물학적 데이터(DNA 서열)를 기반으로 하며, 실제 분자가 행동하는 방식에서 유도된 규칙을 가진 퍼즐.

결과는 명확했습니다. 합성 퍼즐의 경우, 새로운 Limsbs-ensemble 방식(하이브리드 팀)이 기존 방식보다 32개 사례 중 20개에서 더 나은 솔루션을 찾아냈고, 8개에서는 동률을 기록했습니다. 단 4개 사례에서만 패배했습니다. 저자들은 통계적 테스트를 실시했으며, 이는 이러한 개선이 단순한 운이 아니라 유의미한 것이었음을 시사했습니다.

실제 생물학적 퍼즐에서도 새로운 방식은 더욱 인상적이었습니다. 기존 방식이 12개 중 20개 사례에서 이겼고, 7개에서 동률을 기록했으며, 단 1개 사례에서만 패배했습니다. 논문은 기존 방식이 가장 고전했던 가장 어렵고 복잡한 퍼즐에서 개선 효과가 가장 눈에 띄었다고 언급했습니다.

핵심 요약

이 논문은 이 문제를 영원히 "해결했다"고 주장하는 것이 아닙니다. 퍼즐은 여전히 어렵고, 솔루션은 여전히 근사치(최선의 추측)입니다. 그러나 이 연구는 **학습 기반 가이드(learning-based guidance)**가 강력한 도구임을 시사합니다. 컴퓨터에게 엄격한 인간의 규칙을 따르도록 강요하는 대신, 스스로 문제에 대해 생각하는 법을 진화하게 함으로써 우리는 더 나은 답을 더 빠르게 찾을 수 있습니다.

저자들은 이 접근 방식이 문제가 무질서하고 복잡해질 때 특히 유용하다고 결론지었습니다. 또한 그들은 실제 생물학에 기반한 새로운 "실제 세계" 테스트 케이스를 도입했으며, 이를 통해 다른 연구자들이 자신의 아이디어를 테스트할 수 있기를 희к 바랍니다. 현재의 성공은 시뮬레이션과 특정 데이터 세트에 국한되어 있지만, 이 논문은 이 "신경 진화된" 전략이 게임의 규칙이 순간마다 변하는 DNA, 단백질, 시계열 데이터를 분석하는 데 있어 게임 체인저가 될 수 있음을 시사합니다. 미래에는 이 AI 코치들이 더 큰 숲과 더 복잡한 생물학적 미스터리를 다룰 수 있도록 가르치는 일이 포함될 수 있다고 그들은 암시합니다.