[논문 리뷰] RL4CO : A Unified Reinforcement Learning for Combinatorial Optimization Library

RL4CO" target="_blank" rel="noopener" data-mce-href="http://RL4CO">http://RL4CO

RL4CO: a Unified Reinforcement Learning for Combinatorial Optimization Library

 

※ 이 글은 위의 논문을 리뷰하여 작성한 것이다

 

Abstract

Deep Reinforcement Learning은 전통적인 방식보다 조합 최적화 문제에 더 나은 솔루션을 제공한다. RL4CO 라이브러리는 조합 최적화 문제에 대한 강화학습 솔루션을 제공하며, 모듈성과 확장성을 갖춘 최신 소프트웨어 관행을 활용한다. 이 라이브러리는 다양한 평가 체계를 통해 기초 RL 솔버의 성능을 벤치마크하며, 일부 최신 방법이 이전 방법보다 성능이 떨어질 수 있음을 발견했다. RL4CO는 연구 커뮤니티가 과학적 탐색을 소프트웨어 엔지니어링으로부터 분리하여 기존 방법과 비교할 수 있는 플랫폼을 제공하고자 한다.

 

1. Introduction

◈ 선행 연구 : CO (Combinatorial Optimization)

• CO는 그래프 이론, 스케줄링, 라우팅 문제 등과 같이 선택의 최적 조합을 찾는 문제에 적용되는 수학적 최적화의 한 분야이다.
• 대부분의 CO 문제는 NP-난해(NP-Hard)로 분류되어, 문제의 크기가 커짐에 따라 해결 공간이 지수적으로 증가한다.
• CO 문제는 주로 정확한 알고리즘, 근사 알고리즘, 휴리스틱 및 메타휴리스틱 방법 등을 포함한 다양한 전통적 최적화 기법을 사용하여 해결
• 크고 복잡한 문제는 많은 계산 자원을 필요로 하며, 때로는 실시간 해결이 어렵습니다.

 

◈ 선행 연구 : NCO (Neural Combinatorial Optimization)

• NCO는 딥러닝, 특히 신경망과 강화학습을 사용하여 조합 최적화 문제를 해결하는 현대적 접근 방식이다.
• NCO는 문제 해결 방법을 자동으로 학습하여, 문제 특정 휴리스틱 또는 솔버 설계에 대한 의존성을 줄인다.
• 훈련된 모델은 다양한 문제 인스턴스에 대해 적응할 수 있는 능력을 가지고 있어, 새로운 유형의 문제에 대해서도 빠르게 적용할 수 있다.
• 접근 방식은 통합된 구현과 일관된 평가 벤치마크의 부재로 인해 재현성과 동료 검증에 어려움을 겪을 수 있다.

 

◈ Contributions

 

이 연구에서는 RL4CO라는 새로운 강화 학습을 위한 조합 최적화 벤치마크를 소개하며, 이는 모듈식, 유연하며 통합된 방식으로 문헌에서 발췌한 기준선, 환경, 보일러플레이트를 포함한 라이브러리다. RL4CO는 철저한 테스트와 문서화를 통해 RL을 CO에 적용하는 최고의 관행을 탐색하고 기존 방법론들이 다양한 평가 메트릭에서 부진한 성능을 보일 수 있음을 보여준다. 이 연구는 또한 RL4CO의 유연성을 통해 실제 문제를 모델링할 수 있는 새로운 문제 영역을 벤치마크한다.

 

2. Preliminaries

조합 최적화(CO) 문제의 해결 공간은 일반적으로 그 크기에 대해 급격하게 증가한다. 이러한 CO의 해결 공간은 한 번에 해결책을 생성하는 NCO 솔버의 학습을 방해하기 때문에 이러한 점을 완화하기 위해, 자동회귀(AR) 방법들은 언어 모델과 유사한 방식으로 한 번에 한 단계씩 해결책을 생성하여 해결책의 실현 가능성과 제약을 다룬다. RL4CO에서는 이러한 방법들의 광범위한 적용 가능성을 고려하여 주로 AR 접근 방식을 벤치마킹에 중점을 둔다.

 

◈ Solving Combinatorial Optimization with Autoregressive Sequence Generation

 

1) Trainable Encoder $f(\theta)$

• 최초 단계에서는 문제 데이터(예를 들어, TSP에서는 노드/도시의 좌표)를 모델이 처리할 수 있는 형태로 인코딩.
• 이 인코딩은 학습 가능한 인코더, 즉 $f(\theta)$를 통해 이루어지며, 여기서 $\theta$는 학습 과정에서 학습되는 인코더의 매개변수를 나타낸다.
• 인코더는 문제 데이터를 고차원의 표현으로 변환하여 문제를 해결하기 위해 필요한 핵심적인 특성을 포착한다.$$ h = f_{\theta}(x)$$

 

2) Decoder $g(\theta)$

