[3줄 Survey] RL for CO

<arxiv> https://arxiv.org/pdf/2003.03600.pdf

1. Combinatorial Optimization(CO)는 일반적으로 TSP등 조합을 최적화하는 매우 어려운(NP-hard)에 대한 솔루션이다. 대표적인 어플리케이션으로는 칩 설계, 교통체계 최적화, 유전자 설계 등이 있다.

가장 적은 비용으로 모든 도시들을 단 한번씩 다 방문하는 솔루션을 찾는 TSP

2. 강화학습으로 Combinatorial Optimization을 풀었을 때의 이점은, 기본적으로 강화학습을 Search Space Reduction의 관점에서 보았을 때에 의미가 있다. 강화학습은 단순히 어떤 조합을 시도하는 것을 넘어 Trial And Error를 통해 비선형적 패턴을 학습하고 조금 더 새로운 샘플을 찾아 나간다. 이것은 RL로 CO를 풀었을 때 결과물의 퀄리티가 매우 좋아지게 하고, 기존 알고리즘에 비해 파멸적인 속도 향상을 보여준다.

강화학습 알고리즘, LSTM/포인터 네트워크 등으로 만드는 엔코더, Max-Cut, TSP 등으로 주어지는 CO 문제를 정의하면 RL-CO의 완성이다.

3. 앞으로 나아갈 점은 Generalization, 더 큰 환경에서의 solution quality improvement, 더 다양한 CO 포뮬레이션에서의 강화학습 적용 등이라고 한다.

4. 반도체공학에서의 칩 설계, 유전공학에서 유전자를 설계하는 등 과학이 발달할수록 복잡한 CO 문제가 많이 생겨나는 만큼, RL-CO 접근이 많이 유용할 것으로 필자는 생각한다.