GECCO 2003 - LNCS 2723

Designing A Hybrid Genetic Algorithm for the Linear Ordering Problem

Gaofeng Huang¹ and Andrew Lim²

¹Department of Computer Science,
National University of Singapore
3 Science Drive 2,
Singapore 117543

²Department of Industrial Engineering and Engineering Management
Hong Kong Univ of Sci and Tech,
Clear Water Bay,
Kowloon, Hong Kong

Abstract. The Linear Ordering Problem(LOP), which is a well-known $\mathcal{NP}$ -hard problem, has numerous applications in various fields. Using this problem as an example, we illustrate a general procedure of designing a hybrid genetic algorithm, which includes the selection of crossover/mutation operators, accelerating the local search module and tuning the parameters. Experimental results show that our hybrid genetic algorithm outperforms all other existing exact and heuristic algorithms for this problem.

Keywords: Linear Ordering Problem, Genetic Algorithm, Hybridization.

LNCS 2723, p. 1053 ff.

Full article in PDF