Enhancing parallel cooperative trajectory based metaheuristics with path relinking

ABSTRACT

This paper proposes a novel algorithm combining path relinking with a set of cooperating trajectory based parallel algorithms to yield a new metaheuristic of enhanced search features. Algorithms based on the exploration of the neighborhood of a single solution, like simulated annealing (SA), have offered accurate results for a large number of real-world problems in the past. Because of their trajectory based nature, some advanced models such as the cooperative one are competitive in academic problems, but still show many limitations in addressing large scale instances. In addition, the field of parallel models for trajectory methods has not deeply been studied yet (at least in comparison with parallel population based models). In this work, we propose a new hybrid algorithm which improves cooperative single solution techniques by using path relinking, allowing both to reduce the global execution time and to improve the efficacy of the method. We test here this new model using a large benchmark of instances of two well-known NP-hard problems: MAXSAT and QAP, with competitive results.

References

1. E. Alba, editor. Parallel Metaheuristics: A New Class of Algorithms. Wiley, 2005.
2. E. Alba, G. Luque, and S. Nesmachnow. Parallel metaheuristics: recent advances and new trends. International Transactions in Operational Research, 20(1):1--48, 2013.
3. W. Bozejko, J. Pempera, and C. Smutnicki. Parallel tabu search algorithm for the hybrid flow shop problem. Computers & Industrial Engineering, 65(3):466--474, 2013.
4. Y.-L. Chang, K.-S. Chen, B. Huang, W.-Y. Chang, J. A. Benediktsson, and L. Chang. A parallel simulated annealing approach to band selection for high-dimensional remote sensing images. Selected Topics in Applied Earth Observations and Remote Sensing, IEEE Journal of, 4(3):579--590, 2011.
5. F. Chicano, G. Luque, and E. Alba. Autocorrelation measures for the quadratiec assignment problem. Applied Mathematics Letters, 25(4):698--705, 2012.
6. J.-F. Cordeau and M. Maischberger. A parallel iterated tabu search heuristic for vehicle routing problems. Computers & Operations Research, 39(9):2033--2050, 2012.
7. M. Eskandarpour, S. H. Zegordi, and E. Nikbakhsh. A parallel variable neighborhood search for the multi-objective sustainable post-sales network design problem. International Journal of Production Economics, 145(1):117--131, 2013.
8. A. Ferreiro, J. Garcia, J. Lopez-Salas, and C. Vazquez. An efficient implementation of parallel simulated annealing algorithm in gpus. Journal of Global Optimization, 57(3):863--890, 2013.
9. M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
10. M. Gendreau. Handbook of metaheuristics, volume 146. Springer, 2010.
11. F. Glover. Tabu Search, part I. ORSA, Journal of Computing, (1):190--206, 1989.
12. F. Glover, M. Laguna, and R. Martí. Fundamentals of scatter search and path relinking. Control and cybernetics, 39(3):653--684, 2000.
13. S. Kirkpatrick, C. Gellatt, and M. Vecchi. Optimization by Simulated Annealing. Science, 220(4598):671--680, 1983.
14. G. Luque, F. Luna, and E. Alba. A new parallel cooperative model for trajectory based metaheuristics. In Distributed Computing and Artificial Intelligence, pages 559--567. Springer, 2010.
15. C. Papadimitriou. The Complexity of Combinatorial Optimization Problems. Master's thesis, Princeton University, 1976.
16. E.-G. Talbi. Parallel combinatorial optimization, volume 58. John Wiley & Sons, 2006.
17. M. Yazdani, M. Amiri, and M. Zandieh. Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Systems with Applications, 37(1):678--687, 2010.

Index Terms

• Computing methodologies

  • Parallel computing methodologies

    • Parallel algorithms

• Theory of computation

  • Design and analysis of algorithms

    • Parallel algorithms