nach oben

Erschienen in:

2014 | OriginalPaper | Buchkapitel

4. Genetic Algorithms

verfasst von : Kumara Sastry, David E. Goldberg, Graham Kendall

Erschienen in: Search Methodologies

Verlag: Springer US

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Genetic algorithms (GAs) are search methods based on principles of natural selection and genetics (Fraser 1957; Bremermann 1958; Holland 1975). We start with a brief introduction of simple GAs and the associated terminologies. GAs encode the decision variables of a search problem into finite-length strings of alphabets of certain cardinality. The strings which are candidate solutions to the search problem are referred to as chromosomes, the alphabets are referred to as genes and the values of genes are called alleles. For example, in a problem such as the traveling salesman problem (TSP), a chromosome represents a route, and a gene may represent a city. In contrast to traditional optimization techniques, GAs work with coding of parameters, rather than the parameters themselves.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Integer Programming

Nächstes Kapitel Scatter Search

Albert LA (2001) Efficient genetic algorithms using discretization scheduling. Master’s thesis, University of Illinois at Urbana-Champaign (also IlliGAL report no 2002005)

Asoh H, Mühlenbein H (1994) On the mean convergence time of evolutionary algorithms without selection and mutation. PPSN 3, pp 98–107

Bäck T (1994) Selective pressure in evolutionary algorithms: a characterization of selection mechanisms. In: Proceedings of the 1st IEEE conference on evolutionary computation, Orlando, pp 57–62

Bäck T (1995) Generalized convergence models for tournament—and (μ, λ)—selection. In: Proceedings of 6th international conference on genetic algorithms, Pittsburgh, pp 2–8

Bäck T (1996) Evolutionary algorithms in theory and practice. Oxford University Press, New York

Baluja S (1994) Population-based incremental learning: a method of integrating genetic search based function optimization and competitive learning. Technical report CMU-CS-94-163, Carnegie Mellon University

Barthelemy J-FM, Haftka RT (1993) Approximation concepts for optimum structural design—a review. Struct Optim 5:129–144CrossRef

Booker LB, Fogel DB, Whitley D, Angeline PJ (1997) Recombination. In: Bäck T, Fogel DB, Michalewicz Z (eds) The handbook of evolutionary computation, chap E3.3. IOP Publishing/Oxford University Press, London/Oxford, pp C3.3:1–C3.3:27

Bosman PAN, Thierens D (1999) Linkage information processing in distribution estimation algorithms. In: Proceedings of the GECCO, Orlando, pp 60–67 (also Technical report no UU-CS-1999-10)

Bremermann HJ (1958) The evolution of intelligence. The nervous system as a model of its environment. Technical report no 1, Department of Mathematics, University of Washington

Bulmer MG (1985) The mathematical theory of quantitative genetics. Oxford University Press, Oxford

Burke EK, Newell JP (1999) A multi-stage evolutionary algorithm for the timetabling problem. IEEE Trans Evol Comput 3:63–74CrossRef

Burke EK, Smith AJ (1999) A memetic algorithm to schedule planned maintenance for the national grid. ACM J Exp Algor 4. doi:10.1145/347792.347801

Burke EK, Smith AJ (2000) Hybrid evolutionary techniques for the maintenance scheduling problem. IEEE Trans Power Syst 15:122–128CrossRef

Burke EK, Elliman DG, Weare RF (1995) Specialised recombinative operators for timetabling problems. In: Fogarty T (ed) Evolutionary computing AISB workshop 1995. LNCS 993. Springer, Berlin, pp 75–85

Burke EK, Newall JP, Weare RF (1996) A memetic algorithm for university exam timetabling. In: Burke EK, Ross P (eds) The practice and theory of automated timetabling I. LNCS 1153. Springer, Berlin, pp 241–250

Burke EK, Newall JP, Weare RF (1998) Initialisation strategies and diversity in evolutionary timetabling. Evol Comput J 6:81–103CrossRef

Burke EK, Cowling PI, De Causmaecker P, Vanden Berghe G (2001) A mimetic approach to the nurse rostering problem. Appl Intell 15:199–214CrossRef

Cantú-Paz E (1999) Migration policies and takeover times in parallel genetic algorithms. In: Proceedings of the GECCO, Orlando, p 775 (also IlliGAL report no 99008)

Cantú-Paz E (2000) Efficient and accurate parallel genetic algorithms. Kluwer, Boston

