[ICML 2024] 확산 모델(Diffusion Model)을 이용한 조합 최적화 풀기

기계 학습 분야의 최고 학술 대회 중 하나인 International Conference on Machine Learning (ICML)은 AI와 데이터 과학 연구의 최전선을 이끄는 행사를 매년 개최하고 있습니다. 올해 오스트리아 빈에서 열린 ICML 2024에서도 다양한 학계의 연구자들이 모여 최신 연구 방향을 공유했습니다. LG AI연구원 Data Intelligence (DI) 랩은 이번 ICML 2024에서 최근 각광받고 있는 생성형 모델(Generative Model)의 한 종류인 확산 모델(Diffusion Model)에 강화학습(Reinforcement Learning)을 결합하여 조합적 최적화 문제를 해결하는 "CADO: Cost-Aware Diffusion Solvers for Combinatorial Optimization through RL fine-tuning"이라는 논문을 발표하고, 연구자들과 함께 AI 기술을 활용한 조합 최적화 알고리즘에 대해 논의했습니다.

본 포스팅에서는 LG AI연구원이 실제 산업에서 적용하는 문제를 조합 최적화 문제로 바라보는 과정을 간단하게 설명하고, 확산 모델을 활용한 조합 최적화 연구 3편을 소개하고자 합니다.

1. Sun et al. Difusco: Graph-based diffusion solvers for combinatorial optimization. NeurIPS 2023. 2. Yoon et al. CADO: Cost-Aware Diffusion Solvers for Combinatorial Optimization through RL fine-tuning. ICML Workshop 24 (2nd SPIGM). 3. Sanokowski et al. A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization. ICML 2024.

조합 최적화란?

조합 최적화(Combinatorial Optimization)는 최적화 분야의 한 갈래로, 유한한 이산(Discrete) 해(Solution)들의 후보 집합에서 최적의 목표값(Objective Value)을 만족하는 해를 찾는 분야입니다. 유명한 조합적 최적화 문제 중 하나인 외판원 문제(Traveling Salesman Problem)^[4]를 예로 들어 설명해 보겠습니다. 외판원이 방문해야 하는 도시들의 위치가 정해져 있을 때, 모든 도시를 한 번씩 들르면서 총 이동거리가 가장 짧도록 도시의 순서를 정하는 것이 외판원 문제입니다. 이 경우 외판원 문제의 목표값은 도시 간 총 이동거리가 됩니다.

이미지 1. 외판원 문제(Traveling Salesman Problem) 예시^[5]

산업계의 조합 최적화 문제

현재 산업계의 다양한 문제들을 조합 최적화로 볼 수 있습니다. 예를 들어 물류 서비스나 공항에서의 비행기 스케줄링, 최근 각광받고 있는 유전자 분석과 시스템 생물학 등이 해당합니다. LG AI연구원에서 현재 진행 중인 인쇄 회로 기판 설계 자동화(Printed Circuit Board, PCB) 과제 문제 역시 조합적 최적화 문제의 한 종류로 볼 수 있습니다.

인쇄 회로 기판이란 전자 기기에 들어가는 핵심 부품으로, 아래 그림을 보면 황금색 핀들이 연한 초록색 배선들로 서로 이어져 있는 것을 확인할 수 있습니다.

이미지 2. 인쇄 회로 기판(Printed Circuit Board, PCB) 예시^[6]

LG AI연구원의 PCB 자동 배선 과제는 부품들의 배선이 서로 겹치지 않으면서 가장 효율적으로 배치되는 구조를 도출하는 것이 목표입니다. 조합 최적화 문제로 바라보면 다음과 같은 직교 스타이너 트리 패킹 문제(Rectilinear Steiner Tree Packing Problem, RSTPP)로 변환됩니다. 아래 그림에서 같은 색의 부품들을 서로 충돌 없이 이어주는 여러 배선들 중 목표값인 총 배선길이가 가장 낮은 최적해를 찾아야 합니다.

이미지 3. RSTPP 형태로 변환된 PCB 인스턴스(instance)와 해(solution)^[7]

