Algoritmos Genéticos

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 esa aproximación no tardaría en llegar: la computación evolutiva estaba definitivamente en el ambiente desde los primeros días de la computadora electrónica.

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 algoritmos escaladores nombrados anteriormente 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 una técnica que llamaron 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. Sin embargo, lo que todavía faltaba en estas dos metodologías era reconocer la importancia del cruzamiento.

En una fecha tan temprana como 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. El libro también intentó colocar los algoritmos genéticos sobre una base teórica firme introduciendo el concepto de esquema. Ese mismo año, la importante tesis de Kenneth De Jong estableció el potencial de los AGs demostrando que podían desenvolverse bien en una gran variedad de funciones de prueba, incluyendo paisajes de búsqueda ruidosos, discontinuos y multimodales.

Estos trabajos fundacionales establecieron un interés más generalizado en la computación evolutiva. Entre principios y mediados de los 80, los algoritmos genéticos se estaban aplicando en una amplia variedad de áreas, desde problemas matemáticos abstractos como el problema de la mochila (bin-packing) y la coloración de grafos hasta asuntos tangibles de ingeniería como el control de flujo en una línea de montaje, reconocimiento y clasificación de patrones y optimización estructural.

Al principio, estas aplicaciones eran principalmente teóricas. Sin embargo, al seguir proliferando la investigación, los algoritmos genéticos migraron hacia el sector comercial, al cobrar importancia con el crecimiento exponencial de la potencia de computación y el desarrollo de Internet. Hoy en día, la computación evolutiva es un campo floreciente, y los algoritmos genéticos están resolviendo problemas de interés cotidiano en áreas de estudio tan diversas como la predicción en la bolsa y la planificación de la cartera de valores, ingeniería aeroespacial, diseño de microchips, bioquímica y biología molecular, y diseño de horarios en aeropuertos y líneas de montaje. La potencia de la evolución ha tocado virtualmente cualquier campo que uno pueda nombrar, modelando invisiblemente el mundo que nos rodea de incontables maneras, y siguen descubriéndose nuevos usos mientras la investigación sigue su curso. Y en el corazón de todo esto se halla nada más que la simple y poderosa idea de Charles Darwin: que el azar en la variación, junto con la ley de selección, es una técnica de resolución de problemas de inmenso poder y de aplicación casi ilimitada.

Aunque a continuación veremos los Algoritmos Genéticos como máximos representantes de estas ideas, hay otros muchos ejemplos en los que se pueden utilizar las ideas de selección por supervivencia para conseguir optimizaciones de problemas. Basándose en la idea de que los más aptos sobreviven mejor a las situaciones del entorno, es posible crear simulaciones en las que los individuos están obligados a sobrevivir en un ambiente hostil, y solo aquellos con las condiciones más adecuadas para ese entorno serán capaces de durar el tiempo suficiente para reproducirse (sea sexual o asexualmente) y dejar descendencia en la que sus caracteres positivos den más opciones a los nuevos individuos, que junto con la mutación, puede producir una paulatina adpatación al medio. Tras este proceso durante generaciones, los individuos que queden reflejarán en sus características una solución (cuasi) óptima al problema de la supervivencia en el entorno.

¿Qué es un algoritmo genético?

Brevemente, un algoritmo genético (AG) es una técnica de resolución de problemas que imita a la evolución biológica como estrategia para resolver problemas, englobándose dentro de lo que antes hemos denominado técnicas basadas en poblaciones. Dado un problema específico a resolver, la entrada del AG es un conjunto de soluciones potenciales a ese problema, codificadas de alguna manera, y una métrica llamada función de aptitud, o fitness, que permite evaluar cuantitativamente a cada solución candidata. Estas candidatas pueden ser soluciones que ya se sabe que funcionan, con el objetivo de que el AG las mejore, pero se suelen generar aleatoriamente.

A partir de ahí, AG evalúa cada candidata de acuerdo con la función de aptitud. Por supuesto, se debe tener en cuenta que estas primeras candidatas generadas aleatoriamente, tendrán una eficiencia mínima con respecto a la resolución del problema, y la mayoría no funcionarán en absoluto. Sin embargo, por puro azar, unas pocas pueden ser prometedoras, pudiendo mostrar algunas características que muestren, aunque sólo sea de una froma débil e imperfecta, cierta capacidad de  solución del problema.

