cultura general







Definición de Metaheurística:
“heurística” deriva del griego heuriskein, que significa “encontrar” o “descubrir”.
Técnicas que buscan soluciones de buena calidad (de valor cercano al óptimo) a un costo computacional razonable, aunque sin garantizar la optimalidad de las mismas. En general, ni siquiera se conoce el grado de error. Clasificación de las heurísticas:
MétodosConstructivos: generan una solución (desde una solución vacía) agregando componentes hasta completar la solución. Son métodos rápidos, de baja calidad en los resultados.
Métodos de Búsqueda local: comienzan desde una solución e iterativamente van remplazando la solución actual con alguna solución parecida de mejor calidad.
La optimización en el sentido de encontrar la mejor solución, o al menos unasolución lo suficientemente buena, para un problema es un campo de vital importancia en el mundo real y, en particular, en ingeniería. Constantemente estamos resolviendo pequeños problemas de optimización, como el camino más corto para ir de un lugar a otro, la organización de una agenda, etc. En general, estos problemas son lo suficientemente pequeños y podemos resolverlos sin ayuda adicional, peroconforme se hacen más grandes y complejos, el uso de los ordenadores para su resolución es inevitable.
Comenzaremos este capítulo dando una definición formal del concepto de optimización. Asumiendo, sin perdida de generalidad, el caso de la minimización, podemos definir un problema de optimización como sigue:

Figura #1
Los algoritmos aproximados para resolver estos problemas están recibiendouna atención cada vez mayor por parte de la comunidad internacional desde hace unas décadas. Estos métodos sacrifican la garantía de encontrar el óptimo a cambio de encontrar una solución satisfactoria en un tiempo razonable.

Figura #2
Clasificación de las Metaheurística:

Hay diferentes formas de clasificar y describir las técnicas metaheurística [29]. Dependiendo de las características quese seleccionen se pueden obtener diferentes taxonomías: basadas en la naturaleza y no basadas en la naturaleza, con memoria o sin ella, con una o varias estructuras de vecindario, etc. Una de las clasificaciones más populares las divide en metaheurística basadas en trayectoria y basadas en población. Las primeras manipulan en cada paso un único elemento del espacio de búsqueda, mientras que lassegundas trabajan sobre un conjunto de ellos (población).
Esta taxonomía se muestra de forma gráfica en la Figura 3.2, que además incluye las técnicas más representativas. Estas metaheurística se describen en las dos secciones siguientes.

Figura #4

Existen varios tipos de metaheurística como por ejemplo:
Simulated Annealing:
Definición: El método SA es un algoritmo probabilístico quepermite resolver problemas de optimización. Se basa en una analogía de un proceso termodinámico, conocido como annealing, consistente en el lento enfriamiento de una sustancia desde su estado líquido hasta su estado sólido. Durante este proceso sus átomos forman un compuesto solido puro que corresponde al estado de mínima energía de la sustancia. Luego, la sustancia es calentada hasta alcanzar su estadolíquido y gradualmente su temperatura es disminuida hasta alcanzar su estado sólido. La analogía entonces se realiza interpretando una solución del problema de optimización como un estado sólido-liquido en equilibrio, entendiendo que la energía que está siendo minimizada en el proceso termodinámico, corresponde con la función objetivo del problema a resolver.
El procedimiento esquematizado en lafigura 1 visita el espacio de búsqueda del problema de optimización reduciendo gradualmente el valor de la función objetivo. A partir de una solución actual se visita una solución vecina la que siempre se acepta en el caso de ser mejor y se acepta eventualmente en el caso de ser peor que la actual respetando una función de probabilidades definidas en este caso como la función de probabilidad de...