fbpx
Wikipedia

Programación genética

En la inteligencia artificial, la programación genética (GP, de sus siglas en inglés: Genetic Programming) es una metodología basada en los algoritmos evolutivos e inspirada en la evolución biológica para desarrollar automáticamente programas de computadoras que realicen una tarea definida por el usuario. Es una especialización de los algoritmos genéticos (GA, de sus siglas en inglés: Genetic Algorithms) donde cada individuo es un programa de computadora. Es una técnica de aprendizaje automático utilizada para optimizar una población de programas de acuerdo a una función de ajuste o aptitud (en inglés: fitness function) que evalúa la capacidad de cada programa para llevar a cabo la tarea en cuestión.

Historia

En 1954, GP se inició con los algoritmos evolutivos utilizado por primera vez por Nils Aall Barricelli y aplicados a simulaciones evolutivas. En 1960 y principios de 1970, los algoritmos evolutivos fueron reconocidos como métodos de optimización. Ingo Rechenberg y su grupo fueron capaces de resolver problemas complejos de ingeniería a través de estrategias de evolutivas como lo documenta en su tesis PhD en 1971 y el libro resultante de 1973. John Holland fue muy influyente durante la década de 1970.

En 1964, Lawrence J. Fogel, uno de los primeros profesionales de la metodología de GP, aplica los algoritmos evolutivos para el problema de descubrir autómatas de estado finito. Más tarde, el trabajo relacionado con GP surgió la comunidad de los sistemas de clasificación basado en aprendizaje, la cual desarrolló un conjunto de reglas que describen las políticas óptimas para los procesos de decisión de Markov. La primera declaración de la moderna GP "basado en árboles" (es decir, procedimiento con una estructuración basada en árboles y operadores adecuadamente definidos en GA) fue dada por Nichael L. Cramer (1985).[1]​ Este trabajo fue posteriormente ampliado en gran medida por John R. Koza., un proponente principal de GP que ha sido pionero en la aplicación de GP en la optimización de diversos y complejos problemas de búsqueda.[2]​ Gianna Giavelli, un estudiante de Koza, luego fue el pionero en el uso de GP como una técnica para modelar la expresión del ADN.[3]

En la década de los 1990's, GP se utilizó principalmente para resolver problemas relativamente simples, ya que es muy costoso computacionalmente. Recientemente, GP ha producido novedosos y excelentes resultados en áreas como la computación cuántica, diseño electrónico, juegos, ordenamiento y búsqueda, debido a las mejoras en la tecnología GP y la crecimiento exponencial de la potencia de la CPU.[4]​ Estos resultados incluyen la reproducción o el desarrollo de varias invenciones posteriores al año 2000. GP también se ha aplicado a los programas de computadoras, así como hardware evolutivo.

El desarrollo de una teoría de la GP ha sido muy difícil, por lo que en la década de 1990's GP fue considerado una especie de paria entre las técnicas de búsqueda.

Representación

 

GP desarrolla programas informáticos, tradicionalmente representados en la memoria como estructuras de árboles.[5]​ Los árboles pueden ser fácilmente evaluados de forma recursiva. Cada nodo del árbol tiene una función como operador y cada nodo terminal tiene un operando, por lo que las expresiones matemáticas son fáciles de evolucionar y evaluar. Así, tradicionalmente GP favorece el uso de lenguaje de programación que, naturalmente, introduce las estructuras de árbol (por ejemplo, Lisp; otros lenguajes de programación funcionales también son adecuados).

Representaciones que no utilizan árboles se han sugerido y aplicado con éxito, tales como programación genética lineal, la cual se adapta a los tradicionales lenguajes imperativos [véase, por ejemplo, Banzhaf et al. (1998)]. El software comercial de GP Discipulus utilizan la inducción automática de código máquina binario ("AIM")[6]​ para lograr un mejor rendimiento. μGP[7]​ usa multigrafos dirigidos para generar programas que explotan al máximo la sintaxis de un dado lenguaje ensamblador.

Operadores genéticos

Los principales operadores usados en algoritmos evolutivos así como GP son cruzamiento y mutación.

Cruzamiento

El cruzamiento es aplicado a un individuo mediante simples intercambios entre uno de sus nodos por otro nodo de otro individuo de la población. Con una representación basada en árboles, la sustitución de un nodo implica la sustitución de toda la rama. Esto añade una mayor efectividad al operador de cruce. Las expresiones resultantes del cruce son muy diferentes de sus padres iniciales.