Chen J-H (2004) Theory and applications of efficient multi-objective evolutionary algorithms. Doctoral dissertation, Feng Chia University, Taiwan

Cheng RW, Gen M (1997) Parallel machine scheduling problems using memetic algorithms. Comput Indust Eng 33:761–764CrossRef

Costa D (1995) An evolutionary tabu search algorithm and the NHL scheduling problem. INFOR 33:161–178

Davis L (1985) Applying algorithms to epistatic domains. In: Proceedings of the international joint conference on artifical intelligence, Los Angeles, pp 162–164

De Jong KA (1975) An analysis of the behavior of a class of genetic adaptive systems. Doctoral dissertation, University of Michigan (University microfilm no 76-9381)

Dennis JE, Torczon V (1997) Managing approximation models in optimization. In: Alexandrov NM, Hussaini MY (eds) Multidisciplinary design optimization: state-of-the-art. SIAM, Philadelphia, pp 330–347

Fitzpatrick JM, Grefenstette JJ, Van Gucht D (1984) Image registration by genetic search. In: Proceedings of the IEEE southeast conference. IEEE Press, Piscataway, Louisville, KY, pp 460–464

Fleurent C, Ferland J (1993) Genetic hybrids for the quadratic assignment problem. DIMACS series in mathematics and theoretical computer science. This DIMACS workshop on Quadratic Assignment and Related Problems was held at DIMACS 16:173–188

Fraser AS (1957) Simulation of genetic systems by automatic digital computers. II. Effects of linkage on rates under selection. Aust J Biol Sci 10:492–499

Goldberg DE (1983) Computer-aided pipeline operation using genetic algorithms and rule learning. Doctoral dissertation, University of Michigan

Goldberg DE (1987) Simple genetic algorithms and the minimal deceptive problem. In: Davis L (ed) Genetic algorithms and simulated annealing, chap 6. Morgan Kaufmann, Los Altos, pp 74–88

Goldberg DE (1989) Genetic algorithms in search optimization and machine learning. Addison-Wesley, Reading

Goldberg DE (1999a) The race, the hurdle, and the sweet spot: lessons from genetic algorithms for the automation of design innovation and creativity. In: Bentley P (ed) Evolutionary design by computers, chap 4. Morgan Kaufmann, San Mateo, pp 105–118

Goldberg DE (1999b) Using time efficiently: genetic-evolutionary algorithms and the continuation problem. In: Proceedings of the GECCO, Orlando, pp 212–219 (also IlliGAL report no 99002)

Goldberg DE (2002) Design of innovation: lessons from and for competent genetic algorithms. Kluwer, Boston

Goldberg DE, Deb K (1991) A comparitive analysis of selection schemes used in genetic algorithms. Foundations of genetic algorithms. Morgan Kaufmann, pp 69–93

Goldberg DE, Lingle R (1984) Alleles, loci, and the TSP. In: Proceedings of the 1st international conference on genetic algorithms, Pittsburgh, pp 154–159

Goldberg DE, Sastry K (2001) A practical schema theorem for genetic algorithm design and tuning. In: Proceedings of the GECCO, San Francisco, pp 328–335 (also IlliGAL report no 2001017)

Goldberg DE, Segrest P (1987) Finite Markov chain analysis of genetic algorithms. In: Proceedings of the 2nd international conference on genetic algorithms, Cambridge, MA, USA, pp 1–8

Goldberg DE, Voessner S (1999) Optimizing global-local search hybrids. In: Proceedings of the GECCO, Orlando, pp 220–228 (also IlliGAL report no 99001)

Goldberg DE, Korb B, Deb K (1989) Messy genetic algorithms: motivation, analysis, and first results. Complex Syst 3:493–530 (also IlliGAL report no 89003)

Goldberg DE, Deb K, Clark JH (1992) Genetic algorithms, noise, and the sizing of populations. Complex Syst 6:333–362 (also IlliGAL report no 91010)

Goldberg DE, Deb K, Kargupta H, Harik G (1993a) Rapid, accurate optimization of difficult problems using fast messy genetic algorithms. In: Proceedings of the international conference on genetic algorithms, Urbana, pp 56–64 (also IlliGAL report no 93004)

Goldberg DE, Thierens D, Deb K (1993b) Toward a better understanding of mixing in genetic algorithms. J Soc Instrum Contr Eng 32:10–16 (also IlliGAL report no 92009)