조합 최적화 문제 해결 방법

그렇다면 이러한 조합 최적화 문제의 최적해는 어떻게 구할 수 있을까요? 외판원 문제의 경우, 가장 직관적이고 쉬운 방법은 도시가 n개 있을 때 방문할 수 있는 모든 경우의 수 n!에서 각 도시 방문 순서에 대한 방문 길이를 계산하고, 그 중 가장 짧은 해를 선택하는 것입니다. 이러한 방법을 무차별 대입 알고리즘(Brute Force)이라고 합니다. 간단하면서도 가장 정확한 해를 구할 수 있지만, 도시의 수가 늘어날수록 계산해야 하는 조합의 수가 기하급수적으로 늘어난다는 단점이 있습니다.

아쉽게도 외판원 문제는 정확한 해를 적당한 시간 안에 계산하기가 불가능하다는 것이 이론적으로 증명된 NP-hard 문제에 해당합니다^[12]. 앞서 언급한 대부분의 조합 최적화 문제들 역시 NP-hard에 속합니다. 따라서, n이 큰 조합 최적화 문제를 해결할 때에는 비록 정답은 아니더라도 최대한 정답에 가까운 근사해를 가급적 빠른 시간 안에 푸는 다양한 방법으로 접근하게 됩니다.

조합 최적화의 근사해를 구하는 알고리즘은 크게 2가지로 분류할 수 있습니다:

1. 휴리스틱(Heuristic) 알고리즘: 사람이 문제의 특성을 고려하여 직접 디자인하는 방법입니다. 여러 조합 최적화 문제들에 대해 빠른 시간 내에 좋은 해를 제공한다는 장점이 있어 지금도 주류로 사용되는 방식입니다. 다만, 이러한 휴리스틱 기반의 방식은 조합 최적화 문제마다 오랜 시간을 들여 알고리즘을 만들어야 하고, 문제가 복잡할수록 알고리즘 설계의 난이도 역시 상승하는 문제점이 있습니다.

2. 인공 신경망(Neural Network) 활용: 주어진 조합 최적화 문제의 패턴을 스스로 학습하여 적절한 최적해를 제공하는 방식입니다. 크게 최적화 문제의 해로 이루어진 데이터를 미리 모아놓고 비슷한 학습을 진행하는 지도학습(Supervised Learning, SL), 스스로 여러 해를 선택하면서 더 나은 목표값을 생성하는 해를 선택하도록 발전하는 강화학습(Reinforcement Learning, RL)로 나누어집니다.

Pathfinder: PCB 자동 배선

LG AI연구원은 현재 RSTPP (Rectilinear Steiner Tree Packing Problem) 문제를 효과적으로 해결하기 위해 Pathfinder++라는 휴리스틱 알고리즘을 자체 개발하여 PCB 자동 배선을 수행하고 있습니다. 이는 기존 네트워크 관련 알고리즘인 Pathfinder^[14]를 개선한 것으로, 다음과 같은 특징을 가지고 있습니다:

1. 제약 조건 처리: 각 배선이 제약 조건을 위반할 경우, 해당 영역에 페널티를 부과합니다.

2. 반복적 개선: 페널티가 부과된 영역을 피해 재배선을 수행하며, 이 과정을 반복하여 최종적으로 모든 제약 조건을 만족하는 배선 결과를 도출합니다.

3. 산업 요구사항 반영: PCB 배선 간 간격 유지, 부품 패드와 배선 간 거리, PCB 층간 수직 Via (전기적 연결을 위한 구멍) 개수 조절 등 다양한 계열사의 요구사항을 고려할 수 있도록 설계되었습니다.

이미지 4. Pathfinder++ Heuristic 알고리즘 작동 예시

현재 Pathfinder++는 LG 계열사의 여러 실제 제품을 대상으로 검증되었고, 대다수의 제품에 대해서 주요 요구사항을 반영한 배선이 가능함을 확인했습니다. 그러나 다음과 같이 개선이 필요한 부분들도 아직 존재합니다.

