viernes, 24 de abril de 2015

Una aplicación útil para la computación evolutiva

Cómo vimos en mi anterior artículo, la computación evolutiva tiene un enorme potencial que, en mi opinión, aún no ha sido suficientemente explotado. Y aunque es cierto que se utiliza con frecuencia para aplicaciones dentro de la inteligencia artificial, su uso podría llegar a ámbitos mucho más diversos. Me gustaría, por lo tanto, aprovechar esta entrada (ahora que ya tenemos una idea de lo que es la computación evolutiva), para mostraros un simple ejemplo práctico que demuestre la gran utilidad que este tipo de procesos computacionales puede tener:

Buscando patrones útiles.

Como ya vimos un ejemplo práctico de computación evolutiva y explicamos su funcionamiento interno, vamos a intentar darle una utilidad práctica a dicho ejemplo. En concreto, el programa de ejemplo era una aproximación numérica a la interpolación de una función desconocida a partir de un conjunto dado de datos.

Vamos por lo tanto a basarnos en esta cualidad del programa, para intentar encontrar patrones desconocidos a partir únicamente de ciertos datos empíricos conocidos. En muchas ocasiones, encontrar este patrón es imposible analíticamente, o si no es imposible, casi siempre es muy laborioso, requiriendo de complejos cálculos.

Un ejemplo de esto que digo puede ser el caso de intentar descubrir el patrón real que hay detrás del crecimiento de la población de un país. En el transcurso de los años, la población no crece o decrece de un modo aleatorio o caótico, sino que, a la vista de los datos, parece seguir cierto patrón o comportamiento. En principio este comportamiento del crecimiento de la población es desconocido, y sólo tenemos los datos empíricos de la población de un conjunto de años (los censos).

Según datos proporcionados por Funk & Wagnalls, el censo de Estados Unidos fue desde 1790 hasta 1990 el siguiente:


Realmente nos gustaría, a partir de estos datos, encontrar cual es el patrón oculto que dirige el crecimiento de la población para así, por ejemplo, poder estimar con cierta seguridad, cual será la población en el 2050 (año para el cual evidentemente aún no tenemos datos xD)

La búsqueda de este patrón es un ejemplo usualmente utilizado en la enseñanza universitaria para explicar al alumnado el concepto de ecuación diferencial. Pero para solucionar algún problema usando ecuaciones diferenciales, primero nos encontramos con el problema de conseguir modelar la situación usando ecuaciones en diferencia, luego nos encontramos con el problema frecuente de buscar el valor adecuado para los posibles parámetros usado en el modelo, y finalmente nos encontramos con el problema de encontrar una solución particular para esa ecuación diferencial a partir de ciertas condiciones iniciales.

Por ejemplo, mediante ecuaciones diferenciales se puede hacer un primer intento de modelado del patrón detrás del crecimiento de la población como este:


Este primer intento de modelo es fácil de calcular, y tiene, como solución analítica:

P(t) = 3.9 * e^(0.003067*t) 

pero cuando se contrasta esta función con los datos, vemos que el error cometido es grande a partir de cierto valor, por lo que finalmente no es un modelo que satisfaga el patrón oculto al crecimiento de la población.



¿Qué hacemos entonces? Pues buscar un nuevo modelo, solucionarlo y comprobar su nivel de aproximación con los datos.

Para este problema concreto, se suele utilizar un modelo llamado modelo logístico de la población, que viene a ser como el anterior, simplemente añadiendo un nuevo parámetro N que hace referencia a la capacidad de soporte del medio. De este modo, el modelo revisado es:


Esta ecuación diferencial ya no es lineal, y su resolución es más compleja, además de que ahora debemos conjeturar el valor de un nuevo parámetro N (además de k).

Este modo de actuar por ensayo y error de modelos es bastante complejo, laborioso y pesado. Para muchos problemas puede ser incluso un método inviable de actuación.

Resolución evolutiva.

¿Qué tal un método sencillo y universal? Un método que no requiera ni siquiera saber qué es una ecuación diferencial y que no necesite que tengamos que conjeturar con modelos para cada problema particular. Este método existe, y consiste simplemente, como seguro ya habréis podido imaginar, en el uso de un algoritmo de computación evolutiva.