Goldberg DE, Sastry K, Latoza T (2001) On the supply of building blocks. In: Proceedings of the GECCO, San Francisco, pp 336–342 (also IlliGAL report no 2001015)

Grefenstette JJ, Fitzpatrick JM (1985) Genetic search with approximate function evaluations. In: Proceedings of the international conference on genetic algorithms and their applications, Pittsburgh, pp 112–120

Harik G (1999) Linkage learning via probabilistic modeling in the ECGA (IlliGAL report no 99010). University of Illinois at Urbana-Champaign

Harik G, Goldberg DE (1997) Learning linkage. Foundations of genetic algorithms 4, pp 247–262 (also IlliGAL report no 96006)

Harik G, Lobo F, Goldberg DE (1998) The compact genetic algorithm. In: Proceedings of the IEEE international conference on evolutionary computation, Piscataway, pp 523–528 (also IlliGAL report no 97006)

Harik G, Cantú-Paz E, Goldberg DE, Miller BL (1999) The gambler’s ruin problem, genetic algorithms, and the sizing of populations. Evol Comput 7:231–253 (also IlliGAL report no 96004)

Hart WE, Belew RK (1996) Optimization with genetic algorithm hybrids using local search. In: Belew RK, Mitchell M (eds) Adaptive individuals in evolving populations. Addison-Wesley, Reading, pp 483–494

Heckendorn RB, Wright AH (2004) Efficient linkage discovery by limited probing. Evol Comput 12:517–545CrossRef

Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor

Ibaraki T (1997) Combinations with other optimixation problems. In: Bäck T, Fogel DB, Michalewicz Z (eds) Handbook of evolutionary computation. Institute of Physics Publishing and Oxford University Press, Bristol/New York, pp D3:1–D3:2

Jin Y (2005) A comprehensive survey of fitness approximation in evolutionary computation. Soft Comput J 9:3–12CrossRef

Kargupta H (1996) The gene expression messy genetic algorithm. In: Proceedings of the international conference on evolutionary computation, Nagoya, pp 814–819

Krasnogor N, Smith JE (2005) A tutorial for competent memetic algorithms: models,taxonomy and design issues. IEEE Trans Evol Comput 9:474–488CrossRef

Krasnogor N, Hart W, Smith JE (eds) (2004) Recent advances in memetic algorithms. Studies in fuzziness and soft computing, vol 166. Springer, Berlin

Louis SJ, McDonnell J (2004) Learning with case injected genetic algorithms. IEEE Trans Evol Comput 8:316–328CrossRef

Miller BL, Goldberg DE (1995) Genetic algorithms, tournament selection, and the effects of noise. Complex Syst 9:193–212 (also IlliGAL report no 95006)

Miller BL, Goldberg DE (1996a) Genetic algorithms, selection schemes, and the varying effects of noise. Evol Comput 4:113–131 (also IlliGAL report no 95009)

Miller BL, Goldberg DE (1996b) Optimal sampling for genetic algorithms. Intelligent engineering systems through artificial neural networks, ASME Press, New York 6:291–297

Moscato P (1989) On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. Technical report C3P 826, California Institute of Technology

Moscato P (1999) Part 4: Memetic algorithms. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimization. McGraw-Hill, New York, pp 217–294

Moscato P, Cotta C (2003) A gentle introduction to memetic algorithms. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics, chap 5. Kluwer, Norwell

Mühlenbein H, Paass G (1996) From recombination of genes to the estimation of distributions I. Binary parameters. PPSN 4, pp 178–187

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

Munetomo M, Goldberg DE (1999) Linkage identification by non-monotonicity detection for overlapping functions. Evol Comput 7:377–398CrossRef

Oliver JM, Smith DJ, Holland JRC (1987) A study of permutation crossover operators on the travelling salesman problem. In: Proceedings of the 2nd international conference on genetic algorithms, Cambridge, pp 224–230

Paechter B, Cumming A, Luchian H (1995) The use of local search suggestion lists for improving the solution of timetable problems with evolutionary algorithms. In: Fogarty T (ed) Evolutionary computing: AISB workshop 1995. LNCS 993. Springer, Berlin, pp 86–93

Paechter B, Cumming A, Norman MG, Luchian H (1996) Extensions to a memetic timetabling system. In: Burke EK, Ross P (eds) The practice and theory of automated timetabling I. LNCS 1153. Springer, Berlin, pp 251–265

Pelikan M (2005) Hierarchical Bayesian optimization algorithm: toward a new generation of evolutionary algorithm. Springer, Berlin

