Algoritmo genético

¿Qué es?

La evolución natural puede modelarse como un juego, en el que las recompensas para un organismo que juega bien a la vida son la transmisión de su material genético a sus sucesores y su supervivencia continuada.^[2] En la evolución natural, el rendimiento de un individuo depende de con quién trabaja y con quién compite, así como del entorno. Los algoritmos genéticos son una simulación de la selección natural sobre una población de soluciones candidatas a un problema de optimización (cromosomas, individuos, criaturas o fenotipos).

Los candidatos se evalúan y se cruzan en un intento de hacer buenas soluciones. Estas soluciones pueden llevar mucho tiempo y no son obvias para un humano. Una fase evolutiva se inicia con una población de seres generados al azar. En cada generación, se evalúa la aptitud de cada individuo de la población. Algunos se seleccionan al azar de la población actual (en función de su aptitud) y se modifican (se recombinan y posiblemente mutan al azar) para formar una nueva población. El ciclo se repite con esta nueva población. El algoritmo finaliza cuando ha pasado un número determinado de generaciones o cuando se ha alcanzado un buen nivel de aptitud para la población. Si el algoritmo ha finalizado por haber alcanzado un número máximo de generaciones, no significa necesariamente que se haya obtenido un buen nivel de aptitud.

Programar esto en un ordenador

El pseudocódigo es:

1. Inicialización: Se crean algunas soluciones posibles; muy a menudo éstas tendrán valores aleatorios
2. Evaluación: Una función de aptitud puntúa cada solución; la puntuación será un número que indica lo bien que esta solución resuelve el problema.
3. Los siguientes pasos se ejecutan hasta que se cumple el requisito de parar:
1. Selección: Elegir las soluciones/individuos para la siguiente iteración
2. Recombinación: Combinar las soluciones elegidas
3. Mutación: Cambia aleatoriamente las soluciones recién creadas
4. Evaluación: Aplicar la función de aptitud, ver paso 2.
5. Si no se cumple el requisito de parar, vuelva a empezar con el paso de selección.

Ejemplo

La descripción anterior es abstracta. Un ejemplo concreto ayuda.

Aplicaciones

En general

Los algoritmos genéticos son buenos para resolver problemas como la planificación de horarios y la programación. También se han aplicado a la ingeniería. Suelen utilizarse para resolver problemas de optimización global.

Como regla general, los algoritmos genéticos pueden ser útiles en dominios de problemas que tienen un paisaje de aptitud complejo, ya que la mezcla está diseñada para alejar a la población de los óptimos locales en los que un algoritmo tradicional de escalada de colinas podría quedarse atascado. Los operadores de cruce comúnmente utilizados no pueden cambiar ninguna población uniforme. La mutación por sí sola puede proporcionar ergodicidad al proceso global del algoritmo genético (visto como una cadena de Markov).

Algunos ejemplos de problemas resueltos por algoritmos genéticos son: espejos diseñados para canalizar la luz del sol hacia un colector solar, antenas diseñadas para captar señales de radio en el espacio, métodos para caminar con figuras de ordenador, diseño óptimo de cuerpos aerodinámicos en campos de flujo complejos

En su Manual de Diseño de Algoritmos, Skiena desaconseja los algoritmos genéticos para cualquier tarea: "Es bastante antinatural modelar las aplicaciones en términos de operadores genéticos como la mutación y el cruce en cadenas de bits. La pseudobiología añade otro nivel de complejidad entre usted y su problema. En segundo lugar, los algoritmos genéticos tardan mucho tiempo en problemas no triviales. [...] La analogía con la evolución -donde un progreso significativo requiere [sic] millones de años- puede ser muy apropiada. [...] Nunca me he encontrado con ningún problema en el que los algoritmos genéticos me parecieran la forma correcta de atacarlo. Además, nunca he visto ningún resultado computacional que se haya comunicado utilizando algoritmos genéticos que me haya impresionado favorablemente. Limítate al recocido simulado para tus necesidades de vudú de búsqueda heurística".

Juegos de mesa

Los juegos de mesa son una parte muy relevante del área de los algoritmos genéticos aplicados a los problemas de la teoría de juegos. Gran parte de los primeros trabajos sobre inteligencia computacional y juegos se dirigieron a los juegos de mesa clásicos, como el tres en raya^[3] el ajedrez y las damas.^[4] En la actualidad, en la mayoría de los casos, los juegos de mesa pueden ser jugados por un ordenador a un nivel superior al de los mejores humanos, incluso con técnicas de búsqueda exhaustiva a ciegas. El Go es una notable excepción a esta tendencia, y hasta ahora ha resistido el ataque de las máquinas. Los mejores jugadores de Go por ordenador juegan ahora al nivel de un buen novato.^[5][6] Se dice que la estrategia del Go se basa en gran medida en el reconocimiento de patrones, y no sólo en el análisis lógico como en el ajedrez y otros juegos más independientes de las piezas. El enorme factor de bifurcación efectivo que se requiere para encontrar soluciones de alta calidad restringe en gran medida el tiempo de espera que se puede utilizar dentro de una búsqueda de secuencias de movimientos.

