딥러닝으로 조합 최적화의 한계를 뛰어넘다: Deep k-grouping의 등장

Deep k-grouping은 대규모 그래프 및 초그래프에서의 k-그룹핑 문제를 효과적으로 해결하는 새로운 비지도 학습 기반 조합 최적화 프레임워크입니다. OH-PUBO, GPU 가속 알고리즘, 지니 계수 기반 어닐링 전략을 통해 기존 방법들을 능가하는 성능을 보였습니다.

최근 AI 컴퓨팅은 과학적 발견 분야에서 놀라운 성과를 거두고 있습니다. 이러한 성공은 이제 조합 최적화(CO, Combinatorial Optimization) 영역으로 확장되고 있습니다. 그러나 기존의 비지도 학습 신경망 솔버들은 대규모 그래프와 초그래프에서의 k-그룹핑 문제(예: 그래프/초그래프 색칠, 분할)를 해결하는 데 어려움을 겪어 왔습니다. 계산 프레임워크의 한계 때문입니다.

이러한 한계를 극복하기 위해 등장한 것이 바로 Deep k-grouping입니다. Sen Bai 등 연구진이 제안한 이 프레임워크는 비지도 학습 기반의 혁신적인 CO 프레임워크로, 다음과 같은 주요 기여를 하고 있습니다.

• OH-PUBO (One-hot encoded Polynomial Unconstrained Binary Optimization)의 도입: 그래프와 초그래프에서의 k-그룹핑 문제(그래프/초그래프 색칠 및 분할 등)를 모델링하는 새로운 방법입니다. 일반적인 이진 변수 대신 원-핫 인코딩된 다항식을 사용하여 문제를 표현합니다.
• GPU 가속 알고리즘: 대규모 k-그룹핑 CO 문제를 효율적으로 해결하기 위해 GPU 가속 알고리즘을 통합하여 학습 파이프라인을 강화했습니다.
• 지니 계수 기반 연속 완화 어닐링 전략: 해의 이산성을 강화하면서 동시에 지역 최적점에 빠지는 것을 방지합니다. 이 전략은 연속적인 완화를 통해 문제를 해결하고, 지니 계수를 이용하여 해의 분포를 평가하여 점진적으로 최적해로 수렴하도록 합니다.

Deep k-grouping은 대규모 OH-PUBO 목적 함수를 미분 가능한 손실 함수로 완화하여 비지도 학습 방식으로 최적화합니다. 이는 기존 신경망 솔버 및 SCIP, Tabu와 같은 고전적 휴리스틱 알고리즘보다 뛰어난 성능을 보이는 것으로 실험을 통해 입증되었습니다. 이 연구는 AI가 조합 최적화 문제를 해결하는 데 있어 새로운 가능성을 제시하며, 앞으로 더욱 발전된 AI 기반 최적화 알고리즘의 개발에 중요한 발판이 될 것으로 예상됩니다.