Estas candidatas prometedoras se conservan y se les permite reproducirse. Se realizan múltiples copias de ellas, pero estas copias no son perfectas, sino que se les introducen algunos cambios aleatorios durante el proceso de copia, a modo de las mutaciones que pueden sufrir los descendientes de una población. Luego, esta descendencia digital prosigue con la siguiente generación, formando un nuevo conjunto de soluciones candidatas, y son de nuevo sometidas a una ronda de evaluación de aptitud. Las candidatas que han empeorado o no han mejorado con los cambios en su código son eliminadas de nuevo; pero, de nuevo, 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. El proceso se repite las iteraciones que haga falta, hasta que obtengamos soluciones suficientemente buenas para nuestros propósitos.

El pseudocódigo asociado a este proceso podría ser:

AG:
  Crea población inicial
  Evalúa los cromosomas de la población inicial
  Repite hasta que se cumpla la condición de parada
      Selección de los cromosomas más aptos en la nueva población
      Cruzamiento de los cromosomas de la población
      Mutación de los cromosomas de la población
      Evaluación de los cromosomas de la población
  Devuele la mejor solución (la más apta) en la población

Aunque a algunos les puede parecer asombroso y antiintuitivo, los algoritmos genéticos han demostrado ser una estrategia enormemente poderosa y exitosa para resolver problemas, demostrando de manera espectacular el poder de los principios evolutivos. Se han utilizado algoritmos genéticos en una amplia variedad de campos para desarrollar soluciones a problemas tan o más difíciles que los abordados por los diseñadores humanos. Además, las soluciones que consiguen son a menudo más eficientes, más elegantes o más complejas que las que un humano produciría.

A continuación podemos ver algunos ejemplos de uso:

Métodos de representación

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 el propio algoritmo pueda procesarlas aplicando las operaciones que le permiten evolucionar. Un enfoque común es codificar las soluciones como cadenas binarias: secuencias de $1$'s y $0$'s, 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, de nuevo, 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 soluciones del problema. Esta técnica se utilizó, por ejemplo, en el trabajo de Steffen Schulze-Kremer, que escribió un algoritmo genético para predecir la estructura tridimensional de una proteína, basándose en la secuencia de aminoácidos que la componen.

El objetivo de cualquier método es que facilite la definición de operadores que causen los cambios aleatorios en las soluciones candidatas seleccionadas: cambiar un $0$ por un $1$ o viceversa, sumar o restar al valor de un número una cantidad elegida al azar, o cambiar una letra por otra.

Otra estrategia, desarrollada principalmente por John Koza, de la Universidad de Stanford, y denominada programación genética, representa a los programas como estructuras de datos ramificadas llamadas árboles. En este método, los cambios aleatorios pueden generarse cambiado el operador, alterando el valor de un cierto nodo del árbol, o sustituyendo un subárbol por otro.

Métodos de selección

Un algoritmo genético puede utilizar muchas técnicas diferentes para seleccionar a los individuos que deben copiarse hacia la siguiente generación. A continuación mostramos una breve explicación de los más habituales (debe tenerse en cuenta que algunos son mutuamente excluyentes, mientras que otros se pueden combinar):

