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 II Trimestre Abril Julio 2012 Proyecto 3 Resolviendo el CVRP con Metaheur sticas Poblacionales 1 Planteamiento del Problema Con este proyecto se quiere ampliar el estudio sobre Capacited Vehicle Routing Problem CVRP hecho en el segundo proyecto En espec fico el objetivo del proyecto es que usted dise e e implemente un algoritmo heur stico que resuelva el CVRP que este basado en alguna de estas metaheur sticas poblacionales Ant Colony Systems Scatter Search Path Relinking Algoritmos Gen ticos o en Algoritmos Mem ticos La implementaci n de su programa debe hacerse usando alguno de estos tres lenguajes de programaci n C C JAVA Las instancias con las que debe probar su algoritmo son las mismas del proyecto pasado Las informaci n de la salida del programa es la misma que se indic en el proyecto pasado Adem s del programa que resuelve el CVRP 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 CVRP Debe describir de manera clara y precisa el algoritmo que dise o para resolver el CVRP 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 st2. ica 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 4 Cualquier otra informaci n que usted considere relevante para la implementaci n del algoritmo Debe justificar y explicar el dise 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 a 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 Tambi n se quiere comparar el resultado de su metaheur stica poblacional con el resultado obtenido por su metaheur stica de trayectoria del proyecto 2 Se debe hacer un an lisis de los resultados de las dos metaheur sticas indicando con cual se obtienen soluciones de mejor calidad si hay problemas en los cuales una heur stica en mejor que otra el tiempo de c mputo empleado p
3. nstalado Su aplicaci n debe poder instalarse y ejecutarse en un equipo del LDC 2 Sobre la entrega Este proyecto es en equipos de m ximo dos personas y tiene un valor de 35 de la nota final La entrega del proyecto es hasta el d a jueves 12 de julio de 2012 a las 3 30 pm Debe entregar el informe del proyecto impreso y por email un archivo tar gz con el c digo del proyecto En caso de no encontrar al encargado del curso en su oficina puede dejar el informe en su casillero en el Departamento de Computaci n o introducirlo debajo de la puerta de su oficina 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
4. or ambas la dificultad de la implementaci n y la afinaci n de ambos algoritmos y cualquier otro aspecto que considere relevante Tambi n debe presentar dos tablas de resultados experimentales La primera tabla debe tener los siguiente datos Nombre de la instancia Distancia promedio de 5 corridas de la heur stica Porcentaje de desviaci n de la 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 5 corridas de la heur stica N mero de ocurrencias de la mejor soluci n en las 5 corridas de la heur stica La segunda tabla debe mostrar los siguientes resultados Nombre de la instancia Distancia de la soluci n ptima Porcentaje de desviaci n de la mejor soluci n de la heur stica del proyecto 2 con respecto a la soluci n ptima Porcentaje de desviaci n de la mejor soluci n de la heur stica con respecto a la soluci n ptima Tiempo promedio de las 5 corridas de la heur stica del proyecto 2 en segundos Tiempo promedio de las 5 corridas de la heur sticas en segundos Tambi n puede incluir cualquier otra tabla o gr fico que considere relevante 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 i
Download Pdf Manuals
Related Search
Enunciado enunciado enunciado significado enunciado que es enunciados cortos enunciado de aa enunciados fonaje enunciados ejemplos enunciados cjf enunciado definicion enunciado del problema enunciados imperativos enunciado 90 fonaje enunciado 13 fonaje enunciado de clausius enunciados oracionales enunciado de la ley de ohm enunciados exclamativos enunciados interrogativos enunciado de kelvin planck enunciado de la ley de coulomb enunciado del alcance del proyecto