RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization
원문 초록
Combinatorial optimization (CO) aims to efficiently find the best solution to NP-hard problems ranging from statistical physics to social media marketing. A wide range of CO applications can benefit from local search methods because they allow reversible action over greedy policies. Deep Q-learning (DQN) using message-passing neural networks (MPNN) has shown promise in replicating the local search behavior and obtaining comparable results to the local search algorithms. However, the over-smoothing and the information loss during the iterations of message passing limit its robustness across applications, and the large message vectors result in memory inefficiency. Our paper introduces RELS-DQN, a lightweight DQN framework that exhibits the local search behavior while providing practical scalability. Using the RELS-DQN model trained on one application, it can generalize to various applications by providing solution values higher than or equal to both the local search algorithms and the existing DQN models while remaining efficient in runtime and memory.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
민첩 관측 위성을 활용한 해상 이동 표적 관측 스케줄링을 위한 암묵적 Q-러닝 기반 개미 군집 최적화
Implicit Q-learning-bootstrapped ant colony optimization for maritime moving-target observation scheduling with agile satellites
민첩 지구 관측 위성을 활용한 해상 이동 표적 관측 스케줄링은 동적이고 순서 의존적인 조합 최적화(combinatorial optimization) 문제입니다. 해수면 표적은 지속적으로 이동하므로, 표적의 움직임과 위성 궤도 기하 구조에 따라 관측 가능 윈도우가 가변적으로 변합니다. 따라서 스케줄러는 시간 윈도우, 자세 기동 및 탑재 자원 제약 조건 하에서 작업 선택, 위성 할당, 관측 윈도우 선택, 관측 순서를 공동으로 결정해야 합니다. 본 논문에서는 다중 위성 해상 이동 표적 관측 스케줄링을 위해 암묵적 Q-러닝(implicit Q-learning)을 부트스트랩한 개미 군집 최적화(ant colony optimization) 방법인 IQACO를 제안합니다. IQACO는 작업 선택 정책을 직접 학습하는 대신, 오프라인 암묵적 Q-러닝 모듈을 구성적 개미 군집 최적화에 임베딩하여 페로몬 요인, 휴리스틱 요인 및 증발률을 적응적으로 조절합니다. 압축된 탐색 상태 표현은 페로몬 분포, 현재 및 역대 최고 해의 품질, 반복(iteration) 진행 상황을 포착합니다. 온라인 스케줄링 중에는 개미 군집 최적화가 실행 가능한 관측 시퀀스를 구성하는 동시에, 학습된 정책이 현재 탐색 상태에 맞춰 탐색 동작을 조정합니다. 다양한 규모와 위성 구성을 가진 14개 시나리오에서의 실험 결과, IQACO는 비교 알고리즘들보다 지속적으로 우수한 성능을 보였으며 기존 개미 군집 최적화 대비 평균 목적 함수 값을 2.86%~9.41% 향상시켰습니다. 추가 비교 및 보완 실험은 다양한 스케줄링 조건과 문제 설정 전반에서 본 방법의 효과성과 강건성을 입증합니다. 이러한 결과는 오프라인 가치 학습이 제약이 있는 해상 이동 표적 관측 스케줄링을 위한 효과적인 적응형 탐색 제어 메커니즘을 제공함을 보여줍니다.
강화학습의 수학적 방법론
Mathematical methods of reinforcement learning
강화학습(RL)은 확률론, 최적화, 작용소 이론의 도구들에 점점 더 깊이 기반을 두고 있다. 이 서베이는 현대 강화학습 알고리즘의 설계와 분석을 뒷받침하는 수학적 구조를 체계적으로 정리한다. 마르코프 결정 과정(MDP)과 벨만 작용소(Bellman operator)에서 출발하여, 수렴 보장과 수렴 속도를 이끌어 내는 수축 사상(contraction mapping), 단조성(monotonicity), 고정점 이론을 가치 반복(value iteration), 정책 반복(policy iteration), 시간차(temporal-difference) 방식에 걸쳐 강조한다. 이어서 최적화 관점을 전개하는데, 확률적 근사(stochastic approximation)와 마팅게일(martingale) 방법, 볼록 쌍대성(convex duality), 그리고 미러/근위(mirror/proximal) 방법과 정규화의 연결 관계를 다룬다. 함수 근사(function approximation)는 선형 및 비선형 설정 모두를 다루며, 안정화(stabilization), 오차 분해(error decomposition), 그리고 종속 데이터 및 혼합 과정에 대한 집중 부등식(concentration inequality)을 통한 샘플 복잡도(sample complexity)를 포함한다. 나아가 오프-정책 평가/학습, 제약 강화학습과 제약 MDP(CMDP)를 다룬다. 전반에 걸쳐 공통된 작용소 및 변분적 관점 하에 알고리즘 템플릿을 통합하고, 유한 샘플 경계와 점근적 결과를 함께 조명한다. 이 논문은 강화학습에 관심 있는 확률론, 최적화, 통계학 연구자들에게 통합된 수학적 진입점을 제공하고자 한다.
Hybridizing a Grouping Metaheuristic with Reinforcement Learning for the One-Dimensional Bin Packing Problem
정확한 잔존 수명 예측을 위한 양자 어닐링 강화학습
Quantum Annealing Enhanced Reinforcement Learning for Accurate Remaining Useful Lifetime Prediction
잔존 수명(RUL) 추정은 예지 보전(predictive maintenance)의 핵심이며, 여기서 계획되지 않은 고장은 자산 자체보다 훨씬 더 큰 비용을 초래할 수 있습니다. 통계적 열화 모델은 실제 시스템의 강한 비선형성을 놓치며, 데이터 기반 모델은 고차원 비볼록(non-convex) 탐색 공간에서 종종 준최적해로 수렴(convergence)하는 경향이 있습니다. 본 연구에서는 양자 어닐링의 샘플링 동작과 Q-learning의 순차적 의사결정을 결합한 양자 어닐링 강화 Q-Learning(QAQL) 프레임워크를 제안합니다. 각 Q-값 업데이트는 그 기저 상태(ground state)가 탐욕적 행동(greedy action)인 작은 이차 무제약 이진 최적화(QUBO) 문제로 인코딩됩니다. 결정론적 옵티마이저(optimizer)로 작동하는 대신, 어닐러는 여러 번의 읽기(reads)에 걸쳐 준최적 행동에 대한 분포를 반환하며, 이러한 확률적 행동 선택은 비선형 열화 궤적에서의 조기 수렴을 억제하는 탐험(exploration)을 제공합니다. QUBO는 마이너 임베딩(minor embedding)을 사용하여 D-Wave Advantage 시스템에서 해결되며, 어닐러는 학습(training) 후에 추가되는 것이 아니라 강화학습(reinforcement learning) 루프에 통합됩니다. 우리는 NASA C-MAPSS 터보팬 엔진 데이터셋(dataset)과 장치 플릿 예지 보전 데이터셋이라는 두 가지 공개 벤치마크(benchmark)에서 QAQL을 검증합니다. 여러 독립적인 실행과 6가지 오차 지표에 대한 평균을 낸 결과, QAQL은 통계적으로 유의미한 개선을 보이며 본 연구에서 고려된 고전 및 양자 기준선(baseline)을 능가했습니다. 결과는 양자 어닐링이 산업용 예지 보전 응용 프로그램의 강화학습 루프 내에서 단순히 이론적인 것이 아닌 실제 사용 가능한 옵티마이저(optimizer)임을 나타냅니다.
최소 제로 포싱(zero-forcing) 집합을 위한 심층 강화학습
Deep Reinforcement Learning for Minimum Zero-Forcing Sets
본 논문은 무방향 그래프에서 최소 제로 포싱(zero-forcing) 집합을 찾는 문제를 탐구하고, 이 문제를 해결하기 위한 적응형 머신러닝 프레임워크를 제안한다. 최소 제로 포싱 집합 문제는 초기 노드 집합의 색이 네트워크 전체로 전파되는 그래프 색칠(graph coloring) 문제이다. 노드 집합이 색 변경 규칙(color-change rule)의 제약 하에서 색이 칠해지지 않은 모든 노드를 색이 바뀌도록 강제하면, 그 집합은 제로 포싱(zero-forcing)이다. 이 문제는 네트워크 과학, 네트워크 제어, 논리 회로 설계 등 여러 분야에서 다양한 응용이 있다. 최소 제로 포싱 집합을 찾는 문제는 NP-hard임이 알려져 있다. 우리는 ZFS 문제에 S2V-DQN 아키텍처를 적응시킨 강화학습 프레임워크인 SD-ZFS를 제안한다. 우리는 이 적응 프레임워크에서 여러 모델을 학습하고, 구조가 서로 다른 그래프 데이터셋에 걸쳐 성능을 분석한다. 우리는 프레임워크에서 학습된 모델이 서로 다른 네트워크 유형에 대해 어떻게 일반화, 스케일링, 전이되는지 평가한다. 결과는 최적해 및 탐욕적 휴리스틱(greedy heuristic)과 비교했을 때 프레임워크의 효과를 보여준다. 우리는 머신러닝을 통해 ZFS 문제를 어떻게 해결할 수 있는지, 그리고 네트워크 구조가 문제에 미치는 영향에 대한 추가적인 통찰을 제공한다.
SplatQ: 2차 선택을 통한 3D 가우시안 스플래팅의 상호작용 인지 가지치기
SplatQ: Interaction-Aware Pruning of 3D Gaussian Splatting via Quadratic Selection
기존의 3D 가우시안 스플래팅(3DGS) 가지치기(pruning) 방법들은 주로 독립적인 중요도 점수에 기반한 전역 Top-K 선택에 의존하여, 영역별 예산 제어가 부족하고 공동 삭제 효과를 무시합니다. 결과적으로 전체 장면에 걸쳐 균형 잡힌 재구성 품질을 보장하지 못합니다. 본 논문에서는 고정된 예산 하에서 영역별 예산 할당과 공동 가우시안 선택을 조율하는 조합 가지치기 알고리즘인 SplatQ를 제안합니다. SplatQ는 공간적 근접성과 외형 유사성을 기준으로 가우시안을 크기가 제한된 블록으로 분할하여, 전역 선택 문제를 특정 크기의 하위 문제들로 분해합니다. 그런 다음 중요도 기반의 블록 유지 할당량을 평활화하여 과도한 예산 집중을 방지합니다. 마지막으로 가우시안 불투명도 변화에 대한 대표 픽셀 색상의 반응을 활용하여 공동 삭제 효과의 2차 근사를 구성합니다. 개별 반응, 쌍별 상호작용 및 할당량 페널티는 2차 비제약 이진 최적화(QUBO) 목적 함수에 통합되며, 모의 담금질(SA) 또는 코히런트 이징 머신(CIM)을 사용하여 이를 해결함으로써 가우시안을 공동으로 선택합니다. 5개 벤치마크에 대한 실험을 통해 SplatQ가 종합적인 재구성 품질, 공간적 품질 균형, 렌더링 속도 측면에서 최신 가지치기 방법들보다 우수한 성능을 보임을 입증합니다. 절제 연구(ablation)를 통해 예산 평활화가 국소적인 세부 표현 재구성을 향상시키는 한편, 상호작용 모델링이 고정된 예산 하에서 가우시안 선택 품질을 향상시킴을 확인합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.