Comparación de una aplicacion de optimizacion de rutas utilizando principios de algoritmos geneticos, en una arquitectura distribuida y local

nCOMPARACIÓN DE UNA APLICACION DE OPTIMIZACION DE RUTAS UTILIZANDO PRINCIPIOS DE ALGORITMOS GENETICOS, EN UNA ARQUITECTURA DISTRIBUIDA Y LOCAL
Sofía Luque y Guzman A20112774@pucp.edu.pe Sergio Horruitiner Costa a20112689@pucp.edu.pe Daniel Campos daniel.campos@pucp.edu.pe Igor Zárate igor.zaratei@pucp.edu.pe

RESUMEN: Los algoritmos genéticos aplicados a la optimización de rutas, se hancentrado en arquitecturas locales y no en arquitecturas distribuidas. En este artículo presentamos una aplicativo de optimalización de rutas utilizando principios de algoritmos genéticos entrenado sobre una arquitectura distribuida, siendo esta arquitectura idónea para un mejor cruzamiento y mutación de la población. Asimismo, mostramos las características más importantes del algoritmo genético entérmino de estimaciones. La aplicación de optimización ha sido desarrollada sobre dos arquitecturas; local y distribuida, cuyo objetivo principal es comparar la ejecución del aplicativo sobres dichas arquitecturas, y a partir de los datos obtenidos automáticamente, determinar la ruta más optima para llegar de un punto a otro. INTRODUCCION La impresionante capacidad de cálculo de los ordenadores actualesy su continuo crecimiento, permiten realizar en un período razonable de tiempo la optimización de problemas ingenieriles imitando a la naturaleza que a lo largo de millones de años y generación tras generación hace sobrevivir al mejor adaptado. Los Algoritmos Genéticos tratan de optimizar imitando el comportamiento natural; su aplicación en ingeniería se debe a los trabajos de Goldberg, y muyrecientemente han aparecido algunas optimizaciones estructurales por este método . Sin embargo su desarrollo en el campo de la bioquímica se inició en la década de los 60 donde un grupo de biólogo utilizó los computadores digitales para realizar simulaciones genéticas; a partir de este momento empiezan a aparecer trabajos cercanos a los algoritmos genético pero fue John HollandI, quien en 1975integró y elaboró sus dos fundamentos básicos: la capacidad de una representación simple (cadenas de bits) para mostrar estructuras complejas y la potencia de simples transformaciones para mejorar tales estructuras. Holland observó, a través de su Teorema de los Esquemas o Teorema Fundamental de los Algoritmos Genéticos que con el conveniente control de la estructura, aparecen rápidas me joras en lascadenas de bits como sucede en las poblaciones de animales. En este trabajo se ha desarrollado , evaluado y diseñado una aplicación basada en principios de algoritmos genéticos para la optimalización de rutas, analizando los resultados de la ejecución de la aplicación sobre una arquitectura distribuida y una arquitectura local, con el fin de determinar cual arquitectura es más eficiente para lapredicción de la mejor ruta. Mediante la asimilación de estructuras a cromosomas representados por cadenas binarias y partiendo de una población generada aleatoriamente, se efectúan los procesos naturales de selección, cruce y mutación. Se evoluciona así, generación tras generación, hacia el

mejor adaptado; o sea, la estructura óptima. 1. ALGORTIMOS GENETICOS Los AG son algoritmos de optimización,es decir, tratan de encontrar la mejor solución a un problema dado entre un conjunto de soluciones posibles. Los mecanismos de los que se valen los AG para llevar a cabo esa búsqueda pueden verse como una metáfora de los procesos de evolución biológica [3]. Los AG son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético delos organismos vivos [3]. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes. Por imitación de este proceso, los AG son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de...