Browsing by Author "DIAZ URRA, ROBERTO NICOLAS"
Now showing 1 - 1 of 1
- Results Per Page
- Sort Options
Thesis ALGORITMO GENÉTICO DE MODELO ISLAS PARA EL PROBLEMA DE RUTAS DE TRÁNSITO URBANO(2015) DIAZ URRA, ROBERTO NICOLAS; Universidad Tecnica Federico Santa Maria UTFSM INFORMATICAUrban Transit Routing Problem es un problema de optimización combinatoria que consisteen encontrar un conjunto de rutas para una ciudad que permita a sus habitantes transportarserápida y cómodamente, mientras se mantiene un bajo costo de mantenimiento parael sistema. Es un problema NP-Duro altamente complejo. La dificultad viene en las restriccionesde número y largo de rutas que dificultan encontrar una buena solución factible. Elproblema además es de naturaleza multi-objetivo por lo que no existe una única soluciónóptima. Si no que existe un conjunto de soluciones conocido como frente de Pareto de solucionesmutuamente no dominantes.El problema ha sido abordado en el pasado con diversos enfoques: Búsqueda Local,Algoritmos Gen éticos, Colonias de Hormigas y Optimización por Enjambre de Partículas.De estos enfoques aquellos que dan mejores resultados vienen a ser algoritmos gen éticos yoptimización por enjambre de partículas.En este trabajo se presenta un Algoritmo Genético Modelo de Islas. Este es un algoritmoque trabaja sobre una población de soluciones que atraviesan fases de selección, mutación,selección y elitismo. El modelo de islas subdivide esta población en islas que funcionancomo algoritmos genéticos independientes que intercambian cada cierto tiempo un ciertonúmero de soluciones.Los parámetros del algoritmo fueron sintonizados mediante ParamILS, una técnica automática que busca obtener el mejor conjunto de valores para parámetros definidos. Otrascaracterísticas del algoritmo fueron probadas y ajustadas manualmente.El rendimiento se evaluó por medio de la comparación con un algoritmo genético equivalentey con trabajos previos. En general, se obtuvieron soluciones de buena calidad para lasinstancias más pequeñas, sin embargo para instancias más grandes del problema el algoritmopuede requerir más recursos o rediseñar ciertas características.
