A Deep Reinforcement Learning-Based Scheme for Solving Multiple Knapsack Problems

Abstract

배낭문제는 조합최적화 문제 중 NP-hard 문제로 여겨진다. 배낭문제의 하나인 다중배낭문제는 아이템을 다중 배낭에 할당하여 각 부분집합의 총 무게가 할당된 배낭의 용량에 만족되어 총가치를 최대화하는 부분집합 및 매핑을 찾는 문제이다. 복잡한 계산 없이 해를 근사하려는 시도들이 발전되어 왔고, 최근 심층신경망의 발전은 기계학습의 조합최적화 문제에 대한 적용을 향상시켰다. 심층신경망을 이용해 단일 배낭문제를 해결하는 최근 기계학습 기반의 연구들은 기존 전통적인 방식을 뛰어넘을 결과를 보였다. 본 논문에서 우리는 배낭의 개수와 알고리즘을 확장해 심층 강화학습 기반의 다중배낭문제 솔루션을 제안한다. 탐욕 방식의 알고리즘으로 가장 좋은 성능을 보장할 수 없는 MKP가 존재하며, 제안된 솔루션은 이를 합리적인 소요 시간으로 최적에 가깝게 해결하도록 한다. 실험에서 해당 문제에 대해 제안된 솔루션을 적용하였을 때, 제안된 솔루션이 실용적인 소요 시간으로 배낭에 할당된 아이템의 이익의 비율이 높은 성능을 낼 수 있음을 검증하였다.|A knapsack problem is an NP-hard Combinatorial Optimization Problem (COP). One of the knapsack problems, the Multiple Knapsack Problem (MKP), is to select disjoint subsets to maximize the total profit and each capacity of the knapsack is no less than the total weights of the subset in the knapsack. Approaches that try to approximate solutions without a large amount of computation have developed continuously until now. The development of Deep Neural Networks (DNNs) has improved the application of Machine Learning (ML), and recent approaches to using machine learning with DNNs outperform existing approaches. The existing solutions based on ML prove near to optimal in a single knapsack problem. In this paper, we propose a Deep Reinforcement Learning-based MKP solution by expanding the number of knapsacks and algorithms. A greedy algorithm does not guarantee the best solution always, and the proposed method could solve the problem instance that the greedy algorithm could not derive the best solution. In the experiment, we validated that our method can produce a high assigned profit ratio of items within reasonable times.