1. Home
  2. Issues
  3. Volume 29, Issue 3 (2018)
  4. Some Further Experiments with Crossover ...

Informatica


Some Further Experiments with Crossover Operators for Genetic Algorithms
Volume 29, Issue 3 (2018), pp. 499–516
Pub. online: 1 January 2018      Type: Research Article      Open accessOpen Access
Received
1 October 2017
Accepted
1 June 2018
Published
1 January 2018

Abstract

Crossover operators play a very important role by creation of genetic algorithms (GAs) which are applied in various areas of computer science, including combinatorial optimization. In this paper, fifteen genetic crossover procedures are designed and implemented using a modern C# programming language. The computational experiments have been conducted with these operators by solving the famous combinatorial optimization problem – the quadratic assignment problem (QAP). The results of the conducted experiments on the characteristic benchmark instances from the QAP instances library QAPLIB illustrate the relative performance of the examined crossover operations.
All crossover procedures are publicly available with the intention that the GA researchers will choose a procedure which suits the individual demand at the highest degree.

References

 
Abdoun, O., Abouchabaka, J. (2011). A comparative study of adaptive crossover operators for genetic algorithms to resolve the traveling salesman problem. International Journal of Computer Applications, 31, 49–57.
 
Ahuja, R.K., Orlin, J.B., Tiwari, A. (2000). A greedy genetic algorithm for the quadratic assignment problem. Computers & Operations Research, 27, 917–934.
 
Burkard, R.E., Karisch, S., Rendl, F. (1997). QAPLIB – a quadratic assignment problem library. Journal of Global Optimization, 10, 391–403. See also http://anjos.mgi.polymtl.ca/qaplib/.
 
Caruana, R.A., Eshelman, L.A., Schaffer, J.D. (1989). Representation and hidden bias II: eliminating defining length bias in genetic search via shuffle crossover. In: Sridharan, N.S. (Ed.), Proceedings of the Eleventh International Joint Conference on AI, Vol. 1. Morgan Kaufmann, San Mateo, pp. 750–755.
 
Çela, E. (1998). The Quadratic Assignment Problem: Theory and Algorithms. Kluwer, Dordrecht.
 
De Jong, K.A., Spears, W.M. (1992). A formal analysis of the role of multi-point crossover in genetic algorithms. Annals of Mathematics and Artificial Intelligence, 5, 1–26.
 
Deb, K., Agrawal, R.B. (1995). Simulated binary crossover for continuous search space. Complex Systems, 9, 115–148.
 
Deep, K., Thakur, M. (2007). A new crossover operator for real coded genetic algorithms. Applied Mathematics and Computation, 188, 895–911.
 
Drezner, Z. (2003). A new genetic algorithm for the quadratic assignment problem. INFORMS Journal on Computing, 15, 320–330.
 
Eiben, A.E., Raue, P.-E., Ruttkay, Z. (1994). Genetic algorithms with multi-parent recombination. Parallel problem solving from nature – PPSN III. In: Davidor, Y., Schwefel, H.P., Männer, R. (Eds.), International Conference on Evolutionary Computation, The Third Conference on Parallel Problem Solving from Nature, Proceedings, Lecture Notes in Computer Science, Vol. 866. Springer, Berlin-Heidelberg, pp. 78–87.
 
Garey, M.R., Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.
 
Glover, F. (1994). Genetic algorithms and scatter search: unsuspected potential. Statistics and Computing, 4, 131–140.
 
Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading.
 
Goldberg, D.E. (2002). The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer, Dordrecht-Norwell.
 
Goldberg, D.E., Lingle, R. (1985). Alleles, loci, and the traveling salesman problem. In: Grefenstette, J.J. (Ed.), Proceedings of the First International Conference on Genetic Algorithms and their Applications. Lowrence Erlbaum, Hillsdale, pp. 154–159.
 
Heaton, J. (2014). Artificial Intelligence for Humans, Vol. 2: Nature-Inspired Algorithms. Heaton Research, Chesterfield.
 
Herrera, F., Lozano, M., Sánchez, A.M. (2003). A taxonomy for the crossover operator for real-coded genetic algorithms: an experimental study. International Journal of Intelligent Systems, 18, 309–338.
 
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.
 
