Scatter Search with Multiple Improvement Methods for the Linear Ordering Problem

Malaysian Journal of Computer Science

Guadalupe Castilla Valdez¹  Héctor José Puga Soberanes¹  Juan Martín Carpio Valadez¹  Laura Cruz Reyes¹  Héctor Joaquín Fraire Huacuja¹  Javier González Barbosa¹  Rodolfo A. Pazos Rangel¹  David Terán Villanueva¹ 

关键词: Metaheuristics;    Scatter Search;    Linear Ordering Problem;    Local Search;    Balancing of intensification and diversification;   

DOI  :  

学科分类：社会科学、人文和艺术（综合）

来源: University of Malaya * Faculty of Computer Science and Information Technology

【 摘 要 】

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 thetraditionalapproachwhich incorporates asingle improvement method.Inthispaper, weproposea Scatter Searchalgorithmwhichusesmultiple improvementmethodstoachieveabetterbalanceofintensificationand diversification.Tovalidateourapproach,astatistically-supportedexperimentalstudyofitsperformancewas 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 ouralgorithmoutperformsthebest algorithmsolutionfor LOP,improving2.89%thenumberofbest-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.

【 授权许可】

Unknown