nach oben

Erschienen in:

2022 | OriginalPaper | Buchkapitel

8. Fitness First

verfasst von : W. B. Langdon

Erschienen in: Genetic Programming Theory and Practice XVIII

Verlag: Springer Nature Singapore

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

With side effect free terminals and functions it is possible to evaluate the fitness of genetic programming trees from their parents without creating them. This allows selection before forming the next generation. Thus avoiding unfit runt Genetic Algorithm individuals, which will themselves have no children. In highly diverse GA populations with strong selection, more than 50% of children need not be created. Even with two parent crossover, in converged populations, \(e^{-2}\) = 13.5% can be saved. Eliminating bachelors and spinsters and extracting the smaller genetic material of each mating before crossover, reduces storage in an N multi-threaded implementation for a population M to \(\le \)0.63M+N, compared to the usual M+2N. Memory efficient crossover achieves 692 billion GP operations per second, 692 giga GPops, at runtime on a 16 core 3.8 GHz desktop.

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 Back to the Future—Revisiting OrdinalGP and Trustable Models After a Decade

Nächstes Kapitel Designing Multiple ANNs with Evolutionary Development: Activity Dependence

Baker, J.E.: Reducing bias and inefficiency in the selection algorithm. In: Grefenstette, J.J. (ed.) Proceedings of the Second International Conference on Genetic Algorithms and their Application, pp. 14–21. Lawrence Erlbaum Associates, Cambridge, MA, USA (1987)

Blickle, T.: Theory of evolutionary algorithms and application to system synthesis. Ph.D. thesis, Swiss Federal Institute of Technology, Zurich, Switzerland (1996). http://dx.doi.org/10.3929/ethz-a-001710359

de Melo, V.V., Fazenda, A.L., Sotto, L.F.D.P., Iacca, G.: A MIMD interpreter for genetic programming. In: Castillo, P.A., Jimenez Laredo, J.L., Fernandez de Vega, F. (eds.) 23rd International Conference, EvoApplications 2020, LNCS, vol. 12104, pp. 645–658. Springer, Seville, Spain (2020). URL http://dx.doi.org/10.1007/978-3-030-43722-0_41

Goldberg, D.E.: Genetic Algorithms in Search Optimization and Machine Learning. Addison-Wesley (1989)

Guizzo, G., Petke, J., Sarro, F., Harman, M.: Enhancing genetic improvement of software with regression test selection. In: van Deursen, A., Xie, T., Dieste, N.J.O. (eds.) Proceedings of the International Conference on Software Engineering, ICSE 2021. IEEE (2021). http://dx.doi.org/10.1109/ICSE43902.2021.00120. Winner ACM SIGSOFT Distinguished Artifact Award

Hrbacek, R., Sekanina, L.: Towards highly optimized cartesian genetic programming: from sequential via SIMD and thread to massive parallel implementation. In: C. Igel, D.V. Arnold, C. Gagne, E. Popovici, A. Auger, J. Bacardit, D. Brockhoff, S. Cagnoni, K. Deb, B. Doerr, J. Foster, T. Glasmachers, E. Hart, M.I. Heywood, H. Iba, C. Jacob, T. Jansen, Y. Jin, M. Kessentini, J.D. Knowles, W.B. Langdon, P. Larranaga, S. Luke, G. Luque, J.A.W. McCall, M.A. Montes de Oca, A. Motsinger-Reif, Y.S. Ong, M. Palmer, K.E. Parsopoulos, G. Raidl, S. Risi, G. Ruhe, T. Schaul, T. Schmickl, B. Sendhoff, K.O. Stanley, T. Stuetzle, D. Thierens, J. Togelius, C. Witt, C. Zarges (eds.) GECCO ’14: Proceedings of the 2014 conference on Genetic and evolutionary computation, pp. 1015–1022. ACM, Vancouver, BC, Canada (2014). URL http://dx.doi.org/10.1145/2576768.2598343

Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA (1992). http://mitpress.mit.edu/books/genetic-programming

Koza, J.R., Andre, D., Bennett III, F.H., Keane, M.: Genetic Programming III: Darwinian Invention and Problem Solving. Morgan Kaufmann (1999). http://www.genetic-programming.org/gpbook3toc.html

Langdon, W.B.: Long-term evolution of genetic programming populations. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’17, pp. 235–236. ACM, Berlin (2017). http://dx.doi.org/10.1145/3067695.3075965

10.

Langdon, W.B.: Parallel GPQUICK. In: C. Doerr (ed.) GECCO ’19: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 63–64. ACM, Prague, Czech Republic (2019). http://dx.doi.org/10.1145/3319619.3326770

11.

Langdon, W.B.: Genetic improvement of genetic programming. In: Brownlee, A.S., Haraldsson, S.O., Petke, J., Woodward, J.R. (eds.) GI @ CEC 2020 Special Session, p. paper id24061. IEEE Computational Intelligence Society, IEEE Press, internet (2020). http://dx.doi.org/10.1109/CEC48606.2020.9185771

12.

Langdon, W.B.: Multi-threaded memory efficient crossover in C++ for generational genetic programming. SIGEVOLution newsletter of the ACM Special Interest Group on Genetic and Evolutionary Computation 13(3), 2–4 (2020). URL http://dx.doi.org/10.1145/3430913.3430914

13.

Langdon, W.B.: Multi-threaded memory efficient crossover in C++ for generational genetic programming (2020). http://arxiv.org/abs/2009.10460

14.

Langdon, W.B.: Fitness first and fatherless crossover. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’21. ACM, Internet, pp. 253–254 (2021). http://dx.doi.org/10.1145/3449726.3459437.

15.

Langdon, W.B.: Incremental evaluation in genetic programming. In: Hu, T., Lourenco, N., Medvet, E. (eds.) EuroGP 2021: Proceedings of the 24th European Conference on Genetic Programming, LNCS, vol. 12691, pp. 229–246. Springer, Virtual Event (2021). http://dx.doi.org/10.1007/978-3-030-72812-0_15

16.

Langdon, W.B., Banzhaf, W.: Continuous long-term evolution of genetic programming. In: Fuechslin, R. (ed.) Conference on Artificial Life (ALIFE 2019), pp. 388–395. MIT Press, Newcastle (2019). http://dx.doi.org/10.1162/isal_a_00191

17.

Langdon, W.B., Banzhaf, W.: Faster genetic programming GPquick via multicore and advanced vector extensions. Technical Report RN/19/01, University College, London, London, UK (2019). http://www.cs.ucl.ac.uk/fileadmin/user_upload/avx_rn1901.pdf

18.

Langdon, W.B., Harman, M.: Optimising existing software with genetic programming. IEEE Trans. Evolut. Comput. 19(1), 118–135 (2015). http://dx.doi.org/10.1109/TEVC.2013.2281544

19.

Langdon, W.B., Petke, J., Clark, D.: Dissipative polynomials. In: Veerapen, N., Malan, K., Liefooghe, A., Verel, S., Ochoa, G. (eds.) 5th Workshop on Landscape-Aware Heuristic Search, GECCO 2021 Companion. ACM, Internet, pp. 1683–1691 (2021). http://dx.doi.org/10.1145/3449726.3463147

20.

Langdon, W.B., Poli, R.: Foundations of Genetic Programming. Springer (2002). http://dx.doi.org/10.1007/978-3-662-04726-2

21.

Lim, M., Guizzo, G., Petke, J.: Impact of test suite coverage on overfitting in genetic improvement of software. In: Galeotti, J.P., Sharif, B. (eds.) 12th International Symposium on Search Based Software Engineering SSBSE 2020, LNCS, vol. 12420, pp. 188–203. Springer, Bari, Italy (2020). http://dx.doi.org/10.1007/978-3-030-59762-7_14

22.

Petke, J.: Constraints: The future of combinatorial interaction testing. In: 2015 IEEE/ACM 8th International Workshop on Search-Based Software Testing, pp. 17–18. Florence (2015). http://dx.doi.org/10.1109/SBST.2015.11

23.

Petke, J., Haraldsson, S.O., Harman, M., Langdon, W.B., White, D.R., Woodward, J.R.: Genetic improvement of software: a comprehensive survey. IEEE Trans. Evolut. Comput. 22(3), 415–432 (2018). http://dx.doi.org/10.1109/TEVC.2017.2693219

24.

Petke, J., Harman, M., Langdon, W.B., Weimer, W.: Using genetic improvement and code transplants to specialise a C++ program to a problem class. In: Nicolau, M., Krawiec, K., Heywood, M.I., Castelli, M., Garcia-Sanchez, P., Merelo, J.J., Rivas Santos, V.M., Sim, K. (eds.) 17th European Conference on Genetic Programming, LNCS, vol. 8599, pp. 137–149. Springer, Granada, Spain (2014). http://dx.doi.org/10.1007/978-3-662-44303-3_12

25.

Petke, J., Harman, M., Langdon, W.B., Weimer, W.: Specialising software for different downstream applications using genetic improvement and code transplantation. IEEE Trans. Softw. Eng. 44(6), 574–594 (2018). http://dx.doi.org/10.1109/TSE.2017.2702606

26.

Petke, J., Le Goues, C., Forrest, S., Langdon, W.B.: Genetic improvement of software: Report from dagstuhl seminar 18052. Dagstuhl Rep. 8(1), 158–182 (2018). http://dx.doi.org/10.4230/DagRep.8.1.158

27.

Poli, R.: TinyGP. TinyGP GECCO 2004 competition (2004). http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/poli04__tinyg.pdf

28.

Poli, R., Langdon, W.B.: Sub-machine-code genetic programming. In: Spector, L., Langdon, W.B., O’Reilly, U.M., Angeline, P.J. (eds.) Advances in Genetic Programming 3, chap. 13, pp. 301–323. MIT Press, Cambridge, MA, USA (1999). http://www.cs.ucl.ac.uk/staff/W.Langdon/aigp3/ch13.pdf

29.

Poli, R., Langdon, W.B.: Running genetic programming backward. In: Yu, T., Riolo, R.L., Worzel, B. (eds.) Genetic Programming Theory and Practice III, Genetic Programming, vol. 9, Chap. 9, pp. 125–140. Springer, Ann Arbor (2005). http://dx.doi.org/10.1007/0-387-28111-8_9

30.

Poli, R., Langdon, W.B., McPhee, N.F.: A field guide to genetic programming. Published via http://lulu.comhttp://www.gp-field-guide.org.uk (2008). http://www.gp-field-guide.org.uk. (With contributions by J. R. Koza)

31.

Singleton, A.: Genetic programming with C++. BYTE pp. 171–176 (1994). http://www.assembla.com/wiki/show/andysgp/GPQuick_Article

32.

White, D.R., Arcuri, A., Clark, J.A.: Evolutionary improvement of programs. IEEE Trans. Evolut. Comput. 15(4), 515–538 (2011). http://dx.doi.org/10.1109/TEVC.2010.2083669

Titel: Fitness First
verfasst von: W. B. Langdon
Verlag: Springer Nature Singapore
Buch: Genetic Programming Theory and Practice XVIII
Print ISBN: 978-981-16-8112-7

Electronic ISBN: 978-981-16-8113-4

Copyright-Jahr: 2022
DOI: https://doi.org/10.1007/978-981-16-8113-4_8

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