Optimización discreta basada en algoritmos genéticos para generación de topología de redes de comunicaciones interconectadas por medios guiados

Discrete optimization based on genetic algorithms for topology generation of communication networks interconnected by guided means

Authors

  • José Ricardo Gómez Rodríguez
  • Remberto Sandoval Arechiga
  • Jorge Flores Troncoso
  • Salvador Ibarra Delgado
  • Víktor Iván Rodríguez Abdalá
  • José Luis Alvarez Flores
  • Cristian Eduardo Boyain
  • Juan Manuel Pérez Díaz

DOI:

https://doi.org/10.46932/sfjdv3n2-029

Keywords:

optimización discreta, algoritmo genético, topología de redes de comunicaciones

Abstract

En este trabajo se utilizan técnicas de optimización discreta con algoritmos genéticos para la generación de topologías de redes de comunicaciones empleando medios guiados. Se modeló el problema empleando grafos no dirigidos, utilizando su matriz de adyacencia. Las posibles soluciones deben satisfacer restricciones como conectividad, evitar auto-lazos en el grafo y tener simetría en la matriz de adyacencia. Además, se busca minimizar una métrica de costo-distancia para reducir el costo de instalación, o garantizar una métrica de grado de conectividad para garantizar tolerancia a fallos. Se presentan la codificación del problema y las funciones objetivo y de restricción. Los resultados obtenidos demuestran que el uso del modelo y técnicas propuestas permiten llegar a topologías válidas óptimas para las métricas establecidas en casos donde el número de nodos es pequeño, y se obtiene soluciones sub-óptimas cuando el orden del problema crece, sin perder la utilidad práctica de la solución.

Published

2022-03-18