- 2024년 5월 17일 오후 3:12
- 조회수: 28503
INFORMATION
- 2024년 5월 17일
- 오전 12시 ~
온라인 비디오 시청 (YouTube)
차민성
TOPIC
On-Line Video
OVERVIEW
조합 최적화 문제는 현실의 문제를 그대로 수리적으로 모델링하고, 최적의 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.
청취자 후기
배진수
조합 최적화 문제 해결을 위한 머신러닝 기반 휴리스틱 알고리즘에 대한 세미나를 청취하였다.
Feasible set이 이산 Countable한 경우의 (결론적인 관점에선 말고) 최적화를 대강 조합 최적화라고 부르는 것 같다. 해당 최적화를 해결하기 위한 머신러닝 기반 휴리스틱 방법론이 무엇일까 궁금했는데, 기존 휴리스틱 알고리즘의 해를 활용하여 지도 학습 혹은 강화학습을 수행하는 개념임을 알게 되었다. 본 세미나의 경우 TSP 문제 해결을 예시로 여러가지 머신러닝 계열의 휴리스틱 조합 최적화 알고리즘에 대해 소개해주고 있는데, 본인처럼 해당 분야에 생소한 사람들도 이해하기 편하게끔 정리되어 있어 관심있는 사람들은 살펴보면 좋을 것 같다. TSP 문제 해결 모델을 대강 Set-to-Sequence 모델로 간주할 수 있으니 Set and Sequence을 입출력으로 간주할 수 있는 딥러닝 계열의 머신러닝 등장 이후로 해당 연구가 활발하게 시작된 듯 하다. 세미나에서는 Seq-2-Seq과 Graph attention, 두 가지 모델 구조의 Backbone 네트워크를 소개한 뒤 TSP 문제의 Set and Sequence를 입출력으로 어떻게 처리하는지 자세히 소개해주고 있다. TSP의 제약 조건의 경우 모델 안에서는 처리하기 힘들 것 같은데 어떻게 처리하는지 궁금하기도 하다.
좋은 세미나를 준비하느라 고생한 민성이에게 감사의 말씀을 전하며 세미나 후기를 마치도록 한다.