jueves, 23 de abril de 2015

¿Qué es la computación evolutiva?


En esta entrada, que ya aviso que será un poco técnica, voy a intentar acercaros la base de lo que es una magnífica herramienta para la resolución de problemas de diversa índole. Me refiero, como no, a la computación evolutiva: la rama de la computación que hace uso del mismo proceso que la naturaleza ha seguido para conseguir fenómenos asombrosos que de otro modo serían totalmente inviables de alcanzar en un tiempo razonable. Por cierto, que gran parte de la moderna inteligencia artificial se basa en este precepto.

Introducción

Entendemos por un algoritmo evolutivo, aquel cuya técnica resolutiva se inspira en la evolución biológica de la naturaleza; imitando de esa manera, el proceso de selección natural que, desde Darwin, es aceptado como el principal motor del proceso evolutivo de los seres vivos.
Existe en la red abundante información teórica al respecto de la computación evolutiva, pero en muy pocos casos me he encontrado con ejemplos prácticos concretos, donde se pongan en práctica dichos principios.

De manera que me he propuesto intentar poner mi granito de arena práctico en esta rama tan interesante de la inteligencia artificial para ayudar así a cualquiera que quiera adentrarse en la materia.

Composición y funcionamiento de un algoritmo evolutivo (AE)

Sin duda, el mejor recurso bibliográfico para iniciarse en el mundo de la CE -compuactión evolutiva- es el magnífico libro Introduction to Evolutionary Computing, de los autores Agoston E. Eiben, y J.E. Smith.

Hemos dicho que la computación evolutiva es una ciencia computacional en la que sus algoritmos imitan el proceso evolutivo de la naturaleza. Veamos de qué partes consta, y cómo funcionan:

Cualquier AE seguirá el siguiente pseudocódigo:



Existe una población de n individuos, los cuales expresan una posible solución. La población es pues, un multiconjunto de genotipos, y forman la unidad de evolución.

Los individuos de la población se van renovando en sucesivas generaciones, que van convergiendo evolutivamente hacia la meta deseada, que no es otra que encontrar una solución a un problema determinado. La evolución se produce durante el paso de las generaciones, y cada generación cumple con el siguiente procedimiento:

La primera generación es especial, y sólo consiste en la generación (y evaluación) de una población inicial de n individuos, normalmente generados aleatoriamente.

El resto de generaciones comienzan con la selección de los individuos que se van a reproducir. Es decir, se seleccionan los padres que conformarán la descendencia.
Y dicha descendencia, será el resultado de un proceso de recombinación y mutación de esos padres previamente seleccionados. Tras la creación de la descendencia, se procede a evaluar su adaptabilidad. Es decir; se calcula, lo bien o mal que se adapta el nuevo individuo a las condiciones del medio ambiente. Este proceso se suele realizar, mediante el uso de una funcion de desempeño (fitness function). Dicha función representará la adaptabilidad del fenotivo expresado por el genotipo en cuestión. Una vez evaluada la progenie, se procede a seleccionar los individuos que finalmente prevalecerán para formar la siguiente generación.

Todo este proceso generacional, se repetirá mientras no se cumpla una condición de parada. La condición de parada normalmente será, o bien que uno o varios genomas expresan un fenotipo que es solución óptima del problema a resolver, o que se alcanzó el máximo de generaciones previstos programáticamente.

A continuación tenéis el programa con el que pondremos en práctica estas ideas. Podéis trastear un poco con él, y más tarde estudiar la explicación técnica del mismo:

Ejemplo VIII:

Podéis descargar el código fuente del ejemplo desde este enlace.

El algoritmo está escrito completamente en Javascript, utilizando hilos mediante la nueva clase Worker nativa de HTML5 (puedes descargar el código fuente desde el enlace de arriba):

Manual de uso

Mediante el algoritmo del ejemplo, vamos a intentar encontrar la solución óptima -si existe-, o la mejor aproximación posible, al siguiente problema:

Tenemos como entrada (inputs), una serie de puntos definidos para ciertos valores de una variable, y queremos buscar la función de interpolación que sea óptima -que pase por todos los puntos dados como entrada- o lo más aproximada posible.

Para introducir los inputs en el programa, debemos rellenar el campo de texto "Datos de interpolación", añadiendo cuantos puntos deseemos. Una entrada válida sería, por ejemplo:

{"x": 0} = 0;{"x": 1} = 3; {"x": 2} = 5.4142;{"x": 3} = 7.732;error_max = 0.001

Si ahora, pulsamos sobre el botón Ejecutar el proceso evolutivo, el programa se iniciará, buscando una de las muchas funciones que interpolan esos puntos, por ejemplo:

f(x) = 2*x + sqrt(x)

