[Open DMQA Seminar] Neural Combinatorial Optimization

조합 최적화 문제는 NP-Hard 문제로, 완전한 해를 탐색하기가 불가능하거나 매우 어려운 문제이다. 이러한 문제는 이론적인 문제 해결뿐만 아니라, 생산 설비 최적화, 컴퓨팅 자원 할당 최적화, 물류 운송 경로 최적화 등 다양한 실세계 문제를 모델링하는 데 사용된다. 조합 최적화 문제를 해결하기 위해 여러 알고리즘이 연구되어 왔으며, 최근에는 딥러닝의 발전으로 이를 적용하려는 시도가 이루어지고 있다. 이번 세미나에서는 대표적인 딥러닝 기반 조합 최적화 문제 해결 방법인 Pointer Network를 살펴본 후, 두 가지 실세계 조합 최적화 문제 해결 연구를 살펴 볼 것이다. 먼저 길찾기 문제에서 A* Search 알고리즘에 딥러닝을 접목한 Neural A* Search와, 반도체 제조 클러스터 장비의 효율적인 운영을 위해 동작 순서를 결정하는 스케줄링 로직을 강화학습의 일환인 DQN 방법론으로 접근한 사례를 차례로 소개한다.
참고자료:
[1] Vinyals, O., Fortunato, M., & Jaitly, N. (2015). Pointer networks. Advances in neural information processing systems, 28.
[2] Bello, I., Pham, H., Le, Q. V., Norouzi, M., & Bengio, S. (2016). Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940.
[3] Yonetani, R., Taniai, T., Barekatain, M., Nishimura, M., & Kanezaki, A. (2021, July). Path planning using neural a* search. In International conference on machine learning (pp. 12029-12039). PMLR.
[4] Kim, H. J., & Lee, J. H. (2024). Scheduling Cluster Tools for Concurrent Processing: Deep Reinforcement Learning With Adaptive Search. IEEE Transactions on Automation Science and Engineering.

[@장재은-b6i]

유익한 리뷰 감사합니다. 혹시 해당 리뷰에서 제안하는 인공지능 알고리즘들의 빅오 복잡도는 어느정도일까요? 휴리스틱에 비해 얼마나 복잡도 이득이 있는지 궁금해서요