Metaheuristica

DISTRIBUCIÓN Y TRANSPORTE


TRABAJO DE METAHEURÍSITCAS















FRANCY JOHANNA SÁNCHEZ BUITRAGO
PEDRO GARCÍA





PRESENTADO: INGENIERO EVER FUENTES






UNIVERSIDAD LIBRE
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA INDUSTRIAL





BOGOTA D.C.
2010






INTRODUCCION





Existen problemas de optimización combinatoria complejosen diversos campos como la economía, el comercio, la ingeniería, la industria o la medicina la genética, la biología, la inteligencia artificial, las matemáticas, la física y la neurología, entre otras. Sin embargo, a menudo estos problemas son muy difíciles de resolver en la práctica; las metaheurísticas incorporan conceptos y estudian la dificultad de muchos estos problemas brindando opciones,alternativas, soluciones y respuestas.































1. OBJETIVOS

• El objetivo principal del trabajo es presentar la metaheurística, remarcando las principales características que la distinguen.

• El trabajo pretende detectar posibles líneas para investigaciones fructíferos de aplicación.

• Conocer la historia de lasmetaheurísticas, sus aplicaciones, clasificaciones en los diferentes campos.













































































Metaheurística




Una metaheurística es un método heurístico para resolver un tipo de problema computacional general, usando los parámetros dados por el usuario sobreunos procedimientos genéricos y abstractos de una manera que se espera eficiente. Normalmente, estos procedimientos son heurísticos. El nombre combina el prefijo griego "meta" ("más allá", aquí con el sentido de "nivel superior") y "heurístico" (de eυριsκeιν, heuriskein, "encontrar").
Las metaheurísticas generalmente se aplican a problemas que no tienen un algoritmo o heurística específica que déuna solución satisfactoria; o bien cuando no es posible implementar ese método óptimo. La mayoría de las metaheurísticas tienen como objetivo los problemas de optimización combinatoria, pero por supuesto, se pueden aplicar a cualquier problema que se pueda reformular en términos heurísticos, por ejemplo en resolución de ecuaciones booleanas. Las metaheurísticas no son la panacea y suelen sermenos eficientes que las heurísticas específicas, en varios órdenes de magnitud, en problemas que aceptan este tipo de heurísticas crudas.

3.1. Conceptos generales y nomenclatura

El objetivo de la optimización combinatoria es encontrar un objeto matemático finito (por ejemplo, un vector de bits o permutación) que maximice (o minimice, dependiendo del problema) una función especificada por elusuario de la metaheurística. A estos objetos se les suele llamar estados, y al conjunto de todos los estados candidatos se le llama espacio de búsqueda. La naturaleza de los estados y del espacio de búsqueda son usualmente específicos del problema.
La función a optimizar se le llama función objetivo, y se da al usuario como un procedimiento caja-negra que evalúa el estado actual o la función.Dependiendo de la metaheurística, el usuario puede tener que dar otras funciones caja-negra que produzcan un nuevo estado, generan variantes del estado actual, elijan un estado entre varios, aporten valores máximos o mínimos para la función objetivo en un conjunto de estados, y en ese estilo.



Algunas metaheurísticas mantienen en cada instante de ejecución un único estado actual, y lo cambian encada iteración por uno nuevo. Este paso básico se conoce como transición de estado, movimiento o actualización del estado. El movimiento es colina arriba o colina abajo dependiendo de si los valores que da la función objetivo se incrementa o se decrementa. El nuevo estado puede estar construido desde la nada por un generador de estados dado por el usuario. Alternativamente, el nuevo estado puede...