Mutación

La mutación afecta a un individuo de la población. Se puede sustituir un nodo entero en el individuo seleccionado, o puede simplemente reemplazar la información del nodo. Para mantener la integridad, las operaciones deben ser salvo fallos o el tipo de información que el nodo tiene debe ser tomada en cuenta. Por ejemplo, la mutación debe ser consciente de nodos operación binaria, o el operador debe ser capaz de manejar los valores que faltan.

Otros enfoques

Las ideas básicas de la programación genética han sido modificadas y extendidas en una variedad de formas:

  • Extended Compact Genetic Programming (ECGP)
  • Embedded Cartesian Genetic Programming (ECGP)
  • Probabilistic Incremental Program Evolution (PIPE)

Programación Meta-Genética

La Programación Meta-Genética es la técnica de evolucionar meta de aprendizaje un sistema de programación usando su propia programación genética. Se sugiere que los cromosomas, el cruzamiento, y la mutación vayan evolucionando ellos mismos, por lo tanto, al igual que sus homólogos en la vida real deben ser flexibles al cambio en el medio escogido por un programador humano. Programación Meta-Genética fue propuesta formalmente por Jürgen Schmidhuber en 1987.[8]Doug Lenat Eurisko es un esfuerzo anterior que puede ser la misma técnica. Se trata de un algoritmo recursivo pero de terminación, lo que le permite evitar una recursión infinita.

Los críticos de esta idea a menudo dicen este enfoque es demasiado amplio en su alcance. Sin embargo, podría ser posible restringir el criterio de la aptitud en una clase general de los resultados, y así obtener un GP evolucionado que sería más eficiente para producir resultados para las sub-clases. Esto podría tomar la forma de una Meta evolutiva GP para producir algoritmos humanos caminantes que se utilizan para evolucionar el funcionamiento humano como correr, saltar, etc. El criterio de aptitud aplicado a la Meta-GP simplemente sería el de eficiencia.

Para las clases de problemas generales puede no haber manera de demostrar que Meta-GP pueda ser viable producir resultados de manera más eficiente que un algoritmo creado mediante distintos enfoques. Lo mismo vale para GP estándar y otros algoritmos de búsqueda.

Véase también

Referencias

  1. . Archivado desde el original el 4 de diciembre de 2005. Consultado el 7 de marzo de 2013. 
  2. genetic-programming.com-Home-Page
  3. The Genetic Coding of Behavioral Attributes in Cellular Automata. Artificial Life at Stanford 1994 Stanford, California, 94305-3079 USA.
  4. humancompetitive
  5. . Archivado desde el original el 4 de diciembre de 2005. Consultado el 7 de marzo de 2013. 
  6. (Peter Nordin, 1997, Banzhaf et al., 1998, Section 11.6.2-11.6.3)
  7. MicroGP page on SourceForge, complete with tutorials and wiki
  8. 1987 THESIS ON LEARNING HOW TO LEARN, METALEARNING, META GENETIC PROGRAMMING, CREDIT-CONSERVING MACHINE LEARNING ECONOMY

Bibliografía

  • 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 di processi di evoluzione, Methodos, pp. 45–68.
  • Brameier, M. and Banzhaf, W. (2007), Linear Genetic Programming, Springer, New York
  • Crosby, Jack L. (1973), Computer Simulation in Genetics, John Wiley & Sons, London.
  • Cramer, Nichael Lynn (1985), "" in Proceedings of an International Conference on Genetic Algorithms and the Applications, Grefenstette, John J. (ed.), Carnegie Mellon University
  • 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, Time-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., Lanza, 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 meta-meta-... hook.) Diploma 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, 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, 2008
  • Carmona, Enrique; Fernández, Severino (2020). Fundamentos de la Computación Evolutiva. Marcombo. ISBN 978-8426727558.

Enlaces externos

  • Riccardo Poli, William B. Langdon, Nicholas F. McPhee, John R. Koza, "" (2008)
  • Vertical search engine for GA/GP resources
  • GP bibliography
  • People who work on GP
  •   Datos: Q629498

