Designing a hybrid genetic algorithm for the linear ordering problem. (English) Zbl 1028.68780

Huang, Gaofeng; Lim, Andrew

Cantú-Paz, Erick (ed.) et al., Genetic and evolutionary computation - GECCO 2003. Genetic and evolutionary computation conference, Chicago, IL, USA, July 12-16, 2003. Proceedings, Part I. Berlin: Springer. Lect. Notes Comput. Sci. 2723, 1053-1064 (2003).

Summary: 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.
For the entire collection see [Zbl 1025.68696].

MSC:

68U99	Computing methodologies and applications
68T05	Learning and adaptive systems in artificial intelligence
68T20	Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Keywords:

Linear Ordering Problem; Genetic Algorithm; Hybridization

Software:

LOLIB