Una regla de parada para la búsqueda con arranque múltiple

Resum

En un problema de optimización combinatoria, se pretende encontrar la solución o soluciones de la región factible, S, que optimizan una determinada función objetivo, f. Para funciones objetivo y/o regiones factibles que cumplan determinadas condiiciones, se conocen métoodos de solución que suministran soluciones óptimas o cercanas a las óptimas cuando el tamaño del problema es moderado. Sin embargo, existe una gran variedad de problemas cuyas componentes no cumplen las condiciones exigidas por los procedimentos de solución, o con tamaño relativamente grande. En estos casos, es útil disponer de procedimientos que sean robustos y eficientes. Entre los procedimientos que verifican estas características se encuentran los Algoritmos Genéticos, la Recristalización Simulada (Simulated Annealing), la Búsqueda Tabú (Tabú Search) y la Búsqueda con Arranque Múltiple (Mulstistart). El presente trabajo se dedica al estudio de la Búsqueda con Arranque Múltiple como método de solución de diversos problemas que surgen en muchos campos de la investigación científica, y, en particular, en la Informática. Asimismo, se propone una nueva regla de parada para el procedimiento basada en el número de iteracciones desarrolladas por el algoritmo.