La cuestión se reduce de este modo a introducir los datos empíricos en el programa, y a esperar a que el proceso evolutivo encuentre la función que mejor aproxime cada punto. Una vez alcanzada tal función con el nivel de aproximación especificado a priori, podemos estar seguro de que será una buena aproximación al patrón oculto a los datos empíricos de partida.

Posteriormente, simplemente tenemos que probar el patrón alcanzado con datos conocidos pero no pasados al programa (para asegurarnos de su fiabilidad), y finalmente, si la fiabilidad es buena, realizar predicciones para situaciones desconocidas utilizando este patrón hallado.

Aplicación práctica real al caso de estudio del crecimiento de la población de Estados Unidos.

Vamos a hacer uso de la aplicación que desarrollé para el artículo anterior. Como datos de entrada, vamos a introducir los datos facilitados por Funk & Wagnalls del censo de Estados Unidos desde 1790. Para poder estudiar la fiabilidad, no incluiremos las décadas posteriores a 1990. Por lo tanto la entrada del programa quedaría así:

{"x": 0} = 3.9;{"x": 10} = 5.3; {"x": 20} = 7.2; {"x": 30} = 9.6; {"x": 40} = 12;{"x": 50} = 17; {"x": 60} = 23; {"x": 70} = 31;{"x": 80} = 38;{"x": 90} = 50;{"x": 100} = 62;{"x": 110} = 75;{"x": 120} = 91;{"x": 130} = 105;{"x": 140} = 150;{"x": 150} = 131;{"x": 160} = 151;{"x": 170} = 179;{"x": 180} = 203;{"x": 190} = 226;{"x": 200} = 249;error_max = 10
Pulsamos en el botón "Ejecutar el proceso evolutivo" y esperamos las generaciones necesarias hasta que el error de interpolación de los puntos sea inferior a 10.

Cuando yo hice la prueba, el proceso terminó tras 271 generaciones, y me ofreció la siguiente función como resultado:


Es una función intimidante, ¿verdad? No te preocupes, es solo que el proceso evolutivo no busca, como puede hacer el científico humano, la sencillez algebraica. No la necesita. Y por eso esta función nos puede parecer extraña y difícil de entender. Pero es que realmente no necesitamos "comprender" el patrón encontrado, sino simplemente utilizarlo para realizar predicciones fiables con él.

Quizás este resultado sea después de todo una solución particular (o una aproximación) para el modelo logístico de la población que vimos antes, con un par de parámetros k y N desconocidos. O quizás no lo sea. No lo sabemos, pero tampoco lo necesitamos saber. Basta con que el patrón sea fiable.

¿El modelo encontrado es fiable?

Vamos a comprobarlo mediante su contrastación con otros datos conocidos pero que no han sido facilitados al programa.

El valor para las décadas posteriores a 1990 no fue facilitado precisamente con este propósito.

Pero primero veamos como se ajusta la función hallada a los datos facilitados al programa:

Año 1830 (t = 40): Valor predicho: 11,973 millones, Valor real: 12 millones, Error: 0,027
Año 1920 (t = 130): Valor predicho: 105,169 millones, Valor real: 105 millones, Error: 0,169
Año 1960 (t = 170): Valor predicho: 178,937 millones, Valor real: 179 millones, Error: 0,063

Se puede comprobar que existe un ajuste extraordinario.

Veamos, a continuación, cómo se ajusta la función a datos no facilitados al programa, pero que son conocidos empíricamente por otros medios. Como la tabla facilitada por Funk & Wagnalls no ofrece más información, usaremos otra fuente de datos alternativa. En concreto, vamos a usar los valores censales de Estados Unidos ofrecidos por la siguiente página web: http://www.datosmacro.com/demografia/poblacion/usa

Tenemos que tener en cuenta, sin embargo, un factor de corrección entre los datos facilitados por Funk & Wagnalls y los ofrecidos por la página web. Existe una variación entre las fuentes de datos de alrededor de un par de millones de habitantes de media. Por lo tanto, cuando usemos nuestra función para comprobar su fiabilidad con los datos de la web, debemos tener en cuenta estos 2 millones de diferencia (al alza o a la baja) entre losestimado por la función y el dato empírico ofrecido por la web datosmacro.

