Employing Learning to Improve the Performance of Meta-RaPS

AbstractIn their search for satisfactory solutions to complex combinatorial problems, metaheuristics methods are expected to intelligently explore the solution space. Various forms of memory have been used to achieve this goal and improve the performance of metaheuristics, which warranted the development of the Adaptive Memory Programming (AMP) framework [1]. This paper follows this framework by integrating Machine Learning (ML) concepts into metaheuristics as a way to guide metaheuristics while searching for solutions. The target metaheuristic method is Meta-heuristic for Randomized Priority Search (Meta-RaPS). Similar to most metaheuristics, Meta-RaPS consists of construction and improvement phases. Randomness coupled with a greedy heuristic are typically employed in the construction phase. While a local search heuristic is used in the improvement phase. This paper proposes adding a new learning phase, in which a ML method will be integrated. An Inductive Decision Tree (IDT) will be incorporated into the learning phase in an effort to learn from the information collected during the construction and improvement phases. The proposed approach will be demonstrated using instances for the Capacitated Vehicle Routing Problem (CVRP)