Algoritmos heurísticos y de búsqueda local

¿Qué es una heurística en un algoritmo heurístico?

• Un proceso que no garantiza obtener la solución óptima del problema

• Un proceso de toma de decisiones basado en experiencias previas en problemas similares

• Un método que puede simular procesos de la naturaleza

• Un algoritmo que busca un tiempo acotado de ejecución

• Todos los anteriores

¿Cómo se define la función de vecindario en un algoritmo de búsqueda local?

• Calcula la distancia entre dos estados en el grafo de estados

• Define los posibles estados sucesores para un estado determinado

• Selecciona el estado con el menor costo

• Determina el estado inicial del problema

¿En qué consiste la búsqueda local en los algoritmos heurísticos?

• Evaluar todas las posibles soluciones locales para la elección de un estado sucesor

• Seleccionar un estado dentro del conjunto de soluciones adyacentes al estado actual del problema

• Seleccionar aleatoriamente un estado inicial e iterar mediante una elección randomizada el estado sucesor que sea local al actual

• Generar y probar diferentes soluciones mediante cambios locales aplicados en la función generativa

La aproximación de múltiple inicio corresponde a ...

• realizar varias ejecuciones del algoritmo modificando el estado inicial

• ejecutar varias veces el algoritmo pero modificando la función de vecindario

• construir el estado inicial de exploración mediante un algoritmo de aproximación

• permitir que el algoritmo tenga múltiples estados iniciales para seleccionar un subconjunto de estos en cada iteración

En Hill Climbing el concepto "ascenso más empinado" se refiere a:

• La utilización de la estrategia de first improvement

• El proceso que permite escapar de un máximo local para llegar al máximo global

• una variable del problema que permite definir el tamaño del subconjunto de estado vecinos a analizar

• Todas las opciones son correctas

• Ninguna de las opciones

¿Qué característica distingue al algoritmo Threshold Accepting?

• Permite seleccionar circunstancialmente una solución de menor valor de función costo al valor actual

• Utiliza una función de vecindario determinística cuyo tamaño disminuye por cada iteración del algoritmo

• Explora un subconjunto de vecinos del estado actual no superando un umbral para seleccionar el siguiente estado

• Rechaza cualquier estado que no aumente cierto umbral de la función costo actual

La técnica de Simulated Annealing ...

• Realiza una exploración exhaustiva de los estados vecinos

• Restringe la elección a estados de soluciones factibles que son mejores al mejor encontrado hasta el momento

• Utiliza un esquema de enfriamiento que ayuda en la atenuación del calculo de la función costo

• Utiliza una probabilidad decreciente para seleccionar estados de menor función costo que el estado actual

• Todos los anteriores

¿Qué representa la palabra 'Tabú' en la metodología de Búsqueda Tabú?

• Una creencia religiosa de pueblos polinesios y una conducta inmoral o inaceptable para un grupo de personas

• La exclusión de estados solución previamente visitados para evitar la generación de ciclos en la exploración del grafo de estados

• A las condiciones del nivel de aspiración que se aplican al cálculo de la función costo

• Una restricción en los movimientos entre estados establecido por el historial de los estados previamente visitados

¿Cuál es la función de la intensificación en la metodología de Búsqueda Tabú?

• Penalizar los movimientos más visitados para diversificar la búsqueda

• Favorecer la selección de movimientos previamente realizados que brindaron buenos resultados

• Evitar la exploración de estados previamente visitados

• Incrementar la cantidad de movimientos tabú permitidos

Cual de los siguientes conceptos NO pertenece a los algoritmos genéticos

• elitismo

• gen

• alelo

• locus

• diversificación