Local search versus Path Relinking in metaheuristics: Redesigning Meta-RaPS with application to the multidimensional knapsack problem

• Meta-RaPS is a recent metaheuristic for optimization problems that is simple and effective.
• The time consuming local search phase of Meta-RaPS is replaced by Path Relinking as a learning module.
• The results show that the newly designed Meta-RaPS is very competitive compared to other metaheuristics used for the MKP.

Most heuristics for discrete optimization problems consist of two phases: a greedy-based construction phase followed by an improvement (local search) phase. Although the best solutions are usually generated after the improvement phase, there is usually a high computational cost for employing a local search algorithm. This paper seeks another alternative to reduce the computational burden of a local search while keeping solution quality by embedding intelligence in metaheuristics. A modified version of Path Relinking is introduced to replace the local search in the improvement phase of Meta-RaPS (Meta-Heuristic for Randomized Priority Search) which is currently classified as a memoryless metaheuristic. The new algorithm is tested using the 0–1 multidimensional knapsack problem, and it is observed that it could solve even the largest benchmark problems in significantly less time while maintaining solution quality compared to other algorithms in the literature.

Figure optionsDownload as PowerPoint slide