Metaheurística

METAHEURISTICA, PROGRAMACION NO LINEAL
Y SUS APLICACIONES

Julián Alberto Garcés Hincapié 1088004897
Daniel Felipe Escobar Alvaran 1088279197
Samuel Sneider Molina 92112756266

Modelos Cuantitativos II

Universidad Tecnológica de Pereira
Pereira, Risaralda
Mayo de 2010

METAHEURISTICA

Es un método de solución general que proporciona tanto una estructura general como criteriosestratégicos para desarrollar un método heurístico específico que se ajuste a un tipo particular de problema.
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óncombinatoria, 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.
La Metaheurística es un tipo general de método de solución que organiza la interacción entre los procedimientos de mejora local y las estrategias de más alto nivel para crear un proceso que sea capaz de escapar de un óptimolocal y realizar una búsqueda vigorosa de una región factible.
En síntesis, la Metaheurística es una estrategia de alto nivel que guía a otras heurísticas para buscar soluciones factibles en dominios donde la tarea es compleja.
Entre las Metaheurísticas más conocidas están:
* La Búsqueda Tabú o Tabú Search
* El Enfriamiento simulado o Simulated Annealing
* Los Algoritmos genéticos oGenetic Algorithms
* Los Algoritmos meméticos (también conocidos como Algoritmos evolutivos) o Memetic Algorithms
* La Optimización aleatoria o Random Optimization
* La Búsqueda Tabú o Tabú Search
* La Búsqueda de primero el mejor o Best-first search
* La Optimización basada en colonias de hormigas o Ant colony optimization
* La Búsqueda local o Local search
* LosAlgoritmos voraces o Greedy algorithms
* La Ascensión de colinas o Hill-Climbing
* La Ascensión de colinas con reinicialización aleatoria o Random-restart hill climbing
* La Búsqueda por difusión estocástica o Stochastic Diffusion Search
* La Optimización extrema o Generalized extremal optimization
* La Inteligencia de enjambre o Swarm Intelligence
* La Búsqueda dearmonía o Harmony search
* Los Patrones Generales de Software para Asignación de Responsabilidades o GRASP (General Responsibility Assignment Software Patterns)

¿EN QUE CONSISTE LA METAHEURISTICA?
Para ilustrar la naturaleza y en qué consiste la Metaheurística, observaremos un ejemplo de un problema de programación lineal pequeño pero moderadamente difícil.
ZMAX=12x5- 975x4+ 28000x3-345000x2+ 1800000x
Sujeta a:
0≤x≤31
Se grafica la función objetivo sobre los valores factibles de la variable x. Esta gráfica revela que el problema tiene tres óptimos locales uno de en x=5, otro en x=20, y el tercero en x=31, donde el optimo global está en x=20.
La función objetivo es tan complicada que sería difícil determinar donde se encuentra el óptimo global sin el beneficio de observarla gráfica. Se podría usar el Cálculo, pero esto requeriría resolver una ecuación polinomial de cuarto grado (después de igualar a cero la primera derivada) para determinar que la función objetivo tiene óptimos locales múltiples en vez de un solo óptimo global.

Este es un ejemplo de programación no convexa, un tipo especial de programación no lineal que por lo general tiene óptimos localesmúltiples.
Para problemas de programación no lineal que perecen ser muy difíciles, como este, un método heurístico común es ejecutar un procedimiento de mejora local. Tal procedimiento comienza con una solución de prueba inicial y después, en cada iteración, busca en la vecindad de la solución de prueba para tratar de encontrar una solución mejor que la actual. Este proceso continua hasta que no...