Kaya, M. (2011). The effects of two new crossover operators on genetic algorithm performance. Applied Soft Computing, 11, 881–890.
 
Maenhout, B., Vanhoucke, M. (2008). Comparison and hybridization of crossover operators for the nurse scheduling problem. Annals of Operations Research, 159, 333–353.
 
Magalhães-Mendes, J. (2013). A comparative study of crossover operators for genetic algorithms to solve the job shop scheduling problem. WSEAS Transactions on Computers, 12, 164–173.
 
Misevičius, A. (2006). Experiments with hybrid genetic algorithm for the grey pattern problem. Informatica, 17, 237–258.
 
Misevičius, A., Blonskis, J., Bukšnaitis, V. (2005). Aspects of combinatorial optimization and genetic algorithms. Informacijos mokslai (Information Sciences), 34, 307–314 (in Lithuanian).
 
Oliver, I.M., Smith, D.J., Holland, J.H. (1987). A study of permutation crossover operators on the traveling salesman problem. In: Grefenstette, J.J. (Ed.), Genetic Algorithms and their Applications: Proceedings of the Second International Conference on Genetic Algorithms and their Applications. Lawrence Erlbaum, Hillsdale, pp. 224–230.
 
Pavai, G., Geetha, T.V. (2017). A survey on crossover operators. ACM Computing Surveys, 49, 1–43.
 
Simon, D. (2013). Evolutionary Optimization Algorithms. Biologically Inspired and Population-Based Approaches to Computer Intelligence. Wiley, Hoboken.
 
Sivanandam, S.N., Deepa, S.N. (2008). Introduction to Genetic Algorithms. Springer, Heidelberg, New York.
 
Syswerda, G. (1989). Uniform crossover in genetic algorithms. In: Schaffer, J.D. (Ed.), Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, pp. 2–9.
 
Taillard, E. (1991). Robust taboo search for the QAP. Parallel Computing, 17, 443–455.
 
Taillard, E. (1995). Comparison of iterative searches for the quadratic assignment problem. Location Science, 3, 87–105.
 
Umbarkar, A.J., Sheth, P.D. (2015). Crossover operators in genetic algorithms: a review. ICTACT Journal on Soft Computing, 6, 1083–1092.

Biographies

Misevičius Alfonsas
alfonsas.misevicius@ktu.lt

A. Misevičius was born in 1962, in Marijampolė, Lithuania. He received dipl. eng. degree from Kaunas Polytechnic Institute, Lithuania, in 1986. A. Misevičius got his doctor’s degree in 1996, Kaunas University of Technology. He was conferred the best refereed technical paper award at 23rd SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence, Cambridge, UK, 2003. A. Misevičius is currently a professor at Department of Multimedia Engineering, Faculty of Informatics, Kaunas Univ. Technol. Author and co-author of over 80 res. papers and academic texts on various topics of computer science. The main research interests include: combinatorial optimization, design and implementation of heuristic and metaheuristic algorithms.

Kuznecovaitė Dovilė
dovile.kuznecovaite@ktu.lt

D. Kuznecovaitė was born in 1989, in Kaunas, Lithuania. She got informatics bachelor degree at Kaunas University of Technology, in 2012, and she received informatics master’s degree, in 2014. D. Kuznecovaitė is currently a PhD student and a lecturer at Department of Multimedia Engineering, Faculty of Informatics, Kaunas Univ. Technol. Her research interests are in the areas of combinatorial optimization and heuristic algorithms.

Platužienė Jūratė
jurate.platuziene@ktu.lt

J. Platužienė was born in 1981, in Kaunas, Lithuania. She received bachelor electroengineering and management degree at Kaunas University of Technology, in 2004. In 2007 J. Platužienė got informatics engineering master‘s degree. She is currently a lecturer at Department of Multimedia Engineering, Faculty of Informatics, Kaunas Univ. Technol. The main scope of her pedagogical and research activity covers 3D modelling and animation.


Full article Related articles Cited by PDF XML
Full article Related articles Cited by PDF XML

Copyright
© 2018 Vilnius University
Open access article under the CC BY license.

Keywords
metaheuristic methods genetic algorithms genetic crossover operators combinatorial optimization quadratic assignment problem

Metrics
since January 2020
1256

Article info
views

 741

Full article
views
551

PDF
downloads

 235

XML
downloads


Share


RSS