ALGORITMOS GENETICOS

Artículo de Guillermo Choque Aspiazu
gchoque@sistemasintegrales.edu.bo

La teoría de la evolución fue descrita por Charles Darwin 20 años después de su viaje por las islas Galápagos en el Beagle, en el libro “Sobre el Origen de las Especies por medio de la Selección Natural”. Este libro fue bastante polémico en su tiempo, y en cualquier caso es una descripción incompleta de la evolución. La hipótesis de Darwin, presentada junto con Wallace, que llegó a las mismas conclusiones independientemente, es que pequeños cambios heredables en los seres vivos y la selección son los dos hechos que provocan el cambio en la naturaleza y la generación de nuevas especies. Pero Darwin desconocía cual es la base de la herencia, pensaba que los rasgos de un ser vivo eran como un fluido, y que los “fluidos” de los dos padres se mezclaban en la descendencia; esta hipótesis tenía el problema de que al cabo de cierto tiempo, una población tendría los mismos rasgos intermedios.

La teoría de la evolución defendida por Charles Darwin se sustenta en cuatro argumentos: (1) La naturaleza está en constante evolución (2) El proceso de cambio es gradual y continuo. (3) Los organismos que presentan semejanzas están emparentados. (4) El cambio evolutivo es el resultado del proceso de selección natural. Gregor Mendel descubrió que los caracteres se heredaban de forma discreta, y que se tomaban del padre o de la madre, dependiendo de su carácter dominante o recesivo.

A estos caracteres que podían tomar diferentes valores se les llamaron genes, y a los valores que podían tomar, alelos.

En realidad, las teorías de Mendel, que trabajó en total aislamiento, se olvidaron y no se volvieron a redes cubrir hasta principios del siglo XX. Y no fue hasta los años 1950, cuando James Watson y Francis Crick descubrieron que la base molecular de los genes se encuentra en el ácido desoxiribonucleico. Los cromosomas están compuestos por acido desoxiribonucleico, y por tanto los genes están en los cromosomas.

Un algoritmo genético es una técnica que emula la evolución biológica como estrategia para resolver problemas.

Dado un problema específico a resolver, la entrada del algoritmo genético es un conjunto de soluciones potenciales a ese problema, codificadas de alguna manera, y una métrica llamada función de adaptación que permite evaluar cuantitativamente a cada candidata.

Estas candidatas, generadas aleatoriamente, pueden ser soluciones que ya se sabe que funcionan, con el objetivo de que el algoritmo genético las mejore.

El algoritmo genético evalúa cada candidata de acuerdo con una función de adaptación. En un acervo de candidatas generadas aleatoriamente, la mayoría no funciona en absoluto, y son eliminadas.

Sin embargo, siguiendo la aleatoriedad, unas pocas pueden ser prometedoras mostrando algunas veces actividad débil e imperfecta, que conducen hacia la solución del problema.

Estas candidatas prometedoras se conservan y se les permite reproducirse.. Se realizan múltiples copias de ellas, pero las copias no son perfectas; se introducen cambios aleatorios durante el proceso de copia.

Luego, esta descendencia prosigue con la siguiente generación, formando un nuevo conjunto de soluciones candidatas, que son sometidas nuevamente a una ronda de evaluaciones de adaptación.

Las candidatas que han empeorado o no han mejorado con los cambios en su código son eliminadas; pero, nuevamente, por puro azar, las variaciones aleatorias introducidas en la población pueden haber mejorado a algunos individuos, convirtiéndolos en mejores soluciones del problema, más completas o más eficientes.

Los primeros hechos relacionados con los algoritmos genéticos surgieron en 1932 cuando Cannon interpreta la evolución natural como un proceso de aprendizaje muy similar al proceso mediante el cual una persona aprende por ensayo y error.

También en 1950 Turing reconoce una conexión entre la evolución y el aprendizaje de una maquina, pero los primeros intentos serios de relacionar la informática y la evolución surgieron a principios de los años sesenta cuando varios biólogos comenzaron a experimentar con simulaciones de sistemas genéticos; esto es, modelos computacionales que imitan la evolución biológica.

El entorno en que viven los animales se representa entonces en el programa por una función que asigna a cada animal su capacidad de llegar a ser adulto y reproducirse. El inicio en el desarrollo de los algoritmos genéticos se debe realmente al trabajo de John Holland, investigador matemático de la Universidad de Michigan, quien estaba convencido de que era la recombinación de grupos de genes, que se realiza mediante el apareamiento, la parte más importante de la evolución.

A mediados de los años 60 desarrolla una novedosa técnica de programación, el Algoritmo Genético, que se adapta a la evolución tanto por el apareamiento como por la mutación.

Durante la década siguiente trabajó para ampliar el alcance de este tipo de algoritmos y fruto de dicha actividad, publica en 1975 la primera monografía sobre el tema denominada “Adaptación en Sistemas Naturales y Artificiales”, en la que se sientan las bases teóricas que fundamentan el desarrollo de los algoritmos genéticos desde el punto de vista computacional, abstrae los conceptos de la genética natural, y los aplica a la economía y al reconocimiento de patrones.

Unos 15 años más adelante, David Goldberg, actual delfín de los algoritmos genéticos, conoció a Holland, y se convirtió en su estudiante. Goldberg era un ingeniero industrial que trabajaba en el diseño de tuberías para la distribución de gas, y fue uno de los primeros que aplicó los algoritmos genéticos a problemas industriales.

Un algoritmo genético simple, el cual opera sobre cromosomas de tamaño fijo, incorpora los siguientes métodos en su operador de adaptabilidad: (1) Selección: Los individuos con adaptabilidad alta son favorecidos en el proceso de reproducción.

De manera concreta, los individuos con adaptabilidad alta tienen una gran probabilidad de sobrevivir y de reproducirse por cuenta propia. (2) Apareamiento: Se denomina así al método de mezclar la información genética de dos individuos; este mecanismo ha contribuido bastante a la adaptación rápida de las especies que se reproducen sexualmente. (3) Mutación: En la evolución real el material genético puede ser cambiado aleatoriamente por reproducción errónea u otras deformaciones de los genes. En los Algoritmos Genéticos la mutación puede ser realizada como una deformación aleatoria de los cromosomas con una cierta probabilidad asociada.

Antes de que un algoritmo genético pueda ponerse a trabajar en un problema, se necesita un método para codificar las soluciones potenciales del problema de forma que una computadora pueda procesarlas. Un enfoque común es codificar las soluciones como cadenas binarias: secuencias de unos y ceros, donde el dígito de cada posición representa el valor de algún aspecto de la solución.

Otro método similar consiste en codificar las soluciones como cadenas de enteros o números decimales, donde cada posición representa algún aspecto particular de la solución.

Este método permite una mayor precisión y complejidad que el método comparativamente restringido de utilizar sólo números binarios, y a menudo “está intuitivamente más cerca del espacio de estados del problema”.

Esta técnica se utiliza, por ejemplo, en un algoritmo genético para predecir la estructura tridimensional de una proteína, basándose en la secuencia de aminoácidos que la componen.

Los algoritmos genéticos para entrenar a las redes neuronales también utilizan a menudo este método de codificación.

Un tercer método consiste en representar a los individuos de un algoritmo genético como cadenas de letras, donde cada letra representa un aspecto específico de la solución.

Un ejemplo de esta técnica es el método basado en “codificación gramatical” en el que a un algoritmo genético se le encarga la tarea de evolucionar un conjunto simple de reglas denominadas gramática libre de contexto, que a su vez se utilizan para generar redes neuronales para una variedad de problemas.

El campo de aplicaciones de este tipo de algoritmos no ha dejado de crecer: diseños de turbinas de aviones, predicciones de la evolución bursátil, estudios de progresión de enfermedades, mediante comparación de imágenes tomadas por resonancia magnética, análisis de la estructura del cristal líquido, son algunos de los ejemplos más significativos.

© 1997 - 2006 EL DIARIO S.A.