Abrimos esta cadena de posts con la siguiente pregunta: ¿cómo aplico a algo inteligencia?.

Bueno, por pasos: primero tendremos que disponer de algo a lo que se pueda aplicar inteligencia. Por hacerlo sencillo, vamos a suponer una simple aplicación de escritorio. Después tendremos que tener claros los objetivos que queremos que esa aplicación cumpla, y esto es un paso muy laborioso, porque además debemos conocer bien la tecnología para no pensar cosas utópicas, y elegir los caminos más acertados. Una vez tenemos claros los objetivos, si conocemos bien la tecnología, deberemos diseñar una solución, es decir, deberemos pensar de qué forma esta aplicación va a tomar decisiones “inteligentes”. Puede que nos suponga incluir algoritmos de búsqueda, puede que tengamos que aplicar conceptos de lógica, y probablemente tendremos que tratar con datos, con lo cual también sería interesante presentar tales datos del modo más cómodo que nos convenga.

Y una vez nos encontramos con un diseño hecho, pues sólo nos quedará implementarlo. ¿Qué lenguaje es el más adecuado?.

Con la pregunta ya planteada, vamos a pasar a responderla, puesto que es bien sencillo: en general, no hay un lenguaje óptimo para cualquier tarea que conlleve utilización de técnicas de IA. Si vamos a desplegar la aplicación en un robot, pues probablemente C o Ada sean los lenguajes que más beneficios puedan aportarnos, pero por las peculiaridades de los lenguajes en sí y no porque nos provean de soluciones de IA de forma directa; por eso esta decisión engloba muchos factores que deben ser discutidos por expertos en tal área.

