MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design

당신이 수백 개의 정류장이 있는 배송 트럭 경로를 정리하거나, 가장 가치 있는 물건들을 최대한 많이 담을 수 있도록 여행 가방을 싸는 것과 같이 거대하고 복잡한 퍼즐을 풀려고 노력하고 있다고 상상해 보십시오. 이것들은 "조합 최적화 문제(combinatorial optimization problems)"로, 가능한 배열의 수가 너무 방대하여 가장 빠른 슈퍼컴퓨터조차 그 모든 경우를 다 확인할 수 없기 때문에 악명 높게 어렵습니다. 수십 년 동안 인간은 이 퍼즐들을 빠르게 풀기 위해 특수한 "경험 법칙(heuristics)"을 작성하려고 노력해 왔습니다. 하지만 여기에는 함정이 있습니다. 격자형 도로 구조를 가진 도시에서 완벽하게 작동하는 규칙이 구불구불하고 원형인 도로가 있는 도시에서는 처참하게 실패할 수 있다는 점입니다. 이것이 바로 "노 프리 런치(No Free Lunch, 공짜 점심은 없다)"의 현실입니다. 즉, 모든 상황에 적용되는 단 하나의 마법 같은 규칙은 존재하지 않습니다.

최근 과학자들은 이야기를 쓰고 질문에 답하는 것과 같은 종류의 AI인 "대규모 언어 모델(LLM)"을 사용하여 이러한 규칙들을 자동으로 만들어내기 시작했습니다. 그러나 대부분의 AI 실험은 마치 학생에게 단 한 권의 작고 특정된 교과서로만 공부시키는 것과 같았습니다. AI는 그 특정 책에 나온 문제들을 푸는 데는 매우 능숙해지겠지만, 만약 약간 다른 유형의 퍼즐을 준다면 혼란에 빠질 것입니다. 이는 마치 요리사에게 완벽한 오믈렛을 만드는 법을 가르치되, 오직 특정 농장의 달걀만을 사용하도록 가르치는 것과 같습니다. 만약 다른 농장의 달걀을 준다면 오믈렛은 망가질 수 있습니다. 기존의 AI 훈련 방식은 단순히 "잘했어" 또는 "못했어"라고만 말하는 매우 단순한 피드백에 의존했습니다. 왜 그런지, 혹은 어디에서 실수가 발생했는지에 대한 설명 없이 말입니다.

조지아 공과대학교 연구진이 개발한 새로운 프레임워크인 MOSAIC가 등장했습니다. MOSAIC를 단일 교과서를 암기하려는 한 명의 학생이 아니라, 서로 다른 유형의 퍼즐을 위해 훈련된 다양한 "전문가" 규칙들이 모여 있는 거대한 살아있는 도서관이라고 생각해 보십시오. MOSAIC는 AI에게 단순히 "더 나은 규칙을 만들어라"라고 요청하는 대신, 고도의 심리전인 '고양이와 쥐 게임'을 설정합니다. 이 게임은 AI의 현재 규칙들을 "적대적(adversarial)" 퍼즐 제작자 팀과 맞붙게 합니다. 이 퍼즐 제작자들 또한 AI이며, 이들의 유일한 임무는 현재의 규칙을 무너뜨리기 위해 특별히 설계된 가장 어렵고 혼란스러운 퍼즐을 만드는 것입니다. 규칙이 실패했을 때, 시스템은 단순히 "당신이 졌다"라고 말하는 데 그치지 않습니다. 대신 스마트한 의사결정 나무(decision tree)를 사용하여 어떤 종류의 퍼즐이 규칙을 무너뜨렸는지 정확히 파악하고, 그 퍼즐과 학습된 교훈을 거대한 격자의 특정 "셀(cell)"에 저장합니다. 시간이 흐름에 따라 이 격자는 다양한 전문가들의 집합체로 채워집니다. 격자형 도시를 위한 규칙 하나, 밀집된 동네를 위한 규칙 하나, 길고 구불구불한 경로를 위한 규칙 하나와 같은 식입니다. 시스템은 이렇게 저장된 교훈들을 사용하여 더욱 진화된 규칙을 만들어내며, 각자가 자신의 영역에서 숙련된 전문가인 팀을 구축합니다.

연구진은 이 아이디어를 세 가지 고전적인 문제, 즉 외판원 문제(Traveling Salesman Problem, 최단 경로 찾기), 배낭 문제(Knapsack Problem, 최대 가치 담기), 그리고 용량 제한 차량 경로 문제(Capacitated Vehicle Routing Problem, 제한된 트럭 공간 내 물품 배송)에 대해 테스트했습니다. 그 결과 MOSAIC가 다른 최첨단 AI 방식들을 지속적으로 능가한다는 것을 발견했습니다. 다른 방식들이 퍼즐이 약간만 변해도 어려움을 겪는 반면, MOSAIC의 "전문가 팀"은 변화를 쉽게 처리하며 종종 완벽한 정답에 훨씬 더 가까운 해답을 찾아냈습니다. 예를 들어, 외판원 문제에서 MOSAIC의 최상위 규칙 팀은 차순위 방식보다 최대 22% 더 정확했습니다.

아마도 더욱 흥激한 점은, MOSAIC가 만들어낸 "적대적" 퍼즐들이 기존 방식들이 만든 것보다 훨씬 더 다양하고 도전적이었다는 사실입니다. 이 시스템은 이전 방식들보다 "특성 공간(feature space, 퍼즐 구조의 다양한 유형)"을 33% 더 많이 커버했으며, 이는 시스템이 훨씬 더 다양한 실제 시나리오를 다루는 법을 배웠음을 의미합니다. 이 연구는 문제를 '공진화적 전투(co-evolutionary battle)'로 취급함으로써—즉, 퍼즐은 약점을 노출하기 위해 더 어려워지고, 규칙은 이를 고치기 위해 더 똑똑해지는 과정—우리가 단순히 몇 가지 예시를 암기하는 것이 아니라, 문제의 지형을 진정으로 이해하는 AI를 구축할 수 있음을 시사합니다. 이는 한 가지 분야에 대해 모든 것을 아는 단 한 명의 천재를 훈련시키는 것에서, 세상의 아주 작은 구석이라도 자신만의 전문 지식을 가진 다양한 전문가 공동체를 구축하는 것으로의 전환입니다.