Programació genètica

Plantilla:Format de referències En l'inteligència artificial, la programació genètica (GP, de les seues sigles en anglés: Genetic Programming) és una metodologia basada en els algoritmes evolutius i inspirada en l'evolució biològica per a desenrollar automàticament programes de computadores que realisen una tasca definida per l'usuari. És una especialisació dels algoritmes genètics (GA, de les seues sigles en anglés: Genetic Algorithms) a on cada individu és un programa de computadora. És una tècnica d'aprenentage automàtic utilisada per a optimisar una població de programes d'acort a una funció d'ajust o aptitut (en anglés: fitness function) que evalua la capacitat de cada programa per a portar a terme la tasca en qüestió.

Història

En 1954, GP es va iniciar en els algoritmes evolutius utilisat per primera volta per Nils Aall Barricelli i aplicats a simulacions evolutives. En 1960 i principis de 1970, els algoritmes evolutius varen ser reconeguts com a métodos d'optimisació. Ingo Rechenberg i el seu grup varen ser capaços de resoldre problemes complexos d'ingenieria a través d'estratègies d'evolutives com ho documenta en la seua tesis PhD en 1971 i el llibre resultant de 1973. John Holland va ser molt influent durant la década de 1970.

En 1964, Lawrence J. Fogel, un dels primers professionals de la metodologia de GP, aplica els algoritmes evolutius per al problema de descobrir autómates d'estat finito. Més vesprada, el treball relacionat en GP va sorgir la comunitat dels sistemes de classificació basat en aprenentage, la qual va desenrollar un conjunt de regles que descriuen les polítiques òptimes per al procés de decisió de Márkov. La primera declaració de la moderna GP "basat en arbres" (és dir, procediment en una estructuració basada en arbres i operadors adequadament definits en GA) va ser donada per Nichael L. Cramer (1985). Este treball va ser posteriorment ampliat en gran mida per John R. Koza., un proponente principal de GP que ha segut pioner en l'aplicació de GP en l'optimisació de diversos i complexos problemes de busca. Gianna Giavelli, un estudiant de Koza, després va ser el pioner en l'us de GP com una tècnica per a modelar l'expressió de el ADN.

En la década dels 1990's, GP es va utilisar principalment per a resoldre problemes relativament simples, ya que és molt costós computacionalment. Recentment, GP ha produït nous i excelents resultats en àrees com la computació quàntica, disseny electrònic, jocs, ordenament i busca, per les millores en la tecnologia GP i la creiximent exponencial de la potència de la CPU. Estos resultats inclouen la reproducció o el desenroll de vàries invencions posteriors a l'any 2000. GP també s'ha aplicat als programes de computadores, aixina com hardware evolutiu.

El desenroll d'una teoria de la GP ha segut molt difícil, per lo que en la década de 1990's GP va ser considerat una espècie de paria entre les tècniques de busca.

Representació

Erro al crear miniatura:

GP desenrolla programes informàtics, tradicionalment representats en la memòria com estructures d'arbres. Els arbres poden ser fàcilment evaluats de forma recursiva. Cada nodo de l'arbre té una funció com a operador i cada nodo terminal té un operant, per lo que les expressions matemàtiques són fàcils d'evolucionar i evaluar. Aixina, tradicionalment GP favorix l'us de llenguage de programació que, naturalment, introduïx les estructures d'arbre (per eixemple, Lisp; uns atres llenguages de programació funcionals també són adequats).

Representacions que no utilisen arbres s'han sugerit i aplicat en èxit, tals com programació genètica llineal, la qual s'adapta als tradicionals llenguages imperatius [vore, per eixemple, Banzhaf et al. (1998)]. El software comercial de GP Discipulus utilisen l'inducció automàtica de còdic màquina binario ("AIM") per a conseguir un millor rendiment. μGP usa multigrafos dirigits per a generar programes que exploten al màxim la sintaxis d'un dau llenguage ensamblador.

Vore també