Para recalcar la potencia del proceso evolutivo por selección, se propone la posibilidad de intentar encontrar la solución, sin realizar la recombinación, mutación y selección de los más aptos, lo que resulta en un algoritmo completamente aleatorio que muy poco probablemente llegará a solucionar el problema.

Es importante señalar, que sólo se permite los operadores + - * /^, y que la prioridad de los mismos es la tradicional. Se permiten números con decimales (con el punto como separador, y una precisión máxima de cuatro decimales).

Al finalizar la ejecución del algoritmo, aparecerá una nueva zona en la aplicación con un par de gráficas, la primera representando los puntos de interpolación, y una segunda con los puntos representados por la función encontrada por el programa. Ambas gráficas coincidirán siempre y cuando se encuentre una solución óptima -si es que existe-.

Análisis del algoritmo

La representación del genotipo en nuestro ejemplo, consiste en un array de caracteres, conformando una cadena de texto, con los siguientes símbolos permitidos:{[0-9],x,+,-,/,*,^,sin,cos,sqrt,log}

Además, los símbolos deben respetar un patrón que forme cadenas con sentido aritmético (pero no se permite usar el símbolo - como operador unitario), permitiéndose genotipos como 2*x*x-1/2*x+23, pero no otros como 2+-x/*.

El AE del ejemplo responde al siguiente pseudocódigo:


t <- 0
Inicialización P(t)
Evaluación P(t)
hacer
S <- Seleccion_padres[P(t)]
Q = Operacion_variación[S]
Evaluación[Q)]
P(t+1) <- selección[P(t) U Q]
t <- t + 1
mientras no condición de parada



donde S, Q, y P son poblaciones de individuos, y t es una variable de tipo entera.

El algoritmo comienza creando aleatoriamente una población P de n individuos, y evaluando la función de desempeño de sus individuos -lo cerca o lejos que están de ser una solución óptima al problema-.

Posteriormente se entra en un bucle del que sólo se saldrá cuando se cumpla que, o bien en la población P(t) hay un individuo que es solución óptima, o bien se ha llegado al máximo de iteraciones previsto en la configuración del programa.

Cada iteración del bucle, se va a corresponder con una nueva generación de individuos, formada por parte de los padres de la generación anterior y por parte de su progenie.

Para realizar una generación se procede como sigue:

1) Se forma una población S con los individuos que van a poder procrear. En el caso concreto de mi ejemplo, todos los miembros de la población P van a tener descendencia. Es decir; S = P(t).

2) Se procede a crear la descendencia mediante recombinación, y mutación. En el ejemplo, se van seleccionando pares de individuos de S y se recombinan dando lugar a cuatro hijos.

Para recombinar, seleccionamos al padre y lo dividimos por un punto aleatorio p (quedando el padre partido en dos partes: padre1 y padre2). Hacemos lo mismo con la madre en un punto p', y se crean los hijos de la siguiente manera:

h1 = padre1 + madre2
h2 = madre1 + padre2
h3 = padre1
h4 = padre2


Posteriormente, cada hijo, sufrirá -con 100% de probabilidad- algún tipo de mutación puntual, que podrá ser más o menos leve, y que podrá modificar algún valor concreto del genotipo del individuo, o añadir o eliminar partes del mismo.

El proceso de reproducción, se repetirá 16 veces por cada par de padres, lo que dará un total de n*16*4 hijos en cada generación -siendo n el número de individuos en la población-.

3) El siguiente paso es evaluar la adaptabilidad de esta población Q que conforman la nueva descendencia.

4) Por último, se procede a seleccionar aquellos individuos que mejor se adaptan al medio de la unión del conjunto de padres de la generación anterior P(t) y el conjunto de sus hijos Q. Como resultado, se obtiene el conjunto P de la generación siguiente, con los supervivientes del proceso de selección.

En nuestro ejemplo, la evaluación de un genotipo se procesa mediante la aplicación de una función de desempeño (fitness function) al mismo. En este caso, la función será el resultado de sumar la diferencia en valor absoluto entre g(x) y el input en dicho punto: abs(y-g(x)).

Un genotipo óptimo, será aquel cuya función de desempeño tenga valor 0.

Para el AE del ejemplo, la selección generacional, se hace ordenando los individuos de [P(t) U Q] según su valor de adaptación -cuanto menos diferencia entre g(x) y los puntos de interpolación mejor- y seleccionando los s primeros, desechándose de esa manera el resto.

Resumen

El algoritmo evolutivo propuesto es capaz de encontrar; si existe, una solución óptima al problema con bastante frecuencia, aunque; como en todo AE existe la posibilidad de que la evolución generacional se localice en torno a una solución local no óptima -pero muy cercana de serlo-. Sin embargo, la aleatoriedad de la fase de mutación, permite teóricamente recomenzar un nuevo camino evolutivo en cualquier momento -aunque es menos probable que esto ocurra conforme pasan las generaciones-.


No hay comentarios:

Publicar un comentario en la entrada