Towards hybrid methods for solving hard combinatorial optimization problems
Iván Javier Dotu Rodríguez · 2006
La Optimizacion Combinatoria es una rama de la optimizacion en matematica aplicada y de la informatica, relacionada con la investigacion operativa, la teoria de algoritmos y la teoria de complejidad computacional, que se encuentra en la interseccion de varios campos, tales como la inteligencia artificial, las matematicas y la ingenieria del software, Los problemas de optimizacion combinatoria suelen consistir en encontrar valores para un conjunto de variables que estan restringidas por un conjunto de restricciones, en algunos casos para optimizar una funcion dada (optimizacion) y en otros tan solo para encontrar una solucion valida (satisfaccion). Los algoritmos de optimizacion combinatoria resuelven instancias de problemas considerados dificiles en general gracias a una exploracion inteligente del espacio de busqueda, en parte reduciendolo de una forma eficiente. En esta tesis nos centramos en los algoritmos de optimizacion combinatoria que se consideran entro del campo de la Inteligencia Artificial (aunque es cierto que la linea que lo separa del campo de la investigacion operativa es muy fina), en vez de en algoritmo de investigacion operativa. Asi pues, metodos como la programacion entera o el Branch-and-Bound no van a ser tratados. El objetivo de esta tesis es mostrar que diferentes tecnicas pueden ser mas adecuadas para diferentes problemas, y que tecnicas hibridas 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 resolucion de problemas dificiles de optimizacion combinatoria como complenitud de cuasigrupos, golfistas social, Golomb rulers, usando varias tecnicas, que dan lugar al desarrollo de un algoritmo hibrido para encontrar Golomb rulers, que incorpora aspectos de algoritmos geneticos, busqueda local, rogramacion con restricciones e incluso clustering.