文章基本信息

标题：Scatter Search with Multiple Improvement Methods for the Linear Ordering Problem
本地全文：下载
作者：Héctor Joaquín Fraire Huacuja ; Guadalupe Castilla Valdez ; Rodolfo A. Pazos Rangel 等
期刊名称：Malaysian Journal of Computer Science
印刷版ISSN：0127-9084
出版年度：2012
卷号：25
期号：2
出版社：University of Malaya * Faculty of Computer Science and Information Technology
摘要：In this work, the Linear Ordering Problem (LOP) is approached. This is an NPhard 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 statisticallysupported 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 stateoftheart algorithm solution for LOP. The experimental evidence shows that our algorithm outperforms the best algorithm solution for LOP, improving 2.89% the number of bestknown solutions obtained, and 71% the average percentage error. It is worth noticing that it obtains 53 new bestknown 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.
关键词：Metaheuristics; Scatter Search; Linear Ordering Problem; Local Search; Balancing of intensification and diversification