Enunciado
Contents
1. Universidad Sim n Bol var Departamento de Computaci n y Tecnolog a de la Informaci n CI 56512 Dise o de Algoritmos I Trimestre Abril Julio 2012 Proyectol Resolviendo el Symmetric Traveling Salesman Problem 1 Planteamiento del Problema Se desea que implemente un software que encuentre soluciones de alta calidad y con un esfuerzo computacional adecuado para el Symmetric Traveling Salesman Problem La informaci n sobre el Symmetric Traveling Salesman Problem STSP la puede obtener del libro The traveling salesman problem and its variations de Gutin y Punnen 2 Se quiere resuelva este problema implementando un algoritmo heur stico que est basado en alguno de estos tres m todos Iterated Hill Climber Stochastic hill climber 4 Simulated annealing La implementaci n de su programa debe hacerse usando alguno de estos tres lenguajes de programaci n C C JAVA Para probar su algoritmo debe hacer uso de cuatro instancias bien conocidas del STSP que son eil51 kroA100 d198 y rat783 Estas instancias y su valor ptimo se encuentran en la p gina web TSPLIB 5 la cual es dep sito de instancias e informaci n del Traveling Salesman Problem Su programa debe recibir como una de sus entradas el archivo con la instancia tal como se encuentra en TSPLIB sin modificar su formato Al finalizar la ejecuci n su programa debe mostrar por la salida est ndar cuatro elementos el orden en que son visitadas las ciudades tour la dist2. ancia del recorrido el n mero de iteraciones del algoritmo que resuelve el STSP y el tiempo de ejecuci n del algoritmo en segundos Tambi n puede mostrar por la salida est ndar cualquier otra informaci n que considere relevante Adem s del programa que resuelve el Symmetric Traveling Salesman Problem debe realizar un informe que contenga los siguientes secciones Portada a Introducci n 1 Motivaci n del proyecto 2 Breve descripci n del problema 3 Descripci n del contenido del informe Algoritmo para el STSP Debe describir de manera clara y precisa el algoritmo que dise o para resolver el STSP La idea es que cualquier profesional competente en ciencias de la computaci n que lea esta secci n debe ser capaz de implementar la heur stica que usted desarroll y de reproducir los resultados que usted obtuvo Debido a esto la secci n deber a contener por lo menos 1 Las estructuras de datos usadas para representar el problema y otras que considere importantes 2 La descripci n de los principales algoritmos para resolver el problema Preferiblemente debe mostrar el pseudoc digo de esos algoritmos 3 Los par metros que usa su algoritmo y la justificaci n de los mismos Por ejemplo la condici n de parada el valor de la temperatura en el caso de usar Simulated annealing etc 4 Cualquier otra informaci n que usted considere relevante para la implementaci n del algoritmo Debe justificar y explicar el dis
3. distancia promedio de la heur stica con respecto a la soluci n ptima Desviaci n est ndar del valor promedio de la heur stica Distancia de la mejor soluci n obtenida en las 10 corridas de la heur stica N mero de ocurrencias de la mejor soluci n en las 10 corridas de la heur stica La segunda tabla debe mostrar los siguentes resultados Nombre de la instancia Distancia de la soluci n ptima Distancia de la mejor soluci n obtenida en las 10 corridas de la heur stica Porcentaje de desviaci n de la mejor soluci n de la heur stica con respecto a la soluci n ptima Tiempo promedio de las 10 corridas de la heur sticas en segundos Tambi n puede incluir cualquier otra tabla o gr fico que considere relevante El porcentaje de desviaci n de una soluci n de la heur stica con respecto a la soluci n ptima se calcula con la siguiente f rmula a x 100 Las pruebas las puede realizar en cualquier computador En el informe debe indicar las caracter sticas del mismo el modelo de procesador la velocidad del reloj del procesador la memoria RAM del sistema y el sistema de operaci n instalado Su aplicaci n debe poder instalarse y ejecutarse en un equipo del LDC Se les proporcionar de implementaciones de los algoritmos de b squeda local para el STSP 2 opt y 3 opt 3 que puede usar en su software si as lo requiere 2 Sobre la entrega Este proyecto es individual y tiene un valor de 20 de la nota
4. e o de su soluci n Instrucciones de operaci n Descripci n detallada de como compilar y correr su aplicaci n as como el estado actual de la misma Resultados Experimentales y Discusi n Ver indicaciones m s adelante Conclusiones y Recomendaciones Referencias bibliogr ficas En cuanto a la secci n de Resultados Experimentales y Discusi n se desea hacer un estudio experimental que permita caracterizar el rendimiento de la soluci n algor tmica propuesta por usted Seg n Barr et al 1 la evaluaci n experimental de una heur stica deber a tomar en cuenta tres aspectos principales Calidad de la soluciones que son obtenidas El objetivo de este punto es ver qu tan cercanos son los valores obtenidos de los valores ptimos Esfuerzo computacional El tiempo de c mputo que debe ser invertido para obtener soluciones factibles de alta calidad Robustez y fiabilidad Es la habilidad de la heur stica de obtener buenos resultados en una amplia gama de problemas y sin necesidad de tener que realizar demasiados ajustes en la configuraci n de los par metros del algoritmo En este proyecto se debe evaluar el m todo heur stico implementado bajo la ptica de los tres puntos expuestos anteriormente Debe presentar dos tablas de resultados experimentales La primera tabla debe tener los siguientes datos Nombre de la instancia Distancia promedio de 10 corridas de la heur stica Porcentaje de desviaci n de la
5. final La fecha l mite de entrega es el d a viernes 18 de mayo de 2012 hasta las 11 30 pm Debe entregar el informe del proyecto y un archivo tar gz con el c digo del proyecto 3 Consideraciones Finales Cualquier error que sea hallado en este enunciado as como cualquier tipo de observaci n adicional sobre el proyecto ser n publicadas como fe de erratas en la p gina web del curso Es responsabilidad de los alumnos revisar peri dicamente la misma No debe haber copia ni intercambio de informaci n espec fica ni ayuda detallada entre los alumnos del curso El incurrir en cualquiera de las acciones descritas anteriormente tendr co mo consecuencia sanciones severas Referencias 1 Barr R GOLDEN B KELLY J RESENDE M AND STEWART W Designing and report ing on computational experiments with heuristic methods Journal of Heuristics 1 1 1995 9 32 2 GUTIN G AND PUNNEN A The traveling salesman problem and its variations vol 12 Kluwer Academic Pub 2002 3 Hoos H AND ST TZLE T Stochastic local search Foundations and applications Morgan Kaufmann 2005 4 MICHALEWICZ Z AND FOGEL D How to solve it modern heuristics Springer Verlag New York Inc 2000 5 REINELT G Tsplib http comopt ifi uni heidelberg de software TSPLIB95 2012
Download Pdf Manuals
Related Search
Enunciado enunciado enunciado significado enunciado de aa enunciados fonaje enunciados cortos enunciados cjf enunciado del problema enunciados ejemplos enunciado bimembre enunciado que es enunciado 97 do fonaje enunciado no oracional enunciado 90 do fonaje enunciado 117 do fonaje enunciado 10 do fonaje enunciado de la ley de ohm enunciado aclarador access consciousness enunciados oracionales y no oracionales enunciado del alcance del proyecto enunciado de la ley de coulomb enunciado de la primera ley de newton