viernes, 19 de junio de 2009

Algoritmo genético simple

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 “algoritmo genético”. Esta técnica se basa en los mecanismos 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, que constituye la unidad básica de codificación de cada uno de los atributos de un ser vivo, y que los atributos más deseables del mismo se transmiten a sus descendientes, cuando éste se reproduce sexualmente.

John Holland desde pequeño, se preguntaba cómo logra la naturaleza, crear seres cada vez más perfectos, teniendo en cuenta además que todo se lleva a cabo a base de interacciones locales entre individuos, y entre estos y lo que les rodea. 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. De hecho, ya de pequeño hacía simulaciones de batallas célebres con todos sus elementos: mapas que copiaba y que cubría luego de pequeños ejércitos que se enfrentaban entre sí. Hacia los años 1950 entró en contacto con las primeras computadoras, donde pudo llevar a cabo algunas de sus ideas, aunque no se encontró con un ambiente intelectual fértil para propagarlas. Fue a principios de los años 1960, en la Universidad de Michigan en Ann Arbor, donde, dentro del grupo “Lógica Computacional”, sus ideas comenzaron a desarrollarse y a dar frutos. Y fue, además, leyendo un libro escrito por un biólogo evolucionista, R. A. Fisher, titulado “Teoría Genética de la Selección Natural”, como comenzó a descubrir los medios para 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.

En la Universidad de Michigan, Holland impartía un curso titulado “Teoría de sistemas adaptativos”. Dentro de este curso, y con una participación activa por parte de sus estudiantes, fue donde se crearon las ideas que más tarde se convertirían en los algoritmos genéticos. Por tanto, cuando Holland se enfrentó a los algoritmos genéticos, los objetivos de su investigación fueron dos: (1) imitar los procesos adaptativos de los sistemas naturales, y (2) diseñar sistemas artificiales que retengan los mecanismos importantes de los sistemas naturales. David Goldberg, uno de los grandes expertos de los algoritmos genéticos, conoció a Holland, y se convirtió en su estudiante. Golberg era un ingeniero industrial trabajando en diseño de redes de tuberías, y fue uno de los primeros que trató de aplicar los algoritmos genéticos a problemas industriales. Aunque Holland trató de disuadirle, porque pensaba que el problema era excesivamente complicado como para aplicarle algoritmos genéticos, Goldberg consiguió lo que quería, escribiendo un algoritmo genético en una computadora personal Apple II. Estas y otras aplicaciones creadas por estudiantes de Holland convirtieron a los algoritmos genéticos en un campo suficientemente aceptado como para celebrar la primera “Conferencia Internacional sobre Algoritmos Genéticos” el año 1985.

Los algoritmos genéticos son programas computacionales cuyo fin es imitar el proceso de “selección natural” que, según la teoría de Darwin, rige el curso de la evolución. El proceso de selección natural descrito de una manera sencilla es: se tiene una población, esa población se multiplica por medio del intercambio de genes, de la nueva generación sólo sobreviven los más capaces de adaptarse a su medio ambiente para así formar una nueva población “mejor” que la anterior. Este ciclo se repite a través del tiempo. Sin embargo, hay ocasiones en que se producen mutaciones en los individuos, lo que origina cambios drásticos en las características del individuo, y con esto se evita que se llegue a un “estancamiento”, en la evolución.

Se dice que el proceso evolutivo es aleatorio en el sentido de que se generan poblaciones cuyas características se parecen a las de sus padres, pero varían de manera aleatoria. Luego, estas poblaciones son “probadas” en el ambiente para ver cuál se “adapta” mejor. Sobreviven los que se adaptan mejor al medio ambiente, pero no se sabe para qué se quiere adaptar al medio ambiente, es decir, con qué fin. Cuando la gente se enfrentó con problemas que no podían ser solucionados por métodos matemáticos o analíticos, y que la única forma de resolverlos era a través de prueba y error dirigido, es decir, probar dónde se creía que podía mejorarse el resultado, se dio cuenta de que este proceso era similar al proceso que seguía la naturaleza, así que se intentó copiar su manera de operar y se crearon los algoritmos genéticos, que en la actualidad sólo son una rama de una extensa materia conocida como computación evolutiva que, en resumen, es la ciencia computacional cuyos algoritmos imitan el proceso evolutivo de la naturaleza.

En un algoritmo genético simple, primero, se genera de manera aleatoria la población inicial, que está constituida por un conjunto de cromosomas, o cadenas de caracteres que representan las soluciones posibles del problema. A cada uno de los cromosomas de esta población se le aplica la función de adaptabilidad a fin de saber qué tan buena es la solución que se está codificando. Sabiendo la adaptabilidad de cada cromosoma, se procede a la selección de los que se aparean en la siguiente generación. Dos son los métodos de selección más comunes: (1) La ruleta. Este método es bastante simple, y consiste en crear una ruleta en la que cada cromosoma tiene asignada una fracción proporcional a su adaptabilidad. (2) El torneo. La idea de este método es muy simple. Se baraja la población y después se hace competir a los cromosomas que la integran en grupos de tamaño predefinido en un torneo del que resultarán ganadores aquellos que tengan valores de adaptabilidad más altos. Una vez realizada la selección, se procede al apareamiento o reproducción sexual de los individuos seleccionados. En esta etapa, los sobrevivientes intercambiarán material cromosómico y sus descendientes formarán la población de la siguiente generación. Las dos formas más comunes de reproducción sexual son: uso de un punto único de apareamiento y uso de dos puntos de apareamiento.

Normalmente el apareamiento se maneja dentro de la implementación del algoritmo genético simple como un porcentaje que indica con qué frecuencia se efectuará. Esto significa que no todas las parejas de cromosomas se aparearan, sino que habrán algunas que pasarán intactas a la siguiente generación. De hecho existe una técnica desarrollada hace algunos años en la que el individuo más apto a lo largo de las distintas generaciones no se aparea con nadie, y se mantiene intacto hasta que surge otro individuo mejor que él, que lo desplaza. Dicha técnica es llamada elitismo. Además de la selección y el apareamiento, existe otro operador llamado mutación, el cual realiza un cambio a uno de los genes de un cromosoma elegido de manera aleatoria. Cuando se usa una representación binaria, el gen seleccionado se sustituye por su complemento. Este operador permite la introducción de nuevo material cromosómico en la población, tal y como sucede con sus equivalentes biológicos. Al igual que el apareamiento, la mutación se maneja como un porcentaje que indica con qué frecuencia se efectuará, aunque se distingue de la primera por ocurrir mucho más esporádicamente.

La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes y confiables. Sin embargo, no todos los problemas pueden ser apropiados para la técnica, y se recomienda en general tomar en cuenta las siguientes características del mismo antes de intentar usarla: (1) Su espacio de búsqueda, sus posibles soluciones, debe estar delimitado dentro de un cierto rango. (2) Debe definirse una función de adaptabilidad que indique qué tan buena o mala es una cierta respuesta. (3) Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora. El primer punto es muy importante, y lo más recomendable es intentar resolver problemas que tengan espacios de búsqueda discretos aunque éstos sean muy grandes. Sin embargo, también podrá intentarse usar la técnica con espacios de búsqueda continuos, pero preferentemente cuando exista un rango de soluciones relativamente pequeño.

Guillermo Choque Aspiazu
www.eldiario.net
Marzo 30 de 2009

No hay comentarios: