Hide/Show Apps

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

Arin, Arif
Rabadi, Ghaith
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.