• 문제가 인코딩되면, 솔루션은 다음에 취할 "액션"(예: 방문할 다음 도시 선택)을 결정함으로써 점진적으로 구성
• 이 결정 과정은 디코더, $g(\theta)$에 의해 처리되며, 여기서 $\theta$는 디코더의 학습 가능한 매개변수를 나타낸다.
• 디코더는 현재의 부분 솔루션(예: 지금까지 방문한 도시 순서)을 입력으로 받아 다음에 취할 액션을 출력한다.

 

3) Decoder의 반복 액션

• 각 액션을 결정한 후(예: 다음에 방문할 도시 선택), 모델은 이 액션을 현재의 부분 솔루션에 업데이트하여 반영
• 이 업데이트된 부분 솔루션은 다음 액션을 결정하기 위해 다시 디코더에 입력됨
• 이 루프는 문제에 대한 완전한 솔루션이 생성될 때까지 반복 (예: TSP의 경우, 모든 도시를 정확히 한 번씩 방문하는 완전한 투어)

$$a_t \sim g_\theta(a_t|a_{t-1}, ..., a_0, h) \quad$$

$$p_\theta(a|x) \triangleq \prod_{t=1}^{T-1} g_\theta(a_t|a_{t-1}, ..., a_0, h)$$

 

 

 

 

◈ Training NCO Solvers via Reinforcement Learning 

 

NCO(Neural Combinatorial Optimization) 솔버는 강화학습(Reinforcement Learning, RL)이나 지도학습(Supervised Learning, SL) 방식으로 훈련될 수 있다. 강화학습 형식에서, NCO의 훈련 문제는 주어진 문제 분포 $P(x)$에서 선택된 문제 $x$에 대해, 솔루션 $a$의 확률 $p_{\theta}(a|x)$을 최대화하는 파라미터 ${\theta}^{*}$를 찾는 것으로 정의된다. 여기서 $R(a,x)$는 주어진 $x$에 대한 보상(음의 비용)을 의미

 

$$ \theta^* = \arg \max_\theta \mathbb{E}_{x \sim P(x)} \left[ \mathbb{E}_{a \sim p_\theta(a|x)} R(a, x) \right]$$

 

3. RL4CO

• RL4CO(Reinforcement Learning for Combinatorial Optimization)는 강화 학습 기법을 사용하여 조합 최적화 분야의 연구와 개발을 지원하는 라이브러리.
• RL4CO의 주요 목표는 연구자와 실무자가 다양한 설정에서 자동 회귀 신경 조합 최적화(AR-NCO) 솔버를 쉽게 훈련시키고 벤치마킹할 수 있도록 모듈화되고 유연한 프레임워크를 제공하는 것

 

3-1. Policy

이 모듈은 자동회귀적으로 해결책을 구성하기 위한 것으로, 다양한 AR NCO(자동회귀 비선형 제약 최적화) 솔버들을 조사한 결과, 다양한 CO(제약 최적화) 문제들에 걸쳐, 정책 네트워크 $\pi_{\theta}$(즉, 솔버)는 인코더 $f_\theta$ 디코더 $g_\theta$를 결합한 구조를 따른다.

 

$$\pi_\theta(a|x) \triangleq \prod_{t=1}^{T-1} g_\theta(a_t|a_{t-1}, ..., a_0, h)$$

 

더 나은 모듈성을 위해, RL4CO는 Initial Embedding, Context Embedding, Dynamic Embedding 등의 요소들을 사용한다.

 

◈ Initial Embedding  & Encoder 

• $f_{\theta}$의 구조는 두 가지 훈련 가능한 모듈로 구성됨: InitEmbedding & Encoder Block
• InitEmbedding 모듈은 일반적으로 문제의 특성을 잠재 공간으로 변환하며, 문제 특화적이다. 이와 대비하여, 인코더 블록은 종종 단순 멀티헤드 어텐션(MHA)을 포함하기도 함$$h = f_{\theta}(x) \triangleq \text{EncoderBlocks}(\text{InitEmbedding}(x))$$

◈ Context Embedding & Decoder

 

• 디코더 gθ는 인코더의 출력 h를 기반으로 솔루션을 자동 회귀적으로 구성한다. 솔루션 디코딩은 완전한 솔루션이 구성될 때까지 반복적인 단계를 포함한다. $$q_t = \text{ContextEmbedding}(h, a_{t-1:0})$$
  $$\bar{q}_t = \text{MHA}(q_t, W^g_k h, W^g_v h)$$
  $$\pi(a_t) = \text{MaskedSoftmax}(\bar{q}_t \cdot W^v_h, M_t)$$

◈ Dynamic Embedding

