Genetic Algorithms and Applications

Genetic algorithms are extremely popular methods for solving optimization problems. They are a population-based method that combine solutions to produce offspring using operators including crossover and mutation. This chapter introduces the general concept of genetic algorithms before describing their main features including the creation of the initial population, the choice of parents, the crossover and mutation operators, and the means for updating the population. The importance of the parameters is discussed, and various interesting adaptations for genetic algorithms are discussed including hybridization, parallelization, and means of maintaining population diversity. Applications are described for the graph coloring problem, nurse scheduling problem, and the job shop scheduling problem, and it is shown that genetic algorithms are still a relevant and current solution method for a wide range of problems.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Similar content being viewed by others

Genetic Algorithms

Genetic algorithms: theory, genetic operators, solutions, and applications

Next Generation Genetic Algorithms: A User’s Guide and Tutorial

References

• Aickelin U (2002) An indirect genetic algorithm for set covering problems. J Oper Res Soc 53(10):1118–1126 ArticleMATHGoogle Scholar
• Aickelin U, Dowsland K (2004) An indirect genetic algorithm for a nurse-scheduling problem. Comput Oper Res 31(5):71–778 ArticleMATHGoogle Scholar
• Bettemir O, Sonmez R (2015) Hybrid genetic algorithm with simulated annealing for resource-constrained project scheduling. J Manag Eng 31(5):04014082 ArticleGoogle Scholar
• Bindu M, Sabu M (2020) A hybrid feature selection approach using artificial bee colony and genetic algorithm. In: Advanced computing and communication technologies for high performance applications. IEEE, Piscataway, pp 211–216 Google Scholar
• Burke E, Newall J, Weare R (1996) A memetic algorithm for university exam timetabling. In: First international conference on the practice and theory of automated timetabling, pp 241–250 Google Scholar
• Cattaruzza D, Absi N, Feillet D, Vidal T (2014) A memetic algorithm for the multi trip vehicle routing problem. Eur J Oper Res 236(1):833–848 ArticleMathSciNetMATHGoogle Scholar
• Chang P, Huang W, Ting C (2010) Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems. Expert Syst Appl 37(3):1863–1878 ArticleGoogle Scholar
• Cowling P, Kendall G, Soubeiga E (2000) Hyperheuristic approach to scheduling a sales summit. In: Proceedings of the third international conference of practice and theory of automated timetabling, vol 2079, pp 176–190 Google Scholar
• Cowling P, Kendall G, Han L (2002) An investigation of a hyperheuristic genetic algorithm applied to a trainer scheduling problem. In: Proceedings of the 2002 congress on evolutionary computation, IEEE, vol 2, pp 1185–1190 Google Scholar
• Davis L (1991) Handbook of genetic algorithms. Van Nostrand Reinhold, New York Google Scholar
• Davoodi M, Golsefidi M, Mesgari M (2019) A hybrid optimisation method for vehicle routing problem using artificial bee colony and genetic algorithm. Int Arch Photogram Remote Sens Spatial Inf Sci 42:293–297 ArticleGoogle Scholar
• Dawkins R (1976) The selfish gene. Oxford University Press, New York Google Scholar
• De Jong K (1975) An analysis of the behaviour of a class of genetic adaptive systems. Doctoral thesis, University of Michigan Google Scholar
• Della Croce F, Tadei R, Volta G (1995) A genetic algorithm for the job shop problem. Comput Oper Res 22(1):15–24 ArticleMATHGoogle Scholar
• Douiri S, Elbernoussi S (2015) Solving the graph coloring problem via hybrid genetic algorithms. J King Saud Univ – Eng Sci 27(1):114–118 Google Scholar
• Duan H, Yu X (2007) Hybrid ant colony optimisation using memetic algorithm for travelling salesman problem. In: IEEE international symposium on approximate dynamic programming and reinforcement learning, pp 92–95 Google Scholar
• Eiben A, Hinterding R, Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Trans Evol Comput 3(2):124–141 ArticleGoogle Scholar
• Ferrucci F, Salza P, Sarro F (2018) Using Hadoop mapreduce for parallel genetic algorithms: a comparison of the global, grid and Island models. Evol Comput 26(4):535–567 ArticleGoogle Scholar
• Galinier P, Hao K (1999) Hybrid evolutionary algorithms for graph coloring. J Comput Optim 3:379–397 ArticleMathSciNetMATHGoogle Scholar
• Glass C, Prugel-Bennett A (2003) Genetic algorithm for graph coloring: exploration of Galinier and Hao’s algorithm. J Comput Optim 7:229–236 ArticleMathSciNetMATHGoogle Scholar
• Goldberg D (1989) Genetic algorithms in search: optimization and machine learning. Addison-Wesley, Reading MATHGoogle Scholar
• Goncalves J, Mendes J, Resende M (2005) A hybrid genetic algorithm for the job shop scheduling problem. Eur J Oper Res 167(1):77–95 ArticleMathSciNetMATHGoogle Scholar
• Grefenstette J (1981) Parallel adaptive algorithms for function optimisation. Technical report CS-81-19, Vanderbilt University, Nashville Google Scholar
• Grobler J, Engelbrecht A, Kendall G, Yadavalli V (2015) Heuristic space diversity control for improved meta-hyper-heuristic performance. Inf Sci 300:49–62 ArticleGoogle Scholar
• Han L, Kendall G (2003) Guided operators for a hyper-heuristic genetic algorithm. In: Australasian joint conference on artificial intelligence, pp 807–820 Google Scholar
• Harik G, Lobo F (1999) A parameter-less genetic algorithm. GECCO 99:258–267 Google Scholar
• Holland J (1975) Adaptation and artificial systems. University of Michigan Press, Ann Arbor Google Scholar
• Jat S, Yang S (2011) A hybrid genetic algorithm and Tabu search approach for post enrolment course timetabling. J Sched 14:617–637 ArticleMathSciNetGoogle Scholar
• Kim S, Ko Y, Uhmn S, Kim J (2014) A strategy to improve performance of genetic algorithm for nurse scheduling problem. Int J Softw Eng Appl 8(1):53–62 Google Scholar
• Kundu S, Mahato M, Mahanty B, Acharyya S (2008) Comparative performance of simulated annealing and genetic algorithm in solving nurse scheduling problem. In: Proceedings of the international multi conference of engineers and computer scientists, vol 1, pp 961–1000 Google Scholar
• Li X, Gao L (2016) An effective hybrid genetic algorithm and Tabu search for flexible job shop scheduling problem. Int J Prod Econ 174:93–110 ArticleGoogle Scholar
• Li T, Yin Y, Yang B, Hou J, Zhou K (2022) A self-learning bee colony and genetic algorithm hybrid for cloud manufacturing services. Computing 104:1977–2003 ArticleGoogle Scholar
• Lozano M, Herrera F, Cano J (2008) Replacement strategies to preserve useful diversity in steady-state Genetic Algorithms. Inf Sci 178:4421–4433 ArticleGoogle Scholar
• Lu Z, Hao J (2010) A memetic algorithm for graph coloring. Eur J Oper Res 203(1):241–250 ArticleMathSciNetMATHGoogle Scholar
• Maenhout B, Vanhoucke M (2008) Comparison and hybridisation of crossover operators for the nurse scheduling problem. Ann Oper Res 159:333–353 ArticleMATHGoogle Scholar
• Michalewicz Z (1995) A survey of constraint handling techniques in evolutionary computation methods. In: Proceedings of the fourth annual conference on evolutionary programming, San Diego, pp 135–155 Google Scholar
• Michalewicz Z, Fogel D (2013) How to solve it: modern heuristics. Springer, Berlin MATHGoogle Scholar
• Moz M, Pato M (2007) A genetic algorithm approach to a nurse rerostering problem. Comput Oper Res 34:667–691 ArticleMATHGoogle Scholar
• Nabeel R (2010) Hybrid genetic algorithms with great deluge for course timetabling. Int J Comput Sci Netw Soc 10:283–288 Google Scholar
• Park B, Choi H, Kim H (2003) A hybrid genetic algorithm for the job shop scheduling problems. Comput Ind Eng 45(4):597–613 ArticleGoogle Scholar
• Pezzella F, Morganti G, Ciaschetti G (2008) A genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res 35(10):3202–3212 ArticleMATHGoogle Scholar
• Rothlauf F (2011) Design of Modern heuristics: principles and applications. Springer, Berlin BookMATHGoogle Scholar
• Salhi S (2017) Heuristic search: the emerging science of problem solving. Palgrave Macmillan, Cham BookGoogle Scholar
• Thangiah SD (2019) A hybrid genetic algorithm, simulated annealing and Tabu search heuristic for vehicle routing problems with time windows. In: Practical handbook of genetic algorithms. CRC Press, Boca Raton, pp 347–384 ChapterGoogle Scholar
• Thomas J, Chaudhari N (2014) Design of efficient packing system using genetic algorithm based on hyper-heuristic approach. Adv Eng Softw 73:45–52 ArticleGoogle Scholar
• Whitley D (1989) The GENITOR algorithm and selection pressure: why rank-based allocation of reproductive trials is best. In: Proceedings of the third international conference on genetic algorithms, pp 116–121 Google Scholar
• Zhu K, Liu Z (2004) Population diversity in permutation-based genetic algorithm. In: European conference on machine learning, pp 537–547 Google Scholar
• Zukhri Z, Paputungan I (2013) A hybrid optimisation algorithm based on genetic algorithm and ant colony optimisation. Int J Artif Intell Appl 4(5):63–75 Google Scholar