programación, genética, este, artículo, sección, tiene, referencias, pero, necesita, más, para, complementar, verificabilidad, este, aviso, puesto, agosto, 2020, referencias, este, artículo, tienen, formato, correcto, puedes, colaborar, editándolas, como, indi. Este articulo o seccion tiene referencias pero necesita mas para complementar su verificabilidad Este aviso fue puesto el 28 de agosto de 2020 Las referencias de este articulo no tienen un formato correcto Puedes colaborar editandolas como se indica en esta pagina Tambien puedes avisar en su pagina de discusion a quien las anadio pegando lo siguiente subst Aviso formato de referencias Programacion genetica Este aviso fue puesto el 28 de agosto de 2020 En la inteligencia artificial la programacion genetica GP de sus siglas en ingles Genetic Programming es una metodologia basada en los algoritmos evolutivos e inspirada en la evolucion biologica para desarrollar automaticamente programas de computadoras que realicen una tarea definida por el usuario Es una especializacion de los algoritmos geneticos GA de sus siglas en ingles Genetic Algorithms donde cada individuo es un programa de computadora Es una tecnica de aprendizaje automatico utilizada para optimizar una poblacion de programas de acuerdo a una funcion de ajuste o aptitud en ingles fitness function que evalua la capacidad de cada programa para llevar a cabo la tarea en cuestion Indice 1 Historia 2 Representacion 3 Operadores geneticos 3 1 Cruzamiento 3 2 Mutacion 4 Otros enfoques 5 Programacion Meta Genetica 6 Vease tambien 7 Referencias 8 Bibliografia 9 Enlaces externosHistoria EditarEn 1954 GP se inicio con los algoritmos evolutivos utilizado por primera vez por Nils Aall Barricelli y aplicados a simulaciones evolutivas En 1960 y principios de 1970 los algoritmos evolutivos fueron reconocidos como metodos de optimizacion Ingo Rechenberg y su grupo fueron capaces de resolver problemas complejos de ingenieria a traves de estrategias de evolutivas como lo documenta en su tesis PhD en 1971 y el libro resultante de 1973 John Holland fue muy influyente durante la decada de 1970 En 1964 Lawrence J Fogel uno de los primeros profesionales de la metodologia de GP aplica los algoritmos evolutivos para el problema de descubrir automatas de estado finito Mas tarde el trabajo relacionado con GP surgio la comunidad de los sistemas de clasificacion basado en aprendizaje la cual desarrollo un conjunto de reglas que describen las politicas optimas para los procesos de decision de Markov La primera declaracion de la moderna GP basado en arboles es decir procedimiento con una estructuracion basada en arboles y operadores adecuadamente definidos en GA fue dada por Nichael L Cramer 1985 1 Este trabajo fue posteriormente ampliado en gran medida por John R Koza un proponente principal de GP que ha sido pionero en la aplicacion de GP en la optimizacion de diversos y complejos problemas de busqueda 2 Gianna Giavelli un estudiante de Koza luego fue el pionero en el uso de GP como una tecnica para modelar la expresion del ADN 3 En la decada de los 1990 s GP se utilizo principalmente para resolver problemas relativamente simples ya que es muy costoso computacionalmente Recientemente GP ha producido novedosos y excelentes resultados en areas como la computacion cuantica diseno electronico juegos ordenamiento y busqueda debido a las mejoras en la tecnologia GP y la crecimiento exponencial de la potencia de la CPU 4 Estos resultados incluyen la reproduccion o el desarrollo de varias invenciones posteriores al ano 2000 GP tambien se ha aplicado a los programas de computadoras asi como hardware evolutivo El desarrollo de una teoria de la GP ha sido muy dificil por lo que en la decada de 1990 s GP fue considerado una especie de paria entre las tecnicas de busqueda Representacion Editar GP desarrolla programas informaticos tradicionalmente representados en la memoria como estructuras de arboles 5 Los arboles pueden ser facilmente evaluados de forma recursiva Cada nodo del arbol tiene una funcion como operador y cada nodo terminal tiene un operando por lo que las expresiones matematicas son faciles de evolucionar y evaluar Asi tradicionalmente GP favorece el uso de lenguaje de programacion que naturalmente introduce las estructuras de arbol por ejemplo Lisp otros lenguajes de programacion funcionales tambien son adecuados Representaciones que no utilizan arboles se han sugerido y aplicado con exito tales como programacion genetica lineal la cual se adapta a los tradicionales lenguajes imperativos vease por ejemplo Banzhaf et al 1998 El software comercial de GP Discipulus utilizan la induccion automatica de codigo maquina binario AIM 6 para lograr un mejor rendimiento mGP 7 usa multigrafos dirigidos para generar programas que explotan al maximo la sintaxis de un dado lenguaje ensamblador Operadores geneticos EditarLos principales operadores usados en algoritmos evolutivos asi como GP son cruzamiento y mutacion Cruzamiento Editar El cruzamiento es aplicado a un individuo mediante simples intercambios entre uno de sus nodos por otro nodo de otro individuo de la poblacion Con una representacion basada en arboles la sustitucion de un nodo implica la sustitucion de toda la rama Esto anade una mayor efectividad al operador de cruce Las expresiones resultantes del cruce son muy diferentes de sus padres iniciales Mutacion Editar La mutacion afecta a un individuo de la poblacion Se puede sustituir un nodo entero en el individuo seleccionado o puede simplemente reemplazar la informacion del nodo Para mantener la integridad las operaciones deben ser salvo fallos o el tipo de informacion que el nodo tiene debe ser tomada en cuenta Por ejemplo la mutacion debe ser consciente de nodos operacion binaria o el operador debe ser capaz de manejar los valores que faltan Otros enfoques EditarLas ideas basicas de la programacion genetica han sido modificadas y extendidas en una variedad de formas Extended Compact Genetic Programming ECGP Embedded Cartesian Genetic Programming ECGP Probabilistic Incremental Program Evolution PIPE Programacion Meta Genetica EditarLa Programacion Meta Genetica es la tecnica de evolucionar meta de aprendizaje un sistema de programacion usando su propia programacion genetica Se sugiere que los cromosomas el cruzamiento y la mutacion vayan evolucionando ellos mismos por lo tanto al igual que sus homologos en la vida real deben ser flexibles al cambio en el medio escogido por un programador humano Programacion Meta Genetica fue propuesta formalmente por Jurgen Schmidhuber en 1987 8 Doug Lenat Eurisko es un esfuerzo anterior que puede ser la misma tecnica Se trata de un algoritmo recursivo pero de terminacion lo que le permite evitar una recursion infinita Los criticos de esta idea a menudo dicen este enfoque es demasiado amplio en su alcance Sin embargo podria ser posible restringir el criterio de la aptitud en una clase general de los resultados y asi obtener un GP evolucionado que seria mas eficiente para producir resultados para las sub clases Esto podria tomar la forma de una Meta evolutiva GP para producir algoritmos humanos caminantes que se utilizan para evolucionar el funcionamiento humano como correr saltar etc El criterio de aptitud aplicado a la Meta GP simplemente seria el de eficiencia Para las clases de problemas generales puede no haber manera de demostrar que Meta GP pueda ser viable producir resultados de manera mas eficiente que un algoritmo creado mediante distintos enfoques Lo mismo vale para GP estandar y otros algoritmos de busqueda Vease tambien EditarSistemas bioinspirados Programacion de expresiones de genes Evolucion gramaticalReferencias Editar Nichael Cramer s HomePage Archivado desde el original el 4 de diciembre de 2005 Consultado el 7 de marzo de 2013 genetic programming com Home Page The Genetic Coding of Behavioral Attributes in Cellular Automata Artificial Life at Stanford 1994 Stanford California 94305 3079 USA humancompetitive Cramer 1985 Archivado desde el original el 4 de diciembre de 2005 Consultado el 7 de marzo de 2013 Peter Nordin 1997 Banzhaf et al 1998 Section 11 6 2 11 6 3 MicroGP page on SourceForge complete with tutorials and wiki 1987 THESIS ON LEARNING HOW TO LEARN METALEARNING META GENETIC PROGRAMMING CREDIT CONSERVING MACHINE LEARNING ECONOMYBibliografia EditarBanzhaf 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 di processi di evoluzione Methodos pp 45 68 Brameier M and Banzhaf W 2007 Linear Genetic Programming Springer New York Crosby Jack L 1973 Computer Simulation in Genetics John Wiley amp Sons London 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 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 Time 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 Lanza 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 meta meta hook Diploma 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 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 2008 Carmona Enrique Fernandez Severino 2020 Fundamentos de la Computacion Evolutiva Marcombo ISBN 978 8426727558 Enlaces externos EditarRiccardo Poli William B Langdon Nicholas F McPhee John R Koza A Field Guide to Genetic Programming 2008 DigitalBiology NET Vertical search engine for GA GP resources Aymen S Saket amp Mark C Sinclair The Hitch Hiker s Guide to Evolutionary Computation GP bibliography People who work on GP Datos Q629498 Obtenido de https es wikipedia org w index php title Programacion genetica amp oldid 132381067, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos