Tipos de Metaheurísticas

Description

Investigación de Operaciones Mind Map on Tipos de Metaheurísticas, created by Lizzi_Flor on 02/10/2013.
Lizzi_Flor
Mind Map by Lizzi_Flor, updated more than 1 year ago
Lizzi_Flor
Created by Lizzi_Flor over 10 years ago
21
0

Resource summary

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

                                                    Similar

                                                    Investigación de Operaciones
                                                    neneeduardo
                                                    INVESTIGACION DE OPERACIONES
                                                    Maryan Acuña
                                                    Programación No Lineal.
                                                    kayzer01
                                                    HISTORIA INVESTIGACION DE OPERACIONES
                                                    Maryan Acuña
                                                    Sistema de líneas de espera
                                                    kayzer01
                                                    Jesus Garcia
                                                    jesus nestor garcia
                                                    Modelos de Inventarios
                                                    kayzer01
                                                    Interpretación Económica de la dualidad
                                                    JORGE GARCIA BONILLA
                                                    Procesos Estocásticos
                                                    María Fernanda Bonelli Márquez
                                                    Aplicacion de la simulacion de Monte Carlo en el calculo de riesgo usando Excel
                                                    Gleidy Sairitupac Condori
                                                    Investigación de Operaciones
                                                    Marlene Velasco