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.
