Optimización combinatoria

LOS'optimización combinatoria, también llamado optimización discreta, es una rama de la optimización en matemáticas aplicadas e informática, también relacionada con la investigación de operaciones, los algoritmos y la teoría de la complejidad. La optimización combinatoria consiste en encontrar en un conjunto un subconjunto que contenga las “mejores soluciones”.

Encontrar una solución óptima en un conjunto discreto y finito es un problema fácil en teoría: solo tienes que probar todas las soluciones y comparar sus cualidades para ver la mejor. Sin embargo, la explosión combinatoria de posibles soluciones de ciertos problemas matemáticos no permite obtener una solución en un tiempo "humano".

Algunos problemas de optimización combinatoria se pueden resolver (exactamente) en tiempo polinomial, por ejemplo mediante un algoritmo programación dinámica o demostrando que el problema puede formularse como un problema de optimización lineal en variables reales. En la mayoría de los casos, el problema es Np-difícil y, para solucionarlo, se deben utilizar algoritmos adecuados.

En la práctica, la complejidad físicamente aceptable es a menudo solo polinomial. Entonces estamos satisfechos con tener una solución aproximada en el mejor de los casos, obtenida por una heurística o una metaheurística. Es importante señalar que algunos de estos métodos proporcionan óptimos globales, la diferencia con los métodos exactos es el hecho de no tener una prueba formal (prueba matemática o de finalidad) de su optimalidad global.

Árbol de soluciones

Es decir mi todas las soluciones a los problemas. Se supone que es discreto y finito. La enumeración de soluciones está representada por árbol. todos los elementos de mi están separados en no subconjunto no vacío disjunto, cada uno de los cuales contiene una parte del conjunto de soluciones. Por ejemplo, el conjunto se puede dividir en dos en el problema de la mochila, tomemos o no un elemento x_k en el bolso.

La operación se puede repetir para cada subconjunto hasta que cada conjunto contenga solo un elemento. En el ejemplo de la mochila, cada subconjunto se separa hasta que se toma una decisión sobre el último elemento.

La raíz del árbol es mi, los cables son los subconjuntos, etc. como se muestra en el siguiente diagrama:

Técnicas de resolución

Exacto

Estos métodos dan una garantía para encontrar la solución óptima para una instancia de tamaño finito en un tiempo limitado y para demostrar su optimalidad.

Heurístico

Cuando la complejidad de un problema es exponencial o presenta una explosión combinatoria, se recomienda el uso de heurísticas. Este es un método que proporciona rápidamente una "buena" solución al problema. Esta solución aproximada puede proporcionar un punto de partida para utilizar un método exacto (como la esquina noroeste para el problema del transporte). Todos los algoritmos codiciosos e ingenuos son heurísticos.

Cabe señalar que las heurísticas están diseñadas para resolver un problema dado y no pueden usarse en otras condiciones a diferencia de las metaheurísticas. Las heurísticas se evalúan según tres criterios:

1. Calidad del resultado: la heurística se enfrenta a los resultados óptimos para un conjunto de valores del problema dado (hablamos de benchmark). La calidad de la solución puede ser una distancia a la solución óptima o una probabilidad de alcanzarla.
2. Costo de la heurística: complejidad en el tiempo y el espacio.
3. Campo de aplicación: el campo de admisibilidad de todas las variables.

Las heurísticas para un problema dado son numerosas, por lo que es importante proporcionar una rápida y proporcionar "buenos" resultados.

Metaheurístico

Las metaheurísticas tienen un mayor nivel de abstracción que las heurísticas, ya que es un método que puede adaptarse a un problema dado. Así, los métodos se pueden aplicar a diversos problemas (en forma de caja negra) sin modificar su funcionamiento. También hablamos de heurística generalista.

Hay dos tipos de metaheurísticas: población (Para) o curso (B). La mayoría de los algoritmos no tienen una población determinada, por lo que es posible utilizar el algoritmo para una ruta o una población.

Ambos tipos funcionan con el mismo proceso de cuatro pasos:

1. Vecindario : la vecindad de una solución es un subconjunto de soluciones que pueden alcanzarse mediante una transformación de la solución inicial (por permutación, por extensión, por mutación, por eyección, etc.).
2. Exploración : la exploración consiste en recopilar datos de todo el barrio.
3. Operación : la operación utiliza la información recolectada para definir las áreas de “interés” del área de investigación que forma el barrio.
4. Memoria : la memoria tiene en cuenta el aprendizaje y permite determinar las zonas susceptibles de tener un óptimo global. Si las nuevas soluciones o los criterios de parada ya no permiten mejorar la solución, el algoritmo se detiene. De lo contrario, regrese al paso 1. Ciertos algoritmos solo funcionan con criterios de detención, por lo que estamos hablando de metaheurísticas sin memoria.