Algoritmo heurístico

¿Qué es un algoritmo? De la enumeración a la avaricia y a la heurística (Parte 1)

Objetivo: qué se debe optimizar

Decisión: decisión basada en el objetivo

Restricción: proceder Condiciones que se debe seguir al tomar decisiones

Ejemplo de cálculo: concretización de los parámetros del problema

Método de enumeración: enumerar todas las soluciones al problema una por una, evaluarlas una por una y seleccionar la mejor El bueno

1. El método de enumeración puede encontrar la solución óptima al problema

2. El tiempo de solución del método de enumeración aumenta explosivamente a medida que crece el tamaño del problema

Método codicioso: al utilizar el método de "construcción" para generar soluciones, la velocidad será relativamente muy rápida. Al mismo tiempo, no aumentará significativamente a medida que crezca el tamaño del problema. p>

¿Qué es el algoritmo? De la enumeración a la codiciosa a la heurística (Parte 2)

Algoritmo heurístico: obtenga una solución más satisfactoria dentro de un rango razonable de recursos de solución (tiempo razonable, sobrecarga de memoria razonable, etc.). En la actualidad, incluye principalmente dos categorías: búsqueda de barrio y biónica de grupo.

Espacio de soluciones: el conjunto de todas las soluciones al problema, incluidas las soluciones factibles y las inviables.

Búsqueda local: no atravesar completamente el espacio de soluciones, sino solo seleccionar una parte para atravesar, reduciendo así en gran medida la búsqueda de los recursos que necesita. Para mejorar la calidad de la búsqueda local, la mayoría de los algoritmos de búsqueda local capturarán continuamente múltiples áreas durante la búsqueda hasta que se cumplan las condiciones de terminación del algoritmo.

Barrio: un conjunto de soluciones bajo la definición de estructura de barrio. Es un concepto relativo, es decir, el barrio debe generarse en base a una determinada solución.

Solución de vecino: vecino El nombre de una solución en el dominio

Estructura de vecindad: define la vecindad de una solución

El diseño de la estructura de vecindad es muy importante en el algoritmo heurístico, determina directamente la resultados de búsqueda El alcance tiene un impacto importante en la estructura de búsqueda final y determina directamente la calidad de los resultados finales

Proceso de búsqueda

Repita los pasos 2 a 5 hasta que se cumpla la condición de terminación. Finalmente, se genera la solución óptima global.

Todas las heurísticas encontradas son soluciones satisfactorias y no se puede decir que sean soluciones óptimas (incluso si realmente lo son), porque atraviesan una parte local del espacio de soluciones.

Generalmente, el tiempo de un algoritmo heurístico aumenta linealmente con el tamaño del problema.

Consejos | ¿Quieres aprender algoritmos de optimización, pero no sabes por dónde empezar?

Clase de búsqueda de vecindario

Algoritmo de búsqueda local iterativo

Algoritmo de recocido simulado

Algoritmo de búsqueda de vecindario variable

Tabú búsqueda

Búsqueda adaptativa de grandes vecindarios

Biónica de enjambre

Algoritmo genético

Algoritmo de colonia de hormigas

Algoritmo de enjambre de partículas

Algoritmo de enjambre de peces artificiales

Aplicación de algoritmo

Algoritmo de búsqueda tabú para resolver el problema de rutas de vehículos con ventana de tiempo

La búsqueda de vecindario variable El algoritmo basado en representación de árbol resuelve el problema del viajante con consideraciones de último en entrar, primero en salir

El algoritmo de búsqueda de vecindad variable resuelve el problema de dispersión máxima-media

El algoritmo genético resuelve el problema Problema de programación de taller de flujo mixto