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