genetic algorithm thesis

Advertisement

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

• Review Article
• Published: 03 February 2023
• Volume 17 , pages 1245–1256, ( 2024 )

Cite this article

• Bushra Alhijawi   ORCID: orcid.org/0000-0003-0806-102X 1 &
• Arafat Awajan 1 , 2  

3091 Accesses

16 Citations

Explore all metrics

A genetic algorithm (GA) is an evolutionary algorithm inspired by the natural selection and biological processes of reproduction of the fittest individual. GA is one of the most popular optimization algorithms that is currently employed in a wide range of real applications. Initially, the GA fills the population with random candidate solutions and develops the optimal solution from one generation to the next. The GA applies a set of genetic operators during the search process: selection, crossover, and mutation. This article aims to review and summarize the recent contributions to the GA research field. In addition, the definitions of the GA essential concepts are reviewed. Furthermore, the article surveys the real-life applications and roles of GA. Finally, future directions are provided to develop the field.

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

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

A review on genetic algorithm: past, present, and future

Particle Swarm Optimization Algorithm and Its Applications: A Systematic Review

Particle swarm optimization algorithm: an overview.

BoussaïD I, Lepagnot J, Siarry P (2013) A survey on optimization metaheuristics. Inf Sci 237:82–117

MathSciNet   Google Scholar  

Agushaka JO, Ezugwu AE, Abualigah L (2022) Dwarf mongoose optimization algorithm. Comput Methods Appl Mech Eng 391:114570

Ezugwu AE, Agushaka JO, Abualigah L, Mirjalili S, Gandomi AH (2022) Prairie dog optimization algorithm. Neural Comput Appl 34(22):20017–20065

Google Scholar  

Abualigah L, Abd Elaziz M, Sumari P, Geem ZW, Gandomi AH (2022) Reptile search algorithm (RSA): a nature-inspired meta-heuristic optimizer. Expert Syst Appl 191:116158

Oyelade ON, Ezugwu AE-S, Mohamed TI, Abualigah L (2022) Ebola optimization search algorithm: a new nature-inspired metaheuristic optimization algorithm. IEEE Access 10:16150–16177