Teniendo esto en cuenta, hacemos las siguientes pruebas con datos no proporcionados al programa:

Año 1975 (t = 185): Valor predicho: 215,206, Valor real: 215,973 +- 2, Error: -0,767 +- 2
Año 1985 (t = 195): Valor predicho: 241,201, Valor real: 238,410 +- 2, Error: 2,791 +- 2
Año 1995 (t = 205): Valor predicho: 263,933, Valor real: 266,458 +- 2, Error: 2,525 +- 2
Año 2000 (t = 210): Valor predicho: 277,575, Valor real: 282,296 +- 2, Error: 4,721 +- 2
Año 2005 (t = 215): Valor predicho: 291,481, Valor real: 296,115 +- 2, Error: -4,634 +- 2
Año 2010 (t = 220): Valor predicho: 303,252, Valor real: 309,761 +- 2, Error: -6,509 +- 2
Año 2015 (t = 225): Valor predicho: 317,500, Valor real: 319,047 +- 2, Error: -1,547 +- 2

Teniendo en cuenta que gran parte del error cometido es probable que se deba al desajuste entre los datos de Funk & Wagnalls y los datos de la web, posiblemente el error medio cometido por la función cuando se contrasta con datos no usados en el proceso de interpolación esté alrededor de entre uno o dos millones. Este error medio, cuando hablamos de cientos de millones de personas, es bastante aceptable, y nos ayuda sin duda a hacernos una idea bastante ajustada de la población de Estados Unidos en cualquier año pasado o futuro (en el futuro será útil siempre que alguna catástrofe muy acusada no modifique el patrón seguido por el crecimiento real hasta ahora).

Predicciones futuras según el modelo.

¿Qué nos deparan las futuras décadas en cuanto a crecimiento de población en Estados Unidos se refiere? Pues, como digo, si no ocurren catástrofes apocalípticas no contempladas por el proceso tales como una epidemia o una guerra nuclear que aniquile a una gran parte de la población (modificando por lo tanto radicalmente el patrón real subyacente), el número de habitantes será con bastante seguridad el siguiente (con un error probable de un par de millones hacia arriba o abajo):

Año 2020 (t = 230): 332,981 millones de habitantes.
Año 2030 (t = 240): 354,429 millones de habitantes.
Año 2040 (t = 250): 387,272 millones de habitantes.
Año 2050 (t = 260): 425,315 millones de habitantes.
Año 2100 (t = 290): 526,467 millones de habitantes.
Año 2500 (t = 690): 3071,513 millones de habitantes.

Dentro de 5 años (ahora mismo estamos en el 2015), podremos comprobar la primera previsión y ver qué error cometió la estimación de nuestro modelo hallado ;).

Si se mantiene el patrón real seguido por Estados Unidos hasta ahora, vemos que pasarán muchas décadas antes de que alcance los 1000 millones de habitantes que tiene China hoy día.

Resumen.

Hemos visto un nuevo ejemplo del potencial que guarda la computación evolutiva. En este caso, hemos estudiado como ofrece una capacidad asombrosa en el descubrimiento de patrones ocultos; patrones que pueden ser demasiado complejos o caóticos para un estudio tradicional, pero que son perfectamente abordables mediante esta interesante y útil técnica de computación.


jueves, 23 de abril de 2015

Ejemplo VIII de computación evolutiva


Entendemos por un algoritmo evolutivo, a 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 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, iniciando lo que espero sea una serie de artículos con ejemplos funcionales -de código abierto-, para ayudar a cualquiera que quiera adentrarse en la materia. Además, espero que realizar esta propuesta, me ayudará a profundizar en mis conocimientos sobre el tema, y prepararme así para realizar el doctorado en ingeniería, que me gustaría algún día tener tiempo de hacer.

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.

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 obtener el código fuente en los recursos del navegador, ya que no hay código ofuscado):

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 applet, debemos rellenar el campo de texto "Datos de interpolación", añadiendo cuantos puntos deseemos. Una entrada válida sería, por ejemplo:

f0 = 0, f1 = 1, f2 = 4, f3 = 9

Si ahora, pulsamos sobre el botón Ejecutar algoritmo evolutivo, el programa finalizará, encontrando una de las muchas funciones que interpolan esos puntos, por ejemplo:

f(x) = x*x ó f(x) = x*x+x-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. Para probar dicho algoritmo aleatorio, hay que pulsar sobre el botón Ejecutar algoritmo aleatorio.

Para probar la potencia del programa, se ha habilitado la posibilidad de calcular automáticamente los puntos a interpolar, a partir de una función de nuestra elección. Con esto, nos aseguramos además, de que existe solución óptima. Sólo hay que pulsar sobre el botón Buscar datos de interpolación, y se nos abrirá una ventana donde deberemos escribir la función generadora de n términos de interpolación.

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), pero no el operador unitario -.

Al finalizar la ejecución del algoritmo, se abrirá una nueva ventana emergente 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 I 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-.


domingo, 12 de abril de 2015

Computación evolutiva: Ejemplo VII


En el siguiente ejemplo de computación evolutiva, veremos como una red neuronal de sólo 40 nodos es capaz de aprender de manera autónoma a realizar sumas de una cifra (el aprendizaje es autónomo, en el sentido de que en ningún momento al algoritmo se le indica cómo hay que sumar, y ni siquiera se le pasan los números en formato decimal).

El proceso consiste en utilizar una red neuronal con conexión hacia delante y una capa oculta (hidden layer). La capa de entrada contiene 20 nodos que se inicializa a 1 ó 0 según sea el input de entrada (el par de números a sumar). Cada nodo de la capa de entrada se une a cada nodo de la capa intermedia (la cual consta de otros 20 nodos), lo que da un total de 400 enlaces (pesos wij). Un último nodo de salida es el responsable de devolver el resultado del proceso neuronal expresando con su nivel de activación el resultado de la suma .

Inicialmente, los pesos wij de la red neuronal son marcados aleatoriamente, por lo que la respuesta de la red neuronal ante el problema será también aleatoria y casi siempre errónea. Hay pues que entrenar la red para que aprenda a evaluar bien la entrada, lo que vamos a conseguir ajustando evolutivamente los pesos de la red neuronal utilizada, además de ajustar el umbral de activación de cada nodo y el nivel de transmisicón o inhibición asociado. Dicho entrenamiento evolutivo se realizará mediante una estrategia evolutiva.

Comenzamos con una población de 750 redes neuronales aleatorias (n = 750 individuos). Cada generación se producirán n individuos más que sufrirán una variación exclusiva por mutación -sin recombinación- y cuya función de desempeño (fitness fuction) será calculada mediante competición -selección por torneo-. Para el proceso de mutación, hay que tener en cuenta que cada individuo; además de un vector de pesos, contiene un vector de variables de ajuste (umbral de activación y valor de transmisión), que también irá evolucionando junto con los pesos. La mutación es de la forma:


Con alpha igual 0.2f, y donde xi indica el peso en la posición i del vector de pesos, y N(0,1) indica un valor tomado aleatoriamente de una distribución normal de desviación típica igual a 1, y media igual a 0. La otra variable que interviene en el proceso se corresponde con la variable de ajuste del elemento i, que; como se puede ver, muta antes de que lo haga el peso xi. La evaluación de un individuo se realiza mediante q pruebas (con q = 100) en donde se pondrá a prueba la capacidad del individuo para resolver las 100 combinaciones posibles en que se pueden sumar dos números en el dominio [0-9]. En el paso final de cada generación, se seleccionan aquellos n individuos que mejor han aproximado su respuesta antes las q sumas.

A continuación podéis probar ese ejemplo VII de computación evolutiva que he desarrollado:


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

El poder del proceso evolutivo:

Es interesante notar la enorme eficiencia y capacidad que tiene la computación evolutiva para encontrar, dentro de un gigantesco conjunto de posibilidades, los valores adecuados para conseguir un fin concreto. En este ejemplo que estamnos viendo, las combinaciones y valores posibles para los pesos wij de los 400 enlaces, así como para el valor del umbral de activación y los valores de transimisión son inmensos. Para que un proceso aleatorio consiguiese ajustar finamente estos valores de modo que la red neuronal pudiese sumar correctamente, probablemente harían falta cientos de miles de años, y sin embargo, el algoritmo evolutivo lo consigue en un par de minutos.