Implementación y análisis de metaheurísticos de optimizaicón combinatoria sobre redes P2P

Abstract

La mayoría de los problemas de optimización combinatoria tienen un difícil tratamiento computacional porque los algoritmos que los solucionan lo realizan en tiempo no polinómico, puesto que existe una relación de estos con la clase de problemas NP-ardua. Debido a que esta situación parece insalvable, a no ser que P=NP, se han desarrollado una serie de métodos genéricos que se aproximan a las soluciones del problema en un tiempo asequible; llamados metaheurísticos. El representante de los problemas de optimización combinatoria es el problema del viajante de comercio (TSP, siglas en inglés). Los problemas complejos suelen tratarse a través de la computación distribuida. Estos sistemas suelen tener un coste muy elevado por la gran envergadura de su infraestructura. Sin embargo, las redes P2P han posibilitado desplegarlos fácilmente a bajo coste, dando origen a la computación voluntaria. Veremos la implementación de algunos metaheurísticos para el problema del viajante de comercio para ser ejecutados en un simulador de redes P2P para observar su comportamiento. Los experimentos, que se han ejecutado en el simulador, han generado una serie de datos, los cuales se han incorporado a este trabajo para su análisis.