Loading AI tools
De Wikipedia, la enciclopedia libre
La optimización combinatoria es una rama de la optimización en matemáticas aplicadas y en ciencias de la computación, relacionada con la investigación de operaciones, Teoría algorítmica de la información y teoría de la complejidad computacional. También está relacionada con otros campos, como la inteligencia artificial e ingeniería de software. Los algoritmos de optimización combinatoria resuelven instancias de problemas que se creen ser difíciles en general, explorando el espacio de soluciones (usualmente grande) para estas instancias. Los algoritmos de optimización combinatoria logran esto reduciendo el tamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente.
Los algoritmos de optimización combinatoria a menudo son implementados en lenguajes imperativos como C y C++ entre otros softwares inteligentes en lenguajes de programación lógicos tales como Prolog, o incluso en lenguajes multi-paradigma tales como Oz.
Mediante el estudio de la teoría de la complejidad computacional es posible comprender la importancia de la optimización combinatoria. Los algoritmos de optimización combinatoria se relacionan comúnmente con problemas NP-hard. Dichos problemas en general no son resueltos eficientemente, sin embargo, varias aproximaciones de la teoría de la complejidad sugieren que ciertas instancias (ej. "pequeñas" instancias) de estos problemas pueden ser resueltas eficientemente. Dichas instancias a menudo tienen ramificaciones prácticas muy importantes.
Una instancia de un problema de optimización combinatoria puede ser descrito formalmente como una tupla donde
Un problema de optimización combinatoria se define como aquel en el que el conjunto de soluciones posibles es discreto. En otras palabras, se trata de un problema de optimización que involucra una cantidad finita o numerable de soluciones posibles.
Este tipo de problemas se diferencia de los problemas de optimización continuos, en los cuales el conjunto de soluciones posibles es infinito e incontable. Esta rama de la optimización se relaciona estrechamente con la investigación operativa, la teoría algorítmica y la teoría de la complejidad computacional. Los algoritmos de optimización combinatoria resuelven problemas que, en general, se consideran difíciles al explorar el amplio espacio de soluciones del problema en cuestión. Los buenos algoritmos de optimización combinatoria logran reducir el tamaño efectivo del espacio de búsqueda y explorarlo de manera eficiente.
Aquí entran los algoritmos de optimización combinatoria. Éstos son capaces de resolver problemas que suelen ser considerados difíciles, ya que exploran un amplio espacio de soluciones. Para lograrlo, estos algoritmos reducen efectivamente el tamaño del espacio y lo exploran de manera eficiente.
En el campo de la optimización combinatoria, es común que la mayoría de los procesos de resolución de problemas no puedan garantizar la solución óptima, incluso dentro del contexto del modelo que se esté utilizando. Sin embargo, la aproximación al óptimo suele ser suficiente para resolver los problemas en la práctica.
Existen diferentes métodos de resolución que pueden ser clasificados en cuatro grandes grupos:
Los métodos más comunes utilizados para resolver problemas en optimización combinatoria son heurísticos o metaheurísticos. Estos métodos son capaces de generar soluciones para el problema, aunque sean aproximaciones que no necesariamente alcancen la solución óptima.
En los primeros días de la Investigación Operativa, las limitaciones de cálculo automático llevaron a la creación de procedimientos heurísticos que pudieran encontrar soluciones de manera rápida, aunque no necesariamente las mejores.
Aunque los métodos heurísticos de resolución no pueden garantizar la solución óptima, son fundamentales por varias razones. En primer lugar, son capaces de generar soluciones, lo cual es mejor que no tener ninguna solución. En segundo lugar, obtener la solución óptima para un modelo que no representa exactamente el problema real no es necesariamente esencial. Por último, diseñar una buena heurística exige un conocimiento profundo del problema, lo cual puede conducir a mejoras de otro tipo.
Por lo tanto, los métodos heurísticos, incluyendo los procesos de mejora local y los algoritmos metaheurísticos, son herramientas valiosas para resolver problemas de optimización combinatoria en la práctica.
En esta categoría se encuentran problemas como:
Los métodos de búsqueda heurísticos (algoritmos metaheuristicos) como los listados abajo han sido usados para resolver problemas de este tipo.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.