Últimamente Microsiervos, la página que aspira a contener todo internet en sí misma, está poniendo vídeos muy relacionados con los temas que tratamos en este blog.

Este robot nos ha hecho sonreír durante un buen rato.

Los equipos de desarrollo que trabajan con Asimo, el robot de Honda, siempre desarrollan cosas muy interesantes.

Este año se celebra la tercera edición de la Javacup, un torneo realizado por Javahispano. Este torneo es noticia en este blog, porque para poder participar en él debemos tener conocimientos de inteligencia artificial. Si deseamos competir deberemos realizar un equipo de fútbol utilizando su framework, y programar unas táctica en java que permitan al equipo conseguir el máximo número de goles en esta competición tan exigente. El torneo consistirá en una serie de fases eliminatorias; en cada una de ellas se enfrentaran dos equipos a un partido, hasta llegar a la gran final. Los jugadores que queden entre los cuatro primeros ganarán un año de suscripción gratuita la revista “Sólo Programadores”, y recibirán un premio de 125€, 250€, 500€ y 1000€ respectivamente. Los concursantes tienen como fecha límite el 30 de mayo del 2009.

La verdad que jugar con este tipo de framework es muy divertido, porque no te tienes que preocupar ni de desarrollar interfaces, ni de cuestiones gráficas, sólo te dedicas a desarrollar la inteligencia de tus jugadores. En ellos puedes aplicar todos los conocimientos que poseas.

Hay multitud de tácticas, combinaciones, formas de desplegarse… fíjate si no en estos vídeos del torneo de año pasado.

Un factor importante en el juego es que existe una gran componente azaroso, y como se puede ver hay muchas formas de contrarrestarlo.

Aunque, como se puede ver en la final, las diferencias eran bastante evidentes.

¿Has participado alguna vez en la Javacup? ¿Tienes pensado participar este año? ¿Tienes experiencia en este tipo de competiciones? Cuéntanoslo.

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.

En el post anterior enunciamos el problema del viajante de comercio. Comentamos que las dimensiones del problema eran demasiado grandes como para abordarlas sin realizar ningún tipo de poda o intentando evitar caminos que nos lleven a situaciones ya ocurridas. Aunque a esta conclusión llegamos mediante la intuición, y no estimamos cuánto tiempo tardaríamos en buscar todas las combinaciones.

Si intentamos evaluar la complejidad del problema, nos damos cuenta de que si nuestro querido comerciante de androides quiere recorrer 18 ciudades y queremos valorar todas las opciones, deberemos calcular todas las combinaciones de 18 elementos, que son 18! posibilidades, es decir, 6.402.373.705.728.000. Si para calcular cada una de las posibilidades empleamos 1µs, necesitaríamos un poco más de 203 años para terminar de comprobar cada una de las posibilidades. Naturalmente eso es mucho tiempo y en ese tiempo se pueden crear ciudades, abandonar otras, o que la Estrella de la Muerte pase por ahí y se cargue el planeta.

Una vez que ha quedado claro el espacio de configuraciones, que vamos a denotar como Ω, vamos a formular una función matemática denominada función de energía, que cuantificará el coste de cada una de sus configuraciones. En este problema la funcion de energía es evidente, ya que equivale a la distancia que recorremos en cada uno de los ciclos completos. Si llamamos cada una de la permutaciones ∏(1)∏(2)∏(3)…∏(N), entonces el coste de un ciclo es:

Donde d(x, y) es la distancia que existe entre las ciudades de x e y.

Teniendo definidas la dimensión del problema y la función de energía, nuestro problema va a consistir en hacer que la configuración mínima sea la menor posible; de esta manera recorreremos todas la ciudades de la manera más óptima.

Por ahora lo dejamos aquí, ya que en próximos posts aplicaremos la distribución de Gibbs para conseguir un nuevo parámetro de control que nos facilite la solución del problema: la temperatura. También simularemos los procesos de templado que se utilizan para endurecer el metal, que nos servirán en nuestro problema para intentar descubrir cuál es la configuración óptima. Tomen aliento, esto acaba de empezar.