Algoritmos Geneticos ( Inteligencia Artificial )

Algoritmos Genéticos

I. DESARROLLO DEL TEMA GENERAL ASIGNADO

1.1 INTRODUCCION

Los algoritmos genéticos intentan replicar comportamientos biológicos, con los avances científicos que ello implica, mediante la computación. Se trata de algoritmos de búsqueda basados en la mecánica de la selección natural y de la genética. Utilizan la información histórica para encontrar nuevos puntos de búsqueda de una solución óptima del problema planteado, con esperanzas de mejorar los resultados.

La principal diferencia del Algoritmo Genético con otras técnicas, es que utiliza la cruza como operador principal y a la mutación como operador secundario (e incluso opcional). El algoritmo genético, al igual que las redes neuronales, funciona como una caja negra que recibe ciertas entradas y produce (tras una cantidad de tiempo indeterminada) las salidas deseadas. Sin embargo, a diferencia de éstas, los algoritmos genéticos no necesitan entrenarse con ejemplos de ningún tipo, sino que son capaces de generar sus propios ejemplos y contraejemplos que guíen la evolución a partir de poblaciones iniciales totalmente aleatorias.

Siendo una heurística, tampoco pueden garantizar encontrar siempre la solución óptima, si se utilizan apropiadamente, pueden proporcionar soluciones muy aceptables y, en la mayoría de los casos, superiores a las encontradas con otras técnicas de búsqueda y optimización.

Lo que hace un algoritmo genético es tomar de los individuos una cantidad determinada de características que corresponden al “padre” y otras tantas de la “madre” y se intercambian. En los seres humanos el 50% del material genético proviene de la madre y el otro 50 del padre; pero el individuo resultante es diferente a los dos progenitores. Algo análogo se hace con algoritmos genéticos.

Finalmente, igual que en la naturaleza, se consideran las mutaciones. Contamos con individuos nuevos con las características de los mejores, pero mezclados y además con ciertas mutaciones para explorar posibles nuevas características. En la computadora tenemos la ventaja de que podemos hacer eso varias miles o millones de veces por segundo. Lo que a la naturaleza le toma millones de años, nosotros lo hacemos en unos segundos. El resultado es que logramos una población de individuos y entre ellos, uno va a ser el mejor.

1.2 HISTORIA

Los primeros ejemplos de lo que hoy podríamos llamar algoritmos genéticos aparecieron a finales de los 50 y principios de los 60, programados en computadoras por biólogos evolutivos que buscaban explícitamente realizar modelos de aspectos de la evolución natural. A ninguno de ellos se le ocurrió que esta estrategia podría aplicarse de manera más general a los problemas artificiales, pero ese reconocimiento no tardaría en llegar: En 1962, investigadores como G.E.P. Box, G.J. Friedman, W.W. Bledsoe y H.J. Bremermann habían desarrollado independientemente algoritmos inspirados en la evolución para optimización de funciones y aprendizaje automático, pero sus trabajos generaron poca reacción. En 1965 surgió un desarrollo más exitoso, cuando Ingo Rechenberg, entonces de la Universidad Técnica de Berlín, introdujo una técnica que llamó estrategia evolutiva, aunque se parecía más a los trepacolinas que a los algoritmos genéticos. En esta técnica no había población ni cruzamiento; un padre mutaba para producir un descendiente, y se conservaba el mejor de los dos, convirtiéndose en el padre de la siguiente ronda de mutación. Versiones posteriores introdujeron la idea de población.

El siguiente desarrollo importante en el campo vino en 1966, cuando L.J. Fogel, A.J. Owens y M.J. Walsh introdujeron en América una técnica llamada programación evolutiva. En este método, las soluciones candidatas para los problemas se representaban como máquinas de estado finito sencillas; al igual que en la estrategia evolutiva de Rechenberg, su algoritmo funcionaba mutando aleatoriamente una de estas máquinas simuladas y conservando la mejor de las dos. También al igual que las estrategias evolutivas, hoy en día existe una formulación más amplia de la técnica de programación evolutiva que todavía es un área de investigación en curso. Sin embargo, lo que todavía faltaba en estas dos metodologías era el reconocimiento de la importancia del cruzamiento.

En 1962, el trabajo de John Holland sobre sistemas adaptativos estableció las bases para desarrollos posteriores; y lo que es más importante, Holland fue también el primero en proponer explícitamente el cruzamiento y otros operadores de recombinación. Sin embargo, el trabajo fundamental en el campo de los algoritmos genéticos apareció en 1975, con la publicación del libro ''Adaptación en Sistemas Naturales y Artificiales''. Basado en investigaciones y papers anteriores del propio Holland y de colegas de la Universidad de Michigan, este libro fue el primero en presentar sistemática y rigurosamente el concepto de sistemas digitales adaptativos utilizando la mutación, la selección y el cruzamiento, simulando el proceso de la evolución biológica como estrategia para resolver problemas. John Holland desde pequeño, se preguntaba cómo logra la naturaleza, crear seres cada vez más perfectos. No sabía la respuesta, pero tenía una cierta idea de como hallarla: tratando de hacer pequeños modelos de la naturaleza, que tuvieran alguna de sus características, y ver cómo funcionaban, para luego extrapolar sus conclusiones a la totalidad.

Fue a principios de los 60, en la Universidad de Michigan en Ann Arbor, donde, dentro del grupo Logic of Computers, sus ideas se desarrollaron y dieron frutos. Y fue, además, leyendo un libro escrito por un biólogo evolucionista, R. A. Fisher, titulado La teoría genética de la selección natural, como comenzó a descubrir los medios de llevar a cabo sus propósitos de comprensión de la naturaleza. De ese libro aprendió que la evolución era una forma de adaptación más potente que el simple aprendizaje, y tomó la decisión de aplicar estas ideas para desarrollar programas bien adaptados para un fin determinado.

Los objetivos de la investigación de Holland fueron:

• Imitar los procesos adaptativos de los sistemas naturales, y

• diseñar sistemas artificiales (normalmente programas) que retengan los mecanismos importantes de los sistemas naturales.

David Goldberg estudiante de Holland fue uno de los primeros que trató de aplicar los Algoritmos Genéticos a problemas industriales. Goldberg escribió un Algoritmo Genético en un ordenador personal Apple II. Estas y otras aplicaciones creadas por estudiantes de Holland

...