Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2016 | OriginalPaper | Chapter

3. Genetic Algorithms

Authors : Ke-Lin Du, M. N. S. Swamy

Published in: Search and Optimization by Metaheuristics

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Evolutionary algorithms (EAs) are the most influential metaheuristics for optimization. Genetic algorithm (GA) is the most popular form of EA. In this chapter, we first give an introduction to evolutionary computation. A state-of-the-art description of GA is then presented.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Simulated Annealing
next chapter Genetic Programming
Literature
1.
Arabas J, Michalewicz Z, Mulawka J. GAVaPS—a genetic algorithm with varying population size. In: Proceedings of the 1st IEEE international conference on evolutionary computation, Orlando, FL, USA, June 1994. p. 73–78.
2.
Araujo L, Merelo JJ. Diversity through multiculturality: assessing migrant choice policies in an island model. IEEE Trans Evol Comput. 2011;15(4):456–69.CrossRef
3.
Ballester PJ, Carter JN. An effective real-parameter genetic algorithm with parent centric normal crossover for multimodal optimisation. In: Proceedings of genetic and evolutionary computation conference (GECCO), Seattle, WA, USA, June 2004. p. 901–913.
4.
Bean J. Genetic algorithms and random keys for sequence and optimization. ORSA J Comput. 1994;6(2):154–60.CrossRefMATH
5.
Beyer H-G, Deb K. On self-adaptive features in real-parameter evolutionary algorithms. IEEE Trans Evol Comput. 2001;5(3):250–70.CrossRef
6.
Bhandari D, Pal NR, Pal SK. Directed mutation in genetic algorithms. Inf Sci. 1994;79:251–70.CrossRefMATH
7.
Burke DS, De Jong KA, Grefenstette JJ, Ramsey CL, Wu AS. Putting more genetics into genetic algorithms. Evol Comput. 1998;6(4):387–410.CrossRef
8.
Cartwright HM, Harris SP. The application of the genetic algorithm to two-dimensional strings: the source apportionment problem. In: Forrest S, editor, Proceedings of the 5th international conference on genetic algorithms, Urbana-Champaign, IL, USA, June 1993. San Mateo, CA: Morgan Kaufmann; 1993. p. 631.
9.
Cervantes J, Stephens CR. Limitations of existing mutation rate heuristics and how a rank GA overcomes them. IEEE Trans Evol Comput. 2009;13(2):369–97.CrossRef
10.
Chakraborty UK, Janikow CZ. An analysis of Gray versus binary encoding in genetic search. Inf Sci. 2000;156:253–69.MathSciNetCrossRef
11.
Chan TM, Man KF, Kwong S, Tang KS. A jumping gene paradigm for evolutionary multiobjective optimization. IEEE Trans Evol Comput. 2008;12(2):143–59.CrossRef
12.
Chen H, Flann NS, Watson DW. Parallel genetic simulated annealing: a massively parallel SIMD algorithm. IEEE Trans Parallel Distrib Syst. 1998;9(2):126–36.CrossRef
13.
Cherkauer KJ. Genetic search for nearest-neighbor exemplars. In: Proceedings of the 4th midwest artificial intelligence and cognitive science society conference, Utica, IL, USA, 1992. p. 87–91.
14.
Chicano F, Sutton AM, Whitley LD, Alba E. Fitness probability distribution of bit-flip mutation. Evol Comput. 2015;23(2):217–48.CrossRef
15.
Chuang Y-C, Chen C-T, Hwang C. A real-coded genetic algorithm with a direction-based crossover operator. Inf Sci. 2015;305:320–48.CrossRef
16.
Civicioglu P. Backtracking search optimization algorithm for numerical optimization problems. Appl Math Comput. 2013;219:8121–44.MathSciNetMATH
17.
Davis L. Bit-climbing, representational bias, and test suite design. In: Proceedings of the 4th international conference on genetic algorithms, San Diego, CA, USA, July 1991. San Mateo, CA: Morgan Kaufmann; 1991. p. 18–23.
18.
Davis L, Grefenstette JJ. Concerning GENESIS and OOGA. In: Davis L, editor. Handbook of genetic algorithms. New York: Van Nostrand Reinhold; 1991. p. 374–377.
19.
Deb K, Anand A, Joshi D. A computationally efficient evolutionary algorithm for real-parameter optimization. Evol Comput. 2002;10(4):371–95.CrossRef
20.
De Jong K. An analysis of the behavior of a class of genetic adaptive systems. PhD Thesis, University of Michigan, Ann Arbor, MI, USA, 1975.
21.
Drugan MM, Thierens D. Recombination operators and selection strategies for evolutionary Markov Chain Monte Carlo algorithms. Evol Intel. 2010;3(2):79–101.CrossRefMATH
22.
Ericsson M, Resende MGC, Pardalos PM. A genetic algorithm for the weight setting problem in OSPF routing. J Comb Optim. 2002;6:299–333.MathSciNetCrossRefMATH
23.
Eshelman LJ. The CHC adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination. In: Rawlins GJE, editor. Foundations of genetic algorithms. San Mateo, CA: Morgan Kaufmannpp; 1991. p. 265–283.
24.
Eshelman LJ, Schaffer JD. Real-coded genetic algorithms and interval-schemata. In: Whitley LD, editor, Foundations of genetic algorithms 2. San Mateo, CA: Morgan Kaufmann; 1993. p. 187–202.
25.
Fogel L, Owens J, Walsh M. Artificial intelligence through simulated evolution. New York: Wiley; 1966.MATH
26.
Fox BR, McMahon MB. Genetic operators for sequencing problems. In: Rawlins GJE, editor. Foundations of genetic algorithms. San Mateo, CA: Morgan Kaufmann; 1991. p. 284–300.
27.
Frantz DR. Non-linearities in Genetic Adaptive Search. PhD Thesis, University of Michigan, Ann Arbor, MI, USA, 1972.
28.
Friedrich T, Hebbinghaus N, Neumann F. Rigorous analyses of simple diversity mechanisms. In: Proceedings of genetic and evolutionary computation conference (GECCO), London, UK, July 2007. p. 1219–1225.
29.
Galan SF, Mengshoel OJ, Pinter R. A novel mating approach for genetic algorithms. Evol Comput. 2012;21(2):197–229.CrossRef
30.
Garcia-Martinez C, Lozano M, Herrera F, Molina D, Sanchez AM. Global and local real-coded genetic algorithms based on parent-centric crossover operators. Eur J Oper Res. 2008;185:1088–113.CrossRefMATH
31.
Goldberg DE. Genetic algorithms in search, optimization, and machine learning. Reading, MA, USA: Addison-Wesley; 1989.MATH
32.
Goldberg D. A note on Boltzmann tournament selection for genetic algorithms and population-oriented simulated annealing. Complex Syst. 4:4:445–460.
33.
Goldberg DE, Deb K. A comparative analysis of selection schemes used in genetic algorithms. In: Rawlins GJE, editor. Foundations of genetic algorithms. San Mateo, CA: Morgan Kaufmann; 1991. p. 69–93.
34.
Goldberg DE, Deb K, Korb B. Messy genetic algorithms: motivation, analysis, and first results. Complex Syst. 1989;3:493–530.MathSciNetMATH
35.
Goldberg DE, Deb K, Kargupta H, Harik G. Rapid, accurate optimization of difficult problems using fast messy genetic algorithms. In: Proceedings of the 5th international conference on genetic algorithms, Urbana-Champaign, IL, USA, June 1993. p. 56–64.
36.
Goldman BW, Punch WF. Fast and efficient black box optimization using the parameter-less population pyramid. Evol Comput. 2015;23(2):451–79.CrossRef
37.
Grefenstette JJ, Gopal R, Rosmaita BJ, Gucht DV. Genetic algorithms for the traveling salesman problem. In: Proceedings of the 1st international conference on genetic algorithms and their applications, Pittsburgh, PA, USA, July 1985. Mahwah, NJ: Lawrence Erlbaum Associates; 1985. p. 160–168.
38.
Harvey I. The SAGA cross: the mechanics of crossover for variable-length genetic algorithms. In: Proceedings of the 2nd conference on parallel problem solving from nature (PPSN II), Brussels, Belgium, Sept 1992. Amsterdam, The Netherlands: North Holland; 1992. p. 269–278.
39.
Harvey I. The microbial genetic algorithm. In: Proceedings of 10th european conference on advances in artificial life: Darwin meets von Neumann, Budapest, Hungary, Sept 2009, Part II, p. 126–133.
40.
Herrera F, Lozano M. Adaptation of genetic algorithm parameters based on fuzzy logic controllers. In: Herrera F, Verdegay JL, editors. Genetic algorithms and soft computing. Berlin: Physica-Verlag; 1996. p. 95–125.
41.
Herrera F, Lozano M. Fuzzy adaptive genetic algorithms: design, taxonomy, and future directions. Soft Comput. 2003;7:545–62.CrossRef
42.
Herrera F, Lozano M, Verdegay JL. Fuzzy connectives based crossover operators to model genetic algorithms population diversity. Fuzzy Sets Syst. 1997;92(1):21–30.CrossRef
43.
Herrera F, Lozano M, S’anchez AM. A taxonomy for the crossover operator for real-coded genetic algorithms: An experimental study. Int J Intell Syst. 2003;18:3:309–338.
44.
Hesser J, Manner R. Towards an optimal mutation probability for genetic algorithms. In: Proceedings of the 1st workshop on parallel problem solving from nature (PPSN I), Dortmund, Germany, Oct 1990. p. 23–32.
45.
Hillis WD. Co-evolving parasites improve simulated evolution as an optimization procedure. Physica D. 1990;42:228–34.CrossRef
46.
47.
Holland J. Adaptation in natural and artificial systems. Ann Arbor, Michigan: University of Michigan Press; 1975.
48.
Holland JH. Building blocks, cohort genetic algorithms and hyperplane-defined functions. Evol Comput. 2000;8(4):373–91.CrossRef
49.
Hutter M, Legg S. Fitness uniform optimization. IEEE Trans Evol Comput. 2006;10(5):568–89.CrossRef
50.
Hutt B, Warwick K. Synapsing variable-length crossover: meaningful crossover for variable-length genomes. IEEE Trans Evol Comput. 2007;11(1):118–31.CrossRef
51.
Jansen T, De Jong KA, Wegener I. On the choice of the offspring population size in evolutionary algorithms. Evol Comput. 2005;13(4):413–40.CrossRef
52.
Khatib W, Fleming PJ. The stud GA: a mini revolution? In: Eiben A, Back T, Schoenauer M, Schwefel H, editors. Proceedings of the 5th international conference on parallel problem solving from nature (PPSN V). Amsterdam: The Netherlands; 1998. p. 683–691.
53.
Knjazew D, Goldberg DE. OMEGA—Ordering messy GA: Solving permutation problems with the fast messy genetic algorithm and random keys. In: Proceedings of genetic and evolutionary computation conference (GECCO), Las Vegas, NV, USA, July 2000. p. 181–188.
54.
Koumousis VK, Katsaras CP. A saw-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance. IEEE Trans Evol Comput. 2006;10(1):19–28.CrossRef
55.
Koza JR. Genetic programming: On the programming of computers by means of natural selection. Cambridge, MA: MIT Press; 1992.MATH
56.
Laskey KB, Myers JW. Population Markov chain Monte Carlo. Mach Learn. 2003;50:175–96.
57.
Lee MA, Takagi H. Dynamic control of genetic algorithms using fuzzy logic techniques. In: Proceedings of the 5th international conference on genetic algorithms (ICGA’93), Urbana, IL, USA, July 1993. p. 76–83.
58.
Lee CY. Entropy-Boltzmann selection in the genetic algorithms. IEEE Trans Syst Man Cybern Part B. 2003;33(1):138–42.CrossRef
59.
Leung FHF, Lam HK, Ling SH, Tam PKS. Tuning of the structure and parameters of a neural network using an improved genetic algorithm. IEEE Trans Neural Networks. 2003;14(1):79–88.CrossRef
60.
Lobo FG, Lima CF. A review of adaptive population sizing schemes in genetic algorithms. In: Proceedings of genetic and evolutionary computation conference (GECCO), Washington, DC, USA, June 2005. p. 228–234.
61.
Mathias K, Whitley LD. Changing representations during search: a comparative study of delta coding. Evol Comput. 1995;2(3):249–78.CrossRef
62.
Matsui K. New selection method to improve the population diversity in genetic algorithms. In: Proceedings of the 1999 IEEE International conference on systems, man, and cybernetics, Tokyo, Japan, Oct 1999. p. 625–630.
63.
Mauldin ML. Maintaining diversity in genetic search. In: Proceedings of the 4th national conference on artificial intelligence (AAAI-84), Austin, TX, USA, Aug 1984. p. 247–250.
64.
Mills KL, Filliben JJ, Haines AL. Determining relative importance and effective settings for genetic algorithm control parameters. Evol Comput. 2015;23(2):309–42.CrossRef
65.
Muhlenbein H. Parallel genetic algorithms, population genetics and combinatorial optimization. In: Proceedings of the 3rd international conference on genetic algorithms, Fairfax, VA, USA, June 1989. San Mateo, CA: Morgan Kaufman; 1989. p. 416–421.
66.
Muhlenbein H. How genetic algorithms really work: mutation and hill climbing. In: Manner R, Manderick B, editors. Proceedings of the 2nd conference on parallel problem solving from nature (PPSN II), Brussels, Belgium, Sept 1992. Amsterdam, The Netherlands: North Holland; 1992. pp. 15–25.
67.
Muhlenbein H, Paab G. From recombination of genes to the estimation of distributions. I. Binary parameters. In: Proceedings of the 4th International conference on parallel problem solving from nature (PPSN IV), Berlin, Germany, Sept 1996. p. 178–187.
68.
Muhlenbein H, Schlierkamp-Voosen D. Predictive models for the breeder genetic algorithm: continuous parameter optimization. Evol Comput. 1994;1(4):25–49.
69.
Mulenbein H, Schlierkamp-Voose D. Analysis of selection, mutation and recombination in genetic algorithms. In: Banzhaf W, Eechman FH, editors. Evolution and biocomputation: Evolution and biocomputation, computational models of evolution. Berlin: Springer; 1995. p. 142–68.
70.
Nawa NE, Furuhashi T. Fuzzy systems parameters discovery by bacterial evolutionary algorithms. IEEE Trans Fuzzy Syst. 1999;7:608–16.CrossRef
71.
Palmer CC, Kershenbaum A. An approach to a problem in network design using genetic algorithms. Networks. 1995;26:151–63.CrossRefMATH
72.
Paulden T, Smith DK. From the Dandelion code to the Rainbow code: a class of bijective spanning tree representations with linear complexity and bounded locality. IEEE Trans Evol Comput. 2006;10(2):108–23.CrossRef
73.
Perales-Gravan C, Lahoz-Beltra R. An AM radio receiver designed with a genetic algorithm based on a bacterial conjugation genetic operator. IEEE Trans Evol Comput. 2008;12(2):129–42.CrossRef
74.
Potter MA, De Jong KA. Cooperative coevolution: an architecture for evolving coadapted subcomponenets. Evol Comput. 2000;8(1):1–29.CrossRef
75.
Rechenberg I. Evolutionsstrategie-optimierung technischer systeme nach prinzipien der biologischen information. Freiburg, Germany: Formman Verlag; 1973.
76.
Ronald E. When selection meets seduction. In: Proceedings of the 6th international conference on genetic algorithms, Pittsburgh, PA, USA, July 1995. p. 167–173.
77.
Rothlauf F, Goldberg DE, Heinzl A. Network random keys—a tree network representation scheme for genetic and evolutionary algorithms. Evol Comput. 2002;10(1):75–97.CrossRef
78.
Rudolph G. Convergence analysis of canonical genetic algorithm. IEEE Trans Neural Networks. 1994;5(1):96–101.CrossRef
79.
Satoh H, Yamamura M, Kobayashi S. Minimal generation gap model for GAs considering both exploration and exploitation. In: Proceedings of the 4th International conference on soft computing (Iizuka’96): Methodologies for the conception, design, and application of intelligent systems, Iizuka, Fukuoka, Japan, Sept 1996. p. 494–497.
80.
Schaffer JD, Caruana RA, Eshelman LJ, Das R. A study of control parameters affecting online performance of genetic algorithms for function optimisation. In: Proceedings of the 3rd international conference on genetic algorithms, Fairfax, VA, USA, June 1989. San Mateo, CA: Morgan Kaufmann; 1989. p. 70–79.
81.
Schraudolph NN, Belew RK. Dynamic parameter encoding for genetic algorithms. Mach Learn. 1992;9(1):9–21.
82.
Schwefel HP. Numerical optimization of computer models. Chichester: Wiley; 1981.MATH
83.
Sharma SK, Irwin GW. Fuzzy coding of genetic algorithms. IEEE Trans Evol Comput. 2003;7(4):344–55.CrossRef
84.
Simoes AB, Costa E. Enhancing transposition performance. In: Proceedings of congress on evolutionary computation (CEC), Washington, DC, USA, July 1999. p. 1434–1441.
85.
Smith J, Vavak F. Replacement strategies in steady state genetic algorithms: static environments. In: Banzhaf W, Reeves C, editors. Foundations of genetic algorithms 5. CA: Morgan Kaufmann; 1999. p. 219–233.
86.
Sokolov A, Whitley D. Unbiased tournament selection. In: Proceedings of the conference on genetic and evolutionary computation (GECCO), Washington, DC, USA, June 2005. p. 1131–1138.
87.
Srinivas M, Patnaik LM. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans Syst Man Cybern. 1994;24(4):656–67.CrossRef
88.
Storn R, Price K. Differential evolution–a simple and efficient adaptive scheme for global optimization over continuous spaces. Technical Report TR-95-012, International Computer Science Institute, Berkeley, CA, March 1995.
89.
Streifel RJ, Marks RJ II, Reed R, Choi JJ, Healy M. Dynamic fuzzy control of genetic algorithm parameter coding. IEEE Trans Syst Man Cybern Part B. 1999;29(3):426–33.CrossRef
90.
Syswerda G. Uniform crossover in genetic algorithms. In: Proceedings of the 3rd international conference on genetic algorithms, Fairfax, VA, USA, June 1989. San Francisco: Morgan Kaufmann; 1989. p. 2–9.
91.
Syswerda G. Simulated crossover in genetic algorithms. In: Whitley LD, editor. Foundations of genetic algorithms 2, San Mateo, CA: Morgan Kaufmann; 1993. p. 239–255.
92.
Thompson E, Paulden T, Smith DK. The Dandelion code: a new coding of spanning trees for genetic algorithms. IEEE Trans Evol Comput. 2007;11(1):91–100.CrossRef
93.
Tsutsui S, Yamamura M, Higuchi T. Multi-parent recombination with simplex crossover in real coded genetic algorithms. In: Proceedings of the genetic and evolutionary computation conference (GECCO), Orlando, FL, USA, July 1999. San Mateo, CA: Morgan Kaufmann; 1999. p. 657–664.
94.
Ursem RK. Diversity-guided evolutionary algorithms. In: Proceedings of the 7th conference on parallel problem solving from nature (PPSN VII), Granada, Spain, Sept 2002. p. 462–471.
95.
Voigt HM, Muhlenbein H, Cvetkovic D. Fuzzy recombination for the breeder genetic algorithm. In: Eshelman L, editor. Proceedings of the 6th international conference on genetic algorithms, Pittsburgh, PA, USA, July 1995. San Mateo, CA: Morgan Kaufmann; 1995. p. 104–111.
96.
Whitley D. The GENITOR algorithm and selective pressure. In: Proceedings of the 3rd international conference on genetic algorithms, Fairfax, VA, USA, June 1989. San Mateo, CA: Morgan Kaufmann; 1989. p. 116–121.
97.
Whitley D, Starkweather T, Fuquay D. Scheduling problems and traveling salesmen: the genetic edge recombination operator. In: Proceedings of the 3rd international conference on genetic algorithms, Fairfax, VA, USA, June 1989. San Mateo, CA: Morgan Kaufmann; 1989. p. 133–140.
98.
Wright AH. Genetic algorithms for real parameter optimization. In: Rawlins G, editor. Foundations of genetic algorithms. San Mateo, CA: Morgan Kaufmann; 1991. p. 205–218.
99.
Yao X, Liu Y, Liang KH, Lin G. Fast evolutionary algorithms. In: Ghosh S, Tsutsui S, editors. Advances in evolutionary computing: theory and applications. Berlin, Springer; 2003. p. 45–9.
100.
Yip PPC, Pao YH. Combinatorial optimization with use of guided evolutionary simulated annealing. IEEE Trans Neural Networks. 1995;6(2):290–5.CrossRef
101.
Yukiko Y, Nobue A. A diploid genetic algorithm for preserving population diversity—pseudo-meiosis GA. In: Parallel problem solving from nature (PPSN III), Vol. 866 of the series Lecture Notes in Computer Science. Berlin: Springer; 1994. p. 36–45.
Metadata
Title
Genetic Algorithms
Authors
Ke-Lin Du
M. N. S. Swamy
Copyright Year
2016
Book
Search and Optimization by Metaheuristics

Print ISBN: 978-3-319-41191-0

Electronic ISBN: 978-3-319-41192-7

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-41192-7_3

Premium Partner

    Image Credits