서지주요정보
Scaleable neural combinatorial optimization and real world logistics application = 큰 규모의 조합최적화를 푸는 신경망 기법 및 실제 로지스틱 문제에 적용
서명 / 저자 Scaleable neural combinatorial optimization and real world logistics application = 큰 규모의 조합최적화를 푸는 신경망 기법 및 실제 로지스틱 문제에 적용 / Jiwoo Son.
발행사항 [대전 : 한국과학기술원, 2024].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8042009

소장위치/청구기호

학술문화관(도서관)2층 학위논문

MIE 24002

휴대폰 전송

도서상태

이용가능(대출불가)

사유안내

반납예정일

리뷰정보

초록정보

This research introduces novel algorithms designed to provide scalable constructive nerual solver to a wide range of combinatorial optimization (CO) problems. These problems, characterized by their NP-completeness and their relationship to the traveling salesman problem, present formidable computational hurdles when attempting to find efficient solutions. In recent years, constructive RL methods have demonstrated competitive performance in small-scale instances (fewer than 100 nodes) when compared to heuristic methods. Their effectiveness diminishes significantly as the problem size increases. because existing constructive methods lack the ability to scale effectively. To address this challenge, our research aims to incorporate inductive bias during both the training and testing phases. Our research encompasses two main topics, namely, Meta-SAGE and Equity-Transformer. Firstly, our approach harnesses pre-trained models to handle larger-scale problems during testing, utilizing two components: a scale meta-learner (SML) and scheduled adaptation with guided exploration (SAGE). Secondly, we delve into the min-max VRPs problem, which adds an additional layer of complexity and closely mirrors real-world logistical challenges. Here, we employ a deep reinforcement learning approach and customize a transformer-based neural architecture, presenting the "Equity-Transformer" as a dedicated solution for effectively tackling min-max VRPs.

이 연구는 다양한 조합최적화 문제들에 대해 스케일러블한 건설적 신경망 솔버를 만들기 위한 새로운 알고리즘들을 제시한다. 조합 최적화 문제들은 NP-완전 성질을 가지고 있기 때문에 빠르게 좋은 솔루션을 찾는 것은 매우 어렵다. 최근 몇 년 동안 건설적 RL 방법은 휴리스틱 방법과 비교할 때 소규모 인스턴스(100개 노드 미만)에서 경쟁력 있는 성능을 입증했지만 문제의 크기가 커지면 작은 스케일에서 보여줬던 성능을 보여주지 못한다. 그 이유는 기존의 건설적인 방법은 스케일러블한 속성이 고려되어있지 않기 때문이다. 이러한 문제를 해결하기 위해 우리 연구에서는 훈련 및 테스트 단계 모두에서 귀납적 편견을 도입하여 스케일러블한 건설적 신경망 솔버가 되도록 디자인 하는 것을 목표로 한다. 우리의 연구는 Meta-SAGE와 Equity-Transformer라는 두 가지 주제가 포함되어있다. 첫째, 우리의 접근 방식은 사전 훈련된 모델을 활용하여 테스트 중에 더 큰 규모의 문제를 처리하며, 스케일에 대한 메타 학습기(SML)와 안내 탐색(SAGE)이라는 두 가지 구성 요소를 활용한다. 두번째 연구는 복잡성을 더욱 가중시키고 실제 물류 문제를 밀접하게 관련있는 최소-최대 VRP 문제를 심층 강화학습 기반 건설적 솔버인 "Equity-Transformer"를 제시하여 효과적으로 풀어낸다.

서지기타정보

서지기타정보
청구기호 {MIE 24002
형태사항 iv, 38p : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 손지우
지도교수의 영문표기 : Jinkyoo Park
지도교수의 한글표기 : 박진규
Including appendix
학위논문 학위논문(석사) - 한국과학기술원 : 산업및시스템공학과,
서지주기 References : p. 25-29
주제 Combinatorial Optimization
Neural constructive solver
deep reinforcement learning
vehicle routing problem
조합최적화
건설적 신경망 솔버
심층 강화학습
차량 경로 문제
QR CODE

책소개

전체보기

목차

전체보기

이 주제의 인기대출도서