Condición de parada

Si ya hemos elegido nuestro algoritmo favorito y la función fitness que vamos a usar, lanzamos nuestro programa y surge un problema ¿Cuando páramos?.

Lo fácil sería decir que cuando alcancemos el resultado deseado, pero eso no es siempre posible o al menos no en un tiempo que sea razonable. Así que tendremos que quedarnos con una buena aproximación. ¿Pero cual es una buen aproximación? Hay veces que lo sabemos, sabemos que resultado nos tiene que dar al función fitness para que la solución sea suficiente para nosotros. ¿Pero que pasa si no sabemos cuando ha llegado al máximo o al mínimo de la misma?. Con las metaheurísticas siempre nos quedaremos con la duda. No podemos saber si hemos encontrado el punto optimo o nos hemos quedados atrapados en un máximo/mínimo local. Todo dependerá de nuestras necesidades y conocimiento del espacio de búsqueda.

Para reducir este problema hay que intentar explorar lo máximo posible el espacio de búsqueda. El punto optimo puede esconderse en cualquier rincón que nos dejemos sin mirar. Pero claro si estamos usando una metaheurística es porque no conocemos el espacio de búsqueda y es muy grande como para que lo exploremos.

Una de las condiciones más usadas en el caso de desconocimiento total es fijar de antemano un número de iteracciones. Es útil cuando tenemos un tiempo o recursos limitados para calcular la solución. Sin embargo puede darse el caso de que el tiempo no sea tan limitante, aunque tampoco nos apetezca tener al algoritmo iterando durante varias veces la vida del universo. En ese caso se puede fijar un umbral de “mejora”. De tal manera que si durante un número determinado de iteracciones el resultado no ha mejorado la solución por encima de ese umbral se para la ejecución ya que se considera que el tiempo invertido no compensa la mejora obtenida.

Por último la que me atrevería a decir que es la condición más usada pero que ningún libro habla de ella. Ir mostrando datos en pantalla y que el usuario decida cuando terminar la ejecución. Puede parecer una solución “poco inteligente” pero durante las pruebas de un algoritmo para ver qué tal se comporta con un problema o viendo si se puede afinar su configuración puede ahorrar mucho de tiempo.

De todas formas muchas veces nos obsesionamos con encontrar el resultado optimo y en la vida real muchas veces basta con una aproximación que ni siquiera sea muy buena.
 

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.