El principal objetivo de las ciencias de la complejidad es el desarrollo de herramientas matemáticas y de cómputo que conlleven un conocimiento interdisciplinario, esto es, que sus resultados puedan ser aplicados a distintas áreas del conocimiento.
Un algoritmo es un conjunto de instrucciones o reglas definidas y no ambiguas que permitan solucionar un problema, realizar un cálculo, procesar datos o llevar a cabo otras tareas o actividades. Dentro de la amplísima variedad de tipos de algoritmos en la búsqueda de soluciones a problemas concretos, destacan los algoritmos genéticos (AG) así llamados porque se inspiran en la evolución biológica y su base genético-molecular.
Para encontrar una solución a ciertos problemas, estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), para seleccionar los mejores de acuerdo a un criterio establecido.
Para esta unidad hay un modelo de NetLogo, RobbyGA, que puede descargarse aquí. Pero es aconsejable usarlo una vez que se haya visto todo el contenido de esta unidad. (Mi transcripción de este modelos es N05.- RobbyGA)
Introducción a los algoritmos genéticos
5.1.- ETAPAS EN LOS ALGORITMOS GENÉTICOS
En el proceso de creación de estos algoritmos genéticos se introducen los conceptos ‘estrategia‘ y ‘población‘ que son fundamentales en estos modelos. Más adelante, al inicializar la población, se introduce el concepto nuclear de los algoritmos genéticos, ‘fitness’, que significa la adecuación de los individuos a los objetivos marcados al establecer el modelo.
5.2.- EL MODELO DEL MUNDO DE ROBBY
El modelo del mundo de Robby es un algoritmo genético simple que permite evolucionar programas de control de robots virtuales. Está inspirado en un robot real llamado Herbert que funcionó en los años 80′ en el Laboratorio de Inteligencia Artificial del M.I.T.
Fue un trabajo de Jonathan Connell, un estudiante de grado del M.I.T. que trabajaba con Rodney Brooks y Peter Ning. Jonathan usaba unos algoritmos muy simples para controlar su comportamiento, que era ir sobre sus ruedas por el laboratorio visitando distintas oficinas y recogiendo latas de refresco vacías llevándolas a los contenedores de reciclado. Nuestro Robby, a diferencia de Helbert, vive en un mundo virtual:
5.3.- DEFINICIÓN DE LA ESTRATEGIA
Si el objetivo es usar un algoritmo genético para optimizar el modelo del robot virtual, es necesario definir una estrategia que es un conjunto de reglas que especifican una acción para cada situación posible.
En general para crear una estrategia hay que conocer las situaciones en la que puedan ocurrir determinadas acciones. Una vez que se tiene este conocimiento, se crea una relación situación-acción que abarque todas ellas.
Para establecer esta relación en el mundo de Robby, se define un entorno, desde su posición actual, que son los cuatro puntos cardinales y en cada uno de ellos, incluida su posición actual, se definen tres posibilidades de acción. En resumen cada una de las posibles 243 relaciones situación-acción da lugar a una estrategia:
5.4.- DEFINICIÓN DE LA POBLACIÓN
Para establecer la población, hay enumerar de alguna forma las estrategias, (243 en el mundo de Robby) y usar alguna codificación que permita, posteriormente, la aplicación de los criterios biológicos propios de estos algoritmos (los procesos de recombinación y mutación). Es decir hay que disponer de una población lo suficientemente numerosa para tomar un pequeño conjunto representativo y hacerlo evolucionar hacia una solución. En el caso de Robby la población, donde una estrategia una :
5.5.- PROCESO DE INICIALIZACIÓN: CONCEPTO DE FITNESS
En la descripción de las etapas del algoritmo genético se mostró que, una vez definida la población, se ejecuta por primera vez -se inicializa- el algoritmo. Ya en esta operación se debe evaluar a los individuos que se han tratado para obtener una medida de su calidad, lo que se conoce como su fitness.
En el mundo de Robby, tal evaluación consiste en cuantificar las acciones que realiza. En general, la secuencia de acciones de una estrategia concreta, que recordemos, identifica a un individuo, debe ser valorada de forma cuantitativa para obtener su fitness.
Una vez definidos los pasos previos, (modelo, estrategias y población) se puede iniciar el procedimiento del algoritmo. El objetivo de este procedimiento es obtener el valor del fitness para cada individuo de la población seccionada. Para ello se somete a cada individuo (a cada estrategia) a una serie de ensayos en diferentes entornos. El valor del fitness puede ser, entre otros, el promedio de puntuaciones obtenidas en cada ensayo.
5.6.- PROCESO DE CREACIÓN DE DESCENDENCIA
Una vez que la población inicial está caracterizada por su fitness, se ejecuta un proceso cíclico de creación de descendencia. Cada ciclo tiene tres subprocesos: selección de parejas, recombinación y mutación. Con ello se consigue una nueva generación que debe ser, de nuevo, evaluada:
El proceso de creación de descendencia se repite hasta tener tantos descendientes como población se haya fijado en las condiciones iniciales. Una vez alcanzado el número de descendientes se eliminan todos los antecesores y los descendientes pasan a ser los antecesores de una nueva generación.
El proceso se repite hasta alcanzar un número especificado de generaciones o bien hasta que se alcance un valor predeterminado de fitness o hasta que este valor no varíe en sucesivas generaciones. En particular, en el mundo de Robby, si en cada ambiente hay 50 latas distribuidas en los 100 retículos y el premio por recoger una lata es de 10 puntos, la máxima puntuación posible es de 500 puntos.
Referencias y lecturas complementarias
1.- Artículo «Algoritmo genético«.
