Tesis doctoral de Dotu Rodríguez Iván Javier
La optimización combinatoria es una rama de la optimización en matemática aplicada y de la informática, relacionada con la investigación operativa, la teoría de algoritmos y la teoría de complejidad computacional, que se encuentra en la intersección de varios campos, tales como la inteligencia artificial, las matemáticas y la ingeniería del software. Los problemas de optimización combinatoria suelen consistir en encontrar valores para un conjunto de variables que están restringidas por un conjunto de restricciones, en algunos casos para optimizar una función dada (optimización) y en otros tan solo para encontrar una solución válida (satisfacción). Los algoritmos de optimización combinatoria resuelven instancias de problemas considerados difíciles en general gracias a una exploración inteligente del espacio de búsqueda, en parte reduciéndolo de una forma eficiente. en esta tesis nos centramos en los algoritmos de optimización combinatoria que se consideran entro del campo de la inteligencia artificial (aunque es cierto que la línea que lo separa del campo de la investigación operativa es muy fina), en vez de en algoritmo de investigación operativa. así pues, métodos como la programación entera o el «branch-and-bound» no van a ser tratados. El objetivo de esta tesis es mostrar que diferentes técnicas pueden ser más adecuadas para diferentes problemas, y que técnicas híbridas que incluyen mecanismos de diferentes paradigmas se pueden beneficiar de las ventajas e intentar minimizar los inconvenientes de los mismos. Todo esto se muestra en esta tesis con la resolución de problemas difíciles de optimización combinatoria como complenitud de cuasigrupos, golfistas social, golomb rulers, usando varias técnicas, que dan lugar al desarrollo de un algoritmo híbrido para encontrar golomb rulers, que incorpora aspectos de algoritmos genéticos, búsqueda local, rogramación con restricciones e incluso clustering.
Datos académicos de la tesis doctoral «Towards hybrid methods for solving hard combinatorial optimization problems«
- Título de la tesis: Towards hybrid methods for solving hard combinatorial optimization problems
- Autor: Dotu Rodríguez Iván Javier
- Universidad: Autónoma de Madrid
- Fecha de lectura de la tesis: 04/09/2006
Dirección y tribunal
- Director de la tesis
- Del Val Latorre álvaro
- Tribunal
- Presidente del tribunal: roberto Moriyón
- Antonio Fernandez (vocal)
- pedro Messeguer (vocal)
- Carlos Ansótegui (vocal)