Author information

Authors and Affiliations

1. Cardiff University, Cardiff, UK Jonathan Thompson

1. Jonathan Thompson

Corresponding author

Editor information

Editors and Affiliations

1. Institute of Artificial Intelligence, MIT World Peace University, Pune, Pune, Maharashtra, India Anand J. Kulkarni
2. Faculty of Engineering and IT, University of Technology Sydney, Ultimo, NSW, Australia Amir H. Gandomi

Section Editor information

1. Institute of Artificial Intelligence, Dr Vishwanath Karad MIT World Peace University, Pune, India Anand J. Kulkarni

Rights and permissions

Copyright information

© 2023 Springer Nature Singapore Pte Ltd.

About this entry

Cite this entry

Thompson, J. (2023). Genetic Algorithms and Applications. In: Kulkarni, A.J., Gandomi, A.H. (eds) Handbook of Formal Optimization. Springer, Singapore. https://doi.org/10.1007/978-981-19-8851-6_30-1

Download citation

• .RIS
• .ENW
• .BIB

• DOI : https://doi.org/10.1007/978-981-19-8851-6_30-1
• Received : 31 July 2023
• Accepted : 10 August 2023
• Published : 18 November 2023
• Publisher Name : Springer, Singapore
• Print ISBN : 978-981-19-8851-6
• Online ISBN : 978-981-19-8851-6
• eBook Packages : Springer Reference Intelligent Technologies and Robotics Reference Module Computer Science and Engineering