[Open DMQA Seminar] Machine Learning for Combinatorial Optimization

조합 최적화 문제는 현실의 문제를 그대로 수리적으로 모델링하고, 최적의 solution을 도출할 수 있다는 점에서 그 유용성이 매우 큰 분야로, 오랜 기간 연구가 이루어지고 있다. 하지만, 대부분의 조합 최적화 문제는 NP-Hard 문제로, 합리적인 시간 내에 최적해를 도출할 수 없다는 한계점이 있다. 이에 따라 최적해에 준할 정도로 좋은 해를 합리적인 시간 내에 얻어내고자 하는 대안 방법론들인 휴리스틱 알고리즘들이 활발하게 연구되고 있다. 하지만 사람이 직접 만드는 hand-crafted heuristics는 그 설계에 있어 깊은 도메인 지식이 필요하거나, 문제의 세부 조건 변화에 따라 그 성능이 크게 변화하는 등의 한계점을 갖는다. 이에 최근에는 조합 최적화 문제에 머신러닝 기반 휴리스틱으로 접근하고자 하는 연구가 활발하게 이루어지고 있다. 본 세미나에서는 이런 머신러닝 기반 휴리스틱의 개념과 핵심적인 알고리즘들을 살펴본다.
참고자료:
[1] Mazyavkina, N., Sviridov, S., Ivanov, S., & Burnaev, E. (2021). Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134, 105400.
[2] Vinyals, O., Fortunato, M., & Jaitly, N. (2015). Pointer networks. Advances in neural information processing systems, 28.
[3] Bello, I., Pham, H., Le, Q. V., Norouzi, M., & Bengio, S. (2016). Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940.
[4] Kool, W., Van Hoof, H., & Welling, M. (2018). Attention, learn to solve routing problems!. arXiv preprint arXiv:1803.08475.

[@Yacktalkun]

이제는 만능이 되어버린 어텐션