Optimización combinatoria

LOS'optimización combinatoria, también llamado optimización discreta, es una rama de la optimización en matemáticas aplicadas y ciencias de la computación, 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: basta probar todas las soluciones y comparar sus cualidades para encontrar la mejor. Sin embargo, la explosión combinatoria de posibles soluciones de determinados problemas matemáticos no permite obtener una solución en 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 suele ser solo polinomial. Entonces estamos satisfechos con tener una mejor solución aproximada, obtenida por una heurística o una meta-heurí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 ninguna prueba formal (matemática o prueba de finalidad) de su optimización 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 disjunto no vacío, 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, ya sea que tomemos o no un elemento x_k en el bolso.

La operación puede repetirse para cada subconjunto hasta que cada conjunto contenga un solo elemento. Para el ejemplo de la mochila, se separa cada subconjunto hasta llegar a la 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 usar un método exacto (como la esquina noroeste para el problema de transporte). Todos los algoritmos codiciosos e ingenuos son heurísticos.

Cabe señalar que las heurísticas se construyen para resolver un problema determinado y no se pueden usar en otras condiciones a diferencia de las metaheurísticas. La heurística se evalúa según tres criterios:

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

La cantidad de heurísticas para un problema dado es numerosa, por lo que es importante proporcionar una que sea rápida y proporcione "buenos" resultados.

Metaheurístico

Las meta-heurísticas tienen un mayor nivel de abstracción que las heurísticas ya que son métodos que se pueden adaptar a un problema dado. Así, los métodos se pueden aplicar a varios problemas (en forma de caja negra) sin modificar su funcionamiento. Hablamos también de heurísticas generales.

Hay dos tipos de metaheurísticas: población (Para) o curso (B). La mayoría de los algoritmos no tienen una población determinada, entonces es posible usar el algoritmo para un curso 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 alcanzables por 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 recoger datos de todo el barrio.
3. Operación : la explotación utiliza la información recopilada para definir las áreas "interesantes" del espacio de búsqueda formado por el barrio.
4. Memoria : la memoria tiene en cuenta el aprendizaje y permite determinar las áreas 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. Algunos algoritmos solo funcionan con criterios de parada, entonces hablamos de metaheurísticas sin memoria.