Sakana AI의 ALE-Agent, AtCoder Heuristic Contest 058에서 인간 전문가 제치고 우승

섹션별 상세

ALE-Agent는 4시간 동안 진행된 AHC058 경기에서 최종 1위를 달성했다. 경기 시작 2시간 만에 첫 제출로 1위에 올랐으며 이후 인간 전문가들과의 순위 경쟁 끝에 우승을 확정 지었다.

대회 과제는 여러 계층의 기계 간 의존 관계를 분석하여 최적의 생산 계획을 수립하는 것이었다. ALE-Agent는 이를 해결하기 위해 탐욕 알고리즘으로 초기 해를 생성하고 담금질 기법으로 이를 정교화하는 이단계 접근법을 사용했다.

가상 파워(Virtual Power)라는 독창적인 휴리스틱 지표를 도입하여 아직 가동되지 않은 기계의 잠재적 가치를 평가에 반영했다. 이를 통해 단순한 현재 스코어 최적화가 아닌 장기적인 생산 효율을 고려한 의사결정을 수행했다.

AI의 강점인 방대한 구현 능력을 활용하여 다양한 근방 조작(Neighborhood Operations)을 프로그램에 포함했다. 전형적인 국소 조작뿐만 아니라 탐욕 알고리즘을 재실행하여 계획을 크게 변경하는 조작을 통해 탐색 범위를 획기적으로 넓혔다.

휴리스틱 콘테스트(Heuristic Contest): — 정답이 명확하지 않은 복잡한 문제에 대해 제한된 시간 내에 가능한 최선의 해를 찾는 프로그래밍 경진 대회이다. 단순 알고리즘 구현을 넘어 문제 특성에 맞는 효율적인 탐색 전략과 평가 지표 설계 능력이 요구된다.
담금질 기법(Simulated Annealing): — 금속을 가열한 후 천천히 식히며 결정 구조를 안정화하는 과정에서 착안한 확률적 최적화 알고리즘이다. 초기에는 좋지 않은 해로의 이동도 허용하여 국소 최적해를 탈출하고 전역 최적해를 찾을 가능성을 높인다.
탐욕 알고리즘(Greedy Algorithm): — 매 선택의 순간마다 당장 눈앞에 보이는 최적의 선택지를 고르는 방식의 알고리즘이다. 계산 속도가 매우 빠르지만 전체적인 최적해를 보장하지는 않으므로 주로 초기 해를 생성하거나 다른 알고리즘의 보조 수단으로 활용된다.
강건성(Robustness): — 다양한 입력 데이터나 환경 변화에도 성능이 크게 저하되지 않고 안정적으로 유지되는 특성을 의미한다. 최적화 문제에서는 특정 케이스에 치우치지 않고 보편적으로 우수한 성능을 내는 알고리즘의 능력을 평가할 때 사용된다.