1. 세분화된 요구 사항 처리: 각 계열사와 제품마다 요구되는 PCB 제약 조건이 매우 다양합니다. Pathfinder++는 현재 필수적인 요구 사항들은 잘 만족시키고 있지만, 수십에서 수백 개에 이르는 세부적인 요구 사항들을 모두 충족하도록 매번 알고리즘을 새로 디자인하는 것은 비효율적이고 비용이 많이 듭니다.

2. 정성적 고려사항 반영: 실제 산업용 PCB 설계 시 정량적으로 명확히 표현하기 어려운 다양한 권고 사항들이 존재합니다. 엔지니어는 이러한 정성적인 요소들을 경험적으로 반영할 수 있지만, 알고리즘에 적용하는 것은 상대적으로 쉽지 않습니다.

이러한 문제들을 해결하기 위해, LG AI연구원에서는 Pathfinder++를 다음과 같이 개선하는 방향으로 연구를 확장하고 있습니다.

1. 사람 데이터 기반 학습: 기존 LG 계열사 엔지니어들이 설계한 실제 PCB 배선 데이터를 학습하여, 단순히 제약 조건을 만족시키는 것을 넘어 실제 설계와 유사한 결과를 도출할 수 있도록 합니다.

2. 생성형 모델 활용: 최근 여러 분야에서 강력한 성능을 보여주는 확산 모델(Diffusion Model)을 활용하여 인공 신경망이 기존 PCB 배선 데이터를 자연스럽게 학습하도록 합니다. 이를 통해 복잡한 패턴과 암묵적인 설계 규칙을 포착할 수 있을 것으로 기대됩니다.

이러한 접근 방식을 통해 더욱 유연하고 효과적인 PCB 자동 배선 시스템을 개발할 수 있을 것입니다. 다양한 요구 사항을 처리하고, 엔지니어의 경험적인 지식을 효율적으로 반영할 수 있기를 기대합니다.

확산 모델을 활용한 조합 최적화 연구

생성형 모델의 한 종류인 확산 모델(Diffusion model)^[13]은 원래 이미지 분야를 풀기 위해서 제안되었습니다. 하지만 최근 들어서 조합 최적화 분야에서도 문제 입력 시 적절한 근사해를 생성하도록 고안된 확산 모델들이 좋은 성과를 내고 있으며, 관련 논문 3편을 소개해 드릴 예정입니다. 확산 모델의 자세한 구조적 설명은 LG AI연구원에서 이전에 발행한 [NeurIPS 2021] 1편: Generative model - Diffusion model Review^[14]에서 확인할 수 있습니다.

이미지 5. 확산 모델^[16]의 이미지 생성 예시와 조합 최적화 해 생성 비교.
본 이미지는 가상의 이미지로 실제와 관련이 없습니다

1. Difusco: Graph-based Diffusion Solvers for Combinatorial Optimization^[1]

Difusco는 확산 모델을 활용하여 조합 최적화를 푸는 방식을 제안한 논문입니다. 이 논문에서는 이미지의 확산 모델을 학습하던 방법을 활용합니다. 주어진 조합 최적화 문제의 다양한 인스턴스들에 대한 최적해 여러 개를 미리 생성합니다. 이후 확산 모델에서 자주 사용되는 Forward Noising Process, Backward Denoising Process를 통해, 모델이 Noise에 가까운 Solution에서도 다시 최적해를 복원할 수 있는 방향으로 학습을 진행하게 됩니다.

따라서, 학습이 잘 되었을 경우에 아래 그림과 같은 Denoising 과정을 통해 주어진 조합 최적화 문제의 해를 근사하게 됩니다. 추가적으로 그림에서 나타난 것처럼 조합 최적화 문제에서는 기본적으로 Noising의 대상이 그래프 형태로 표현되기에, 그래프 구조 형태의 데이터를 잘 처리하는 Graph Neural Network의 일종인 Anisotropic Graph Neural Network^[10]를 사용하게 됩니다. 이러한 점은 기존에 Image 데이터를 잘 처리하는 Convoluational Neural Network 기반의 U-net 구조를 활용하던 기존 연구와의 차이점입니다.

