Algoritmos genéticos aplicados al diseño de redes de telecomunicaciones
View/ Open
Date
2000Author
Lima Romero, Manuel Jaime
MANUEL JAIME LIMA ROMERO:3176062
Metadata
Show full item record
Export citation
Abstract
El diseño de redes es materia de estudio formal por parte de la investigación de operaciones, aunque cualquier otra área que haga uso de redes intentará dar solución al problema de obtener la red óptima para resolver algún problema específico. Existen procedimientos formales para encontrar solución a los problemas de minimización de costos o de longitud de enlaces en una red. Estos procedimientos muestran que los árboles de mínima expansión, o de mínima cobertura, son parte del espacio de soluciones y entre ellos se encuentra la solución óptima al problema de minimización. El uso de algoritmos genéticos (AG) es una técnica que ayuda a aproximarse a las soluciones óptimas cuando alguna o varias de las siguientes condiciones está presente: 1. La definición del problema lo hace intratable para usar procedimientos de búsqueda que operen en tiempo polinomial. 2. No se necesita la solución exacta sino que es suficiente una buena aproximación al máximo global. 3. No se conoce con detalle el espacio de búsqueda. 4. No tiene una solución unimodal. Este trabajo tuvo como principio, la intención de desarrollar un procedimiento de optimización de la topología de una red de telecomunicaciones, que es mejor conocida como una red de área amplia, WAN. El propósito de usar los AG en la búsqueda de soluciones parte de la necesidad de obtener las mejores propuestas para el diseño de una red W AN. Conocidas las características de capacidad de los enlaces que conectarán a los nodos de la red, el tráfico entre los usuarios, y la pertenencia de cada usuario a uno de los nodos definidos en la red, es lógico suponer que se desea obtener el máximo global, en el espacio de búsqueda de que se trate. Y aunque la obtención del éste máximo es deseable, al conocer las alternativas con las mejores aptitudes, es viable que el diseñador opte por usar una de ellas. Los resultados muestran que es posible obtener soluciones con un buen nivel de aptitud, permitiendo seleccionar la topología de la red de mínimo costo entre las soluciones de mayor aptitud obtenidas en el proceso. El modelo utilizado, así como los procedimientos desarrollados durante su implementación tienen una referencia en la literatura de AG, donde ha dominado el uso de cromosomas binarios, en tanto este AG usa no sólo un alfabeto que contiene un número de símbolos proporcional al número de objetos a representar, sino que también utiliza cromosomas en duplas no homogéneas, lo que introduce nuevamente estos elementos poco usados en el tratamiento de problemas con AG. Adicionalmente, ha sido una oportunidad de ampliar el conocimiento de la aplicación de los AG en la búsqueda de soluciones en redes, permitiendo seguir afinando los parámetros del AG y de los operadores genéticos que intervienen en la selección y modificación de las poblaciones durante el proceso evolutivo de la población de soluciones.