Si hablamos de aplicaciones de escritorio, como en el ejemplo de arriba, con un lenguaje de alto nivel (como pueda ser C++, Java, o C#/.NET) puede ser suficiente, puesto que supondrá aplicar algoritmos con una fuerte fuente matemática.

La gracia viene cuando necesitamos manejar datos a la vez que construcciones programáticas que operen dichos datos, y cuando debemos realizar esto de una forma continuada y masiva. Esto de manejar datos, operándolos, modificando ciertos atributos, mezclándolos, etc, pues suena a sistema experto, ¿no? Si recordamos, un sistema experto se centraba en un dominio de conocimiento para resolver problemas asociados a tal dominio. Para este fin, este sistema debe manejar datos del entorno, datos que le introduzcamos, y los irá operando para hallar una respuesta o un conjunto de éstas.

Además, podemos entender que casi cualquier aplicación a la que queramos dotar con técnicas de IA va a tener ciertos módulos que manejen datos como si de un sistema experto se tratase (probablemente sea así), y es precisamente aquí donde introducimos Lisp.

; ---FACTORIAL----
;Definición matemática
; Factorial(x) = 1 si x=0 caso base
; x*factorial(x-1) si x>0 caso recursivo
;Función factorial hecha con recursividad no final
(defun factorial (n)
(if (= 0 n)
1 ; caso base
(* n (factorial (- n 1))))) ; caso recursivo
(factorial 4) ;esto nos devolvería 24=4*3*2*1

Lisp es un lenguaje de programacion de alto nivel y declarativo, que data del 58, diseñado por John McCarthy en el MIT, y desarrollado precisamente para facilitar las tareas en las que es abrumadora la necesidad de cruzar datos con operaciones, y modificar éstos segun muchísimos criterios para obtener una salida, que a su vez pasará por otra operacion que hará que estos datos… etc, etc. Es un lenguaje cuya estructura fundamental es la lista, y es precisamente este hecho el que facilita ciertas tareas, y por lo que ha sido usado ampliamente desde sus inicios para la IA. Detallar más explícitamente por qué es apto para ese tipo de aplicaciones es una tarea difícil de realizar; el fin del post era arrojar algo de luz sobre aspectos de más bajo nivel de la IA (como es su implementación), comentar qué herramientas se utilizan en algunos casos, puesto que como es de esperar, herramientas para la IA hay infinitas, así como lenguajes, técnicas, etc.

….Esperando comentarios de cualquier tipo…

En el anterior post explicamos el algoritmo Metrópolis y por qué era tan importante para resolver el problema del viajante de comercio. En éste vamos a explicaros qué es el algoritmo simulated annealing y cómo se codifica para poder utilizarlo en cualquier aplicación.

Recordaréis que el algoritmo Metrópolis devuelve una serie de configuraciones. Esto sucede así hasta que llega a una situación de equilibrio, que habitualmente consiste en alcanzar un número de configuraciones determinado. En cada ciclo, el algoritmo Metrópolis nos devuelve una muestra de la distribución de Gibbs para una determinada temperatura. Para saber si dicha muestra es un mínimo global, hay que repetir los muestreos disminuyendo de manera monótona la temperatura, hasta que el valor se aproxime a 0. Esta sucesión de muestreos es lo que llamamos simulated annealing. El pseudocódigo del algoritmo es el siguiente:

comienzo SIMULATED_ANNEALING {
     C[0] = INI_CONFIGURACION ( );
     T = INI_TEMPERATURA ( );
     t = 0;
     repetir {
          C = C[t];
          repetir {
               auxC = GEN_CONFIGURACION(C);
               ∆E = E(auxC)-E(C);
               q = mín{1, e^(-∆E/T)};
               si (ALEATORIO(0,1)< q) entonces { C = auxC;  } ;
          } hasta( TEST_EQUILIBRIO );
          t = t +1;
          C[t] = C;
          T = ENFRIAR (T, t);
     }hasta (T ≈ 0);
     devolver C[t] = C* = arg mín E(C);
}

Tenemos que realizar las siguiente aclaraciones:

• Las funciones INI_CONFIGURACION y INI_TEMPERATURA, proporcionan una configuración inicial (normalmente aleatoria) y la temperatura inicial, respectivamente.
• La función GENERAR devuelve una configuración local a la dada.
• La función ALEATORIO devuelve un valor uniformemente distribuido entre los límites que se pasan por el argumento.
• El control de convergencia de algoritmo Metrópolis lo realiza la función TEST_EQULIBRIO, el cual lo que hace es comprobar en qué ciclo se encuentra y escapar del bucle cuando satisfaga la restricción.
• La función ENFRIAR merece un capítulo sólo para ella, ya que ésta es la que se encarga de reducir la temperatura de manera monótona, y es la que permite que el sistema funcione.

La característica más interesante de este algoritmo es su capacidad para evitar los mínimos locales, lo cual se debe a la cuidadosa gestión del parámetro T. En el siguiente post os contaremos cómo debemos desarrollar la función de ENFRIAR. Ya casi hemos resuelto el problema.

En el anterior post sobre búsqueda, hablamos sobre la utilización de la temperatura para hacer converger nuestro sistema a un mínimo global que permita encontrar la solución óptima. También hemos dicho, en diversas ocasiones, que intentar analizar todos los casos del espacio Ω es inviable, debido a su magnitud. Lo ideal es encontrar una forma para que se seleccionen las mejores soluciones, y solamente evaluar éstas. El algoritmo Metrópolis se encarga de esto.

En primer lugar vamos a suponer que la temperatura T es constante. Lo primero que debemos hacer es asignar una configuración inicial C0, y despues vamos a estar interesados en generar una serie de configuraciones C1, C2 … hasta que consigamos encontrar la configuración de mínima energía para esa temperatura. Lo que podríamos hacer es evaluar todas las configuraciones en función de P(C), asumiendo que las mejores configuraciones van a tener mayor posibilidad de salir; el problema es que si el número de configuraciones es excesivamente grande, y este número es un numero significativamente menor que Ω, esto no es lo más óptimo.

Sin embargo, nosotros vamos a evitar evaluar las configuraciones directamente a través de P(C), ya que resulta mucho más fácil modelar la secuencia como una Cadena de Márkov (una secuencia de eventos donde el evento siguiente depende del anterior), porque evaluaremos una función P(C[t+1] | C[t]), pero no aseguraremos que esta probabilidad converge a la distribución de P(C), en este caso a la distribución de Gibbs, si el numero de muestras es suficientemente elevado.

El algoritmo Metrópolis aporta una estrategia de muestreo de este tipo y se caracteriza por dos aspectos básicos:

• La configuración de C[t+1] se consigue a través de C[t], de forma que C[t+1] es una configuración vecina o localmente próxima a C[t]. En el caso del viajante de comercio es coger una ramificación, lo que se traduce en permutar dos ciudades.
• La nueva configuración C[t+1] no se acepta directamente, sino que se acepta con una cierta probabilidad definida como:

  

  Siendo P(C) una disribución de Gibbs, y como tenemos una T fija:

  

  
  Si la variación de energía es menor o igual que cero, entonces la configuración C[t+1] se coge sin duda, ya que significa una disminución de energía. En caso contrario, entonces la probabilidad de que esta nueva configuración nos lleve a la óptima decae exponencialmente con el empeoramiento del balance energético, y dicho decaimiento está atenuado por T. Se debe elegir umbral que decida a partir de qué probabilidad q se debe aceptar una configuración. Este umbral es r.

El algoritmo Metrópolis termina cuando satisface una condición de equilibrio, que en la práctica se traduce en un determinado número de muestras. En el siguiente post, después de haber comentado todas las herramientas que utilizamos para el simulated annealing, describiremos este algoritmo y cómo utiliza el algoritmo Metrópolis para obtener la solución óptima.

En el último post sobre búsqueda definimos las dimensiones del problema del viajante de comercio, y definimos una función de energía que nos sirve de medida para saber si la solución es óptima.

Ya conocemos la función de coste:

Nos damos cuenta de que la función de coste E(C) ≥ 0 para todo C perteneciente a Ω. Para poder aplicar nuestro algoritmo de búsqueda, en este caso el algoritmo Simulated Annealing (Templado Simulado), asumimos que la probabilidad de una determinada configuración C decae exponencialmente con su coste siguiendo la distribución de Gibbs:

Z es un factor de normalización denominado función de partición, y T un parámetro de control denominado temperatura. Cuando T tiende a infinito, resulta que la probabilidad de una determinada configuración C es uniforme, de tal manera que todas las configuraciones tienden a ser equiprobables independientemente de su coste. Sin embargo, si T tiende a 0, P(C) se concentra en los picos de la distribución de Gibbs, de tal manera que sólo las configuraciones de mínimo coste tienen configuración no nula. En conclusión, para una misma temperatura, la probabilidad de una determinada configuración decae exponencialmente con su coste, y dicho decaimiento es atenuado por la temperatura; es decir, la configuraciones que tienen mínimo coste son más probables que el resto.

¿Y qué tendrá que ver todo esto con el viajante de comercio? estamos hablando de probabilidades, de funciones de coste, pero no sabemos qué vamos a hacer con todo ello. Calma, os dije que esta parte no iba ser fácil.

Todo este modelo probabilístico que he propuesto se relaciona con la búsqueda de la configuración de mínimo coste, mediante una analogía entre la resolución de un problema de optimización y la solución de un proceso de templado del metal. Para templar un metal, lo primero que hacemos es exponerlo a temperaturas muy elevadas, y despues descender esta temperatura hasta encontrar la configuración de mínima energía, que es cuando el metal alcana estructuras reticulares, extrema su resistencia y su dureza. Pero al realizar el templado, tenemos que tener en cuenta el ritmo con el que enfriamos el metal. Un ritmo demasiado rápido alcanzara configuraciones de baja energía, que no se corresponderán a estructura reticulares, sino a estructuras amorfas que harán que el metal pierda su resistencia y su dureza. Esto es debido a que no se alcanzado un mínimo de energía global, sino uno local que no es el óptimo, y que puede estar muy alejado de la solución del problema. Pero si se elige una buena velocidad de descenso de temperatura que permita saltarse esos mínimos locales, se garantiza la convergencia al estado óptimo global. El algoritmo Simulated Annealing garantiza esta convergencia y se aplica para problema combinatoriales, como es el caso del viajante de comercio.

En el próximo post, describiremos el proceso de Muestreo a través del algoritmo Metrópolis. Este algoritmo genera una secuencia de configuraciones que utilizará el algoritmo Simulated Annealing para alcanzar la configuración óptima. Empieza lo interesante.