• DynamicEmbedding 모듈은 디코딩 도중 정보 관련 비선택 노드(예: VRP에서 방문하지 않은 도시들)의 '동적' 변화를 반영하여 다중 헤드 주의(MHA)와 소프트맥스의 키와 값들을 동적으로 업데이트 한다.
• 구체적으로, DynamicEmbedding이 포함된 디코더는 디코딩 중 정보 관련된 미선택 노드의 동적 변화를 반영하기 위해 MHA와 소프트맥스의 키와 값들을 동적으로 업데이트하는 구조로 정의. $$K_{g_t}, V_{g_t}, V_t = \text{DynamicEmbedding}(W_{g_k} h, W_{g_v} h, W_{v} h, a_{t-1:0}, h, x) $$ 

이 부분이 Decoder 부분에 추가된다고 보면 된다.

 

3.2. Environment

• 이 환경 구현은 고모듈성과 좋은 런타임 성능을 목표로 하는 PyTorch용 오픈 소스 RL 라이브러리인 TorchRL을 기반으로 한다.
• 이러한 설계 결정은 RL4CO의 범위를 벗어나더라도 환경 구현을 독립적으로 만들며, TorchRL이라는 커뮤니티 지원 라이브러리의 강력한 지원을 받는다.
• 데이터 이동에 TensorDicts를 사용함으로써 더욱 유연한 환경을 제공한다.

 

3.3. RL Algorithm

• 이 모듈은 환경(Environment)과 그 문제 인스턴스, 그리고 정책(Policy)을 취하고 REINFORCE, A2C, PPO 등의 강화 학습(RL) 알고리즘에 의해 정의된 $\theta$의 그래디언트를 계산하는 루틴을 정의한다.

 

[코드 리뷰] RL4CO on TSP Environment

 

• 필요한 라이브러리 로드
• 필자는 Policy를 Autoregressive 대신 Attention Model로 설정하였다. 

import torch

from rl4co.envs import TSPEnv
from rl4co.models.zoo import AttentionModel, AttentionModelPolicy
from rl4co.utils.trainer import RL4COTrainer

 

 

• TSP 문제의 환경 설정
• Attention Policy 정책 설정과 Attention Model 구조 설계
• 원래 논문 상에서는 노드 개수가 50개이지만 시간 절약을 위해 20개로 축소

env = TSPEnv(num_loc=20)

# Policy: neural network, in this case with encoder-decoder architecture
policy = AttentionModelPolicy(env.name,
                              embedding_dim=128,
                              num_encoder_layers=3,
                              num_heads=8,
                            )

# Model: default is AM with REINFORCE and greedy rollout baseline
model = AttentionModel(env,
                       baseline="rollout",
                       train_data_size=10000,
                       val_data_size=1000,
                       optimizer_kwargs={"lr": 1e-4},
                       )

 

 

 

• 장치 설정: CUDA가 실행 가능한 경우 cuda를 사용하고, 그 외 cpu를 사용하여 연산 장치를 설정
• 환경 초기화 및 배치 설정: 환경을 재설정하고, 배치 크기를 3으로 설정. 이는 동시에 3개의 TSP 문제 인스턴스를 생성하고 처리한다는 것을 의미. 생성된 초기 데이터는 설정된 장치(device)로 이동
• 모델 실행 및 결과 추출:  테스트 단계에서 실행하고, 탐욕적 방식으로 액션을 선택, 각 TSP 인스턴스에 대한 액션(경로)과 보상(비용의 음수 값)을 반환

# Greedy rollouts over untrained model
device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
td_init = env.reset(batch_size=[3]).to(device)
model = model.to(device)
out = model(td_init.clone(), phase="test", decode_type="greedy", return_actions=True)
actions_untrained = out['actions'].cpu().detach()
rewards_untrained = out['reward'].cpu().detach()

for i in range(3):
    print(f"Problem {i+1} | Cost: {-rewards_untrained[i]:.3f}")
    env.render(td_init[i], actions_untrained[i])​

 

 

• 결과 시각화

import matplotlib.pyplot as plt
for i, td in enumerate(td_init):
    fig, axs = plt.subplots(1,2, figsize=(11,5))
    env.render(td, actions_untrained[i], ax=axs[0])
    env.render(td, actions_trained[i], ax=axs[1])
    axs[0].set_title(f"Untrained | Cost = {-rewards_untrained[i].item():.3f}")
    axs[1].set_title(r"Trained $\pi_\theta$" + f"| Cost = {-out['reward'][i].item():.3f}")

 

 

 

 

위 시각화 결과는 훈련되지 않은 모델(좌)과 훈련된 모델(우)의 결과를 나란히 비교한다.

 

Codes" target="_blank" rel="noopener" data-mce-href="http://Codes">http://Codes

GitHub - ai4co/rl4co: A PyTorch library for all things Reinforcement Learning (RL) for Combinatorial Optimization (CO)

 

논문에 사용된 코드가 담긴 깃허브 주소이다. 전체 소스코드를 여기서 볼 수 있다.