Holland J, Goldberg D (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Massachusetts

Mattfeld DC (2013) Evolutionary search and the job shop: investigations on genetic algorithms for production scheduling

Arabali A, Ghofrani M, Etezadi-Amoli M, Fadali MS, Baghzouz Y (2013) Genetic-algorithm-based optimization approach for energy management. IEEE Trans Power Deliv 28(1):162–170

Koza JR (1994) Genetic programming as a means for programming computers by natural selection. Stat Comput 4(2):87–112

Kim J-H, Myung H (1997) Evolutionary programming techniques for constrained optimization problems. IEEE Trans Evol Comput 1(2):129–140

Storn R, Price K (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Global Optim 11(4):341–359

Rechenberg I (1973) Evolution strategy: optimization of technical systems by means of biological evolution. Fromman Holzboog Stuttgart 104:15–16

Holland JH (1975) Adaptation in natural and artificial systems. In: An introductory analysis with application to biology, control, and artificial intelligence. Ann Arbor: University of Michigan Press, pp 439–444

Man K-F, Tang K-S, Kwong S (1996) Genetic algorithms: concepts and applications [in engineering design]. IEEE Trans Ind Electron 43(5):519–534

Mitchell M (1998) An introduction to genetic algorithms

Sudholt D (2018) The benefits of population diversity in evolutionary algorithms: a survey of rigorous runtime analyses. arXiv preprint arXiv:1801.10087

Kazimipour B, Li X, Qin AK (2014) A review of population initialization techniques for evolutionary algorithms. In: 2014 IEEE congress on evolutionary computation (CEC), IEEE, pp 2585–2592

Whitley D (1994) A genetic algorithm tutorial. Stat Comput 4(2):65–85

Mukhopadhyay A, Maulik U, Bandyopadhyay S, Coello CAC (2014) A survey of multiobjective evolutionary algorithms for data mining: part i. IEEE Trans Evol Comput 18(1):4–19

Bodenhofer U (2003) Genetic algorithms: theory and applications. Lecture notes, Fuzzy logic laboratorium Linz-Hagenberg, Winter

Sastry K, Goldberg DE, Kendall G (2014) Genetic algorithms. In: Search methodologies, pp 93–117

Goldberg DE, Holland JH (1988) Genetic algorithms and machine learning. Mach Learn 3(2):95–99

Baker JE (1987) Reducing bias and inefficiency in the selection algorithm. In: Proceedings of the second international conference on genetic algorithms, pp 14–21

Goldberg DE, Deb K (1991) A comparative analysis of selection schemes used in genetic algorithms. Found Genetic Algorithms 1:69–93

Schlierkamp-Voosen D, Mühlenbein H (1993) Predictive models for the breeder genetic algorithm. Evol Comput 1(1):25–49

Spears WM, De Jong KD (1995) On the virtues of parameterized uniform crossover. Technical report, Naval Research Lab Washington DC

Sivrikaya-Şerifoğlu F (1997) A new uniform order-based crossover operator for genetic algorithm applications to multi-component combinatorial optimization problems. Unpublished PhD dissertation, Boğaziçi University, Istanbul

Paul PV, Ramalingam A, Baskaran R, Dhavachelvan P, Vivekanandan K, Subramanian R (2014) A new population seeding technique for permutation-coded genetic algorithm: service transfer approach. J Comput Sci 5(2):277–297

Deng Y, Liu Y, Zhou D (2015) An improved genetic algorithm with initial population strategy for symmetric TSP. In: Mathematical problems in engineering

Hassanat AB, Prasath V, Abbadi MA, Abu-Qdari SA, Faris H (2018) An improved genetic algorithm with a new initialization mechanism based on regression techniques. Information 9(7):167

Kaya M (2011) The effects of two new crossover operators on genetic algorithm performance. Appl Soft Comput 11(1):881–890

Rafsanjani MK, Eskandari S (2011) A new combinational selection operator in genetic algorithm. AIP Conf Proc 1389:1082–1085 ( AIP )

Rafsanjani MK, Eskandari S (2012) The effect of a new generation based sequential selection operator on the performance of genetic algorithm. Indian J Sci Technol 5(12):3758–3761

Hussain A, Muhammad YS (2020) Trade-off between exploration and exploitation with genetic algorithm using a novel selection operator. Complex Intell Syst 6(1):1–14

Kaya Y, Uyar M, Tekın R (2011) A novel crossover operator for genetic algorithms: ring crossover. arXiv preprint arXiv:1105.0355

Semenkin E, Semenkina M (2012) Self-configuring genetic algorithm with modified uniform crossover operator. In: International conference in swarm intelligence, Springer, pp 414–421

Thakur M (2014) A new genetic algorithm for global optimization of multimodal continuous functions. J Comput Sci 5(2):298–311

Elsayed SM, Sarker RA, Essam DL (2014) A new genetic algorithm for solving optimization problems. Eng Appl Artif Intell 27:57–69

Osaba E, Onieva E, Carballedo R, Diaz F, Perallos A (2014) An adaptive multi-crossover population algorithm for solving routing problems. In: Nature inspired cooperative strategies for optimization (NICSO 2013), pp 113–124

Jin C, Li F, Tsang EC, Bulysheva L, Kataev MY (2017) A new compound arithmetic crossover-based genetic algorithm for constrained optimisation in enterprise systems. Enterpr Inf Syst 11(1):122–136

Demirci H, Ozcerit A, Ekiz H, Kutlu A (2015) Chaotic crossover operator on genetic algorithm. In: Proceedings of 2nd international conference on information technology

Alkafaween E (2018) Novel methods for enhancing the performance of genetic algorithms. CoRR https://arxiv.org/abs/1801.02827

Hassanat AB, Alkafaween E (2017) On enhancing genetic algorithms using new crossovers. Int J Comput Appl Technol 55(3):202–212

Xue Y, Zhu H, Liang J, Słowik A (2021) Adaptive crossover operator based multi-objective binary genetic algorithm for feature selection in classification. Knowl Based Syst 227:107218

Koohestani B (2020) A crossover operator for improving the efficiency of permutation-based genetic algorithms. Expert Syst Appl 151:113381

Manzoni L, Mariot L, Tuba E (2020) Balanced crossover operators in genetic algorithms. Swarm Evol Comput 54:100646

Viana MS, Morandin Junior O, Contreras RC (2020) A modified genetic algorithm with local search strategies and multi-crossover operator for job shop scheduling problem. Sensors 20(18):5440

Albayrak M, Allahverdi N (2011) Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms. Expert Syst Appl 38(3):1313–1320

Marung U, Theera-Umpon N, Auephanwiriyakul S (2016) Top-n recommender systems using genetic algorithm-based visual-clustering methods. Symmetry 8(7):54

Yuan Y, Wang W, Pang W (2021) A genetic algorithm with tree-structured mutation for hyperparameter optimisation of graph neural networks. In: 2021 IEEE congress on evolutionary computation (CEC), IEEE, pp 482–489

Haghrah A, Nekoui M, Nazari-Heris M, Mohammadi-ivatloo B (2021) An improved real-coded genetic algorithm with random walk based mutation for solving combined heat and power economic dispatch. J Ambient Intell Humaniz Comput 12(8):8561–8584

Alhijawi B, Kilani Y (2020) A collaborative filtering recommender system using genetic algorithm. Inf Process Manag 57(6):102310

Armagan A, Dunson DB, Lee J (2013) Generalized double pareto shrinkage. Stat Sin 23(1):119

Kumar M, Husian M, Upreti N, Gupta D (2010) Genetic algorithm: review and application. Int J Inf Technol Knowl Manag 2(2):451–454

Paulinas M, Ušinskas A (2007) A survey of genetic algorithms applications for image enhancement and segmentation. Inf Technol Control 36:3

Połap D (2020) An adaptive genetic algorithm as a supporting mechanism for microscopy image analysis in a cascade of convolution neural networks. Appl Soft Comput 97:106824

Sun Y, Xue B, Zhang M, Yen GG, Lv J (2020) Automatically designing CNN architectures using the genetic algorithm for image classification. IEEE Trans Cybern 50(9):3840–3854

Chen R, Yang B, Li S, Wang S (2020) A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem. Comput Ind Eng 149:106778

Zhou Z, Li F, Zhu H, Xie H, Abawajy JH, Chowdhury MU (2020) An improved genetic algorithm using greedy strategy toward task scheduling optimization in cloud environments. Neural Comput Appl 32(6):1531–1541

Maulik U, Bandyopadhyay S (2000) Genetic algorithm-based clustering technique. Pattern Recogn 33(9):1455–1465

Sheikh RH, Raghuwanshi MM, Jaiswal AN (2008) Genetic algorithm based clustering: a survey. In: 2008. ICETET’08. First international conference on emerging trends in engineering and technology, IEEE, pp 314–319

Mohammadrezapour O, Kisi O, Pourahmad F (2020) Fuzzy c-means and k-means clustering with genetic algorithm for identification of homogeneous regions of groundwater quality. Neural Comput Appl 32(8):3763–3775

Harman M, McMinn P, De Souza JT, Yoo S (2012) Search based software engineering: techniques, taxonomy, tutorial. In: Empirical software engineering and verification, pp 1–59

Srivastava PR, Kim T (2009) Application of genetic algorithm in software testing. Int J Softw Eng Appl 3(4):87–96

Harman M (2007) The current state and future of search based software engineering. In: 2007 Future of software engineering, IEEE Computer Society, pp 342–357

Ramkumar R, Mala G (2021) Non functional requirement based software architecture scheme with security requirement using hybrid group search optimization and genetic algorithm. J Ambient Intell Humaniz Comput 12(5):4863–4876

Alhijawi B, Awajan A (2021) Novel textual entailment technique for the Arabic language using genetic algorithm. Comput Speech Lang 68:101194

Iqbal F, Hashmi JM, Fung BC, Batool R, Khattak AM, Aleem S, Hung PC (2019) A hybrid framework for sentiment analysis using genetic algorithm based feature reduction. IEEE Access 7:14637–14652

Ar Y, Bostanci E (2016) A genetic algorithm solution to the collaborative filtering problem. Expert Syst Appl 61:122–128

Dwivedi P, Kant V, Bharadwaj KK (2018) Learning path recommendation based on modified variable length genetic algorithm. Educ Inf Technol 23(2):819–836

Hashemi S, Kiani S, Noroozi N, Moghaddam ME (2010) An image contrast enhancement method based on genetic algorithm. Pattern Recogn Lett 31(13):1816–1824

Daniel E, Anitha J (2015) Optimum green plane masking for the contrast enhancement of retinal images using enhanced genetic algorithm. Optik Int J Light Electron Opt 126(18):1726–1730

Deborah H, Arymurthy AM (2010) Image enhancement and image restoration for old document image using genetic algorithm. In: 2010 Second international conference on advances in computing, control and telecommunication technologies (ACT), IEEE, pp 108–112

Guo F, Peng H, Tang J (2016) Genetic algorithm-based parameter selection approach to single image defogging. Inf Process Lett 116(10):595–602

Wijayaningrum VN, Mahmudy WF (2016) Optimization of ship’s route scheduling using genetic algorithm. Indones J Electr Eng Comput Sci 2(1):180–186

Xu Y, Li K, Hu J, Li K (2014) A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf Sci 270:255–287

Faghihi V, Reinschmidt KF, Kang JH (2014) Construction scheduling using genetic algorithm based on building information model. Expert Syst Appl 41(16):7565–7578

Konar D, Bhattacharyya S, Sharma K, Sharma S, Pradhan SR (2017) An improved hybrid quantum-inspired genetic algorithm (Hqiga) for scheduling of real-time task in multiprocessor system. Appl Soft Comput 53:296–307

Keshanchi B, Souri A, Navimipour NJ (2017) An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing. J Syst Softw 124:1–21

Soundarya V, Kanimozhi U, Manjula D (2017) Recommendation system for criminal behavioral analysis on social network using genetic weighted k-means clustering. JCP 12(3):212–220

Wang Z, Yu X, Feng N, Wang Z (2014) An improved collaborative movie recommendation system using computational intelligence. J Vis Lang Comput 25(6):667–675

Georgiou O, Tsapatsoulis N (2010) Improving the scalability of recommender systems by clustering using genetic algorithms. In: International conference on artificial neural networks, Springer, pp 442–449

El-Samak AF, Ashour W (2015) Optimization of traveling salesman problem using affinity propagation clustering and genetic algorithm. J Artif Intell Soft Comput Res 5(4):239–245

Rahman MA, Islam MZ (2014) A hybrid clustering technique combining a novel genetic algorithm with k-means. Knowl Based Syst 71:345–365

Shaw MKE (2015) K-means clustering with automatic determination of k using a multiobjective genetic algorithm with applications to microarray gene expression data. PhD thesis, San Diego State University

Lahari K, Murty MR, Satapathy SC (2015) Partition based clustering using genetic algorithm and teaching learning based optimization: performance analysis. In: Emerging ICT for bridging the future-proceedings of the 49th annual convention of the computer society of India CSI, vol 2, Springer, pp 191–200

Ahmed MA, Hermadi I (2008) Ga-based multiple paths test data generator. Comput Oper Res 35(10):3107–3124

Rao KK, Raju G, Nagaraj S (2012) Optimizing the software testing efficiency using genetic algorithm-implementation methodology. Softw Eng Technol 4(10):432–439

Räihä O (2010) A survey on search-based software design. Comput Sci Rev 4(4):203–249

Bhatia N (2016) A cluster adaptive genetic model for improving the recommender system. Imp J Interdiscip Res 2:8

Gupta A, Shivhare H, Sharma S (2015) Recommender system using fuzzy c-means clustering and genetic algorithm based weighted similarity measure. In: International conference on computer, communication and control (IC4), IEEE

Alahmadi DH, Zeng X-J (2015) Twitter-based recommender system to address cold-start: a genetic algorithm based trust modelling and probabilistic sentiment analysis. In: IEEE 27th international conference on tools with artificial intelligence (ICTAI), IEEE, pp 1045–1052

Verma A, Virk HK (2015) A hybrid recommender system using genetic algorithm and KNN approach. Int J Comput Sci Trends Technol (IJCST) 6(3):131–134

Verma A, Virk H (2015) A hybrid genre-based recommender system for movies using genetic algorithm and KNN approach. Int J Innov Eng Technol 5(4):48–55

Alhijawi B, Kilani Y (2016) Using genetic algorithms for measuring the similarity values between users in collaborative filtering recommender systems. In: 2016 IEEE/ACIS 15th international conference on computer and information science (ICIS), IEEE, pp 1–6

Xiao J, Luo M, Chen J-M, Li J-J (2015) An item based collaborative filtering system combined with genetic algorithms using rating behavior. In: International conference on intelligent computing, Springer, pp 453–460

Alhijawi B, Kilani Y, Alsarhan A (2020) Improving recommendation quality and performance of genetic-based recommender system. Int J Adv Intell Paradig (IJAIP) 10:1

Fong S, Ho Y, Hang Y (2008) Using genetic algorithm for hybrid modes of collaborative filtering in online recommenders. In: Eighth international conference on hybrid intelligent systems, HIS’08, IEEE, pp 174–179

Salehi M (2014) Latent feature based recommender system for learning materials using genetic algorithm. Inf Syst Telecommun 137

Athani M, Pathak N, Khan AU (2014) Dynamic music recommender system using genetic algorithm. Int J Eng Adv Technol 3(4):230–232

Zhang F, Chang H-y (2006) A collaborative filtering algorithm employing genetic clustering to ameliorate the scalability issue, IEEE, pp 331–338

Download references

Author information

Authors and affiliations.

Princess Sumaya University for Technology, Amman, Jordan

Bushra Alhijawi & Arafat Awajan

Mutah University, Al-Karak, Jordan

Arafat Awajan

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Bushra Alhijawi .

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Alhijawi, B., Awajan, A. Genetic algorithms: theory, genetic operators, solutions, and applications. Evol. Intel. 17 , 1245–1256 (2024). https://doi.org/10.1007/s12065-023-00822-6

Download citation

Received : 24 July 2022

Revised : 02 December 2022

Accepted : 31 December 2022

Published : 03 February 2023

Issue Date : June 2024

DOI : https://doi.org/10.1007/s12065-023-00822-6

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Genetic algorithms
• Evolutionary algorithm
• Genetic operators
• Optimization
• Find a journal
• Publish with us
• Track your research

An official website of the United States government

The .gov means it’s official. Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

The site is secure. The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

• Publications
• Account settings

Preview improvements coming to the PMC website in October 2024. Learn More or Try it out now .

• Advanced Search
• Journal List
• Springer Nature - PMC COVID-19 Collection

A review on genetic algorithm: past, present, and future

Sourabh katoch.

Computer Science and Engineering Department, National Institute of Technology, Hamirpur, India

Sumit Singh Chauhan

Vijay kumar.

In this paper, the analysis of recent advances in genetic algorithms is discussed. The genetic algorithms of great interest in research community are selected for analysis. This review will help the new and demanding researchers to provide the wider vision of genetic algorithms. The well-known algorithms and their implementation are presented with their pros and cons. The genetic operators and their usages are discussed with the aim of facilitating new researchers. The different research domains involved in genetic algorithms are covered. The future research directions in the area of genetic operators, fitness function and hybrid algorithms are discussed. This structured review will be helpful for research and graduate teaching.

Introduction

In the recent years, metaheuristic algorithms are used to solve real-life complex problems arising from different fields such as economics, engineering, politics, management, and engineering [ 113 ]. Intensification and diversification are the key elements of metaheuristic algorithm. The proper balance between these elements are required to solve the real-life problem in an effective manner. Most of metaheuristic algorithms are inspired from biological evolution process, swarm behavior, and physics’ law [ 17 ]. These algorithms are broadly classified into two categories namely single solution and population based metaheuristic algorithm (Fig.  1 ). Single-solution based metaheuristic algorithms utilize single candidate solution and improve this solution by using local search. However, the solution obtained from single-solution based metaheuristics may stuck in local optima [ 112 ]. The well-known single-solution based metaheuristics are simulated annealing, tabu search (TS), microcanonical annealing (MA), and guided local search (GLS). Population-based metaheuristics utilizes multiple candidate solutions during the search process. These metaheuristics maintain the diversity in population and avoid the solutions are being stuck in local optima. Some of well-known population-based metaheuristic algorithms are genetic algorithm (GA) [ 135 ], particle swarm optimization (PSO) [ 101 ], ant colony optimization (ACO) [ 47 ], spotted hyena optimizer (SHO) [ 41 ], emperor penguin optimizer (EPO) [ 42 ], and seagull optimization (SOA) [ 43 ].

Classification of metaheuristic Algorithms

Among the metaheuristic algorithms, Genetic algorithm (GA) is a well-known algorithm, which is inspired from biological evolution process [ 136 ]. GA mimics the Darwinian theory of survival of fittest in nature. GA was proposed by J.H. Holland in 1992. The basic elements of GA are chromosome representation, fitness selection, and biological-inspired operators. Holland also introduced a novel element namely, Inversion that is generally used in implementations of GA [ 77 ]. Typically, the chromosomes take the binary string format. In chromosomes, each locus (specific position on chromosome) has two possible alleles (variant forms of genes) - 0 and 1. Chromosomes are considered as points in the solution space. These are processed using genetic operators by iteratively replacing its population. The fitness function is used to assign a value for all the chromosomes in the population [ 136 ]. The biological-inspired operators are selection, mutation, and crossover. In selection, the chromosomes are selected on the basis of its fitness value for further processing. In crossover operator, a random locus is chosen and it changes the subsequences between chromosomes to create off-springs. In mutation, some bits of the chromosomes will be randomly flipped on the basis of probability [ 77 , 135 , 136 ]. The further development of GA based on operators, representation, and fitness has diminished. Therefore, these elements of GA are focused in this paper.

The main contribution of this paper are as follows:

• The general framework of GA and hybrid GA are elaborated with mathematical formulation.
• The various types of genetic operators are discussed with their pros and cons.
• The variants of GA with their pros and cons are discussed.
• The applicability of GA in multimedia fields is discussed.

The main aim of this paper is two folds. First, it presents the variants of GA and their applicability in various fields. Second, it broadens the area of possible users in various fields. The various types of crossover, mutation, selection, and encoding techniques are discussed. The single-objective, multi-objective, parallel, and hybrid GAs are deliberated with their advantages and disadvantages. The multimedia applications of GAs are elaborated.

The remainder of this paper is organized as follows: Section 2 presents the methodology used to carry out the research. The classical genetic algorithm and genetic operators are discussed in Section 3 . The variants of genetic algorithm with pros and cons are presented in Section 4 . Section 5 describes the applications of genetic algorithm. Section 6 presents the challenges and future research directions. The concluding remarks are drawn in Section 7 .

Research methodology

PRISMA’s guidelines were used to conduct the review of GA [ 138 ]. A detailed search has been done on Google scholar and PubMed for identification of research papers related to GA. The important research works found during the manual search were also added in this paper. During search, some keywords such as “Genetic Algorithm” or “Application of GA” or “operators of GA” or “representation of GA” or “variants of GA” were used. The selection and rejection of explored research papers are based on the principles, which is mentioned in Table ​ Table1 1 .

Selection criterion for shortlisted research papers

Total 27,64,792 research papers were explored on Google Scholar, PubMed and manual search. The research work related to genetic algorithm for multimedia applications were also included. During the screening of research papers, all the duplicate papers and papers published before 2007 were discarded. 4340 research papers were selected based on 2007 and duplicate entries. Thereafter, 4050 research papers were eliminated based on titles. 220 research papers were eliminated after reading of abstract. 70 research papers were left after third round of screening. 40 more research papers were discarded after full paper reading and facts found in the papers. After the fourth round of screening, final 30 research papers are selected for review.

Based on the relevance and quality of research, 30 papers were selected for evaluation. The relevance of research is decided through some criteria, which is mentioned in Table ​ Table1. 1 . The selected research papers comprise of genetic algorithm for multimedia applications, advancement of their genetic operators, and hybridization of genetic algorithm with other well-established metaheuristic algorithms. The pros and cons of genetic operators are shown in preceding section.

In this section, the basic structure of GA and its genetic operators are discussed with pros and cons.

Classical GA

Genetic algorithm (GA) is an optimization algorithm that is inspired from the natural selection. It is a population based search algorithm, which utilizes the concept of survival of fittest [ 135 ]. The new populations are produced by iterative use of genetic operators on individuals present in the population. The chromosome representation, selection, crossover, mutation, and fitness function computation are the key elements of GA. The procedure of GA is as follows. A population ( Y ) of n chromosomes are initialized randomly. The fitness of each chromosome in Y is computed. Two chromosomes say C1 and C2 are selected from the population Y according to the fitness value. The single-point crossover operator with crossover probability (C p ) is applied on C1 and C2 to produce an offspring say O . Thereafter, uniform mutation operator is applied on produced offspring ( O ) with mutation probability (M p ) to generate O′ . The new offspring O′ is placed in new population. The selection, crossover, and mutation operations will be repeated on current population until the new population is complete. The mathematical analysis of GA is as follows [ 126 ]:

GA dynamically change the search process through the probabilities of crossover and mutation and reached to optimal solution. GA can modify the encoded genes. GA can evaluate multiple individuals and produce multiple optimal solutions. Hence, GA has better global search capability. The offspring produced from crossover of parent chromosomes is probable to abolish the admirable genetic schemas parent chromosomes and crossover formula is defined as [ 126 ]:

where g is the number of generations, and G is the total number of evolutionary generation set by population. It is observed from Eq.( 1 ) that R is dynamically changed and increase with increase in number of evolutionary generation. In initial stage of GA, the similarity between individuals is very low. The value of R should be low to ensure that the new population will not destroy the excellent genetic schema of individuals. At the end of evolution, the similarity between individuals is very high as well as the value of R should be high.

According to Schema theorem, the original schema has to be replaced with modified schema. To maintain the diversity in population, the new schema keep the initial population during the early stage of evolution. At the end of evolution, the appropriate schema will be produced to prevent any distortion of excellent genetic schema [ 65 , 75 ]. Algorithm 1 shows the pseudocode of classical genetic algorithm.

Algorithm 1: Classical Genetic Algorithm (GA)

Genetic operators

GAs used a variety of operators during the search process. These operators are encoding schemes, crossover, mutation, and selection. Figure ​ Figure2 2 depicts the operators used in GAs.

Operators used in GA

Encoding schemes

For most of the computational problems, the encoding scheme (i.e., to convert in particular form) plays an important role. The given information has to be encoded in a particular bit string [ 121 , 183 ]. The encoding schemes are differentiated according to the problem domain. The well-known encoding schemes are binary, octal, hexadecimal, permutation, value-based, and tree.

Binary encoding is the commonly used encoding scheme. Each gene or chromosome is represented as a string of 1 or 0 [ 187 ]. In binary encoding, each bit represents the characteristics of the solution. It provides faster implementation of crossover and mutation operators. However, it requires extra effort to convert into binary form and accuracy of algorithm depends upon the binary conversion. The bit stream is changed according the problem. Binary encoding scheme is not appropriate for some engineering design problems due to epistasis and natural representation.

In octal encoding scheme, the gene or chromosome is represented in the form of octal numbers (0–7). In hexadecimal encoding scheme, the gene or chromosome is represented in the form of hexadecimal numbers (0–9, A-F) [ 111 , 125 , 187 ]. The permutation encoding scheme is generally used in ordering problems. In this encoding scheme, the gene or chromosome is represented by the string of numbers that represents the position in a sequence. In value encoding scheme, the gene or chromosome is represented using string of some values. These values can be real, integer number, or character [ 57 ]. This encoding scheme can be helpful in solving the problems in which more complicated values are used. As binary encoding may fail in such problems. It is mainly used in neural networks for finding the optimal weights.

In tree encoding, the gene or chromosome is represented by a tree of functions or commands. These functions and commands can be related to any programming language. This is very much similar to the representation of repression in tree format [ 88 ]. This type of encoding is generally used in evolving programs or expressions. Table ​ Table2 2 shows the comparison of different encoding schemes of GA.

Comparison of different encoding schemes

Selection techniques

Selection is an important step in genetic algorithms that determines whether the particular string will participate in the reproduction process or not. The selection step is sometimes also known as the reproduction operator [ 57 , 88 ]. The convergence rate of GA depends upon the selection pressure. The well-known selection techniques are roulette wheel, rank, tournament, boltzmann, and stochastic universal sampling.

Roulette wheel selection maps all the possible strings onto a wheel with a portion of the wheel allocated to them according to their fitness value. This wheel is then rotated randomly to select specific solutions that will participate in formation of the next generation [ 88 ]. However, it suffers from many problems such as errors introduced by its stochastic nature. De Jong and Brindle modified the roulette wheel selection method to remove errors by introducing the concept of determinism in selection procedure. Rank selection is the modified form of Roulette wheel selection. It utilizes the ranks instead of fitness value. Ranks are given to them according to their fitness value so that each individual gets a chance of getting selected according to their ranks. Rank selection method reduces the chances of prematurely converging the solution to a local minima [ 88 ].

Tournament selection technique was first proposed by Brindle in 1983. The individuals are selected according to their fitness values from a stochastic roulette wheel in pairs. After selection, the individuals with higher fitness value are added to the pool of next generation [ 88 ]. In this method of selection, each individual is compared with all n-1 other individuals if it reaches the final population of solutions [ 88 ]. Stochastic universal sampling (SUS) is an extension to the existing roulette wheel selection method. It uses a random starting point in the list of individuals from a generation and selects the new individual at evenly spaced intervals [ 3 ]. It gives equal chance to all the individuals in getting selected for participating in crossover for the next generation. Although in case of Travelling Salesman Problem, SUS performs well but as the problem size increases, the traditional Roulette wheel selection performs relatively well [ 180 ].

Boltzmann selection is based on entropy and sampling methods, which are used in Monte Carlo Simulation. It helps in solving the problem of premature convergence [ 118 ]. The probability is very high for selecting the best string, while it executes in very less time. However, there is a possibility of information loss. It can be managed through elitism [ 175 ]. Elitism selection was proposed by K. D. Jong (1975) for improving the performance of Roulette wheel selection. It ensures the elitist individual in a generation is always propagated to the next generation. If the individual having the highest fitness value is not present in the next generation after normal selection procedure, then the elitist one is also included in the next generation automatically [ 88 ]. The comparison of above-mentioned selection techniques are depicted in Table ​ Table3 3 .

Comparison of different selection techniques

Crossover operators

Crossover operators are used to generate the offspring by combining the genetic information of two or more parents. The well-known crossover operators are single-point, two-point, k-point, uniform, partially matched, order, precedence preserving crossover, shuffle, reduced surrogate and cycle.

In a single point crossover, a random crossover point is selected. The genetic information of two parents which is beyond that point will be swapped with each other [ 190 ]. Figure ​ Figure3 3 shows the genetic information after swapping. It replaced the tail array bits of both the parents to get the new offspring.

Swapping genetic information after a crossover point

In a two point and k-point crossover, two or more random crossover points are selected and the genetic information of parents will be swapped as per the segments that have been created [ 190 ]. Figure ​ Figure4 4 shows the swapping of genetic information between crossover points. The middle segment of the parents is replaced to generate the new offspring.

Swapping genetic information between crossover points

In a uniform crossover, parent cannot be decomposed into segments. The parent can be treated as each gene separately. We randomly decide whether we need to swap the gene with the same location of another chromosome [ 190 ]. Figure ​ Figure5 5 depicts the swapping of individuals under uniform crossover operation.

Swapping individual genes

Partially matched crossover (PMX) is the most frequently used crossover operator. It is an operator that performs better than most of the other crossover operators. The partially matched (mapped) crossover was proposed by D. Goldberg and R. Lingle [ 66 ]. Two parents are choose for mating. One parent donates some part of genetic material and the corresponding part of other parent participates in the child. Once this process is completed, the left out alleles are copied from the second parent [ 83 ]. Figure ​ Figure6 6 depicts the example of PMX.

Partially matched crossover (PMX) [ 117 ]

Order crossover (OX) was proposed by Davis in 1985. OX copies one (or more) parts of parent to the offspring from the selected cut-points and fills the remaining space with values other than the ones included in the copied section. The variants of OX are proposed by different researchers for different type of problems. OX is useful for ordering problems [ 166 ]. However, it is found that OX is less efficient in case of Travelling Salesman Problem [ 140 ]. Precedence preserving crossover (PPX) preserves the ordering of individual solutions as present in the parent of offspring before the application of crossover. The offspring is initialized to a string of random 1’s and 0’s that decides whether the individuals from both parents are to be selected or not. In [ 169 ], authors proposed a modified version of PPX for multi-objective scheduling problems.

Shuffle crossover was proposed by Eshelman et al. [ 20 ] to reduce the bias introduced by other crossover techniques. It shuffles the values of an individual solution before the crossover and unshuffles them after crossover operation is performed so that the crossover point does not introduce any bias in crossover. However, the utilization of this crossover is very limited in the recent years. Reduced surrogate crossover (RCX) reduces the unnecessary crossovers if the parents have the same gene sequence for solution representations [ 20 , 139 ]. RCX is based on the assumption that GA produces better individuals if the parents are sufficiently diverse in their genetic composition. However, RCX cannot produce better individuals for those parents that have same composition. Cycle crossover was proposed by Oliver [ 140 ]. It attempts to generate an offspring using parents where each element occupies the position by referring to the position of their parents [ 140 ]. In the first cycle, it takes some elements from the first parent. In the second cycle, it takes the remaining elements from the second parent as shown in Fig.  7 .

Cycle Crossover (CX) [ 140 ]

Table ​ Table4 4 shows the comparison of crossover techniques. It is observed from Table ​ Table4 4 that single and k-point crossover techniques are easy to implement. Uniform crossover is suitable for large subsets. Order and cycle crossovers provide better exploration than the other crossover techniques. Partially matched crossover provides better exploration. The performance of partially matched crossover is better than the other crossover techniques. Reduced surrogate and cycle crossovers suffer from premature convergence.

Comparison of different crossover techniques

Mutation operators

Mutation is an operator that maintains the genetic diversity from one population to the next population. The well-known mutation operators are displacement, simple inversion, and scramble mutation. Displacement mutation (DM) operator displaces a substring of a given individual solution within itself. The place is randomly chosen from the given substring for displacement such that the resulting solution is valid as well as a random displacement mutation. There are variants of DM are exchange mutation and insertion mutation. In Exchange mutation and insertion mutation operators, a part of an individual solution is either exchanged with another part or inserted in another location, respectively [ 88 ].

The simple inversion mutation operator (SIM) reverses the substring between any two specified locations in an individual solution. SIM is an inversion operator that reverses the randomly selected string and places it at a random location [ 88 ]. The scramble mutation (SM) operator places the elements in a specified range of the individual solution in a random order and checks whether the fitness value of the recently generated solution is improved or not [ 88 ]. Table ​ Table5 5 shows the comparison of different mutation techniques.

Comparison of different mutation operators

Table ​ Table6 6 shows the best combination of encoding scheme, mutation, and crossover techniques. It is observed from Table ​ Table6 6 that uniform and single-point crossovers can be used with most of encoding and mutation operators. Partially matched crossover is used with inversion mutation and permutation encoding scheme provides the optimal solution.

Best combination of various operators under optimal Environment

Variants of GA

Various variants of GA’s have been proposed by researchers. The variants of GA are broadly classified into five main categories namely, real and binary coded, multiobjective, parallel, chaotic, and hybrid GAs. The pros and cons of these algorithms with their application has been discussed in the preceding subsections.

Real and binary coded GAs

Based on the representation of chromosomes, GAs are categorized in two classes, namely binary and real coded GAs.

Binary coded GAs

The binary representation was used to encode GA and known as binary GA. The genetic operators were also modified to carry out the search process. Payne and Glen [ 153 ] developed a binary GA to identify the similarity among molecules. They used binary representation for position of molecule and their conformations. However, this method has high computational complexity. Longyan et al. [ 203 ] investigated three different method for wind farm design using binary GA (BGA). Their method produced better fitness value and farm efficiency. Shukla et al. [ 185 ] utilized BGA for feature subset selection. They used mutual information maximization concept for selecting the significant features. BGAs suffer from Hamming cliffs, uneven schema, and difficulty in achieving precision [ 116 , 199 ].

Real-coded GAs

Real-coded GAs (RGAs) have been widely used in various real-life applications. The representation of chromosomes is closely associated with real-life problems. The main advantages of RGAs are robust, efficient, and accurate. However, RGAs suffer from premature convergence. Researchers are working on RGAs to improve their performance. Most of RGAs are developed by modifying the crossover, mutation and selection operators.

The searching capability of crossover operators are not satisfactory for continuous search space. The developments in crossover operators have been done to enhance their performance in real environment. Wright [ 210 ] presented a heuristics crossover that was applied on parents to produce off-spring. Michalewicz [ 135 ] proposed arithmetical crossover operators for RGAs. Deb and Agrawal [ 34 ] developed a real-coded crossover operator, which is based on characteristics of single-point crossover in BGA. The developed crossover operator named as simulated binary crossover (SBX). SBX is able to overcome the Hamming cliff, precision, and fixed mapping problem. The performance of SBX is not satisfactory in two-variable blocked function. Eshelman et al. [ 53 ] utilized the schemata concept to design the blend crossover for RGAs. The unimodal normal distribution crossover operator (UNDX) was developed by Ono et al. [ 144 ]. They used ellipsoidal probability distribution to generate the offspring. Kita et al. [ 106 ] presented a multi-parent UNDX (MP-UNDX), which is the extension of [ 144 ]. However, the performance of RGA with MP-UNDX is much similar to UNDX. Deep and Thakur [ 39 ] presented a Laplace crossover for RGAs, which is based on Laplacian distribution. Chuang et al. [ 27 ] developed a direction based crossover to further explore the all possible search directions. However, the search directions are limited. The heuristic normal distribution crossover operator was developed by Wang et al. [ 207 ]. It generates the cross-generated offspring for better search operation. However, the better individuals are not considered in this approach. Subbaraj et al. [ 192 ] proposed Taguchi self-adaptive RCGA. They used Taguchi method and simulated binary crossover to exploit the capable offspring.

Mutation operators generate diversity in the population. The two main challenges have to tackle during the application of mutation. First, the probability of mutation operator that was applied on population. Second, the outlier produced in chromosome after mutation process. Michalewicz [ 135 ] presented uniform and non-uniform mutation operators for RGAs. Michalewicz and Schoenauer [ 136 ] developed a special case of uniform mutation. They developed boundary mutation. Deep and Thakur [ 38 ] presented a novel mutation operator based on power law and named as power mutation. Das and Pratihar [ 30 ] presented direction-based exponential mutation operator. They used direction information of variables. Tang and Tseng [ 196 ] presented a novel mutation operator for enhancing the performance of RCGA. Their approach was fast and reliable. However, it stuck in local optima for some applications. Deb et al. [ 35 ] developed polynomial mutation that was used in RCGA. It provides better exploration. However, the convergence speed is slow and stuck in local optima. Lucasius et al. [ 129 ] proposed a real-coded genetic algorithm (RCGA). It is simple and easy to implement. However, it suffers from local optima problem. Wang et al. [ 205 ] developed multi-offspring GA and investigated their performance over single point crossover. Wang et al. [ 206 ] stated the theoretical basis of multi-offspring GA. The performance of this method is better than non-multi-offspring GA. Pattanaik et al. [ 152 ] presented an improvement in the RCGA. Their method has better convergence speed and quality of solution. Wang et al. [ 208 ] proposed multi-offspring RCGA with direction based crossover for solving constrained problems.

Table ​ Table7 7 shows the mathematical formulation of genetic operators in RGAs.

Mathematical formulation of genetic operators in RGAs

Multiobjective GAs

Multiobjective GA (MOGA) is the modified version of simple GA. MOGA differ from GA in terms of fitness function assignment. The remaining steps are similar to GA. The main motive of multiobjective GA is to generate the optimal Pareto Front in the objective space in such a way that no further enhancement in any fitness function without disturbing the other fitness functions [ 123 ]. Convergence, diversity, and coverage are main goal of multiobjective GAs. The multiobjective GAs are broadly categorized into two categories namely, Pareto-based, and decomposition-based multiobjective GAs [ 52 ]. These techniques are discussed in the preceding subsections.

Pareto-based multi-objective GA

The concept of Pareto dominance was introduced in multiobjective GAs. Fonseca and Fleming [ 56 ] developed first multiobjective GA (MOGA). The niche and decision maker concepts were proposed to tackle the multimodal problems. However, MOGA suffers from parameter tuning problem and degree of selection pressure. Horn et al. [ 80 ] proposed a niched Pareto genetic algorithm (NPGA) that utilized the concept of tournament selection and Pareto dominance. Srinivas and Deb [ 191 ] developed a non-dominated sorting genetic algorithm (NSGA). However, it suffers from lack of elitism, need of sharing parameter, and high computation complexity. To alleviate these problems, Deb et al. [ 36 ] developed a fast elitist non-dominated sorting genetic algorithm (NSGA-II). The performance of NSGA-II may be deteriorated for many objective problems. NSGA-II was unable to maintain the diversity in Pareto-front. To alleviate this problem, Luo et al. [ 130 ] introduced a dynamic crowding distance in NSGA-II. Coello and Pulido [ 28 ] developed a multiobjective micro GA. They used an archive for storing the non-dominated solutions. The performance of Pareto-based approaches may be deteriorated in many objective problems [ 52 ].

Decomposition-based multiobjective GA

Decomposition-based MOGAs decompose the given problem into multiple subproblems. These subproblems are solved simultaneously and exchange the solutions among neighboring subproblems [ 52 ]. Ishibuchi and Murata [ 84 ] developed a multiobjective genetic local search (MOGLS). In MOGLS, the random weights were used to select the parents and local search for their offspring. They used generation replacement and roulette wheel selection method. Jaszkiewicz [ 86 ] modified the MOGLS by utilizing different selection mechanisms for parents. Murata and Gen [ 141 ] proposed a cellular genetic algorithm for multiobjective optimization (C-MOGA) that was an extension of MOGA. They added cellular structure in MOGA. In C-MOGA, the selection operator was performed on the neighboring of each cell. C-MOGA was further extended by introducing an immigration procedure and known as CI-MOGA. Alves and Almeida [ 11 ] developed a multiobjective Tchebycheffs-based genetic algorithm (MOTGA) that ensures convergence and diversity. Tchebycheff scalar function was used to generate non-dominated solution set. Patel et al. [ 151 ] proposed a decomposition based MOGA (D-MOGA). They integrated opposition based learning in D-MOGA for weight vector generation. D-MOGA is able to maintain the balance between diversity of solutions and exploration of search space.

Parallel GAs

The motivation behind the parallel GAs is to improve the computational time and quality of solutions through distributed individuals. Parallel GAs are categorized into three broad categories such as master-slave parallel GAs, fine grained parallel GAs, and multi-population coarse grained parallel Gas [ 70 ]. In master-slave parallel GA, the computation of fitness functions is distributed over the several processors. In fine grained GA, parallel computers are used to solve the real-life problems. The genetic operators are bounded to their neighborhood. However, the interaction is allowed among the individuals. In coarse grained GA, the exchange of individuals among sub-populations is performed. The control parameters are also transferred during migration. The main challenges in parallel GAs are to maximize memory bandwidth and arrange threads for utilizing the power of GPUs [ 23 ]. Table ​ Table8 8 shows the comparative analysis of parallel GAs in terms of hardware and software. The well-known parallel GAs are studied in the preceding subsections.

Analysis of parallel GAs in terms of hardware and software

Master slave parallel GA

The large number of processors are utilized in master-slave parallel GA (MS-PGA) as compared to other approaches. The computation of fitness functions may be increased by increasing the number of processors. Hong et al. [ 79 ] used MS-PGA for solving data mining problems. Fuzzy rules are used with parallel GA. The evaluation of fitness function was performed on slave machines. However, it suffers from high computational time. Sahingzo [ 174 ] implemented MS-PGA for UAV path finding problem. The genetic operators were executed on processors. They used multicore CPU with four cores. Selection and fitness evaluation was done on slave machines. MS-PGA was applied on traffic assignment problem in [ 127 ]. They used thirty processors to solve this problem at National University of Singapore. Yang et al. [ 213 ] developed a web-based parallel GA. They implemented the master slave version of NSGA-II in distributed environment. However, the system is complex in nature.

Fine grained parallel GA

In last few decades, researchers are working on migration policies of fine grained parallel GA (FG-PGA). Porta et al. [ 161 ] utilized clock-time for migration frequency, which is independent of generations. They used non-uniform structure and static configuration. The best solution was selected for migration and worst solution was replaced with migrant solution. Kurdi [ 115 ] used adaptive migration frequency. The migration procedure starts until there is no change in the obtained solutions after ten successive generations. The non-uniform and dynamic structure was used. In [ 209 ], local best solutions were synchronized and formed a global best solutions. The global best solutions were transferred to all processors for father execution. The migration frequency depends upon the number of generation. They used uniform structure with fixed configuration. Zhang et al. [ 220 ] used parallel GA to solve the set cover problem of wireless networks. They used divide-and-conquer strategy to decompose the population into sub-populations. Thereafter, the genetic operators were applied on local solutions and Kuhn-Munkres was used to merge the local solutions.

Coarse grained parallel GA

Pinel et al. [ 158 ] proposed a GraphCell. The population was initialized with random values and one solution was initialized with Min-min heuristic technique. 448 processors were used to implement the proposed approach. However, coarse grained parallel GAs are less used due to complex in nature. The hybrid parallel GAs are widely used in various applications. Shayeghi et al. [ 182 ] proposed a pool-based Birmingham cluster GA. Master node was responsible for managing global population. Slave node selected the solutions from global population and executed it. 240 processors are used for computation. Roberge et al. [ 170 ] used hybrid approach to optimize switching angle of inverters. They used four different strategies for fitness function computation. Nowadays, GPU, cloud, and grid are most popular hardware for parallel GAs [ 198 ].

Chaotic GAs

The main drawback of GAs is premature convergence. The chaotic systems are incorporated into GAs to alleviate this problem. The diversity of chaos genetic algorithm removes premature convergence. Crossover and mutation operators can be replaced with chaotic maps. Tiong et al. [ 197 ] integrated the chaotic maps into GA for further improvement in accuracy. They used six different chaotic maps. The performance of Logistic, Henon and Ikeda chaotic GA performed better than the classical GA. However, these techniques suffer from high computational complexity. Ebrahimzadeh and Jampour [ 48 ] used Lorenz chaotic for genetic operators of GA to eliminate the local optima problem. However, the proposed approach was unable to find relationship between entropy and chaotic map. Javidi and Hosseinpourfard [ 87 ] utilized two chaotic maps namely logistic map and tent map for generating chaotic values instead of random selection of initial population. The proposed chaotic GA performs better than the GA. However, this method suffers from high computational complexity. Fuertes et al. [ 60 ] integrated the entropy into chaotic GA. The control parameters are modified through chaotic maps. They investigated the relationship between entropy and performance optimization.

Chaotic systems have also used in multiobjective and hybrid GAs. Abo-Elnaga and Nasr [ 5 ] integrated chaotic system into modified GA for solving Bi-level programming problems. Chaotic helps the proposed algorithm to alleviate local optima and enhance the convergence. Tahir et al. [ 193 ] presented a binary chaotic GA for feature selection in healthcare. The chaotic maps were used to initialize the population and modified reproduction operators were applied on population. Xu et al. [ 115 ] proposed a chaotic hybrid immune GA for spectrum allocation. The proposed approach utilizes the advantages of both chaotic and immune operator. However, this method suffers from parameter initialization problem.

Genetic Algorithms can be easily hybridized with other optimization methods for improving their performance such as image denoising methods, chemical reaction optimization, and many more. The main advantages of hybridized GA with other methods are better solution quality, better efficiency, guarantee of feasible solutions, and optimized control parameters [ 51 ]. It is observed from literature that the sampling capability of GAs is greatly affected from population size. To resolve this problem, local search algorithms such as memetic algorithm, Baldwinian, Lamarckian, and local search have been integrated with GAs. This integration provides proper balance between intensification and diversification. Another problem in GA is parameter setting. Finding appropriate control parameters is a tedious task. The other metaheuristic techniques can be used with GA to resolve this problem. Hybrid GAs have been used to solve the issues mentioned in the preceding subsections [ 29 , 137 , 186 ].

Enhance search capability

GAs have been integrated with local search algorithms to reduce the genetic drift. The explicit refinement operator was introduced in local search for producing better solutions. El-Mihoub et al. [ 54 ] established the effect of probability of local search on the population size of GA. Espinoza et al. [ 50 ] investigated the effect of local search for reducing the population size of GA. Different search algorithms have been integrated with GAs for solving real-life applications.

Generate feasible solutions

In complex and high-dimensional problems, the genetic operators of GA generate infeasible solutions. PMX crossover generates the infeasible solutions for order-based problems. The distance preserving crossover operator was developed to generate feasible solutions for travelling salesman problem [ 58 ]. The gene pooling operator instead of crossover was used to generate feasible solution for data clustering [ 19 ]. Konak and Smith [ 108 ] integrated a cut-saturation algorithm with GA for designing the communication networks. They used uniform crossover to produce feasible solutions.

Replacement of genetic operators

There is a possibility to replace the genetic operators which are mentioned in Section 3.2 with other search techniques. Leng [ 122 ] developed a guided GA that utilizes the penalties from guided local search. These penalties were used in fitness function to improve the performance of GA. Headar and Fukushima [ 74 ] used simplex crossover instead of standard crossover. The standard mutation operator was replaced with simulated annealing in [ 195 ]. The basic concepts of quantum computing are used to improve the performance of GAs. The heuristic crossover and hill-climbing operators can be integrated into GA for solving three-matching problem.

Optimize control parameters

The control parameters of GA play a crucial role in maintaining the balance between intensification and diversification. Fuzzy logic has an ability to estimate the appropriate control parameters of GA [ 167 ]. Beside this, GA can be used to optimize the control parameters of other techniques. GAs have been used to optimize the learning rate, weights, and topology of neutral networks [ 21 ]. GAs can be used to estimate the optimal value of fuzzy membership in controller. It was also used to optimize the control parameters of ACO, PSO, and other metaheuristic techniques [ 156 ]. The comparative analysis of well-known GAs are mentioned in Table ​ Table9 9 .

Comparative study of GA’s variants in terms of pros and cons

Applications

Genetic Algorithms have been applied in various NP-hard problems with high accuracy rates. There are a few application areas in which GAs have been successfully applied.

Operation management

GA is an efficient metaheuristic for solving operation management (OM) problems such as facility layout problem (FLP), supply network design, scheduling, forecasting, and inventory control.

Facility layout

Datta et al. [ 32 ] utilized GA for solving single row facility layout problem (SRFLP). For SRFLP, the modified crossover and mutation operators of GA produce valid solutions. They applied GA to large sized problems that consists of 60–80 instances. However, it suffers from parameter dependency problem. Sadrzadeh [ 173 ] proposed GA for multi-line FLP have multi products. The facilities were clustered using mutation and heuristic operators. The total cost obtained from the proposed GA was decreased by 7.2% as compared to the other algorithms. Wu et al. [ 211 ] implemented hierarchical GA to find out the layout of cellular manufacturing system. However, the performance of GA is greatly affected from the genetic operators. Aiello et al. [ 7 ] proposed MOGA for FLP. They used MOGA on the layout of twenty different departments. Palomo-Romero et al. [ 148 ] proposed an island model GA to solve the FLP. The proposed technique maintains the population diversity and generates better solutions than the existing techniques. However, this technique suffers from improper migration strategy that can be utilized for improving the population. GA and its variants has been successfully applied on FLP [ 103 , 119 , 133 , 201 ].

GA shows the superior performance for solving the scheduling problems such as job-shop scheduling (JSS), integrated process planning and scheduling (IPPS), etc. [ 119 ]. To improve the performance in the above-mentioned areas of scheduling, researchers developed various genetic representation [ 12 , 159 , 215 ], genetic operators, and hybridized GA with other methods [ 2 , 67 , 147 , 219 ].

Inventory control

Besides the scheduling, inventory control plays an important role in OM. Backordering and lost sales are two main approaches for inventory control [ 119 ]. Hiassat et al. [ 76 ] utilized the location-inventory model to find out the number and location of warehouses. Various design constraints have been added in the objective functions of GA and its variants for solving inventory control problem [].

Forecasting and network design

Forecasting is an important component for OM. Researchers are working on forecasting of financial trading, logistics demand, and tourist arrivals. GA has been hybridized with support vector regression, fuzzy set, and neural network (NN) to improve their forecasting capability [ 22 , 78 , 89 , 178 , 214 ]. Supply network design greatly affect the operations planning and scheduling. Most of the research articles are focused on capacity constraints of facilities [ 45 , 184 ]. Multi-product multi-period problems increases the complexity of supply networks. To resolve the above-mentioned problem, GA has been hybridized with other techniques [ 6 , 45 , 55 , 188 , 189 ]. Multi-objective GAs are also used to optimize the cost, profit, carbon emissions, etc. [ 184 , 189 ].

GAs have been applied in various fields of multimedia. Some of well-known multimedia fields are encryption, image processing, video processing, medical imaging, and gaming.

Information security

Due to development in multimedia applications, images, videos and audios are transferred from one place to another over Internet. It has been found in literature that the images are more error prone during the transmission. Therefore, image protection techniques such as encryption, watermarking and cryptography are required. The classical image encryption techniques require the input parameters for encryption. The wrong selection of input parameters will generate inadequate encryption results. GA and its variants have been used to select the appropriate control parameters. Kaur and Kumar [ 96 ] developed a multi-objective genetic algorithm to optimize the control parameters of chaotic map. The secret key was generated using beta chaotic map. The generated key was use to encrypt the image. Parallel GAs were also used to encrypt the image [ 97 ].

Image processing

The main image processing tasks are preprocessing, segmentation, object detection, denoising, and recognition. Image segmentation is an important step to solve the image processing problems. Decomposing/partitioning an image requires high computational time. To resolve this problem, GA is used due to their better search capability [ 26 , 102 ]. Enhancement is a technique to improve the quality and contrast of an image. The better image quality is required to analyze the given image. GAs have been used to enhance natural contrast and magnify image [ 40 , 64 , 99 ]. Some researchers are working on hybridization of rough set with adaptive genetic algorithm to merge the noise and color attributes. GAs have been used to remove the noise from the given image. GA can be hybridized with fuzzy logic to denoise the noisy image. GA based restoration technique can be used to remove haze, fog and smog from the given image [ 8 , 110 , 146 , 200 ]. Object detection and recognition is a challenging issue in real-world problem. Gaussian mixture model provides better performance during detection and recognition process. The control parameters are optimized through GA [ 93 ].

Video processing

Video segmentation has been widely used in pattern recognition, and computer vision. There are some critical issues that are associated with video segmentation. These are distinguishing object from the background and determine accurate boundaries. GA can be used to resolve these issues [ 9 , 105 ]. GAs have been implemented for gesture recognition successfully by Chao el al. [ 81 ] used GA for gesture recognition. They applied GAs and found an accuracy of 95% in robot vision. Kaluri and Reddy [ 91 ] proposed an adaptive genetic algorithm based method along with fuzzy classifiers for sign gesture recognition. They reported an improved recognition rate of 85% as compared to the existing method that provides 79% accuracy. Beside the gesture recognition, face recognition play an important role in criminal identification, unmanned vehicles, surveillance, and robots. GA is able to tackle the occlusion, orientations, expressions, pose, and lighting condition [ 69 , 95 , 109 ].

Medical imaging

Genetic algorithms have been applied in medical imaging such as edge detection in MRI and pulmonary nodules detection in CT scan images [ 100 , 179 ]. In [ 120 ], authors used a template matching technique with GA for detecting nodules in CT images. Kavitha and Chellamuthu [ 179 ] used GA based region growing method for detecting the brain tumor. GAs have been applied on medical prediction problems captured from pathological subjects. Sari and Tuna [ 176 ] used GA used to solve issues arises in biomechanics. It is used to predict pathologies during examination. Ghosh and Bhattachrya [ 62 ] implemented sequential GA with cellular automata for modelling the coronavirus disease 19 (COVID-19) data. GAs can be applied in parallel mode to find rules in biological datasets [ 31 ]. The authors proposed a parallel GA that runs by dividing the process into small sub-generations and evaluating the fitness of each individual solution in parallel. Genetic algorithms are used in medicine and other related fields. Koh et al. [ 61 ] proposed a genetic algorithm based method for evaluation of adverse effects of a given drug.

Precision agriculture

GAs have been applied on various problems that are related to precision agriculture. The main issues are crop yield, weed detection, and improvement in farming equipment. Pachepsky and Acock [ 145 ] implemented GA to analyze the water capacity in soil using remote sensing images. The crop yield can be predicted through the capacity of water present in soil. The weed identification was done through GA in [ 142 ]. They used aerial image for classification of plants. In [ 124 ], color image segmentation was used to discriminate the weed and plant. Peerlink et al. [ 154 ] determined the appropriate rate of fertilizer for various portions of agriculture field. They GA for determining the nitrogen in wheat field. The energy requirements in water irrigation systems can be optimized by viewing it as a multi-objective optimization problem. The amount of irrigation required and thus power requirements change continuously in a SMART farm. Therefore, GA can be applied in irrigation systems to reduce the power requirements [ 33 ].

GAs have been successfully used in games such as gomoku. In [ 202 ], the authors shown that the GA based approach finds the solution having the highest fitness than the normal tree based methods. However, in real-time strategy based games, GA based solutions become less practical to implement [ 82 ]. GAs have been implemented for path planning problems considering the environment constraints as well as avoiding the obstacles to reach the given destination. Burchardt and Salomon [ 18 ] described an implementation for path planning for soccer games. GA can encode the path planning problems via the coordinate points of a two-dimensional playing field, hence resulting in a variable length solution. The fitness function in path planning considers length of path as well as the collision avoiding terms for soccer players.

Wireless networking

Due to adaptive, scalable, and easy implementation of GA, it has been used to solve the various issues of wireless networking. The main issues of wireless networking are routing, quality of service, load balancing, localization, bandwidth allocation and channel assignment [ 128 , 134 ]. GA has been hybridized with other metaheuristics for solving the routing problems. Hybrid GA not only producing the efficient routes among pair of nodes, but also used for load balancing [ 24 , 212 ].

Load balancing

Nowadays, multimedia applications require Quality-of-Service (QoS) demand for delay and bandwidth. Various researchers are working on GAs for QoS based solutions.GA produces optimal solutions for complex networks [ 49 ]. Roy et al. [ 172 ] proposed a multi-objective GA for multicast QoS routing problem. GA was used with ACO and other search algorithms for finding optimal routes with desired QoS metrics. Load balancing is another issue in wireless networks. Scully and Brown [ 177 ] used MicroGAs and MacroGAs to distribute the load among various components of networks. He et al. [ 73 ] implemented GA to determine the balance load in wireless sensor networks. Cheng et al. [ 25 ] utilized distributed GA with multi-population scheme for load balancing. They used load balancing metric as a fitness function in GA.

Localization

The process of determining the location of wireless nodes is called as localization. It plays an important role in disaster management and military services. Yun et al. [ 216 ] used GA with fuzzy logic to find out the weights, which are assigned according to the signal strength. Zhang et al. [ 218 ] hybridized GA with simulated annealing (SA) to determine the position of wireless nodes. SA is used as local search to eliminate the premature convergence.

Bandwidth and channel allocation

The appropriate bandwidth allocation is a complex task. GAs and its variants have been developed to solve the bandwidth allocation problem [ 92 , 94 , 107 ]. GAs were used to investigate the allocation of bandwidth with QoS constraints. The fitness function of GAs may consists of resource utilization, bandwidth distribution, and computation time [ 168 ]. The channel allocation is an important issue in wireless networks. The main objective of channel allocation is to simultaneously optimize the number of channels and reuse of allocated frequency. Friend et al. [ 59 ] used distributed island GA to resolve the channel allocation problem in cognitive radio networks. Zhenhua et al. [ 221 ] implemented a modified immune GA for channel assignment. They used different encoding scheme and immune operators. Pinagapany and Kulkarni [ 157 ] developed a parallel GA to solve both static and dynamic channel allocation problem. They used decimal encoding scheme. Table ​ Table10 10 summarizes the applications of GA and its variants.

Applications of GA

Challenges and future possibilities

In this section, the main challenges faced during the implementation of GAs are discussed followed by the possible research directions.

Despite the several advantages, there are some challenges that need to be resolved for future advancements and further evolution of genetic algorithms. Some major challenges are given below:

Selection of initial population

Initial population is always considered as an important factor for the performance of genetic algorithms. The size of population also affects the quality of solution [ 160 ]. The researchers argue that if a large population is considered, then the algorithm takes more computation time. However, the small population may lead to poor solution [ 155 ]. Therefore, finding the appropriate population size is always a challenging issue. Harik and Lobo [ 71 ] investigated the population using self-adaption method. They used two approaches such as (1) use of self-adaption prior to execution of algorithm, in which the size of population remains the same and (2) in which the self-adaption used during the algorithm execution where the population size is affected by fitness function.

Premature convergence

Premature convergence is a common issue for GA. It can lead to the loss of alleles that makes it difficult to identify a gene [ 15 ]. Premature convergence states that the result will be suboptimal if the optimization problem coincides too early. To avoid this issue, some researchers suggested that the diversity should be used. The selection pressure should be used to increase the diversity. Selection pressure is a degree which favors the better individuals in the initial population of GA’s. If selection pressure (SP1) is greater than some selection pressure (SP2), then population using SP1 should be larger than the population using SP2. The higher selection pressure can decrease the population diversity that may lead to premature convergence [ 71 ].

Convergence property has to be handled properly so that the algorithm finds global optimal solution instead of local optimal solution (see Fig. ​ Fig.8). 8 ). If the optimal solution lies in the vicinity of an infeasible solution, then the global nature of GA can be combined with local nature of other algorithms such as Tabu search and local search. The global nature of genetic algorithms and local nature of Tabu search provide the proper balance between intensification and diversification.

Local and global optima [ 149 ]

Selection of efficient fitness functions

Fitness function is the driving force, which plays an important role in selecting the fittest individual in every iteration of an algorithm. If the number of iterations are small, then a costly fitness function can be adjusted. The number of iterations increases may increase the computational cost. The selection of fitness function depends upon the computational cost as well as their suitability. In [ 46 ], the authors used Davies-Bouldin index for classification of documents.

Degree of mutation and crossover

Crossover and mutation operators are the integral part of GAs. If the mutation is not considered during evolution, then there will be no new information available for evolution. If crossover is not considered during evolution, then the algorithm can result in local optima. The degree of these operators greatly affect the performance of GAs [ 72 ]. The proper balance between these operators are required to ensure the global optima. The probabilistic nature cannot determine the exact degree for an effective and optimal solution.

Selection of encoding schemes

GAs require a particular encoding scheme for a specific problem. There is no general methodology for deciding whether the particular encoding scheme is suitable for any type of real-life problem. If there are two different problems, then two different encoding schemes are required. Ronald [ 171 ] suggested that the encoding schemes should be designed to overwhelm the redundant forms. The genetic operators should be implemented in a manner that they are not biased towards the redundant forms.

Future research directions

GAs have been applied in different fields by modifying the basic structure of GA. The optimality of a solution obtained from GA can be made better by overcoming the current challenges. Some future possibilities for GA are as follows:

• There should be some way to choose the appropriate degree of crossover and mutation operators. For example Self-Organizing GA adapt the crossover and mutation operators according to the given problem. It can save computation time that make it faster.
• Future work can also be considered for reducing premature convergence problem. Some researchers are working in this direction. However, it is suggested that new methods of crossover and mutation techniques are required to tackle the premature convergence problem.
• Genetic algorithms mimic the natural evolution process. There can be a possible scope for simulating the natural evolution process such as the responses of human immune system and the mutations in viruses.
• In real-life problems, the mapping from genotype to phenotype is complex. In this situation, the problem has no obvious building blocks or building blocks are not adjacent groups of genes. Hence, there is a possibility to develop novel encoding schemes to different problems that does not exhibit same degree of difficulty.

Conclusions

This paper presents the structured and explained view of genetic algorithms. GA and its variants have been discussed with application. Application specific genetic operators are discussed. Some genetic operators are designed for representation. However, they are not applicable to research domains. The role of genetic operators such as crossover, mutation, and selection in alleviating the premature convergence is studied extensively. The applicability of GA and its variants in various research domain has been discussed. Multimedia and wireless network applications were the main attention of this paper. The challenges and issues mentioned in this paper will help the practitioners to carry out their research. There are many advantages of using GAs in other research domains and metaheuristic algorithms.

The intention of this paper is not only provide the source of recent research in GAs, but also provide the information about each component of GA. It will encourage the researchers to understand the fundamentals of GA and use the knowledge in their research problems.

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

• Search Menu

Sign in through your institution

• Browse content in Arts and Humanities
• Browse content in Archaeology
• Anglo-Saxon and Medieval Archaeology
• Archaeological Methodology and Techniques
• Archaeology by Region
• Archaeology of Religion
• Archaeology of Trade and Exchange
• Biblical Archaeology
• Contemporary and Public Archaeology
• Environmental Archaeology
• Historical Archaeology
• History and Theory of Archaeology
• Industrial Archaeology
• Landscape Archaeology
• Mortuary Archaeology
• Prehistoric Archaeology
• Underwater Archaeology
• Urban Archaeology
• Zooarchaeology
• Browse content in Architecture
• Architectural Structure and Design
• History of Architecture
• Residential and Domestic Buildings
• Theory of Architecture
• Browse content in Art
• Art Subjects and Themes
• History of Art
• Industrial and Commercial Art
• Theory of Art
• Biographical Studies
• Byzantine Studies
• Browse content in Classical Studies
• Classical History
• Classical Philosophy
• Classical Mythology
• Classical Literature
• Classical Reception
• Classical Art and Architecture
• Classical Oratory and Rhetoric
• Greek and Roman Epigraphy
• Greek and Roman Law
• Greek and Roman Archaeology
• Greek and Roman Papyrology
• Late Antiquity
• Religion in the Ancient World
• Digital Humanities
• Browse content in History
• Colonialism and Imperialism
• Diplomatic History
• Environmental History
• Genealogy, Heraldry, Names, and Honours
• Genocide and Ethnic Cleansing
• Historical Geography
• History by Period
• History of Agriculture
• History of Education
• History of Emotions
• History of Gender and Sexuality
• Industrial History
• Intellectual History
• International History
• Labour History
• Legal and Constitutional History
• Local and Family History
• Maritime History
• Military History
• National Liberation and Post-Colonialism
• Oral History
• Political History
• Public History
• Regional and National History
• Revolutions and Rebellions
• Slavery and Abolition of Slavery
• Social and Cultural History
• Theory, Methods, and Historiography
• Urban History
• World History
• Browse content in Language Teaching and Learning
• Language Learning (Specific Skills)
• Language Teaching Theory and Methods
• Browse content in Linguistics
• Applied Linguistics
• Cognitive Linguistics
• Computational Linguistics
• Forensic Linguistics
• Grammar, Syntax and Morphology
• Historical and Diachronic Linguistics
• History of English
• Language Acquisition
• Language Variation
• Language Families
• Language Evolution
• Language Reference
• Lexicography
• Linguistic Theories
• Linguistic Typology
• Linguistic Anthropology
• Phonetics and Phonology
• Psycholinguistics
• Sociolinguistics
• Translation and Interpretation
• Writing Systems
• Browse content in Literature
• Bibliography
• Children's Literature Studies
• Literary Studies (Asian)
• Literary Studies (European)
• Literary Studies (Eco-criticism)
• Literary Studies (Modernism)
• Literary Studies (Romanticism)
• Literary Studies (American)
• Literary Studies - World
• Literary Studies (1500 to 1800)
• Literary Studies (19th Century)
• Literary Studies (20th Century onwards)
• Literary Studies (African American Literature)
• Literary Studies (British and Irish)
• Literary Studies (Early and Medieval)
• Literary Studies (Fiction, Novelists, and Prose Writers)
• Literary Studies (Gender Studies)
• Literary Studies (Graphic Novels)
• Literary Studies (History of the Book)
• Literary Studies (Plays and Playwrights)
• Literary Studies (Poetry and Poets)
• Literary Studies (Postcolonial Literature)
• Literary Studies (Queer Studies)
• Literary Studies (Science Fiction)
• Literary Studies (Travel Literature)
• Literary Studies (War Literature)
• Literary Studies (Women's Writing)
• Literary Theory and Cultural Studies
• Mythology and Folklore
• Shakespeare Studies and Criticism
• Browse content in Media Studies
• Browse content in Music
• Applied Music
• Dance and Music
• Ethics in Music
• Ethnomusicology
• Gender and Sexuality in Music
• Medicine and Music
• Music Cultures
• Music and Religion
• Music and Culture
• Music and Media
• Music Education and Pedagogy
• Music Theory and Analysis
• Musical Scores, Lyrics, and Libretti
• Musical Structures, Styles, and Techniques
• Musicology and Music History
• Performance Practice and Studies
• Race and Ethnicity in Music
• Sound Studies
• Browse content in Performing Arts
• Browse content in Philosophy
• Aesthetics and Philosophy of Art
• Epistemology
• Feminist Philosophy
• History of Western Philosophy
• Metaphysics
• Moral Philosophy
• Non-Western Philosophy
• Philosophy of Science
• Philosophy of Action
• Philosophy of Law
• Philosophy of Religion
• Philosophy of Language
• Philosophy of Mind
• Philosophy of Perception
• Philosophy of Mathematics and Logic
• Practical Ethics
• Social and Political Philosophy
• Browse content in Religion
• Biblical Studies
• Christianity
• East Asian Religions
• History of Religion
• Judaism and Jewish Studies
• Qumran Studies
• Religion and Education
• Religion and Health
• Religion and Politics
• Religion and Science
• Religion and Law
• Religion and Art, Literature, and Music
• Religious Studies
• Browse content in Society and Culture
• Cookery, Food, and Drink
• Cultural Studies
• Customs and Traditions
• Ethical Issues and Debates
• Hobbies, Games, Arts and Crafts
• Natural world, Country Life, and Pets
• Popular Beliefs and Controversial Knowledge
• Sports and Outdoor Recreation
• Technology and Society
• Travel and Holiday
• Visual Culture
• Browse content in Law
• Arbitration
• Browse content in Company and Commercial Law
• Commercial Law
• Company Law
• Browse content in Comparative Law
• Systems of Law
• Competition Law
• Browse content in Constitutional and Administrative Law
• Government Powers
• Judicial Review
• Local Government Law
• Military and Defence Law
• Parliamentary and Legislative Practice
• Construction Law
• Contract Law
• Browse content in Criminal Law
• Criminal Procedure
• Criminal Evidence Law
• Sentencing and Punishment
• Employment and Labour Law
• Environment and Energy Law
• Browse content in Financial Law
• Banking Law
• Insolvency Law
• History of Law
• Human Rights and Immigration
• Intellectual Property Law
• Browse content in International Law
• Private International Law and Conflict of Laws
• Public International Law
• IT and Communications Law
• Jurisprudence and Philosophy of Law
• Law and Politics
• Law and Society
• Browse content in Legal System and Practice
• Courts and Procedure
• Legal Skills and Practice
• Primary Sources of Law
• Regulation of Legal Profession
• Medical and Healthcare Law
• Browse content in Policing
• Criminal Investigation and Detection
• Police and Security Services
• Police Procedure and Law
• Police Regional Planning
• Browse content in Property Law
• Personal Property Law
• Study and Revision
• Terrorism and National Security Law
• Browse content in Trusts Law
• Wills and Probate or Succession
• Browse content in Medicine and Health
• Browse content in Allied Health Professions
• Arts Therapies
• Clinical Science
• Dietetics and Nutrition
• Occupational Therapy
• Operating Department Practice
• Physiotherapy
• Radiography
• Speech and Language Therapy
• Browse content in Anaesthetics
• General Anaesthesia
• Neuroanaesthesia
• Browse content in Clinical Medicine
• Acute Medicine
• Cardiovascular Medicine
• Clinical Genetics
• Clinical Pharmacology and Therapeutics
• Dermatology
• Endocrinology and Diabetes
• Gastroenterology
• Genito-urinary Medicine
• Geriatric Medicine
• Infectious Diseases
• Medical Oncology
• Medical Toxicology
• Pain Medicine
• Palliative Medicine
• Rehabilitation Medicine
• Respiratory Medicine and Pulmonology
• Rheumatology
• Sleep Medicine
• Sports and Exercise Medicine
• Clinical Neuroscience
• Community Medical Services
• Critical Care
• Emergency Medicine
• Forensic Medicine
• Haematology
• History of Medicine
• Browse content in Medical Dentistry
• Oral and Maxillofacial Surgery
• Paediatric Dentistry
• Restorative Dentistry and Orthodontics
• Surgical Dentistry
• Medical Ethics
• Browse content in Medical Skills
• Clinical Skills
• Communication Skills
• Nursing Skills
• Surgical Skills
• Medical Statistics and Methodology
• Browse content in Neurology
• Clinical Neurophysiology
• Neuropathology
• Nursing Studies
• Browse content in Obstetrics and Gynaecology
• Gynaecology
• Occupational Medicine
• Ophthalmology
• Otolaryngology (ENT)
• Browse content in Paediatrics
• Neonatology
• Browse content in Pathology
• Chemical Pathology
• Clinical Cytogenetics and Molecular Genetics
• Histopathology
• Medical Microbiology and Virology
• Patient Education and Information
• Browse content in Pharmacology
• Psychopharmacology
• Browse content in Popular Health
• Caring for Others
• Complementary and Alternative Medicine
• Self-help and Personal Development
• Browse content in Preclinical Medicine
• Cell Biology
• Molecular Biology and Genetics
• Reproduction, Growth and Development
• Primary Care
• Professional Development in Medicine
• Browse content in Psychiatry
• Addiction Medicine
• Child and Adolescent Psychiatry
• Forensic Psychiatry
• Learning Disabilities
• Old Age Psychiatry
• Psychotherapy
• Browse content in Public Health and Epidemiology
• Epidemiology
• Public Health
• Browse content in Radiology
• Clinical Radiology
• Interventional Radiology
• Nuclear Medicine
• Radiation Oncology
• Reproductive Medicine
• Browse content in Surgery
• Cardiothoracic Surgery
• Gastro-intestinal and Colorectal Surgery
• General Surgery
• Neurosurgery
• Paediatric Surgery
• Peri-operative Care
• Plastic and Reconstructive Surgery
• Surgical Oncology
• Transplant Surgery
• Trauma and Orthopaedic Surgery
• Vascular Surgery
• Browse content in Science and Mathematics
• Browse content in Biological Sciences
• Aquatic Biology
• Biochemistry
• Bioinformatics and Computational Biology
• Developmental Biology
• Ecology and Conservation
• Evolutionary Biology
• Genetics and Genomics
• Microbiology
• Molecular and Cell Biology
• Natural History
• Plant Sciences and Forestry
• Research Methods in Life Sciences
• Structural Biology
• Systems Biology
• Zoology and Animal Sciences
• Browse content in Chemistry
• Analytical Chemistry
• Computational Chemistry
• Crystallography
• Environmental Chemistry
• Industrial Chemistry
• Inorganic Chemistry
• Materials Chemistry
• Medicinal Chemistry
• Mineralogy and Gems
• Organic Chemistry
• Physical Chemistry
• Polymer Chemistry
• Study and Communication Skills in Chemistry
• Theoretical Chemistry
• Browse content in Computer Science
• Artificial Intelligence
• Computer Architecture and Logic Design
• Game Studies
• Human-Computer Interaction
• Mathematical Theory of Computation
• Programming Languages
• Software Engineering
• Systems Analysis and Design
• Virtual Reality
• Browse content in Computing
• Business Applications
• Computer Security
• Computer Games
• Computer Networking and Communications
• Digital Lifestyle
• Graphical and Digital Media Applications
• Operating Systems
• Browse content in Earth Sciences and Geography
• Atmospheric Sciences
• Environmental Geography
• Geology and the Lithosphere
• Maps and Map-making
• Meteorology and Climatology
• Oceanography and Hydrology
• Palaeontology
• Physical Geography and Topography
• Regional Geography
• Soil Science
• Urban Geography
• Browse content in Engineering and Technology
• Agriculture and Farming
• Biological Engineering
• Civil Engineering, Surveying, and Building
• Electronics and Communications Engineering
• Energy Technology
• Engineering (General)
• Environmental Science, Engineering, and Technology
• History of Engineering and Technology
• Mechanical Engineering and Materials
• Technology of Industrial Chemistry
• Transport Technology and Trades
• Browse content in Environmental Science
• Applied Ecology (Environmental Science)
• Conservation of the Environment (Environmental Science)
• Environmental Sustainability
• Environmentalist Thought and Ideology (Environmental Science)
• Management of Land and Natural Resources (Environmental Science)
• Natural Disasters (Environmental Science)
• Nuclear Issues (Environmental Science)
• Pollution and Threats to the Environment (Environmental Science)
• Social Impact of Environmental Issues (Environmental Science)
• History of Science and Technology
• Browse content in Materials Science
• Ceramics and Glasses
• Composite Materials
• Metals, Alloying, and Corrosion
• Nanotechnology
• Browse content in Mathematics
• Applied Mathematics
• Biomathematics and Statistics
• History of Mathematics
• Mathematical Education
• Mathematical Finance
• Mathematical Analysis
• Numerical and Computational Mathematics
• Probability and Statistics
• Pure Mathematics
• Browse content in Neuroscience
• Cognition and Behavioural Neuroscience
• Development of the Nervous System
• Disorders of the Nervous System
• History of Neuroscience
• Invertebrate Neurobiology
• Molecular and Cellular Systems
• Neuroendocrinology and Autonomic Nervous System
• Neuroscientific Techniques
• Sensory and Motor Systems
• Browse content in Physics
• Astronomy and Astrophysics
• Atomic, Molecular, and Optical Physics
• Biological and Medical Physics
• Classical Mechanics
• Computational Physics
• Condensed Matter Physics
• Electromagnetism, Optics, and Acoustics
• History of Physics
• Mathematical and Statistical Physics
• Measurement Science
• Nuclear Physics
• Particles and Fields
• Plasma Physics
• Quantum Physics
• Relativity and Gravitation
• Semiconductor and Mesoscopic Physics
• Browse content in Psychology
• Affective Sciences
• Clinical Psychology
• Cognitive Neuroscience
• Cognitive Psychology
• Criminal and Forensic Psychology
• Developmental Psychology
• Educational Psychology
• Evolutionary Psychology
• Health Psychology
• History and Systems in Psychology
• Music Psychology
• Neuropsychology
• Organizational Psychology
• Psychological Assessment and Testing
• Psychology of Human-Technology Interaction
• Psychology Professional Development and Training
• Research Methods in Psychology
• Social Psychology
• Browse content in Social Sciences
• Browse content in Anthropology
• Anthropology of Religion
• Human Evolution
• Medical Anthropology
• Physical Anthropology
• Regional Anthropology
• Social and Cultural Anthropology
• Theory and Practice of Anthropology
• Browse content in Business and Management
• Business Strategy
• Business History
• Business Ethics
• Business and Government
• Business and Technology
• Business and the Environment
• Comparative Management
• Corporate Governance
• Corporate Social Responsibility
• Entrepreneurship
• Health Management
• Human Resource Management
• Industrial and Employment Relations
• Industry Studies
• Information and Communication Technologies
• International Business
• Knowledge Management
• Management and Management Techniques
• Operations Management
• Organizational Theory and Behaviour
• Pensions and Pension Management
• Public and Nonprofit Management
• Strategic Management
• Supply Chain Management
• Browse content in Criminology and Criminal Justice
• Criminal Justice
• Criminology
• Forms of Crime
• International and Comparative Criminology
• Youth Violence and Juvenile Justice
• Development Studies
• Browse content in Economics
• Agricultural, Environmental, and Natural Resource Economics
• Asian Economics
• Behavioural Finance
• Behavioural Economics and Neuroeconomics
• Econometrics and Mathematical Economics
• Economic Systems
• Economic Methodology
• Economic History
• Economic Development and Growth
• Financial Markets
• Financial Institutions and Services
• General Economics and Teaching
• Health, Education, and Welfare
• History of Economic Thought
• International Economics
• Labour and Demographic Economics
• Law and Economics
• Macroeconomics and Monetary Economics
• Microeconomics
• Public Economics
• Urban, Rural, and Regional Economics
• Welfare Economics
• Browse content in Education
• Adult Education and Continuous Learning
• Care and Counselling of Students
• Early Childhood and Elementary Education
• Educational Equipment and Technology
• Educational Strategies and Policy
• Higher and Further Education
• Organization and Management of Education
• Philosophy and Theory of Education
• Schools Studies
• Secondary Education
• Teaching of a Specific Subject
• Teaching of Specific Groups and Special Educational Needs
• Teaching Skills and Techniques
• Browse content in Environment
• Applied Ecology (Social Science)
• Climate Change
• Conservation of the Environment (Social Science)
• Environmentalist Thought and Ideology (Social Science)
• Natural Disasters (Environment)
• Social Impact of Environmental Issues (Social Science)
• Browse content in Human Geography
• Cultural Geography
• Economic Geography
• Political Geography
• Browse content in Interdisciplinary Studies
• Communication Studies
• Museums, Libraries, and Information Sciences
• Browse content in Politics
• African Politics
• Asian Politics
• Chinese Politics
• Comparative Politics
• Conflict Politics
• Elections and Electoral Studies
• Environmental Politics
• European Union
• Foreign Policy
• Gender and Politics
• Human Rights and Politics
• Indian Politics
• International Relations
• International Organization (Politics)
• International Political Economy
• Irish Politics
• Latin American Politics
• Middle Eastern Politics
• Political Methodology
• Political Communication
• Political Philosophy
• Political Sociology
• Political Theory
• Political Behaviour
• Political Economy
• Political Institutions
• Politics and Law
• Politics of Development
• Public Administration
• Public Policy
• Quantitative Political Methodology
• Regional Political Studies
• Russian Politics
• Security Studies
• State and Local Government
• UK Politics
• US Politics
• Browse content in Regional and Area Studies
• African Studies
• Asian Studies
• East Asian Studies
• Japanese Studies
• Latin American Studies
• Middle Eastern Studies
• Native American Studies
• Scottish Studies
• Browse content in Research and Information
• Research Methods
• Browse content in Social Work
• Addictions and Substance Misuse
• Adoption and Fostering
• Care of the Elderly
• Child and Adolescent Social Work
• Couple and Family Social Work
• Direct Practice and Clinical Social Work
• Emergency Services
• Human Behaviour and the Social Environment
• International and Global Issues in Social Work
• Mental and Behavioural Health
• Social Justice and Human Rights
• Social Policy and Advocacy
• Social Work and Crime and Justice
• Social Work Macro Practice
• Social Work Practice Settings
• Social Work Research and Evidence-based Practice
• Welfare and Benefit Systems
• Browse content in Sociology
• Childhood Studies
• Community Development
• Comparative and Historical Sociology
• Economic Sociology
• Gender and Sexuality
• Gerontology and Ageing
• Health, Illness, and Medicine
• Marriage and the Family
• Migration Studies
• Occupations, Professions, and Work
• Organizations
• Population and Demography
• Race and Ethnicity
• Social Theory
• Social Movements and Social Change
• Social Research and Statistics
• Social Stratification, Inequality, and Mobility
• Sociology of Religion
• Sociology of Education
• Sport and Leisure
• Urban and Rural Studies
• Browse content in Warfare and Defence
• Defence Strategy, Planning, and Research
• Land Forces and Warfare
• Military Administration
• Military Life and Institutions
• Naval Forces and Warfare
• Other Warfare and Defence Issues
• Peace Studies and Conflict Resolution
• Weapons and Equipment

• < Previous chapter
• Next chapter >

11Chapter 1 Genetic Algorithms: A 30-Year Perspective

• Published: March 2005
• Cite Icon Cite
• Permissions Icon Permissions

I continue to be surprised and pleased by the dramatic growth of interest in and applications of genetic algorithms (GAs) in recent years. This growth, in turn, has placed a certain amount of healthy "stress" on the field as current understanding and traditional approaches are stretched to the limit by challenging new problems and new areas of application. At the same time, other forms of evolutionary computation such as evolution strategies [50] and evolutionary programming [22], continue to mature and provide alternative views on how the process of evolution might be captured in an efficient and useful computational framework. I don't think there can be much disagreement about the fact that Holland's initial ideas for adaptive system design have played a fundamental role in the progress we have made in the past thirty years [23, 46]. So, an occasion like this is an opportunity to reflect on where the field is now, how it got there, and where it is headed. In the following sections, I will attempt to summarize the progress that has been made, and to identify critical issues that need to be addressed for continued progress in the field. The widespread availability of inexpensive digital computers in the 1960s gave rise to their increased use as a modeling and simulation tool by the scientific community. Several groups around the world including Rechenberg and Schwefel at the Technical University of Berlin [49], Fogel et al. at the University of California at Los Angeles [22], and Holland at the University of Michigan in Ann Arbor [35] were captivated by the potential of taking early simulation models of evolution a step further and harnessing these evolutionary processes in computational forms that could be used for complex computer-based problem solving. In Holland's case, the motivation was the design and implementation of robust adaptive systems, capable of dealing with an uncertain and changing environment. His view emphasized the need for systems which self-adapt over time as a function of feedback obtained from interacting with the environment in which they operate. This led to an initial family of "reproductive plans" which formed the basis for what we call "simple genetic algorithms" today, as outlined in figure 1.

Signed in as

Institutional accounts.

• Google Scholar Indexing
• GoogleCrawler [DO NOT DELETE]

Personal account

• Sign in with email/username & password
• Get email alerts
• Save searches
• Purchase content
• Activate your purchase/trial code
• Add your ORCID iD

Institutional access

Sign in with a library card.

• Sign in with username/password
• Recommend to your librarian
• Institutional account management
• Get help with access

Access to content on Oxford Academic is often provided through institutional subscriptions and purchases. If you are a member of an institution with an active account, you may be able to access content in one of the following ways:

IP based access

Typically, access is provided across an institutional network to a range of IP addresses. This authentication occurs automatically, and it is not possible to sign out of an IP authenticated account.

Choose this option to get remote access when outside your institution. Shibboleth/Open Athens technology is used to provide single sign-on between your institution’s website and Oxford Academic.

• Click Sign in through your institution.
• Select your institution from the list provided, which will take you to your institution's website to sign in.
• When on the institution site, please use the credentials provided by your institution. Do not use an Oxford Academic personal account.
• Following successful sign in, you will be returned to Oxford Academic.

If your institution is not listed or you cannot sign in to your institution’s website, please contact your librarian or administrator.

Enter your library card number to sign in. If you cannot sign in, please contact your librarian.

Society Members

Society member access to a journal is achieved in one of the following ways:

Sign in through society site

Many societies offer single sign-on between the society website and Oxford Academic. If you see ‘Sign in through society site’ in the sign in pane within a journal:

• Click Sign in through society site.
• When on the society site, please use the credentials provided by that society. Do not use an Oxford Academic personal account.

If you do not have a society account or have forgotten your username or password, please contact your society.

Sign in using a personal account

Some societies use Oxford Academic personal accounts to provide access to their members. See below.

A personal account can be used to get email alerts, save searches, purchase content, and activate subscriptions.

Some societies use Oxford Academic personal accounts to provide access to their members.

Viewing your signed in accounts

Click the account icon in the top right to:

• View your signed in personal account and access account management features.
• View the institutional accounts that are providing access.

Signed in but can't access content

Oxford Academic is home to a wide variety of products. The institutional subscription may not cover the content that you are trying to access. If you believe you should have access to that content, please contact your librarian.

For librarians and administrators, your personal account also provides access to institutional account management. Here you will find options to view and activate subscriptions, manage institutional settings and access options, access usage statistics, and more.

Our books are available by subscription or purchase to libraries and institutions.

• About Oxford Academic
• Publish journals with us
• University press partners
• What we publish
• New features  
• Open access
• Rights and permissions
• Accessibility
• Advertising
• Media enquiries
• Oxford University Press
• Oxford Languages
• University of Oxford

Oxford University Press is a department of the University of Oxford. It furthers the University's objective of excellence in research, scholarship, and education by publishing worldwide

• Copyright © 2024 Oxford University Press
• Cookie settings
• Cookie policy
• Privacy policy
• Legal notice

This Feature Is Available To Subscribers Only

Sign In or Create an Account

This PDF is available to Subscribers Only

For full access to this pdf, sign in to an existing account, or purchase an annual subscription.

Genetic Algorithm- A Literature Review

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

A Genetic Algorithm for Resource-Constrained Scheduling

by Matthew B Wall

Submitted to the Department of Mechanical Engineering on 14 May 1996 in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Mechanical Engineering

This work describes a genetic algorithm approach to resource-constrained scheduling using a direct, time-based representation. Whereas traditional solution methods are typically sequence-based, this representation encodes schedule information as a dual array of relative delay times and integer execution modes. The representation supports multiple execution modes, preemption, non-uniform resource availability/usage, a variety of resource types, probabilistic resource performance models, overlapping precedence relationships, and temporal constraints on both tasks and resources. In addition, the representation includes time-varying resource availabilities and requirements. Many objective measures can be defined such as minimization of makespan, maximization of net present value, or minimization of average tardiness. Multiple, possibly conflicting objectives are supported. The genetic algorithm adapts to dynamic factors such as changes to the project plan or disturbances in the schedule execution.

In addition to the scheduling representation, this thesis presents a structured method for defining and evaluating multiple constraints and objectives.

The genetic algorithm was applied to over 1000 small job shop and project scheduling problems (10-300 activities, 3-10 resource types). Although computationally expensive, the algorithm performed fairly well on a wide variety of problems. With little attention given to its parameters, the algorithm found solutions within 2% of published best in 60% of the project scheduling problems. Performance on the jobshop problems was less encouraging; in a set of 82 jobshop problems with makespan as the single performance measure, the algorithm found solutions with makespan 2 to 3 times the published best. On project scheduling problems with multiple execution modes, the genetic algorithm performed better than deterministic, bounded enumerative search methods for 10% of the 538 problems tested.

The test runs were performed with minimal attention to tuning of the genetic algorithm parameters. In most cases, better performance is possible simply by running the algorithm longer or by varying the selection method, population size or mutation rate. However, the results show the flexibility and robustness of a direct representation and hint at the possibilities of integrating the genetic algorithm approach with other methods.

Mark Jakiela 1 , Associate Professor of Mechanical Engineering, MIT Woodie Flowers, Pappalardo Professor of Mechanical Engineering, MIT Stephen Graves, Professor of Management Science, Sloan School of Management Karl Ulrich, Associate Professor of Operations and Information Management, The Wharton School

1 effective 1 August 1996, Hunter Associate Professor of Mechanical Design and Manufacturing, Mechanical Engineering, Washington University, St. Louis.

The complete thesis is available from http://lancet.mit.edu/~mbwall/phd/thesis/thesis.pdf

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications

Optimization of the Sensitivity of Avian Compass using Genetic Algorithm

94tejas/Thesis-Genetic-Algorithm

Folders and files, repository files navigation, thesis-genetic-algorithm, introduction:.

The idea that some biological processes might operate on quantum mechanical laws has been around for about a century. Recent studies in the past few decades have indicated a possible link between some biological processes and Quantum Physics. Quantum mechanical processes are believed to be the working force underlying some biological processes like Photosynthesis, charge transfer in DNA and Cellular Respiration. The impressive navigational ability of the migratory birds like the Robin are also shown to be derived from quantum mechanical processes undergoing in the bird’s retina. Experiments with European Robins have showed that the navigational ability of the bird is dependent on the local geomagnetic field. Avian magnetoreception is the ability of migratory birds to sense the geomagnetic field for navigation. This mechanism of sensing the geomagnetic field is called as the ‘Avian Compass’.

A bird’s retina is believed to contain photoreceptor pigments (like cryptochrome), aligned along the curvature of the retina, with varying molecular axis directions. When light is incident on the retina, electron transfer takes place between adjacent pigments in the retina. This polarization leads to the formation of radical pairs (pair of charged molecules) with each molecule having an electron with unpaired spin. Under the influence of the geomagnetic field, the spins undergo either singlet or triplet transitions. The radical pairs formed are short-lived (lifetime of order of microseconds) and recombine to form singlet chemical product and triplet chemical product based on their spin states. The coherence time is estimated to be in the order of microseconds. The amount of the chemical product formed varies along the curvature of the retina and is dependent on the geomagnetic field and the molecular axis orientation. This information of the varying chemical product in the bird’s retina is transferred to the bird’s brain and it processes the information to correlate with the geomagnetic field. Thus, the profile of the local geomagnetic field is transferred to the bird’s brain in the form of profile of varying amount of chemicals formed. This process has a coherence time of the order of microseconds. This results in the bird getting a sense of direction repeatedly.

A quantum mechanical model is proposed for this avian compass. The spin of the electron is coupled with the spin of its nucleus and the spin of the other electron in the radical pair. A study has shown that the spin of one of the electrons in the radical pair is effectively uncoupled from that of any other particle and is only dependent on the geomagnetic field. The sensitivity of this avian compass is calculated as the difference of the singlet product yield between the ends of the field of vision of the bird. The higher the sensitivity, better is the navigational ability. This sensitivity is dependent on variables like the hyperfine tensor, the recombination rate of radical pairs and the initial state of the system. The Hamiltonian of this model assumes the hyperfine tensor components and other elements like the initial state of the spins and the recombination rate. This project aims to optimize the sensitivity of this Avian compass with respect to the components of the hyperfine tensor by using Genetic algorithm.

Since the hyperfine tensor has 3 components, traditional optimization algorithms would be inefficient and may give the wrong answer. Genetic algorithms are used for this purpose. They generate random solution space, calculate the sensitivity for each one of the possible solutions, choose the most promising solutions as the next solution space. This procedure is repeated as many times as required to reach a tentative solution. Genetic algorithms imitate the nature’s process of evolution, by making constant improvements over many generations. They may not provide the best possible solution, but they provide many good solutions for the problem

Genetic Algorithm:

Genetic algorithms are optimization algorithms used for optimizing functions with multiple variables. They are different than traditional approach to optimization which involves varying the value of the variables linearly, moving in one direction, generating data for the entire range and then finding the global maximum (minimum). For functions having more than 2 variables, it becomes a time consuming and computationally expensive task when using traditional algorithms. Genetic algorithms work in a different manner by generating random sets of possible solution values which span across the entire permitted range, and then moving towards the more promising solutions and disregarding the solutions which are farther away from the optimum value.

Genetic algorithms are inspired from the natural evolution process. In nature, in every generation of a species, the part of the population with better survival traits have a higher tendency to mate and higher chance of passing their traits to the next generation. Therefore, every generation is on average better than the previous generation. Genetic algorithms use this principle to move towards the optimum solution generation by generation. Genetic algorithms do not necessarily always give the best possible solution, but they provide a small number of good solutions.

The terminology used in genetic algorithms is explained below -

Population : The solution space at any given point of time

Phenotype : Population in real world solution space

Genotype : Population in computational space

Chromosome : An element of the population

Gene : An element position in the chromosome

Allele : Possible value a gene can take

Generation : each stage of population

Fitness Function : function to be optimized

The encoding of our current sensitivity optimization problem is as follows -

Fitness function : Sensitivity (Δs) Variables : Components of the Hyperfine tensor (Ax, Ay, Az) Population : Variable (usually taken 10^5) Phenotype : Range of each variable is of the order of 10 5 to 10 8 Genotype : Binary representation of each variable Chromosome : 30 bytes long character string (10 bytes for each variable) Allele : Character ‘0’ or ‘1’

Crossover Mutation

Crossover functions are analogous to mating in natural evolution. They allow chromosomes with higher fitness function values to mate and produce children which have a higher chance of giving a higher fitness value. Crossover takes place between two chromosome of the same population. When the genotype is binary representation, there are multiple ways of implementing the crossover function like,

One-point crossover: The binary string is broken down at a fixed point and the one half of a chromosome is swapped with the corresponding half portion of the second chromosome.

Two-point crossover: The binary string is divided at 2 points in the string and the portions at the end are swapped with corresponding portions of the second string.

Uniform crossover: Each child is formed gene by gene by taking the corresponding gene from one of the parents. The probability for a particular gene to be taken from a parent is 50%.

Mutation Function

In natural evolution, mutation takes place with low probability in a generation. Its purpose is to introduce diversity in the population with the hope of that diversity leading to a better breed with higher survival chances. Mutation in genetic algorithms works in the same way and serves the same purpose i.e. introducing diversity. The probability of mutation happening in a generation is usually kept low at around 1-5% so as to not steer the population away from the optimum solution’s path. When the genotype is binary, mutation can be implemented as-

• Bit flip operation: Randomly flip the bits of random chromosomes in a population
• Bit swap: Swap the bits on random positions in a chromosome

Survival Selection

This step involves choosing the parts of the population to promote to the next generation and the parts to discard entirely. This step has a major effect on the performance of the genetic algorithm. Selection of chromosomes can be done in two ways: Age-based selection or Fitness- based selection methods. In age-based selection method, the number of generations for which a chromosome has been in the population is the deciding factor. If it is greater than a fixed number, then it discarded. In fitness based selection, higher the fitness value higher is the chance of being promoted to the next generation. Fitness based selection methods consist of probabilistic methods like Roulette-wheel selection method or tournament selection method.

Termination Condition

Termination condition can be when a fixed value of the objective is reached or a fixed number of generations have passed or the current population size is lower than a certain number or there is no or little improvement in the solutions generated over the past few generations

Problem specific conditions

Choosing the appropriate function to use for crossover, mutation, survival selection, etc. is all based on the specific details of the problem. There is a lot of flexibility in implementing the functions mentioned above. The functions should be tailored to the problem. The more problem-specific knowledge is fed into the algorithm, the better it performs and sooner it converges to the optimum solution. Effective implementation of genetic algorithms is all about balancing the diversity in the population with problem-specific knowledge. If the diversity is kept low, the algorithm has a high chance of converging at the nearest local optimum. Crossover and mutation help in maintaining diversity in the population.

For this particular problem of optimizing sensitivity, I am using two-point crossover function applied for each variable individually. The mutation function is a bit flip function which has a 5-10% probability of occurring in a generation. For the survival selection function, I tried many methods like roulette wheel selection method and tournament selection method. The lack of problem specific knowledge in this case, led to failure of these methods to converge at a point. Therefore, I choose to select top 40% of the population with highest fitness value and bottom 10% of the population (with lowest fitness value) for the next generation and discarded the 50% of the population left. The bottom 10% was kept to maintain diversity. Thus, the population is reduced to half its number after every generation. This led to a steady increase in the average fitness value of each generation and the algorithm converged to a point. The termination condition was kept at when the population size was reduced to less than 10.

Implementation

The C++ library linear algebra 'Eigen' has been used for calculation of the eigenvalues and eigenvectors of the Hamiltonian. Eigen library is useful for performing large matrix operations.

The GCC compiler (version 4.4 or higher) is required for compilation. The command used for compilation is,

g++ -std=c++11 main.cpp -o output_filename

The results are stored in ‘output.txt’ in the same folder as the main.cpp file. To plot the Sensitivity vs. Theta plot compile and run the ‘phi_vs_theta.cpp’ file in the same manner as above. Enter the values of (Ax, Ay, Az) obtained in output.txt as input. The output of this program is stored in ‘phiS.txt’.

‘gnuplot’ software has been used to plot all the graphs. The file ‘printGraphs.p’ has the code to plot the two kind graphs. To plot the graphs, open gnuplot, navigate to the correct directory and simply run the command,

load ‘printGraphs.p’

The following Fitness vs. Generation number plots for different values of K show the average fitness moving towards the maximum fitness in each generation. In more than 25 tests, the maximum fitness was reached was about ~ 5.6.

Multiple combination of values of (Ax, Ay, Az) give fitness in the range of 5.2-5.7. Some of them are – (1.2e06, 1.2e06, 510000), (5.72e06, 5.72e06, 540000), (9.88e06, 9.88e06, 26000), (10.04e06, 10.04e06, 26000), etc. The common pattern in all the solutions is that of, (Ax=Ay >Az). This falls into the disk-shaped hyperfine parameter regime.

The following plots are for Singlet product yield vs. Theta. They show a steadily increasing function for different values of K.

The values of the variables (Ax, Ay, Az) discovered for the maximum sensitivity help in describing the characteristics of the nuclear part of the molecules which form radical pairs. Nature improves the biological mechanisms generation after generation, by estimating the optimal sensitivity and hyperfine parameters we get closer to the actual working of the avian compass. Also, research is ongoing to create a geomagnetic sensor which can detect its location on Earth based on the local geomagnetic field using similar mechanism. The optimized values calculated can be used for maximizing the sensitivity of the artificial compass. Future scope of work includes the study of the effects of recombination rate and the initial state on the sensitivity of the avian compass.