A study on the role of memory in heuristic search. The case for discrete dispersion problems
This work focuses on the design of effective solution methodologies for a combinatorial optimization problem that integrates diversity maximization with group fairness constraints. In particular, we investigate two metaheuristic paradigms, the Greedy Randomized Adaptive Search Procedure (GRASP) and Probabilistic Tabu Search (PTS), and analyze how different memory mechanisms influence search performance.
We propose two novel PTS variants that incorporate memory in distinct phases: one in the improvement phase through tabu and frequency-based structures, and another in the construction phase via probabilistic biasing guided by elite solutions and entropy-based control. We further introduce an advanced hybrid framework that integrates memory-based perturbation with strategic oscillation to effectively balance intensification and diversification. Results highlight the key role of memory in improving performance.
Palabras clave: metaheuristics combinatorial optimization