이미지 6. 이미지와 조합 최적화에서의 확산 프로세스 비교

2. CADO: Cost-Aware Diffusion Solvers for Combinatorial Optimization through RL Fine-tuning^[2]

DIFUSCO^[1]는 확산 모델을 활용하여 크기가 큰 조합 최적화에서도 좋은 성능을 보여주었지만, 몇 가지 한계점이 있습니다. 우선 조합 최적화에서 해가 좋고 나쁨을 나누는 기준은 단순히 최적해와 얼마나 비슷한지 보다, 실제 해의 목표값이 얼마나 좋은지에 따라서 결정됩니다.

이미지7. 외판원 문제의 2가지 해를 비교

위 이미지에서 두 개의 Solution을 비교해 보겠습니다. A solution과 B solution은 모두 최적해와 비교했을 때 2개 틀린 Edge를 선택했지만, 실제 목표값은 B가 더 좋게 나타납니다. 따라서 조합 최적화에서 좋은 근사해를 찾기 위해서는, 단순히 학습하였던 최적해와 비슷한 Solution만 생성하는 것이 아니라, 생성 과정에서 가급적 좋은 목표값의 해를 생성하도록 확산 모델을 다시 Finetuning해야 할 필요성이 생기게 됩니다.

우리 연구에서는 학습된 확산 모델을 다시 강화학습을 통해 파인 튜닝(Finetuning)하였습니다. 생성된 해가 좋은 목표값을 가지고 있을 경우 더 큰 보상(Reward)을 제공하여, 학습된 생성 모델이 더 좋은 목표값의 해를 생성하도록 합니다. 이러한 기법은 Chat GPT나 이미지 생성 모델 등 다양한 생성 모델에서도 널리 활용되고 있습니다.

이미지 8. 학습된 확산 모델을 다시 RL finetuning하는 CADO framework

확산 모델에서 강화학습으로 Finetuning을 위해 확산 모델의 Markov Decision Process (MDP)를 아래 그림과 같이 정의하고 REINFORCE^[11]알고리즘을 활용하여 학습을 진행합니다.

이미지 9. 확산 프로세스를 다시 Markov Decision Process (MDP)로 정의

이미지 10의 수식을 통해 DIFUSCO와 CADO의 차이를 조금 더 구체적으로 확인할 수 있습니다. DIFUSCO의 학습 함수인 연두색 SL Objective는 학습 과정에서 목표값을 고려하지 않고, 단순하게 실제 최적해와 비슷한 모양으로 학습하도록 유도했습니다. 반면 CADO는 실제로 생성되는 해의 목표값을 좋게 만드는 방향으로 설계되었습니다.

이미지 10. Supervised Objective (DIFUSCO)와 Reinforcement Learning Objective (CADO) 비교

최종적으로 목표값을 고려하면서 Finetuning된 CADO는 기존 DIFUSCO 대비 조합 최적화에서 사용되는 성능 평가 지표를 기준으로 20% ~ 70%가량 개선된 성능을 보여주었습니다.

3. A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization^[3]

DIFSUCO^[1]와 CADO^[2]의 공통적인 한계점은 처음에 확산 모델을 학습하기 위해 충분한 최적해로 이뤄진 데이터가 미리 준비되어야 하는 점입니다. 조합 최적화 문제가 크거나 어려울 경우, 이러한 데이터셋을 충분한 크기로 준비하는 것 역시 비용이 많이 들거나 불가능할 수도 있습니다. 물론 CADO에서 제안한 강화학습 기법을 사용할 경우, 학습 데이터 없이도 확산 모델을 학습할 수는 있습니다. 다만, 일반적으로 크고 어려운 조합 최적화 문제를 학습 데이터 없이 바로 강화학습하면 학습 효율이 떨어지고 불안정하다는 문제점이 있습니다. 비유하자면 초등학생한테 적절한 기초 교과 지식 없이 상대성 이론을 바로 알려주는 느낌입니다.