• Selección elitista: se garantiza la selección de los miembros más aptos de cada generación. (La mayoría de los AGs no utilizan elitismo puro, sino una forma modificada por la que el individuo mejor, o algunos de los mejores, son copiados hacia la siguiente generación en caso de que no surja nada mejor).
• Selección proporcional a la aptitud: los individuos más aptos tienen más probabilidad de ser seleccionados, pero no la certeza.
• Selección por rueda de ruleta: una forma de selección proporcional a la aptitud en la que la probabilidad de que un individuo sea seleccionado es proporcional a la diferencia entre su aptitud y la de sus competidores.
• Selección escalada: al incrementarse la aptitud media de la población, la fuerza de la presión selectiva también aumenta y la función de aptitud se hace más discriminadora. Este método puede ser útil para seleccionar más tarde, cuando todos los individuos tengan una aptitud relativamente alta y sólo les distingan pequeñas diferencias en la aptitud.
• Selección por torneo: se eligen subgrupos de individuos de la población, y los miembros de cada subgrupo compiten entre ellos. Sólo se elige a un individuo de cada subgrupo para la reproducción.
• Selección por rango: a cada individuo de la población se le asigna un rango numérico basado en su aptitud, y la selección se basa en este ranking, en lugar de las diferencias absolutas en aptitud. La ventaja de este método es que puede evitar que individuos muy aptos ganen dominancia al principio a expensas de los menos aptos, lo que reduciría la diversidad genética de la población y podría obstaculizar la búsqueda de una solución aceptable.
• Selección generacional: la descendencia de los individuos seleccionados en cada generación se convierte en toda la siguiente generación. No se conservan individuos entre las generaciones.
• Selección jerárquica: los individuos atraviesan múltiples rondas de selección en cada generación. Las evaluaciones de los primeros niveles son más rápidas y menos discriminatorias, mientras que los que sobreviven hasta niveles más altos son evaluados más rigurosamente. La ventaja de este método es que reduce el tiempo total de cálculo al utilizar una evaluación más rápida y menos selectiva para eliminar a la mayoría de los individuos que se muestran poco o nada prometedores, y sometiendo a una evaluación de aptitud más rigurosa y computacionalmente más costosa sólo a los que sobreviven a esta prueba inicial.

Métodos de cambio

Una vez que la selección ha elegido a los individuos aptos, éstos deben ser alterados aleatoriamente con la esperanza de mejorar su aptitud para la siguiente generación. Existen dos estrategias básicas para realizar esta tarea:

1. La primera y más sencilla es la que se conoce como mutación. Al igual que una mutación en los seres vivos cambia un gen por otro, una mutación en un algoritmo genético también causa pequeñas alteraciones en puntos concretos de la codificación del individuo.
   
   
2. El segundo método se llama cruzamiento, y consiste en seleccionar a dos individuos para que intercambien segmentos de su código genético, produciendo una "descendencia" artificial cuyos individuos son combinaciones de sus padres. Este proceso pretende simular el proceso análogo de la recombinación que se da en los cromosomas durante la reproducción sexual. Las formas comunes de cruzamiento incluyen al cruzamiento de un punto, en el que se establece un punto de intercambio en un lugar aleatorio del genoma de los dos individuos, y uno de los individuos contribuye todo su código anterior a ese punto y el otro individuo contribuye todo su código a partir de ese punto para producir una descendencia, al cruzamiento en dos puntos, en el que se intercembian los genes que aparecen en el intervalo dee genes delimitados por dos puntos, y al cruzamiento uniforme, en el que el valor de una posición dada en el genoma de la descendencia corresponde al valor en esa posición del genoma de uno de los padres o al valor en esa posición del genoma del otro padre, elegido con un 50% de probabilidad.
   
   

Desventajas y limitaciones

A pesar de las bondades apuntadas anteriormente para este tipo de algoritmos, debemos mencionar algunas de las limitaciones que presentan:

• Como ocurre en muchos problemas de optimización, si tiene una alta complejidad entonces la función de evaluación puede resultar demasiado costosa en términos de tiempo y recursos.
• Hay casos en los que, dependiendo de los parámetros que se utilicen para la evaluación, el algoritmo puede no converger a una solución óptima, o bien terminar en una convergencia prematura con resultados no satisfactorios (es decir, devolviendo un óptimo local o incluso un punto arbitrario).
• No poseen una buena escalabilidad con la complejidad. En sistemas en los que intervienen muchas variables, componentes o elementos el espacio de búsqueda asociado puede crecer de manera exponencial debido, entre otras cosas, a las relaciones no lineales que puedan surgir entre los subconjuntos de variables.
• La mejor solución lo es solo en comparación a otras soluciones, por lo que no se tiene demasiado claro un criterio de cuándo detenerse ya que no se cuenta con una solución específica.
• No es recomendable utilizarlos para problemas que buscan respuesta a problemas con soluciones simples como Sí/No o problemas de decisión, ya que el algoritmo difícilmente convergerá y el resultado será casi aleatorio.
• El diseño de la función de aptitud (fitness) y la selección de los criterios de mutación entre otros, necesitan de cierta pericia y conocimiento previo del problema para obtener buenos resultados.