Zusammenfassung der Ressource
Tipos de Metaheurísticas
- De Relajación
- Es un modelo simplificado obtenido al eliminar, debilitar o
modificar restricciones (u objetivos) del problema real.
- Son estrategias para el empleo de relajaciones
del problema en el diseño de heurísticas.
- Modifican elementos del problema para proponer la solución de las
modificaciones como solución heurística del problema original.
- Constructivas
- Aportan soluciones incorporando iterativamente elementos
a una estructura, que representa a la solución.
- Establecen estrategias para seleccionar las componentes
con las que se construye una buena solución del problema.
- Entre las metaheurísticas primitivas se encuentra: greedy
- GRASP
- Incorpora greedy con
pasos aleatorios,
adaptativos para la
selección de elementos de
la solución.
- De búsqueda
- Es el más importante
- Establece estrategias para recorrer el espacio de soluciones del
problema, transformando iterativamente soluciones de partida.
- Búsquedas monótonas
- Descendentes o ascendentes
- Algoritmos escaladores
- hill-climbing
- Búsquedas locales
- La mejora se obtiene en base al
análisis de soluciones similares a la
que realiza la búsqueda.
- Soluciones vecinas
- Basa su estrategia en el
estudio de soluciones del
vecindario o entorno de
la solución que realiza el
recorrido.
- Invonveniente: Quedan atrapadas
en un óptimo local, una solución que
no puede ser mejorada por un
análisis local.
- Búqueda Global
- Incorporan pautas para tres formas básicas de
escapar de los óptimos locales de baja calidad
- Búsqueda desde otra solución de arranque
- Modificar la estructura
- Permitir movimientos o transformaciones
de la solución de búsqueda
- Arranque múltiple
- Búsquedas descendentes
- Entorno Variable
- Modifican en forma sistemática el tipo de
movimiento para evitar un entorno rígido.
- Búsqueda no monótona
- Aplican movimientos de no mejora
durante el recorrido de búsqueda.
- Controlan los posibles movimientos de empeoramiento de la solución, mediante criterios.
- Criterios de aceptación
Estocásticos
- Establecen pautas para regular la probabilidad de
aceptar transformaciones que no mejores la solución
- Recorrido Simulado
- La probabilidad de aceptación es una función
exponencial del empeoramiento producido.
- Memoria del proceso
de búsqueda
- Utilizan información sobre el recorrido para evitar que la
búsqueda se concentre en una misma zona del espacio
- Evolutivas
- Establecen estrategias para conducir la evolución
en el espacio de conjuntos de soluciones
- Poblaciones
- Interacción entre los miembros de la población
frente a la información de soluciones individuales
- Otros
- Intermedios entre
relajación y constructivas
- De descomposición
- Establecen pautas para resolver un
problema determinando
subproblemas, construyendo una
solución al problema original
- De memoria a largo plazo
- Son capaces de emplear información obtenida
en la aplicación del procedimiento (a un
problema especíco o a un tipo o clase).
- Su objetivo es
obtener
subproblemas más
fáciles de resolver
que los originales y
con soluciones
efectivas