Métodos Heurísticos.

MÉTODOS HEURÍSTICOS

El término heurístico  proviene del griego heuriskein, que significa hallar ó inventar, es la técnica de la indagación y del descubrimiento o como la manera de buscar la

solución de un problema mediante métodos no rigurosos, es decir sin atajos.

En ciencia, es la idea más general está relacionada con la tarea de resolver inteligentemente problemas reales empleando el conocimiento adquirido

Cuando se desarrollan algoritmos heurísticos, es importante evaluar que el mismo sea eficiente, bueno (

y robusto, para lo cual se pueden emplear procedimientos tales como:

• comparación con la solución óptima
• comparación con una cota
• comparación con un método exacto truncado
• comparación con otros heurísticos y análisis del peor caso  

Debido a la naturaleza tan diversa de los métodos heurísticos, señalan que resulta difícil dar una clasificación completa de los mismos y plantea un conjunto de categorías en las que se pueden ubicar los principales métodos desarrollados. Estos son:

• Métodos de descomposición: el problema se descompone en subproblemas más fáciles de resolver.
• Métodos inductivos: busca generalizar propiedades o técnicas identificadas de casos más pequeños y sencillos, al problema complejo o general.
• Métodos de reducción: tienen como propósito restringir o reducir el espacio de soluciones, simplificando así el problema.
• Métodos constructivos: se basan en la construcción progresiva de una solución del problema, mediante la selección de la mejor opción en iteraciones sucesivas. Dentro de ellos se pueden mencionar:

• heurísticos del vecino más próximo.
• heurísticos de inserción.
• heurísticos basados en árboles generadores.
•  heurísticos basados en ahorros.

• Métodos de búsqueda local: se caracterizan por iniciar con una solución del problema, la cual debe ser mejorada progresivamente a lo largo del procedimiento. Dentro de esta categoría se pueden mencionar:

• procedimientos de dos intercambio
• procedimientos de  intercambio y algoritmo de Lin y Kernighan.

• Métodos combinados: De todos los métodos mencionados hasta el momento, los métodos constructivos y los métodos de búsqueda local merecen especial atención, debido a que su combinación ha permitido el surgimiento de nuevos métodos heurísticos, llamados métodos combinados y que constituyen el eslabón entre los métodos heurísticos y las metaheurísticas.

 Dentro de estos métodos combinados se pueden mencionar:

• Procedimientos aleatorizados
• Métodos
• Multi-arranque
• GRASP (Greedy Randomized Adaptive Search Procedures).

METAHEURÍSTICAS
La metaheurística nace con el propósito de evitar tener que comenzar de cero cada vez que se presente un problema cuyo modelo no puede ser tratado por los métodos convencionales, para encontrar una solución óptima.[pic 1]

...