Title: A new hybrid Evolutionary Algorithm for the MinLA problem

Authors: Reeti Sharma, Kamal Srivastava

Addresses: Faculty of Science, Department of Mathematics, Dayalbagh Educational Institute, Dayalbagh, Agra 282005, India. ' Faculty of Science, Department of Mathematics, Dayalbagh Educational Institute, Dayalbagh, Agra 282005, India

Abstract: In this paper, we deal with a particular layout problem of graph: the Minimum Linear Arrangement Problem (MinLA). A new Evolutionary Algorithm (EA) is presented here with knowledge-based operator designed to search the solution space. The proposed technique is a hybrid approach, which incorporates Simulated Annealing (SA) into the selection process of EA. It also utilises the features of level structure, Depth First Search (DFS), Frontal Increase Minimisation (FIM) method and Spectral Sequencing (SS) of the graphs. The proposed technique produces results that are well comparable with the existing approaches known for their good results.

Keywords: MinLA; minimum linear arrangement problem; evolutionary algorithms; graph layout; simulated annealing.

DOI: 10.1504/IJOR.2009.025009

International Journal of Operational Research, 2009 Vol.5 No.2, pp.229 - 249

Published online: 06 May 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article