Meta-RaPS with Q Learning Approach Intensified by Path Relinking for the 0-1 Multidimensional Knapsack Problem

摘要

Many successful metaheuristics employ intelligent procedures to obtain high quality solutions for optimization problems. Intelligence emerges in these metaheuristics via memory and learning. Meta-RaPS (Metaheuristic for Randomized Priority Search) which can produce promising solutions is classified as a memoryless metaheuristic. To improve its performance, Q learning and Path Relinking (PR) are selected as memory and learning mechanisms to be incorporated into Meta-RaPS. In the proposed algorithm, Meta-RaPS Q-PR, Q learning and PR approaches serve as mechanisms that learn the best policy to construct a solution, and learn "good" attributes of best solutions to reach the optimum solution while losing "bad" attributes of the current solution. The 0-1 multidimensional knapsack problem will be used to evaluate the Meta-RaPS Q-PR.