Categoria: None
Idioma: Español
Evento: VIII CONGRESO DE INVESTIGACION OPERATIVA - OPTIMA 2009 - Actas del Congreso ISBN: 978-956-332-163-0 - Universidad del BIOBIO - Región del BIOBIO - Chile. Octubre 2009
RESUMEN
En este artículo se propone un algoritmo basado en Autómatas Finitos Deterministas (AFD) y expresiones regulares como mecanismo de solución al problema del agente viajero simétrico (TSP) multiobjetivo. Los objetivos que se desean optimizar son el tiempo y el costo total de recorrido.
Paralelamente, se especifica un Autómata Finito Determinista de Intercambio (AFD – I) el cual permite modelar el espacio de soluciones factibles de un problema de naturaleza combinatoria. Por medio del AFD – I se diseña el conjunto de soluciones factibles para el TSP.
Se ejecutaron dos pruebas fundamentales para medir la precisión y veracidad del algoritmo. La primera consistió en comparar los resultados obtenidos por medio del algoritmo con los resultados encontrados mediante búsqueda exhaustiva, esta última, proporciona las mejores soluciones al explorar completamente el conjunto de soluciones factibles. En este primer experimento se trabajó con instancias de máximo diez ciudades ya que para una mayor cantidad, el algoritmo de búsqueda exhaustiva es ineficiente. Los resultados de esta prueba son tabulados y analizados. En el último ensayo se comparó el algoritmo con dos técnicas reconocidas para la solución del TSP. La primera El Algoritmo de Recocido Simulado (SA) y la segunda Colonia de Hormigas (ACO), cada uno de estos algoritmos son especificados. Los Frentes de Pareto obtenidos son graficados y analizados. El algoritmo propuesto superó las técnicas comparadas ofreciendo mejores ó iguales soluciones en menor tiempo.
Palabras Clave: Programación Multiobjetivo, Optimización Combinatoria, Autómatas Finitos Deterministas.
Paralelamente, se especifica un Autómata Finito Determinista de Intercambio (AFD – I) el cual permite modelar el espacio de soluciones factibles de un problema de naturaleza combinatoria. Por medio del AFD – I se diseña el conjunto de soluciones factibles para el TSP.
Se ejecutaron dos pruebas fundamentales para medir la precisión y veracidad del algoritmo. La primera consistió en comparar los resultados obtenidos por medio del algoritmo con los resultados encontrados mediante búsqueda exhaustiva, esta última, proporciona las mejores soluciones al explorar completamente el conjunto de soluciones factibles. En este primer experimento se trabajó con instancias de máximo diez ciudades ya que para una mayor cantidad, el algoritmo de búsqueda exhaustiva es ineficiente. Los resultados de esta prueba son tabulados y analizados. En el último ensayo se comparó el algoritmo con dos técnicas reconocidas para la solución del TSP. La primera El Algoritmo de Recocido Simulado (SA) y la segunda Colonia de Hormigas (ACO), cada uno de estos algoritmos son especificados. Los Frentes de Pareto obtenidos son graficados y analizados. El algoritmo propuesto superó las técnicas comparadas ofreciendo mejores ó iguales soluciones en menor tiempo.
Palabras Clave: Programación Multiobjetivo, Optimización Combinatoria, Autómatas Finitos Deterministas.
Si deseas el paper envía un correo a elias.d.nino@gmail.com / If you want the paper then you will email me to elias.d.nino@gmail.com
No hay comentarios:
Publicar un comentario