Pelikan M, Sastry K (2004) Fitness inheritance in the Bayesian optimization algorithm. In: Proceedings of the GECCO 2, Seattle, pp 48–59 (also IlliGAL report no 2004009)

Pelikan M, Goldberg DE, Cantú-Paz E (2000) Linkage learning, estimation distribution, and Bayesian networks. Evol Comput 8:314–341 (also IlliGAL report no 98013)

Pelikan M, Sastry K, Cantú-Paz E (eds) (2006) Scalable optimization via probabilistic modeling: algorithms to applications. Springer, Berlin

Rudolph G (2000) Takeover times and probabilities of non-generational selection rules. In: Proceedings of the GECCO, Las Vegas, pp 903–910

Sakamoto Y, Goldberg DE (1997) Takeover time in a noisy environment. In: Proceedings of the 7th international conference on genetic algorithms, East Lansing, pp 160–165

Sastry K (2001) Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master’s thesis, University of Illinois at Urbana-Champaign (also IlliGAL report no 2002004)

Sastry K, Goldberg DE (2003) Scalability of selectorecombinative genetic algorithms for problems with tight linkage. In: Proceedings of the GECCO, Chicago, pp 1332–1344 (also IlliGAL report no 2002013)

Sastry K, Goldberg DE (2004) Let’s get ready to rumble: crossover versus mutation head to head. In: Proceedings of the GECCO 2, Seattle, pp 126–137 (also IlliGAL report no 2004005)

Sastry K, Goldberg DE, Pelikan M (2001) Don’t evaluate, inherit. In: Proceedings of the GECCO, San Francisco, pp 551–558 (also IlliGAL report no 2001013)

Sastry K, Pelikan M, Goldberg DE (2004) Efficiency enhancement of genetic algorithms building-block-wise fitness estimation. In: Proceedings of the IEEE international congress on evolutionary computation. Portland, OR, USA, pp 720–727

Sastry K, Goldberg DE, Llorà X (2007) Towards billion bit optimization via efficient estimation of distribution algorithms. In: Proceedings of the GECCO, London, pp 577–584 (also IlliGAL report no 2007007)

Sinha A (2003) Designing efficient genetic and evolutionary hybrids. Master’s thesis, University of Illinois at Urbana-Champaign (also IlliGAL report no 2003020)

Smith R, Dike B, Stegmann S (1995) Fitness inheritance in genetic algorithms. In: Proceedings of the ACM symposium on applied computing. ACM, New York, pp 345–350

Spears WM, De Jong KA (1994) On the virtues of parameterized uniform crossover. In: Proceedings of the 4th international conference on genetic algorithms, San Diego, pp 230–236

Syswerda G (1989) Uniform crossover in genetic algorithms. In: Proceedings of the 3rd international conference on genetic algorithms, San Mateo, pp 2–9

Thierens D (1999) Scalability problems of simple genetic algorithms. Evol Comput 7:331–352CrossRef

Thierens D, Goldberg DE (1994) Convergence models of genetic algorithm selection schemes. PPSN 3, Springer, Berlin/New York, pp 116–121

Thierens D, Goldberg DE, Pereira AG (1998) Domino convergence, drift, and the temporal-salience structure of problems. In: Proceedings of the IEEE international congress on evolutionary computation, pp 535–540

Valenzuala J, Smith AE (2002) A seeded memetic algorithm for large unit commitment problems. J Heuristics 8:173–196CrossRef

Watson JP, Rana S, Whitely LD, Howe AE (1999) The impact of approximate evaluation on the performance of search algorithms for warehouse scheduling. J Scheduling 2:79–98CrossRef

Whitley D (1995) Modeling hybrid genetic algorithms. In: Winter G, Périaux J, Galán M, Cuesta P (eds) Genetic algorithms in engineering and computer science. Wiley, Chichester, pp 191–201

Yu T-L (2006) A matrix approach for finding extrema: problems with modularity, hierarchy, and overlap. Doctoral dissertation, University of Illinois at Urbana-Champaign (also IlliGAL report no 2007012)

Titel: Genetic Algorithms
verfasst von: Kumara Sastry
David E. Goldberg
Graham Kendall
Verlag: Springer US
Buch: Search Methodologies
Print ISBN: 978-1-4614-6939-1

Electronic ISBN: 978-1-4614-6940-7

Copyright-Jahr: 2014
DOI: https://doi.org/10.1007/978-1-4614-6940-7_4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner