Algoritmos genéticos

En términos muy generales se puede definir la computación evolutiva como una familia de modelos computacionales inspirados en la evolución. Formalmente, el término de computación evolutiva se refiere al estudio de los fundamentos y aplicaciones de ciertas técnicas heurísticas inspiradas en los principios de la evolución natural. Estas técnicas heurísticas pueden clasificarse en tres grandes categorías:

• Algoritmos genéticos

• Estrategias de evolución

• Programación evolutiva

Algoritmos genéticos.

A mediados de la década de los años sesenta, el Dr. John Henry Holland, mejor conocido como el padre del algoritmo genético, desarrolló una técnica de programación que se adaptaba muy bien a la evolución. El propósito original de Holland era estudiar de un modo formal, el fenómeno de la adaptación tal y como ocurre en la naturaleza, y desarrollar vías para extrapolar esos mecanismos de adaptación natural a los sistemas computacionales (H. Holland, Genetic Algorithms).
En 1975 con apoyo de trabajos anteriores y en colaboración con otros investigadores y alumnos, logró presentar en el libro Adaptación en Sistemas Naturales y Artificiales el algoritmo genético como una abstracción de la evolución biológica, con esto Holland fue el primero en intentar colocar la computación evolutiva sobre una base teórica firme, 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 trabajo por más de 40 años en la investigación de la la teoría y práctica de los algoritmos genéticos. En la década de los años ochenta los algoritmos genéticos comenzaban a aplicarse en una amplia variedad de áreas, desde problemas matemáticos abstractos como el problema de la mochila bin-packing, la coloración de grafos, hasta problemas de control de flujo, reconocimiento y clasificación de patrones y optimización estructural (Sancho Caparrini, Algoritmos Genéticos).
Los algoritmos genéticos se convirtieron solucionadores de problemas en distintas áreas, tal como la optimización, tanto en espacios discretos como en espacios continuos. En un breve resumen, los algoritmos genéticos son algoritmos de optimización, búsqueda y aprendizaje inspirados en los procesos de evolución natural y evolución genética.
La evolución es un proceso que opera sobre los cromosomas. Estos cromosomas pueden ser considerados como herramientas orgánicas que codifican la vida. Toda la información contenida en los cromosomas se conoce como genotipo, sin embargo dicha información puede o no manifestarse en el individuo. El fenotipo es el resultado de la expresión del genotipo conjuntamente con la influencia del medio y factores epigenéticos (caracteres observables).
La selección natural, expuesta en la teoría de la evolución biológica por Charles Darwin (1859), es un mecanismo que relaciona los cromosomas (genotipo) con el fenotipo y otorga a los individuos más adaptados un mayor número de oportunidades de reproducirse. Los procesos evolutivos tienen lugar durante la etapa de reproducción, aunque existe una larga serie de mecanismos que afectan a la reproducción, el más común es la mutación, causante de que los cromosomas en la descendencia sean diferentes a los de los padres y el cruce o recombinación, que combina los cromosomas de los padres para producir la descendencia («Selección natural»). Rigurosamente podemos definir la selección natural como el proceso que se da en una población de entidades biológicas cuando se cumplen las tres condiciones siguientes:

1. Variación fenotípica entre los individuos de una población: los distintos individuos de una población difieren en sus caracteres observables.

2. Eficacia biológica diferencial asociada a la variación: ciertos fenotipos o variantes están asociados a una mayor descendencia y/o una mayor supervivencia.

3. La herencia de la variación: permite la transmisión de los fenotipos seleccionados a la siguiente generación.

Si en una población de organismos se dan estas tres condiciones, entonces se sigue necesariamente un cambio en la composición genética de la población por selección natural. La selección es, por lo tanto, el proceso que resulta de las tres premisas citadas. Y esto es lógicamente cierto tanto en éste como en cualquier otro mundo imaginable.
En un algoritmo genético para alcanzar la solución a un problema se parte de un conjunto inicial de individuos, llamado población, el cual es generado de manera aleatoria. Cada uno de estos individuos representa una posible solución al problema. En el campo de los algoritmos genéticos, se construye una función objetivo mejor conocida como fitness function y se definen los paisajes del potencial (fitness landscapes o adaptive landscapes), los cuales son evaluaciones de la función objetivo para todos las soluciones candidatas. Para evaluar las soluciones en un algoritmo genético se utiliza la función de evaluación, la cual establece una medida numérica, mejor conocida como bondad de ajuste de una solución.
Esta medición permite controlar el número de selecciones, cruces y copias. En la naturaleza este ajuste puede entenderse como la probabilidad de que un individuo sobreviva hasta la edad de reproducción y se reproduzca.

Representación

La codificación utilizada en los algoritmos genéticos es una abstracción del genotipo de los individuos. Existen varias formas de representar a los cromosomas, la más sencilla es la binaria, aunque no siempre resulta ser la más natural, en estos casos se utilizan valores reales. (Gestal et al., Introducción a los Algoritmos genéticos y la Programación Genética).
El genotipo de un individuo en un algoritmo genético que emplea cadenas de bits es sencillamente, la configuración de bits del cromosoma de ese individuo. Aquí la noción de fenotipo no aparece en el contexto de los algoritmos genéticos, aunque en avances recientes, hay algoritmos que poseen un nivel “genotípico’’ y uno “fenotípico’’, por ejemplo, la cadena de bits que codifica una red neuronal. En la Figura 1 se muestra un ejemplo de un individuo binario que codifica 3 parámetros.

Operadores Genéticos

Una generación se obtiene a partir de la anterior por medio de operadores, que son mejor conocidos como operadores genéticos. Los más empleados son los operadores de selección, cruce, copia y mutación (Gestal et al., Introducción a los Algoritmos genéticos y la Programación Genética).
El pseudocódigo de un algoritmo genético se puede ver de la siguiente forma (Sancho Caparrini, Algoritmos Genéticos).

while no se cumpla el criterio de terminación do
	      Selección de los cromosomas más aptos en la nueva 		población
	      Cruzamiento de los cromosomas
	      Mutación de los cromosomas
	      Evaluación de los cromosomas
  end while
  Devuelve la mejor solución (la más apta) en la población

En cuanto a los criterios de terminación o parada, los más utilizados son (Sancho Caparrini, Algoritmos Genéticos):

• Los mejores individuos de la población representan soluciones suficientemente buenas para el problema que se desea resolver.

• La población ha convergido. Un gen ha convergido cuando el noventa y cinco porciento de la población tiene el mismo valor (caso de codificaciones binarias) o valores dentro de un rango especificado (otro tipo de codificaciones).

• Se ha alcanzado el número de generaciones máximo especificado.

Selección

La selección es el mecanismo por el cual son seleccionados los individuos que serán los padres de la siguiente generación. Similarmente a lo que ocurre en la selección natural, se otorga un mayor número de oportunidades de reproducción a los individuos más aptos. Es importante destacar que no se deben eliminar por completo las opciones de reproducción de los individuos menos aptos, pues en pocas generaciones la población podría volverse homogénea. (Gestal et al., Introducción a los Algoritmos genéticos y la Programación Genética).
Existen diversas formas de realizar una selección:

• Selección por truncamiento: elegimos a los padres entre los mejores k cromosomas de la población.

• Selección de torneos: se eligen subgrupos de individuos de la población y los integrantes de cada subgrupo compiten entre ellos. Sólo se elige a un individuo de cada subgrupo para la reproducción.

• Selección por ruleta: cada padre se elige con una probabilidad proporcional a su desempeño en relación con la población.

• Selección por jerárquica: los individuos atraviesan diversas rondas de selección en cada generación. Las evaluaciones de los primeros niveles son más sencillas, mientras que aquellos que sobreviven hasta niveles más altos son evaluados más rigurosamente.

Los algoritmos de selección pueden ser divididos en dos grupos: probabilísticos, en este grupo se encuentran los algoritmos de selección por ruleta, y determinísticos, en este grupo se encuentran los algoritmos de selección por jerarquías, muestreo determinístico, estado uniforme, sobrante estocástico, entre otros.
Una vez que se han elegido a los individuos más aptos por medio de la selección, estos deben ser cruzados y mutados para formar una nueva generación de individuos.

Cruce

El cruce consiste, como en el caso biológico, en un intercambio de material genético entre dos cromosomas de dos padres y a partir de esto se genera una descendencia. Al igual que en la selección existen diversas formas de hacer un cruce, entre ellos se encuentran:

• Cruce de un solo punto

• Cruce de dos puntos

• Cruce uniforme

La idea principal del cruce se basa en que si se toman dos individuos correctamente adaptados al medio y se obtiene una descendencia que comparta genes de ambos, al compartir las características buenas de dos individuos, la descendencia, o al menos parte de ella, debería tener una mayor bondad que cada uno de los padres por separado. Sin embargo, puede suceder que el cruce no agrupe las mejores características en uno de los hijos y por tanto la descendencia tendrá un peor ajuste que los padres. Por lo que optando por una estrategia de cruce no destructiva garantizamos que pasen a la siguiente generación los mejores individuos. Si aún en esta circunstancia se opta por insertar a la descendencia dado que los genes de los padres continuarán en la población, dispersos y posiblemente modificados por la mutación, en posteriores cruces se puede volver a obtener a los padres, recuperando así la bondad previamente perdida. (Salazar Larico, Algoritmos Genéticos).

Mutación

Análogo a la mutación biológica, una mutación en un algoritmo genético también causa pequeñas alteraciones en puntos determinados de la codificación del individuo. Este operador produce variaciones de modo aleatorio en un cromosoma. Cada bit tiene una pequeña probabilidad de ser invertido. Para un cromosoma con m bits, esta tasa de mutación generalmente se establece como 1/m. En el caso de tratar con codificaciones binarias, la mutación consiste simplemente en negar un bit.
La mutación suele realizarse después del cruce. Por lo general primero se seleccionan dos individuos de la población para realizar el cruce y si el cruce tiene éxito entonces uno de los descendientes, o ambos, se muta con cierta probabilidad. En la siguiente figura podemos observar un ejemplo de mutación y cruce.

Reemplazo

Cuando trabajamos con una población que no es temporal, y sobre la que se realizan selecciones e inserciones, deberá tenerse en cuenta que para insertar un nuevo individuo deberá de eliminarse previamente otro de la población. A esta operación se le conoce como reemplazo. (Gestal et al., Introducción a los Algoritmos genéticos y la Programación Genética).
Existen diferentes métodos de reemplazo:

• Aleatorio: el nuevo individuo se inserta en un lugar escogido de manera aleatoria en la población.

• Reemplazo de padres: se obtiene espacio para la nueva descendencia liberando el espacio ocupado por los padres.

• Reemplazo de similares: una vez obtenido el ajuste de la descendencia se selecciona un grupo de individuos de la población con un ajuste similar. Y se reemplazan aleatoriamente los que sean necesarios.

• Reemplazo de los peores: entre un porcentaje de los peores individuos de la población se seleccionan aleatoriamente los necesarios para dejar sitio a la descendencia.

Copia

Se trata de un operador de tipo asexual, pues consiste simplemente en la copia de un individuo en la nueva generación. La copia, es otra estrategia reproductiva para la obtención de una nueva generación a partir de la anterior. Un determinado número de individuos pasa, sin sufrir ninguna variación, directamente a la siguiente generación (Gestal et al., Introducción a los Algoritmos genéticos y la Programación Genética).

Elitismo

El elitismo es un caso particular del operador de copia, consiste en copiar siempre al mejor o mejores individuos. (Gestal et al., Introducción a los Algoritmos genéticos y la Programación Genética).

Ventajas y restricciones

Los algoritmos presentan algunas ventajas, al igual que ciertas restricciones en relación a otros algoritmos tradicionales de optimización. La principal es que a diferencia de otros algoritmos de optimización, los algoritmos genéticos buscan una población de puntos, no un único punto y además los algoritmos genéticos emplean la función objetivo, es decir, no necesitan derivadas ni otros objetos complementarios, lo cual muchas veces resulta costoso y difícil de calcular. Por otro lado, uno de los mayores obstáculos en los algoritmos genéticos suele ser la elección de la función objetivo, de ella depende que se alcancen soluciones más aptas en el problema. Otros de los parámetros que deben elegirse con mucho cuidado son el tamaño de la población, la tasa de mutación y cruce, dado que una mala elección de estas podría traer problemas en la convergencia del algoritmo.
Uno los problemas que suelen suceder en problemas con poblaciones pequeñas se conoce como convergencia prematura, esta ocurre cuando un individuo es más apto que el resto, entonces este ha de reproducir muchos más individuos que otros, esto reduce la diversidad en la población y provoca que el algoritmo converja a un óptimo local que representa este individuo en lugar de buscar el paisaje del potencial (fitness landscape) para poder encontrar la solución global óptima (Genetic Algorithms: The Reality).

Aplicaciones

Algunas de las aplicaciones de los algoritmos genéticos se señalan a continuación:

• Optimización

• Aprendizaje de máquina

• Economía

• Ecología: modelización de fenómenos ecológicos.

• Medicina

• Criptoanálisis

• Robótica: actualmente los algoritmos genéticos son utilizados para crear robots cuyo comportamiento imita a un humano en diversas tareas. Los algoritmos genéticos son técnicas de búsqueda adaptativas que se utilizan para aprender estructuras de conocimiento de alto rendimiento.

• Procesamiento de imagen

Durante muchos años, a través de la observación de la evolución y adaptación de distintas especies naturales, se logró adaptar esos sistemas naturales en sistemas artificiales, a esto se le conoce como biónica. Actualmente hay un gran desarrollo en torno a la computación evolutiva, algoritmos genéticos y programación evolutiva y que, como mencionamos en un principio, han logrado aprovechar el proceso de evolución para la resolución de distintos problemas.

Bibliografía