Juegos de ordenador

El algoritmo genético puede utilizarse en los juegos de ordenador para crear inteligencia artificial (el ordenador juega contra ti). Esto permite una experiencia de juego más realista; si un jugador humano puede encontrar una secuencia de pasos que siempre conducen al éxito, incluso cuando se repiten en diferentes juegos, no puede quedar ningún desafío. Por el contrario, si una técnica de aprendizaje, como un algoritmo genético para un estratega, puede evitar la repetición de errores pasados, el juego tendrá más rejugabilidad.

Los algoritmos genéticos requieren las siguientes partes:

• Un método para representar el desafío en términos de la solución (por ejemplo, el enrutamiento de los soldados en un ataque en un juego de estrategia)
• Una función de aptitud o de evaluación para determinar la calidad de una instancia (por ejemplo, una medida del daño causado a un oponente en un ataque de este tipo).

La función de aptitud acepta una instanciación mutada de una entidad y mide su calidad. Esta función se adapta al dominio del problema. En muchos casos, en particular los que implican la optimización del código, la función de aptitud puede ser simplemente una función de sincronización del sistema. Una vez que se definen una representación genética y una función de aptitud, un algoritmo genético instanciará candidatos iniciales como se ha descrito anteriormente, y luego los mejorará mediante la aplicación repetitiva de operadores de mutación, cruce, inversión y selección (según se defina en función del dominio del problema).

Limitaciones

El uso de un algoritmo genético tiene limitaciones en comparación con otros algoritmos de optimización:

• La evaluación repetida de la función de aptitud para problemas complejos suele ser el segmento más limitante de los algoritmos evolutivos artificiales. Encontrar la solución óptima a problemas complejos suele requerir evaluaciones de funciones de aptitud muy costosas. En problemas del mundo real, como los de optimización estructural, una sola evaluación de la función puede requerir de varias horas a varios días de simulación completa. Los métodos típicos de optimización no pueden hacer frente a este tipo de problemas. A menudo es necesario utilizar la aproximación, ya que el cálculo de la solución exacta lleva demasiado tiempo. Los algoritmos genéticos combinan a veces diferentes modelos de aproximación para resolver problemas complejos de la vida real.
• Los algoritmos genéticos no se escalan bien. Es decir, cuando el número de elementos que se exponen a la mutación es grande, suele haber un aumento exponencial del tamaño del espacio de búsqueda. Esto dificulta enormemente el uso de la técnica en problemas como el diseño de un motor, una casa o un avión. Para utilizar los algoritmos genéticos con este tipo de problemas, hay que descomponerlos en una representación lo más sencilla posible. Por esta razón, vemos que los algoritmos evolutivos codifican diseños de aspas de ventilador en lugar de motores, formas de edificios en lugar de planos detallados de construcción y perfiles aéreos en lugar de diseños completos de aviones. El segundo problema de complejidad es la cuestión de cómo proteger las partes que han evolucionado para representar buenas soluciones de nuevas mutaciones destructivas, especialmente cuando su evaluación de la aptitud requiere que se combinen bien con otras partes.
• La solución "mejor" es sólo en comparación con otras soluciones. En consecuencia, el criterio de parada no está claro en todos los problemas.
• En muchos problemas, los algoritmos genéticos tienen tendencia a converger hacia los óptimos locales o incluso hacia puntos arbitrarios en lugar de hacia el óptimo global del problema. Esto significa que el algoritmo no "sabe" sacrificar la aptitud a corto plazo para ganar aptitud a largo plazo. La probabilidad de que esto ocurra depende de la forma de la función de aptitud: ciertos problemas facilitan la búsqueda del óptimo global, mientras que otros pueden facilitar que la función encuentre los óptimos locales. Este problema puede reducirse utilizando una función de aptitud diferente, aumentando la tasa de mutación o utilizando técnicas de selección que mantengan una población diversa de soluciones. Una técnica común para mantener la diversidad es utilizar una "penalización de nicho": a cualquier grupo de individuos de suficiente similitud (radio de nicho) se le añade una penalización, que reducirá la representación de ese grupo en las siguientes generaciones, permitiendo que otros individuos (menos similares) se mantengan en la población. Este truco, sin embargo, puede no ser eficaz, dependiendo del paisaje del problema. Otra técnica posible sería simplemente sustituir parte de la población por individuos generados aleatoriamente, cuando la mayor parte de la población es demasiado similar entre sí. La diversidad es importante en los algoritmos genéticos (y en la programación genética) porque el cruce de una población homogénea no produce nuevas soluciones. En las estrategias de evolución y la programación evolutiva, la diversidad no es esencial porque se depende más de la mutación.
• Operar con conjuntos de datos dinámicos es difícil, ya que los genomas empiezan a converger pronto hacia soluciones que pueden dejar de ser válidas para datos posteriores. Se han propuesto varios métodos para arreglar esto aumentando la diversidad genética de alguna manera y evitando la convergencia temprana, ya sea aumentando la probabilidad de mutación cuando la calidad de la solución cae (lo que se llama hipermutación desencadenada), o introduciendo ocasionalmente elementos totalmente nuevos, generados al azar, en el acervo genético (lo que se llama inmigrantes aleatorios). De nuevo, las estrategias de evolución y la programación evolutiva pueden implementarse con la llamada "estrategia de coma", en la que los padres no se mantienen y los nuevos padres se seleccionan sólo a partir de la descendencia. Esto puede ser más eficaz en los problemas dinámicos.
• Los algoritmos genéticos no pueden resolver eficazmente los problemas en los que la única medida de aptitud es una única medida de acierto/error (como los problemas de decisión), ya que no hay forma de converger en la solución (no hay colina que escalar). En estos casos, una búsqueda aleatoria puede encontrar una solución tan rápidamente como un AG. Sin embargo, si la situación permite que el ensayo de éxito/fracaso se repita dando (posiblemente) resultados diferentes, entonces la proporción de éxitos y fracasos proporciona una medida de aptitud adecuada.
• Para problemas de optimización e instancias de problemas específicos, otros algoritmos de optimización pueden ser más eficientes que los algoritmos genéticos en términos de velocidad de convergencia. Entre los algoritmos alternativos y complementarios se encuentran las estrategias de evolución, la programación evolutiva, el recocido simulado, la adaptación gaussiana, la escalada de colinas y la inteligencia de enjambre (por ejemplo: optimización de colonias de hormigas, optimización de enjambre de partículas) y los métodos basados en la programación lineal entera. La idoneidad de los algoritmos genéticos depende del grado de conocimiento del problema; los problemas bien conocidos suelen tener enfoques mejores y más especializados.

