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 esta nueva sección del blog vamos a intentar explicar cuáles son los diferentes entornos que nos permitirán simular, en un ordenador, condiciones de la vida real, o simplemente nos darán unas herramientas para poder aplicar nuestro conocimientos sobre inteligencia artificial en un entorno determinado. La simulación en ordenador consiste en un software en un ordenador, o dispuesto en una red de ordenadores, que controlan todas las variables de un modelo abstracto que se aplica a un sistema.

Existen multitud de simuladores, desde los simuladores de carreras, o deportivos, hasta los simuladores de vida artificial, con los que puedes programar la reacciones de una célula o de un organismo completo haciendo que estos aprendan y evolucionen.

Todos estos entornos se caracterizan por dar al usuario un serie de herramientas que le permiten desarrollar sus propios ejemplos, e introducirlos en el entorno. El sistema devolverá los datos de cómo ha reaccionado el sujeto en el entorno de simulación, y entonces el usuario analizará estos resultados y modificará el ejemplar para volverlo a introducir en entorno, hasta que los datos sean satisfactorios. La utilidad de estos sistemas es que permiten hacer pruebas de ensayo y error sin poner en peligro medios materiales o humanos y reduciendo los gastos en pruebas, ya que el simulador intenta emular todas las condiciones reales. Los simuladores pueden devolver resultados casi en tiempo real o necesitar de una red de ordenadores enorme para dar una respuesta en un par de días, todo depende de la complejidad del modelo y de los parecido que sea con el mundo real. Dependiendo de lo crítico que sea el sistema, esta similitud puede ser vital, y marcar la diferencia entre un estrepitoso fracaso o un rotundo éxito.

Nosotros nos vamos a centrar en entornos de simulación simples, con una rápida curva de aprendizaje. A la vez deben ser amenos y divertidos lo que nos facilitará programar ejemplos, ya que lo haremos jugando:

• Robocode. Tal vez sea uno de los entornos de simulación más sencillos y más divertidos de usar. En él nos encontramos en un mundo de dos dimensiones de un tamaño reducido, en donde los tanques luchan entre sí en diferentes modos de combate (por equipos o todos contra todos). El entorno permite la programación de nuevos tanques, o la programación de equipos, todo ello utilizando Java como lenguaje. En este simulador podemos aplicar multitud de técnicas de inteligencia artificial, tanto de búsqueda como de aprendizaje. Al permitirnos el trabajo en equipos podemos utilizar sistemas de aprendizaje distribuidos. Robocode es open source y una herramienta perfecta para aplicar todos tus conocimientos sobre inteligencia artificial.

  

• Tao of soccer. Este entorno simula un partido de fútbol en el cual podremos controlar a todos los jugadores de un equipo y enfrentarnos contra otros jugadores manejados por el ordenador. El sistema tiene una arquitectura cliente-servidor: el servidor se encarga de montar el entorno gráfico, de que se respeten la reglas del juego y de comunicar el estado del juego al resto de jugadores. Esta comunicación se realiza mediante paquetes UDP; de esta manera, los clientes se pueden desarrollar en cualquier lenguaje que soporte el manejo de sockets UDP. Al contrario que en Robocode, este entorno no tiene que implementar interfaces, ni heredar de objetos, ni basarse en un librerías previamente desarrolladas, únicamente se debe respetar el protocolo de comunicación entre el cliente y el servidor. En este entorno podemos desarrollar técnicas de inteligencia artificial para grupo, tanto aprendizaje distribuido como estrategias de colaboración. Este entorno también es perfecto para el aprendizaje y permite de una forma divertida mejorar en técnicas de colectivas.

  

• RARS. Crear una inteligencia artificial capaz de manejar un coche de carreras: esto es lo que nos permite RARS. A través de programación en ANSI C o C++, podremos desarrollar los bots que controlen nuestros vehículos, y de esta manera competir con otros bots ya creados. En este programa podrás usar procesos de aprendizaje complejos, ya que el sistema devuelve una gran cantidad de datos del entorno del coche. Además, dependiendo del circuito, el competidor deberá tomar diferentes decisiones que pueden cambiar el transcurso de la carrera, por lo que el uso de árboles de decisión también puede ser interesante. Un simulador completo para gente que quiera pasar un buen rato y tenga unos conocimientos amplios sobre la inteligencia artificial.

  

• Breve. Éste es quizá el simulador más complejo de los cuatro, ya que permite el desarrollo de infinitos objetos distintos, donde los grados de libertad los decide el usuario. Breve es un entorno de simulación ideal para los desarrollos de vida artificial, ya que el control físico de los agentes es realizado por el entorno. Para desarrollar en Breve podemos optar por utilizar Phyton o usar Steve, un lenguaje orientado objetos parecido a Objetive-C o Small Talk que ha sido creado específicamente para crear agentes para el sistema. También se facilitan interfaces que permiten extender el simulador a través de plugins. Un entorno muy completo, pero para usuarios muy avanzados, donde podemos aplicar todos nuestros conocimientos sobre inteligencia artificial y seguramente nos quedemos cortos si queremos crear agentes complejos.

  

Todos estos entornos nos permiten probar los conocimientos que poco a poco iremos enseñando y, por tanto, es importante que conozcamos este software, ya que estas herramientas nos ayudan a comprender cuáles son las ventajas y desventajas de utilizar ciertas técnicas respecto a otras. Más adelante nos encargaremos de enseñaros los entresijos de estos programas, y cómo poder aplicar vuestros conocimientos de inteligencia artificial en entornos de simulación.

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.