Algoritmos

CAPITULO I









Introducción: Los algoritmos genéticos





1. Introducción


En este primer capítulo se relata la utilidad de los algoritmos genéticos, así como su uso en problemas de optimización y de simulación. Además se explica un poco de la historia de los algoritmos genéticos, y se nombra diversas aplicaciones de los mismos, de las cuales he podidodesarrollar unos cuantos ejemplos para la comprensión de los mismos.

Se conoce que muchos problemas pueden ser resueltos de una forma computacional determinística, mientras que otros no tienen un método de resolución exacta y utilizan métodos numéricos o técnicas computacionales; pero todos estos métodos de resolución son complejos en su implantación y uso. Para la solución de éstos puedeutilizarse métodos heurísticos y metaheurísticos como los algoritmos genéticos.


Los algoritmos genéticos forman parte de la inteligencia artificial de los sistemas inspirados en la naturaleza y la evolución, y son métodos que simulan los procesos naturales y los aplican a la solución de problemas reales de búsqueda, optimización, diseño y simulación, aplicando la idea darwiniana dela selección natural de acuerdo a la aptitud y la disposición, y la combinan con otros operadores genéticos para producir métodos de gran robustez y de aplicación óptima.

Los algoritmos genéticos es una técnica de búsqueda basada en la teoría de la evolución de Darwin, que ha cobrado tremenda popularidad en todo el mundo durante los últimos años. Se presentarán aquí los conceptosbásicos que se requieren para abordarla, así como unos sencillos ejemplos que permitan a los lectores comprender cómo aplicarla al problema de su elección.

En los últimos años, la comunidad científica internacional ha mostrado un creciente interés en una nueva técnica de búsqueda basada en la teoría de la evolución y que se conoce como el algoritmo genético. Esta técnica se basa en losmecanismos de selección que utiliza la naturaleza, de acuerdo a los cuales los individuos más aptos de una población son los que sobreviven, al adaptarse más fácilmente a los cambios que se producen en su entorno. Hoy en día se sabe que estos cambios se efectúan en los genes de un individuo que es la unidad básica de codificación de cada uno de los atributos de un ser vivo, y que sus atributos másdeseables, es decir los que le permiten adaptarse mejor a su entorno, se transmiten a sus descendientes cuando éste se reproduce sexualmente.

Una definición bastante completa de un algoritmo genético es la propuesta por John Koza: "Es un algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos individuales con respecto al tiempo usando operacionesmodeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse presentado de forma natural una serie de operaciones genéticas de entre las que destaca la recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres (letras o números) de longitud fija que se ajusta al modelo de las cadenas de cromosomas, y se les asocia con unacierta función matemática que refleja su aptitud."

Un aspecto por demás importante de ellos es su aplicación como técnica de optimización que se basa en el azar, pero que aprovecha criterios que la naturaleza ha desarrollado, tales como la selección de los cromosomas más aptos, el cruce de genes en los cromosomas y la mutación. Por esto, no es de extrañarse que en algoritmos genéticosse utilicen términos tomados de la genética natural.

Estos algoritmos están basados en los procesos genéticos de los organismos biológicos, codificando una posible solución a un problema de cromosomas compuesto por cadena de bits y caracteres. Estos cromosomas representan individuos qué son llevados a lo largo de varias generaciones, en forma similar a los problemas naturales,...