Malaysian Journal of Computer Science (ISSN 0127-9084)
Indexing Page
Visit the official web site at http://ejum.fsktm.um.edu.my

Article Information
Title:Scatter Search with Multiple Improvement Methods for the Linear Ordering Problem
Auhtor(s): Héctor Joaquín Fraire Huacuja,Guadalupe Castilla Valdez,Rodolfo A. Pazos Rangel,Javier González Barbosa,Laura Cruz Reyes ,Juan Martín Carpio Valadez,Héctor José Puga Soberanes,David Terán Villanueva,
Journal:Malaysian Journal of Computer Science (ISSN 0127-9084)
Volume:25, No 2
Year:2012
Keywords:Metaheuristics, Scatter Search, Linear Ordering Problem, Local Search, Balancing of intensification and diversification
Abstract:In this work, the Linear Ordering Problem (LOP) is approached. This is an NP-hard problem which has been solved with different metaheuristic algorithms. Particularly, it has been solved with a Scatter Search algorithm that applies the traditional approach which incorporates a single improvement method. In this paper, we propose a Scatter Search algorithm which uses multiple improvement methods to achieve a better balance of intensification and diversification. To validate our approach, a statistically-supported experimental study of its performance was carried out using the most challenging standard instances. The overall performance of the proposed Scatter Search algorithm was compared with the state-of-the-art algorithm solution for LOP. The experimental evidence shows that our algorithm outperforms the best algorithm solution for LOP, improving 2.89% the number of best-known solutions obtained, and 71% the average percentage error. It is worth noticing that it obtains 53 new best-known solutions for the instances used. We claim that the combination of multiple improvement methods (local searches) can be applied to improve the balance between intensification and diversification in other metaheuristics to solve LOP and problems in other domain.
File:Download

Volume Listing