AI 최적화의 혁신: 유전 알고리즘으로 분기한정 검색 전략 자동 생성
Gwen Maudet과 Grégoire Danoy의 연구는 유전 알고리즘을 활용한 새로운 분기한정(B&B) 검색 전략 생성 방법인 GP2S를 제시합니다. GP2S는 기존 방법보다 계산 비용이 적으면서도 우수한 성능을 보이며, 다양한 최적화 문제에 효과적인 대안을 제시합니다.

정수 프로그래밍에서 정확한 솔루션을 찾는 분기한정(Branch and Bound, B&B) 방법은 검색 공간을 트리 구조로 재귀적으로 분할하는 알고리즘입니다. 이 과정에서 트리 내에서 다음으로 탐색할 하위 문제를 결정하는 검색 전략은 매우 중요합니다. 기존에는 주로 사람이 설계한 휴리스틱(heuristic)이 사용되었지만, 모든 문제 유형에 효과적이지 못했습니다. 최근에는 신경망을 활용하는 접근 방식이 등장했지만, 계산 비용이 과도하게 높다는 단점이 있었습니다.
Gwen Maudet과 Grégoire Danoy가 발표한 논문 "Search Strategy Generation for Branch and Bound Using Genetic Programming"은 이러한 문제에 대한 혁신적인 해결책을 제시합니다. 바로 GP2S(Genetic Programming for Search Strategy) 라는 새로운 머신러닝 기법입니다. GP2S는 유전 알고리즘을 이용하여 B&B 검색 전략 휴리스틱을 자동으로 생성합니다. 이는 지능적인 의사결정을 하면서도 계산 비용을 낮추는 것을 목표로 합니다.
GP2S는 B&B 노드의 특징과 문제의 특징을 결합하여 노드의 질을 평가하는 정책(policy)을 함수로 정의합니다. 그리고 이 노드 순위를 기반으로 최선우선탐색(best-first search)을 사용하여 검색 전략 정책을 정의합니다. 유전 알고리즘을 사용하여 정책 공간을 탐색하고, 훈련 세트에서 가장 좋은 성능을 달성하는 정책을 선택합니다.
연구 결과는 놀랍습니다. GP2S는 SCIP 솔버의 표준 방법, 최근의 그래프 신경망 기반 방법 및 수작업 휴리스틱과 비교하여 평가되었습니다. 훈련 세트와 유사한 인스턴스와 더 큰 인스턴스에서 세 가지 유형의 어려운 최적화 문제에 대한 평가에서, GP2S는 최고 기준선보다 최대 2% 느린 수준이었지만, SCIP보다 평균 11.3% 빠른 속도 향상을 달성했습니다. 더 나아가 MIPLIB 2017 데이터 세트에서도 테스트되었으며, 서로 다른 인스턴스 부분집합에서 여러 휴리스틱을 생성했습니다. 15배 더 많은 인스턴스와 15배 더 긴 시간 제한 내에서 10가지 경우 중 7가지에서 SCIP의 평균 성능을 능가했고, 실현 가능한 솔루션의 수나 최적성 간격 측면에서 대부분의 실험에서 GP2S 방법이 앞섰습니다.
GP2S는 계산 비용을 최소화하면서 효율적인 검색 전략을 자동으로 생성하여 정수 프로그래밍 문제 해결에 새로운 가능성을 제시했습니다. 이는 AI 기반 최적화 기술의 발전에 중요한 기여를 할 것으로 기대됩니다. 향후 연구에서는 더욱 다양한 문제 유형에 대한 GP2S의 성능 평가 및 개선이 필요할 것으로 보입니다.
Reference
[arxiv] Search Strategy Generation for Branch and Bound Using Genetic Programming
Published: (Updated: )
Author: Gwen Maudet, Grégoire Danoy
http://arxiv.org/abs/2412.09444v2