visuse

VISUal Search Engine

Evaluación de la disposición de imágenes

Los tiempos de ejecución obtenidos mediante el enfriamiento simulado no son demasiados buenos, para 10 iteraciones (un número muy bajo para el enfriamiento simulado) en un computador moderno tarda más de 10 segundos, lo que claramente es un rendimiento inaceptable. Analizando con un el ‘profiler‘ de la extensión Firebug para Mozilla Firebug se detectan los principales cuellos de botella: más del 50% del tiempo es invertido en calcular el fitness de la solución, por lo que utilizando como función de evaluación el número de espacios que quedan en la matriz no es factible aplicar el enfriamiento simulado. Podríamos utilizar otros como función de fitness el número de imágenes utilizado, pero puede utilizándose muchas imágenes el desaprovechamiento de la pantalla sea muy grande.

Evolución del fitness de la solución en 10 iteraciones

Analizando también la calidad de la solución obtenida, llegamos a la conclusión de que apenas existe diferencia entre aplicar el enfriamiento simulado unas pocas iteraciones y quedarnos con la primera solución de la que partíamos, como se puede observar comparando las figuras siguientes:

Espacio ocupado y libre en la ventana sin aplicar el enfriamiento simulado

Espacio ocupado y libre en la ventana tras aplicar el enfriamiento simulado durante 10 iteraciones

Para estimar cuántas iteraciones serían necesarias para obtener resultados que fuesen apreciables se hace una ejecución de 50 iteraciones en la que se enfría la temperatura cada 5 y los resultados son los observados en la imagen siguiente, comparando el espacio que queda ahora libre con el total disponible ahora sí se aprecia una importante mejora. Sin embargo, debido al tiempo que tarda cada una de las ejecuciones no es viable.

Espacio ocupado y libre en la ventana tras aplicar el enfriamiento simulado durante 50 iteraciones

La razón por la que es difícil conseguir mejoras con respecto al algoritmo greedy inicial puede ser debida a la ordenación de mayor a menor realizada al inicio de éste. Como ya estudió Daniel Selator, una buena técnica es empezar colocando las imágenes mayores para después intentar rellenar los huecos dejados por ellas con las imágenes más pequeñas. Es obvio que si en último lugar consideramos las imágenes más grandes nos va a ser más difícil conseguir una óptima distribución.

5 agosto 2010 Posted by | Mejoras | , , , , , , | Deja un comentario

Aplicación del enfriamiento simulado

El enfriamiento simulado (o recocido simulado o simulated annealing) consiste en una búsqueda por entornos que, a diferencia de la búsqueda local, permite aceptar soluciones peores en función de una probabilidad que va disminuyendo con el tiempo. De esta forma, al principio se realiza una búsqueda con mayor diversificación y al final se intensifica la búsqueda, al ser más difícil que se acepte una solución peor.

Para aplicar el enfriamiento simulado se adapta el código desarrollado por Jesús González Peñalver que optimiza la disposición de un periódico online La temperatura inicial, que determina la probabilidad para aceptar soluciones peores, es iniciada según sugiere Kirkpatrick y el algoritmo recibe como parámetros el número de iteraciones a realizar y cada cuántas iteraciones se modificará la temperatura.

Como el resultado del algoritmo voraz depende de el orden en que se consideran las imágenes, lo que se hace es aplicar la técnica del enfriamiento simulado sobre el orden de dichas imágenes de entrada, siendo inicialmente el orden de este de mayor a menor importancia. Aplicar el enfriamiento simulado sobre la salida del algoritmo voraz sería más complicado y no merecería la pena, ya que no sería muy difícil aplicar una mutación sobre el resultado que minimice el número de huecos dejados.

El operador de mutación empleado consiste en intercambiar dos miembros distintos y seleccionados al azar de la lista. La función de evaluación o fitness es el número de huecos que quedan tras aplicar el algoritmo voraz.

18 julio 2010 Posted by | Mejoras | , , , , , , , , , , , , , , | Deja un comentario

Acelerando Visuse

Desde un primer momento tuve claro que la velocidad del buscador es fundamental para dejar contentos a los usuarios y que lo siguiesen utilizando, por ellos los últimos esfuerzos que acabo de realizar en el proyecto son para mejorar la velocidad en la que el código JavaScript muestra los resultados.

En lo que es el algoritmo de situación de las imágenes había poco que optimizar, ya que se trata de un algoritmo voraz que consigue determinar la posición de cada imagen muy rápido. Sin embargo, a la hora de utilizar este algoritmo cometía algunos errores imperdonables y que hacían parecer al buscador lento y pesado:

  • Cada vez que se pasaba de página se comprobaba si las imágenes habían cargado.
  • No empezaban a descargarse las imágenes hasta que todos los resultados no habían llegado.
  • Las imágenes mostradas sólo se actualizaban cada vez que se descargaban todos los resultados de un buscador.

Tras reestructurar completamente el código, finalmente se logró el comportamiento esperado:

  • Las imágenes únicamente se cargan al principio (o se comprueba si han cargado en caso de que estén en caché).
  • Las imágenes empiezan a descargarse tan pronto como llegan los resultados del primer buscador.
  • La actualización de las imágenes mostradas se hace cada 2 segundos, mientras no hayan cargado todas las imágenes.

Estas mejoras, junto con la resolución de algunos bugs y mejoras en la interfaz, son las principales características que incorporará la próxima versión del software (la 0.3) y que espero lanzar en los próximos días (de cara a la final del CUSL nacional).

8 mayo 2010 Posted by | Mejoras | , , , , , , , , , | 1 comentario

Un diseño simple para Visuse

Como comenté anteriormente, debido a que se acerca la fase final del CUSL Granadino, estoy trabajando duro en algunos aspectos del proyecto y uno que tenía pendiente de mejorar era el aspecto que presenta Visuse de cara a un próximo lanzamiento. Es un diseño muy simple, pero muestra una imagen más seria y bonita.

Esta es la apariencia actual de Visuse:

Índice de Visuse

Resultados de búsqueda

Gracias a Andrés Bayona de Intermagina que me ayudó con él y quien también hizo el diseño del logo.

19 abril 2010 Posted by | Mejoras | , , , , , , , , , , , | Deja un comentario

Nueva estructura de módulos

Una de las conclusiones más productivas del I Hackathon fue la necesidad de reestructurar los módulos para de que sea más fácil desarrollarlos, para reorganizar cierta información y para facilitar las pruebas. Tras varias mejoras realizadas hechas desde entonces ya tengo completamente lista una nueva versión de los módulos y el sistema de pruebas para ellos.

Las ventajas de esta nueva estructura son las siguientes:

  • Aplicación de la POO (programación orientada a objetos).
  • Los parámetros de configuración ahora se encuentran todos en un fichero independiente de los módulos.
  • Sistema de pruebas.
  • Mayor sencillez para integrar los módulos al ejemplo de prueba hecho.
  • Nueva jerarquía en las clases que organizan los resultados.

Para facilitar el desarrollos de estos, he creado una presentación que espero contenga toda la información necesaria:

18 abril 2010 Posted by | Mejoras | , , , , , , , , , | 2 comentarios