¿Puede un programa comportarse de forma inteligente sin implementar conocimiento de un experto? Anteriormente te he explicado cómo transformar el conocimiento de un experto en un conjunto de reglas y una base de hechos, mediante programación lógica. Otro día hemos aproximado parte del problema con ayuda de un experto para escoger los candidatos más prometedores.
¿Pero qué pasa si no tenemos ni idea de cómo resolver el problema? Lo que voy a enseñarte hoy parece pura magia.
Imagina este problema: Una tubería conduce gas desde Santander a Torrelavega, a lo largo de 30 Km. Como todas las grandes conducciones de fluidos, esta tubería sufre pérdidas y por lo tanto no siempre entrega la misma cantidad de Kg de gas en la salida que se introdujo en la entrada.
Sabemos que algunos factores alteran el transporte y son, entre otros, la lluvia, el viento y la temperatura. Imagina que a más calor, menos pérdidas y con más lluvia, más pérdidas. Pero aún así, las combinaciones de los tres elementos son tan enormes que ningún experto se atreve a aventurar unas reglas que permitan predecir la cantidad de gas que llega al final. Y por si fuera poco, las instalaciones ya tienen unos cuantos años y los tubos están empezando a tener micro-fisuras.
Para rematar, a la altura de Requejada (un saludo a los habitantes de Requejada) existe un boquete por el que se cuelan los gatos en los periodos en los que no se envía gas. Y crían dentro. Por lo que muchas veces hay camadas enteras de gatos dentro de la conducción que impiden el paso normal del gas.
Como el ejemplo es mío, el gas es inocuo y lo único que provoca en los gatos es relajación y un maullido grave que puede hacerlos confundir con Shere-Kahn. Pero de todas formas, estorban dentro del tubo.
¿Cómo puede un programa predecir la proporción de gas a la salida, respecto de la entrada, si los expertos no saben controlar todas las variables a la vez?
Base de conocimiento
No tenemos grandes expertos que nos aporten reglas ni pistas para solución, pero sí podemos tener un montón de datos históricos de los envíos y las recepciones de gas.
Imaginad que para este problema hemos recogido miles de registros de envíos de gas en los que hemos anotado todas las variables conocidas: la temperatura, la hora del día, las precipitaciones, la fuerza del viento, la dirección del viento, el número de kilos enviados y el número de kilos recibidos (como resultado).
Tendremos un conjunto de datos que dividiremos en dos: un conjunto grande, entre un 80 y un 90% de los datos, será la base de entrenamiento y el resto, el 10% serán datos de contraste.
Utilizaremos el mayor de los conjuntos para «entrenar» al sistema y el otro 10% para comprobar que la solución que encontremos realmente es capaz de predecir el resultado.
Utilizando algoritmos genéticos
Es una técnica de programación de los años 70, basada en la selección natural de Darwin, en la que se establece un conjunto heterogéneo de individuos que son candidatos a solución del problema. Dichos individuos se van a combinar con cruces entre los mejores especímenes (los que den mejores resultados). En nuestro caso buscamos la «fórmula» que calcula la proporción de gas en la salida del tubo respecto de la entrada.
Y la solución será una función matemática de los parámetros de entrada:
En este árbol aparecen una serie de valores (o variables) en las hojas y una serie de operaciones en los nodos intermedios. Las operaciones se pueden recorrer en inorden (primero cada rama, luego el nodo padre) o en cualquier otro orden, pero siempre el mismo orden en cada paso:
(x + ((((-4 * (-5 – 2)) / (-1 / -2)) + -3) / -1))
A cada fórmula, la vamos a llamar individuo y tendremos un conjunto generoso y heterogéneo de individuos al que llamaremos población. La población la generaremos aleatoriamente al principio de la ejecución.
Si hacemos pasar la base de entrenamiento por un individuo, obtendremos medidas de error (número de errores, error medio, dispersión).
Ejecución del algoritmo genético
Un algoritmo genético consiste en conseguir un individuo que cumpla con una medida de error aceptable en su ejecución sobre la base de entrenamiento. Para ello hay que definir matemáticamente la parada de la iteración (número de errores, media del error, dispersión, etc…)
Una vez definida la función de parada, se iniciará una iteración que consistirá en los siguientes pasos
- Evaluación: del error que presenta cada uno de los individuos de la población
- Selección: de los individuos más prometedores (con mejores resultados).
- Recombinación: combinamos los individuos más prometedores cruzando las ramas por puntos aleatorios. De cada cruce se producirán muchos individuos hijos.
- Mutación: con una frecuencia muy pequeña, de vez en cuando, añadiremos nuevos nodos o ramas a alguno de los individuos, independientemente de su evaluación (una mutación sobre un mal individuo puede dar un resultado mejor que los individuos más prometedores a priori).
- Reemplazo: Se vuelve a evaluar a los individuos y eliminaremos a los menos prometedores, conservando fijo el número de la población.
En cada iteración obtendremos mejores resultados que en la iteración anterior, o al menos los mismos. En la condición de parada pondremos que tras varias generaciones sin mejora, se pare el algoritmo.
Ventajas
El resultado de la ejecución devuelve como resultado una fórmula que representa lo que pasa en el sistema que estamos evaluando (en el ejemplo, la tubería).
Inconvenientes
- Son algoritmos muy pesados, con muchísimo consumo de CPU y ejecuciones larguísimas. Piensa que hay que evaluar el 90% de la base de conocimiento sobre cada individuo en cada iteración.
- El resultado obtenido representa una fórmula que explica el comportamiento del sistema, pero no necesariamente la fórmula más sencilla:
Imagínate que la función que define el problema es
f (lluvia, temperatura, masa) = masa - 0.5 * lluvia / temperatura
El resultado de un algoritmo genético puede ser mucho más grande:
f(L,T,M) = M - (1/2) * (((0.5 * L)/ (1/2)) / (((0.2 * 15) / 3) * T))
Y con este ejemplo me quedo muy corto. Salen árboles enormes.
Más inconvenientes:
- Hay muchos parámetros sobre el algoritmo: tamaño de la población, tamaño de la selección, procedimiento de recombinación, número de hijos, frecuencia de la mutación, etc.
Se deben modificar estos parámetros y hacer ejecuciones con variaciones de los mismos para obtener mejores resultados.
Aplicaciones de los algoritmos genéticos
(via wikipedia)
- Diseño automatizado, incluyendo investigación en diseño de materiales y diseño multiobjetivo de componentes automovilísticos: mejor comportamiento ante choques, ahorros de peso, mejora de aerodinámica, etc.
- Optimización de carga de contenedores.
- Diseño de sistemas de distribución de aguas.
- Análisis lingüístico, incluyendo inducción gramática, y otros aspectos de Procesamiento de lenguajes naturales, tales como eliminación de ambigüedad de sentido.
- Construcción de horarios en grandes universidades, evitando conflictos de clases
Una última reflexión
Nos queda el tema de las fisuras y de los gatetes.
Parte de la problemática de nuestro ejemplo eran imponderables como las grietas o la presencia de objetos imprevistos en el tubo. Algunos de estos problemas se solucionarán mediante ramas del árbol. Por ejemplo, imagina que el 10% se pierde por una fisura. En ese caso aparecerá una rama como:
(- 10 * (Masa / 100))
Pero hay casuísticas que difícilmente tendrán reflejo en el algoritmo. Para eso y muchas cosas más, existen técnicas basadas en la naturaleza como las redes neuronales, que serán objeto de estudio en otro artículo porque este ya me ha quedado muy largo.
¿Preguntas? ¿Opiniones? Puedes dejar un comentario.
Pingback: La vida como programador – Josedetorre