• Sistemes bioinspirados
• Programació d'expressions de gens
• Evolució gramatical

Bibliografia

• Banzhaf, W., Nordin, P., Keller, R.E., and Francone, F.D. (1998), Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications, Morgan Kaufmann
• Barricelli, Nils Aall (1954), Esempi numerici vaig donar processi vaig donar evoluzione, Methodos, pp. 45–68.
• Brameier, M. and Banzhaf, W. (2007), Linear Genetic Programming, Springer, New York
• Carmona, Enrique J.; Fernández, Severino (2020). Fonaments de la Computació Evolutiva. Marcombo. ISBN 978-8426727558.
• Cramer, Nichael Lynn (1985), "A representation for the Adaptive Generation of Simple Sequential Programs" in Proceedings of an International Conference on Genetic Algorithms and the Applications, Grefenstette, John J. (ed.), Carnegie Mellon University
• Crosby, Jack L. (1973), Computer Simulation in Genetics, John Wiley & Sons, London.
• Fogel, David B. (2000) Evolutionary Computation: Towards a New Philosophy of Machine Intelligence IEEE Press, New York.
• Fogel, David B. (editor) (1998) Evolutionary Computation: The Fossil Record, IEEE Press, New York.
• Forsyth, Richard (1981), BEAGLE A Darwinian Approach to Pattern Recognition Kybernetes, Vol. 10, pp. 159–166.
• Fraser, Alex S. (1957), Simulation of Genetic Systems by Automatic Digital Computers. I. Introduction. Australian Journal of Biological Sciences vol. 10 484-491.
• Fraser, Alex and Donald Burnell (1970), Computer Models in Genetics, McGraw-Hill, New York.
• Holland, John H (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor
• Korns, Michael (2007), Large-Scale, Clave-Constrained, Symbolic Regression-Classification, in Genetic Programming Theory and Practice V. Springer, New York.
• Korns, Michael (2009), Symbolic Regression of Conditional Target Expressions, in Genetic Programming Theory and Practice VII. Springer, New York.

• Korns, Michael (2010), Abstract Expression Grammar Symbolic Regression, in Genetic Programming Theory and Practice VIII. Springer, New York.
• Koza, J.R. (1990), Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems, Stanford University Computer Science Department technical report STAN-CS-90-1314. A thorough report, possibly used as a draft to his 1992 book.
• Koza, J.R. (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press
• Koza, J.R. (1994), Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press
• Koza, J.R., Bennett, F.H., Andre, D., and Keane, M.A. (1999), Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann
• Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., Llança, G. (2003), Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers
• Langdon, W. B., Genetic Programming and Data Structures, Springer ISBN 0-7923-8135-1
• Langdon, W. B., Poli, R. (2002), Foundations of Genetic Programming, Springer-Verlag ISBN 3-540-42451-2
• Nordin, J.P., (1997) Evolutionary Program Induction of Binary Machine Code and its Application. Krehl Verlag, Muenster, Germany.
• Poli, R., Langdon, W. B., McPhee, N. F. (2008). A Field Guide to Genetic Programming, Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4.
• Rechenberg, I. (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Fromman-Holzboog (1973).
• Schmidhuber, J. (1987). Evolutionary principles in self-referential learning. (On learning how to learn: The fique-meta-... hook.) Diplomar thesis, Institut f. Informatik, Tech. Univ. Munich.
• Smith, S.F. (1980), A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh)
• Smith, Jeff S. (2002), Evolving a Better Solution
• Archivat el 11 de maig de 2013 archivat en Wayback Machine., Developers Network Journal, March 2002 issue
• Shu-Heng Chen et al. (2008), Genetic Programming: An Emerging Engineering Tool, International Journal of Knowledge-based Intelligent Engineering System, 12(1): 1-2, 2008.
• Weise, T, Global Optimization Algorithms: Theory and Application
• Archivat el 11 de setembre de 2008 archivat en Wayback Machine., 2008.