본 논문에서는 이러한 어려움을 다음과 같은 아이디어를 활용하여 해결했습니다. 먼저 조합 최적화에서 나올 수 있는 가능한 해 $x$에 대해서 다음과 같은 Boltzmann 분포를 정의합니다. 이 분포는 $q_{\beta }\left(x\right)=\frac{e^{-\beta c\left(x\right)}}{Z} \mathrm{where} Z={\sum }_x{e}^{-\beta c\left(x\right)}$로 정의됩니다. 여기서 $c\left(x\right)$는 해 $x$의 목표값을 의미합니다. $\beta$는 분포가 얼마나 치우쳤는지를 의미합니다.

$\beta =0$일 때, $q_{\beta }$는 Uniform Distribution이고, ${\pi }_{\theta }$가 커질수록 좋은 목표값이 나올 확률이 올라가는 분포가 됩니다. 극단적으로 $\beta =\infty$일 경우에는 최적해만 생성하게 됩니다. 확산 모델이 생성하는 해의 분포인 ${\pi }_{\theta }$가 ${\pi }_{\theta }\approx q_{\beta }$가 되도록 ${\pi }_{\theta }$를 학습하게 됩니다. 사용되는 Loss 함수는 Reverse KL Divergence라고 불리는 $KL\left({\pi }_{\theta }\right|\left|q_{\beta }\right)$가 사용됩니다.

처음에는 $\beta =1$일 때를 기준으로 학습하고, 이후에 점차 $\beta$값을 키워나가면서 더 성능이 좋은 분포를 학습하게 됩니다. $\left(KL\right({\pi }_{\theta }\left|\right|q_1)\to KL({\pi }_{\theta }\left|\right|q_2)\to \dots \to KL({\pi }_{\theta }\left|\right|q_{100})\to \dots ).$ 이러한 과정을 통해서 처음부터 학습하기가 어려운 분포인 $q_{\infty }$가 아닌 단계별로 적절한 난이도의 $q_{\beta }$를 생성할 수 있도록 유도합니다. 결과적으로 학습 데이터가 없이도 복잡한 확산 모델이 안정적으로 학습될 수 있습니다.

결론

본 포스팅에서는 LG AI연구원에서 다루고 있는 조합 최적화 문제에 대해 간단히 소개하고, 확산 모델을 활용하여 조합 최적화 문제를 푸는 다양한 논문을 살펴보았습니다. NP-hard의 특성상 조합 최적화를 푸는 데에는 다양한 접근방법이 활용될 수 있으며, 확산 모델로 한정 지어도 각기 다른 개성과 장단점을 가지는 다양한 방식이 존재할 수 있음을 확인했습니다. 특히 조합 최적화에 확산 모델을 사용할 때는 이미지에서와 달리 목표 값을 적절히 고려하는 것이 중요함을 알 수 있었습니다.

앞에서 설명한 것처럼, LG AI연구원에서 진행하고 있는 PCB 배선 문제는 일반적인 조합 최적화 문제보다도 고려해야 하는 요소들이 훨씬 많아 난이도가 높습니다. 그래서 이번에 소개한 최고 수준의 성능을 보여주는 확산 모델들로도 당장 상용 엔지니어를 대체할 수 있는 완벽한 PCB 배선을 하기는 다소 어려운 상황입니다. LG AI연구원은 확산 모델과 현재 진행하고 있었던 Rule 기반의 Heuristic 알고리즘을 결합하는 식으로 성능을 단계별로 발전시켜 나가려고 합니다.

또한 조합 최적화 문제를 풀기 위해서 한 가지 접근 방식을 고집하기보다는, 최근 많은 각광을 받고 있는 거대 언어모델이나 강화학습 등을 활용하는 다양한 방안들도 같이 고려하면서 진행하고 있습니다. 앞으로 저희가 얻은 연구 성과들을 PCB 칩 설계 및 공정 최적화뿐만 아니라 여러 산업 분야의 조합 최적화로 연구의 범위를 계속 확장할 예정입니다. 

▶ICML 2024 Review Series : ICML 2024에서 확인한 Tabular Learning 연구 동향