Historia

En 1950, Alan Turing propuso una "máquina de aprendizaje" que fuera paralela a los principios de la evolución. La simulación de la evolución por ordenador comenzó ya en 1954 con los trabajos de Nils Aall Barricelli, que utilizaba el ordenador en el Instituto de Estudios Avanzados de Princeton (Nueva Jersey). Su publicación de 1954 no tuvo mucha repercusión. A partir de 1957, el genetista cuantitativo australiano Alex Fraser publicó una serie de trabajos sobre la simulación de la selección artificial de organismos con múltiples loci que controlan un rasgo medible. A partir de estos inicios, la simulación informática de la evolución por parte de los biólogos se hizo más común a principios de la década de 1960, y los métodos se describieron en los libros de Fraser y Burnell (1970) y Crosby (1973). Las simulaciones de Fraser incluían todos los elementos esenciales de los algoritmos genéticos modernos. Además, Hans-Joachim Bremermann publicó una serie de trabajos en la década de 1960 que también adoptaban una población de solución de problemas de optimización, sometida a recombinación, mutación y selección. La investigación de Bremermann también incluía los elementos de los algoritmos genéticos modernos. Otros pioneros dignos de mención son Richard Friedberg, George Friedman y Michael Conrad. Fogel (1998) recoge muchos de los primeros trabajos.

Aunque Barricelli, en un trabajo del que informó en 1963, había simulado la evolución de la habilidad para jugar a un juego sencillo, la evolución artificial se convirtió en un método de optimización ampliamente reconocido a raíz de los trabajos de Ingo Rechenberg y Hans-Paul Schwefel en los años sesenta y principios de los setenta: el grupo de Rechenberg fue capaz de resolver problemas complejos de ingeniería mediante estrategias de evolución. Otro enfoque fue la técnica de programación evolutiva de Lawrence J. Fogel, propuesta para generar inteligencia artificial. La programación evolutiva utilizaba originalmente máquinas de estado finito para predecir entornos, y empleaba la variación y la selección para optimizar las lógicas de predicción. Los algoritmos genéticos, en particular, se hicieron populares gracias al trabajo de John Holland a principios de los años 70, y en particular a su libro Adaptation in Natural and Artificial Systems (1975). Su trabajo se originó en los estudios sobre autómatas celulares, realizados por Holland y sus estudiantes en la Universidad de Michigan. Holland introdujo un marco formalizado para predecir la calidad de la siguiente generación, conocido como teorema del esquema deHolland. La investigación sobre los AGs siguió siendo en gran medida teórica hasta mediados de los años 80, cuando se celebró la Primera Conferencia Internacional sobre Algoritmos Genéticos en Pittsburgh, Pennsylvania.