Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2018 | OriginalPaper | Chapter

2. Biased Random-Key Genetic Progamming

Authors: José Fernando Gonçalves, Mauricio G. C. Resende

Published in: Handbook of Heuristics

Publisher: Springer International Publishing

share
SHARE

Abstract

This chapter introduces biased random-key genetic programming, a new metaheuristic for evolving programs. Each solution program is encoded as a vector of random keys, where a random key is a real number randomly generated in the continuous interval [0, 1]. A decoder maps each vector of random keys to a solution program and assigns it a measure of quality. A Program-Expression is encoded in the chromosome using a head-tail representation which is later transformed into a syntax tree using a prefix notation rule. The artificial simulated evolution of the programs is accomplished with a biased random-key genetic algorithm. Examples of the application of this approach to symbolic regression are presented.
Literature
1.
go back to reference Banzhaf W, Nordin P, Keller RE, Francone FD (1998) Genetic programming: an introduction. Morgan Kaufmann, San Francisco Banzhaf W, Nordin P, Keller RE, Francone FD (1998) Genetic programming: an introduction. Morgan Kaufmann, San Francisco
2.
go back to reference Barricelli NA et al (1954) Esempi numerici di processi di evoluzione. Methodos 6(21–22): 45–68 Barricelli NA et al (1954) Esempi numerici di processi di evoluzione. Methodos 6(21–22): 45–68
3.
go back to reference Bean JC (1994) Genetic algorithms and random keys for sequencing and optimization. ORSA J Comput 6:154–160 Bean JC (1994) Genetic algorithms and random keys for sequencing and optimization. ORSA J Comput 6:154–160
4.
go back to reference Brameier MF, Banzhaf W (2007) Linear genetic programming. Springer, New York Brameier MF, Banzhaf W (2007) Linear genetic programming. Springer, New York
5.
go back to reference Cramer NL (1985) A representation for the adaptive generation of simple sequential programs. In: Proceedings of the first international conference on genetic algorithms, Pittsburg, pp 183–187 Cramer NL (1985) A representation for the adaptive generation of simple sequential programs. In: Proceedings of the first international conference on genetic algorithms, Pittsburg, pp 183–187
6.
go back to reference Ferreira C (2001) Gene expression programming: a new adaptive algorithm for solving problems. Complex Syst 13:87–129 Ferreira C (2001) Gene expression programming: a new adaptive algorithm for solving problems. Complex Syst 13:87–129
7.
go back to reference Ferreira C (2006) Designing neural networks using gene expression programming. In: Abraham A (ed) Applied soft computing technologies: the challenge of complexity. Springer, Berlin, pp 517–535 Ferreira C (2006) Designing neural networks using gene expression programming. In: Abraham A (ed) Applied soft computing technologies: the challenge of complexity. Springer, Berlin, pp 517–535
8.
go back to reference Ferreira C (2006) Gene expression programming: mathematical modeling by an artificial intelligence. Studies in computational intelligence. Springer, New York Ferreira C (2006) Gene expression programming: mathematical modeling by an artificial intelligence. Studies in computational intelligence. Springer, New York
9.
go back to reference Fogel LJ (1964) On the organization of intellect. PhD thesis, UCLA Fogel LJ (1964) On the organization of intellect. PhD thesis, UCLA
10.
go back to reference Fontes DBMM, Gonçalves JF (2013) A multi-population hybrid biased random key genetic algorithm for hop-constrained trees in nonlinear cost flow networks. Optimization Letters, 7(6):1303–1324 Fontes DBMM, Gonçalves JF (2013) A multi-population hybrid biased random key genetic algorithm for hop-constrained trees in nonlinear cost flow networks. Optimization Letters, 7(6):1303–1324
11.
go back to reference Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading
12.
go back to reference Gonçalves JF, Almeida J (2002) A hybrid genetic algorithm for assembly line balancing. J Heuristics 8:629–642 Gonçalves JF, Almeida J (2002) A hybrid genetic algorithm for assembly line balancing. J Heuristics 8:629–642
13.
go back to reference Gonçalves JF, Resende MGC (2011) Biased random-key genetic algorithms for combinatorial optimization. J Heuristics 17:487–525 Gonçalves JF, Resende MGC (2011) Biased random-key genetic algorithms for combinatorial optimization. J Heuristics 17:487–525
14.
go back to reference Gonçalves JF, Resende MGC (2013) A biased random-key genetic algorithm for a 2D and 3D bin packing problem. Int J Prod Econ 145:500–510 Gonçalves JF, Resende MGC (2013) A biased random-key genetic algorithm for a 2D and 3D bin packing problem. Int J Prod Econ 145:500–510
15.
go back to reference Gonçalves JF, Resende MG (2014) An extended Akers graphical method with a biased random-key genetic algorithm for job-shop scheduling. Int Trans Oper Res 21(2):215–246 Gonçalves JF, Resende MG (2014) An extended Akers graphical method with a biased random-key genetic algorithm for job-shop scheduling. Int Trans Oper Res 21(2):215–246
16.
go back to reference Gonçalves JF, Resende MGC (2015) A biased random-key genetic algorithm for the unequal area facility layout problem. Eur J Oper Res 246(1):86–107 Gonçalves JF, Resende MGC (2015) A biased random-key genetic algorithm for the unequal area facility layout problem. Eur J Oper Res 246(1):86–107
17.
go back to reference Gonçalves J, Resende M, Toso R (2014) An experimental comparison of biased and unbiased random-key genetic algorithms. Pesquisa Operacional 34:143–164 Gonçalves J, Resende M, Toso R (2014) An experimental comparison of biased and unbiased random-key genetic algorithms. Pesquisa Operacional 34:143–164
18.
go back to reference Gonçalves JF, Resende MGC, Costa MD (2014) A biased random-key genetic algorithm for the minimization of open stacks problem. Int Trans Oper Res. Published online 2 July 2014 Gonçalves JF, Resende MGC, Costa MD (2014) A biased random-key genetic algorithm for the minimization of open stacks problem. Int Trans Oper Res. Published online 2 July 2014
19.
go back to reference Gonçalves JF, de Magalhães Mendes JJ, Resende MG (2015) The basic multi-project scheduling problem. In: Schwindt C, Zimmermann J (eds) Handbook on project management and scheduling, vol 2. Springer, Berlin, pp 667–683 Gonçalves JF, de Magalhães Mendes JJ, Resende MG (2015) The basic multi-project scheduling problem. In: Schwindt C, Zimmermann J (eds) Handbook on project management and scheduling, vol 2. Springer, Berlin, pp 667–683
20.
go back to reference Koza JR (1992) Genetic programming: on the programming of computers by means of natural selection, vol 1. MIT, Cambridge Koza JR (1992) Genetic programming: on the programming of computers by means of natural selection, vol 1. MIT, Cambridge
21.
go back to reference Koza JR (1994) Genetic programming II: automatic discovery of reusable subprograms. MIT, Cambridge Koza JR (1994) Genetic programming II: automatic discovery of reusable subprograms. MIT, Cambridge
22.
go back to reference Koza JR, Bennett FH III, Andre D, Keane MA (1999) Genetic Programming III: Darwinian invention and problem solving. Morgan Kaufmann, San Francisco Koza JR, Bennett FH III, Andre D, Keane MA (1999) Genetic Programming III: Darwinian invention and problem solving. Morgan Kaufmann, San Francisco
23.
go back to reference Koza JR, Keane MA, Streeter MJ, Mydlowec W, Yu J, Lanza G (2003) Genetic programming IV: routine human-competitive machine intelligence. Kluwer Academic, Norwell/Dordrecht Koza JR, Keane MA, Streeter MJ, Mydlowec W, Yu J, Lanza G (2003) Genetic programming IV: routine human-competitive machine intelligence. Kluwer Academic, Norwell/Dordrecht
24.
go back to reference Poli R (1997) Evolution of graph-like programs with parallel distributed genetic programming. In: Proceedings of the 7th international conference on genetic algorithms (ICGA), East Lansing, pp 346–353 Poli R (1997) Evolution of graph-like programs with parallel distributed genetic programming. In: Proceedings of the 7th international conference on genetic algorithms (ICGA), East Lansing, pp 346–353
25.
go back to reference Spears WM, DeJong KA (1991) On the virtues of parameterized uniform crossover. In: Proceedings of the fourth international conference on genetic algorithms, San Diego, pp 230–236 Spears WM, DeJong KA (1991) On the virtues of parameterized uniform crossover. In: Proceedings of the fourth international conference on genetic algorithms, San Diego, pp 230–236
Metadata
Title
Biased Random-Key Genetic Progamming
Authors
José Fernando Gonçalves
Mauricio G. C. Resende
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-07124-4_25

Premium Partner