Portada original de la primera edición de “El origen de las especies”. Fuente: Wikimedia commons.
Hoy sabemos que el código genético de un individuo, el genotipo, formado por largas moléculas de ADN, contiene toda la información acerca de las características del individuo: función de las células, morfología, metabolismo, etc. Cuando dos individuos se cruzan, la descendencia de ambos tendrá como ADN una mezcla del ADN de ambos padres. Las mutaciones son el resultado de una copia imperfecta en una de las cadenas de ADN del hijo. De forma análoga, los algoritmos genéticos, que son un tipo de algoritmo evolutivo, usan cadenas de 0s y 1s, habitualmente llamadas cromosomas por analogía con el caso natural, que representan algún tipo de objeto dentro de un ordenador: la solución a un problema, un conjunto de valores numéricos, una imagen, un sonido o incluso una partitura, por poner algunos ejemplos.
Un algoritmo genético está formado por un conjunto de cadenas binarias (individuos) al cual se le llama población. Inicialmente la población está formada por cadenas binarias aleatorias. Seguidamente, algunas de estas cadenas son seleccionadas para realizar la operación de cruce, en la que dos cadenas intercambian parte de sus valores (también llamados genes). Después, un cambio aleatorio en algunos genes simula una mutación y, tras esto, el individuo es evaluado para comprobar si es apto en su hábitat. ¿Qué significa ser apto en este caso? Normalmente se asigna un valor numérico al individuo usando alguna función matemática y este valor representa la aptitud del individuo. Cuanto mayor es el valor mayores son las probabilidades de sobrevivir e incorporarse en la siguiente generación de la población. Este proceso se repite continuamente hasta el momento en que el usuario del algoritmo decida parar.
Ejemplos de operadores de cruce y mutación para el caso de individuos binarios. Fuente: el autor.
¿Por qué podríamos estar interesados en simular dentro de un ordenador la evolución de especies? Una interesante característica de los algoritmos evolutivos es que, debido a su naturaleza aleatoria, el resultado que se obtiene tras cada ejecución del mismo puede ser diferente. El algoritmo puede sorprender al usuario con distintas poblaciones de individuos al final. Imaginemos que los individuos representan una imagen. En ese caso, obtendremos distintas imágenes cada vez que ejecutemos el algoritmo y si la función que calcula la aptitud del individuo está especialmente diseñada para puntuar más alto imágenes con gran valor estético para un humano podríamos conseguir que el algoritmo ofrezca bellas imágenes tras su ejecución.
Imagen generada con un algoritmo evolutivo. Fuente: Wikipedia.
El uso de los algoritmos evolutivos para crear obras de arte se conoce con el nombre de arte evolutivo y existen congresos internacionales especializados en esta forma de arte [1]. Un caso particular, es el de la música compuesta por ordenador usando algoritmos evolutivos. Aunque este tópico no es nuevo, recientemente ha llamado especialmente la atención de los músicos el sistema Iamus [2], desarrollado en el departamento de Lenguajes y Ciencias de la Computación de la Universidad de Málaga con Francisco J. Vico a la cabeza. La función de aptitud de Iamus tiene en cuenta aspectos formales de la partitura y es capaz de generar una composición completa en cuestión de minutos. Para conseguir una partitura en tan poco tiempo es necesario diseñar muy bien los operadores de cruce y mutación, uno de los secretos mejor guardados de Iamus. El sistema ha merecido un artículo en la prestigiosa revista Nature [3] y la revista norteamericana Discover lo ha incluido en el TOP 100 de novedades científicas del año 2012. Se ha comercializado un CD con 10 composiciones de Iamus, donde participa la Orquesta Sinfónica de Londres, y, recientemente, una de sus obras fue estrenada por la Orquesta Filarmónica de Málaga en el XIX Ciclo de Música Contemporánea de la ciudad.
La creación artística no es la única aplicación de los algoritmos evolutivos. Éstos pueden utilizarse para resolver problemas de optimización, es decir, encontrar soluciones de muy buena calidad para problemas difíciles de resolver. Un ejemplo de problema de optimización es el de colocar paquetes en un camión de forma que quepa el mayor número posible. No se conoce ningún algoritmo que sea capaz de dar la mejor solución en un tiempo razonable. Los algoritmos conocidos que dan la mejor solución requieren, en el peor de los casos, un tiempo que crece exponencialmente con el tamaño del problema (número de paquetes a colocar). Para resolver un problema como este usando algoritmo evolutivos, tan solo es necesario codificar las soluciones de manera que el ordenador las entienda y programar la función de aptitud, que en este caso podría ser el número de paquetes que caben en la forma indicada por la solución. La principal ventaja del uso de estos algoritmos en optimización es la facilidad con la que pueden aplicarse a la resolución del problema. No es necesario tener un conocimiento profundo del problema para resolverlo, basta con saber evaluar la calidad de las soluciones. Por otro lado, los resultados experimentales con algoritmos evolutivos ponen de manifiesto que las soluciones obtenidas por éstos son, en muchos casos de relevancia práctica, óptimas o se encuentran cercanas al óptimo, mientras que el tiempo requerido para obtener dichas soluciones es reducido (del orden de minutos o segundos).
El uso de algoritmos evolutivos para resolver problemas de optimización ha recibido una importante atención en las últimas décadas y actualmente se pueden contar por decenas los congresos especializados en este tema y las revistas que publican artículos relacionados. En el mencionado departamento de la UMA, profesores como Enrique Alba y Carlos Cotta llevan investigando desde hace casi 20 años el potencial de los algoritmos evolutivos para resolver problemas de optimización. Entre los problemas resueltos por estos investigadores encontramos la optimización de los semáforos para reducir el tiempo de espera de los conductores en una ciudad, la asignación de frecuencias de radio a antenas en una red de telefonía celular, la generación automática de casos de prueba para programas de ordenador, etc [4]. Todos ellos problemas complejos en los que, generalmente, es difícil predecir la influencia de un cambio de la solución en su calidad.
Haciendo uso de algoritmos evolutivos es posible reducir el tráfico de una ciudad. Fuente: wikimedia commons.
La computación evolutiva no es el único dominio de la Informática que se ha nutrido de ideas de la naturaleza. En 1983, Kirkpatrick, Gelatt y Vecchi propusieron un algoritmo para resolver problemas de optimización que se basa en el enfriamiento de un metal [5]. Más tarde, en 1992, Dorigo describía en su tesis doctoral una familia de algoritmos que se inspiraba en la forma en que las hormigas buscan comida [6]. Kennedy y Eberhart desarrollaron en 1995 un algoritmo que basaba su funcionamiento en el comportamiento de los pájaros y los peces [7]. Estos dos últimos algoritmos se integran en la actualidad dentro de la línea de investigación conocida como Inteligencia de Enjambre (Swarm Intelligence) que ha servido de inspiración para crear novelas como “Presa”, de Michael Crichton.
El proyecto swarmanoid, coordinado por Marco
Dorigo, explora el uso de la inteligencia de enjambre para coordinar un
conjunto de robots heterogéneos. Fuente: www.swarmanoid.com
Difícilmente podía Darwin imaginar que sus ideas, con las que pretendía explicar la evolución de las especies, servirían, siglo y medio más tarde, para deleitar al público que acude a un concierto o agilizar el tráfico de una ciudad.
Referencias:
[1] Página Web de la edición de 2013 de EvoMUSART, congreso centrado en la música y el arte evolutivo. http://www.kevinsim.co.uk/evostar2013/cfpEvoMUSART.html
[2] Página Web de Iamus. http://melomics.com/iamus
[3] Artículo de Philipp Ball en Nature sobre Iamus. http://www.nature.com/nature/journal/v488/n7412/full/488458a.html?WT.ec_id=NATURE-20120823
[4] Páginas Web del grupo NEO. http://neo.lcc.uma.es
[5] S. Kirkpatrick, C. D. Gelatt y M. P. Vecchi. 1983. Optimization by simulated annealing. Science, 13 May 1983 220, 4598, 671–680.
[6] M. Dorigo. 1992. Optimization, learning and natural algorithms. Ph.D. thesis, DEI, Politecnico di Milano, Italy.
[7] J. Kennedy y R. Eberhart. 1995. Particle swarm optimization, Proceedings of the IEEE International Conference on Neural Networks, vol.4, pp. 1942-1948.
Tomado de:
Año Turing