Abstract
The Linear Ordering Problem(LOP), which is a well-known
-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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Laguna, R. Martí and V. Campos: Intensification and diversification with elite tabu search solutions for the linear ordering problem, Computer and Operation Research, vol.26, pp. 1217–1230, (1999)
V. Campos, M. Laguna and R. Martí: Scatter Search for the Linear Ordering Problem, New Ideas in Optimization, D. Corne, M. Dorigo and F. Glover (Eds.), McGraw-Hill, pp. 331–339 (1999)
Carlos García González and Dionisio Pérez-Brito: A Variable Neighborhood Search for Solving the Linear Ordering Problem, In the Proceedings of MIC’2001-4th Metaheuristics International Conference, pp. 181–185, Porto, Portugal, (2001)
Alexandre Belloni and Abilio Lucena: Lagrangian Based Heuristics for the Linear Ordering Problem, In the Proceedings of MIC’2001-4th Metaheuristics International Conference, pp. 445–449, Porto, Portugal, (2001)
S. Chanas and P. Kobylanski: A New Heuristic Algorithm Solving the Linear Ordring Problem, Computational Optimization and Applications, vol.6, pp. 191–205, (1996)
M. Grotschel, M. Junger and G. Reinelt: A Cutting Plane Algorithm for the Linear Ordering Problem, Operations Research, vol.32, no.6, pp. 1995–1220, (1984)
M. Groetschel, M. Juenger and G. Reinelt: Optimal Triangulation of Large Real World Input-Output Matrices, Statistische Hefte 25, 261–295, (1984)
J. E. Mitchell and B. Borchers: Solving linear ordering problems with a combined interior point/simplex cutting plane algorithm, High Performance Optimization, Kluwer Academic Publishers, Dordrecht, The Netherlands, H. Frenk et al. (Eds.), pp. 349–366, (2000)
R.M. Karp: Reducibility among combinatorial problems, In R.E. Miller and J.W. Thatcher (Eds.), Complexcity of Computer Computations, pp. 85–103, New York, (1972)
D. Goldberg and R. Lingle: Alleles, loci, and the traveling salesman problem, in the Proceedings of the 1st International Conference on Genetic ALgorithms and Their Applications, pp. 154–159, Lawrence Erlbaum, Hillsdale, New Jersey, (1985).
D. Goldberg: Genetic Algorithms in Search, Optimization and Machine Learing, Addison-Wesley, Reading, MA, (1989)
I. Oliver, D. Smith, and J. Holland: A study of permutation crossover operators on the tsp, in the Proceedings of the 2nd International Conference on Genetic ALgorithms and Their Applications, pp. 224–230, Hillsdale, New Jersey, (1987).
G. Syswerda: Schedule Optimization Using Genetic Algorithms, in L. Davis (Ed.) Handbook of Genetic ALgorithms, pp. 332–349, New York, (1991)
Z. Michalewicz: Genetic Algorithms + Data Structure = Evolution Programs, Springer-Verlag, Berlin Heidelberg, (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huang, G., Lim, A. (2003). Designing a Hybrid Genetic Algorithm for the Linear Ordering Problem. In: Cantú-Paz, E., et al. Genetic and Evolutionary Computation — GECCO 2003. GECCO 2003. Lecture Notes in Computer Science, vol 2723. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45105-6_115
Download citation
DOI: https://doi.org/10.1007/3-540-45105-6_115
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40602-0
Online ISBN: 978-3-540-45105-1
eBook Packages: Springer Book Archive