Advance Search

Algoritmos Evolutivos Guiados por Redes Barabási–Albert: El Problema del Agente Viajero

Victor Andres Bucheli
Universidad del Valle, Colombia
Oswaldo Solarte Pabón
Universidad del Valle, Colombia
Lady Linibec Diaz Molano
Universidad del Valle, Colombia
Hugo Armando Ordoñez
Universidad Del Cauca, Colombia
Palabras clave:
Copyright and Licensing:

Derechos de autor 2023 Investigación e Innovación en Ingenierías

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Share:

Resumen

Objetivo: Desarrollar un algoritmo evolutivo que se apoye en redes del tipo Barabási–Albert para dirigir la interacción entre individuos en una población con el fin de tratar el problema del agente viajero. El algoritmo propuesto produce mejores resultados en comparación con enfoques tradicionales. Metodología: El algoritmo propuesto combina una estrategia de computación evolutiva con redes del tipo Barabási–Albert para resolver el problema del agente viajero (TSP). En esta propuesta el cruce de la población se representa como redes complejas de la siguiente manera: un grafo representa el grupo de soluciones, donde los vértices (nodos) representan a los individuos o población de soluciones, y las aristas (enlaces) representan las conexiones entre los individuos (soluciones). Por lo tanto, para mejorar las soluciones, se crean enlaces entre los nodos existentes de la población a través de una estructura de red Barabási–Albert. El algoritmo propuesto obtiene mejores resultados que los que produce el algoritmo evolutivo tradicional. Resultados: Se llevó a cabo un experimento para evaluar el rendimiento tanto del algoritmo propuesto como del algoritmo evolutivo. Se analizó el modelo propuesto sobre el TSP y su habilidad para converger y su capacidad para disminuir los tiempos de ejecución en contraste con el enfoque tradicional. Conclusiones: Los resultados muestran que las redes complejas Barabási–Albert permiten obtener resultados superiores que el algoritmo evolutivo tradicional. De esta manera, el mecanismo de enlace preferencial del modelo Barabási–Albert influye en el cruce de individuos y en el rendimiento del algoritmo evolutivo.

PDF
PDF

Citas

  1. Z. Michalewicz, “Heuristic methods for evolutionary computation techniques,” Journal of Heuristics, vol. 1, pp. 177–206, 1996. DOI: https://doi.org/10.1007/BF00127077
  2. L. J. Fogel, A. J. Owens, and M. J. Walsh, Artificial intelligence through simulated evolution. John Wiley & Sons, UK, 1996
  3. A. E. Eiben, R. Hinterding and Z. Michalewicz, "Parameter control in evolutionary algorithms," in IEEE Transactions on Evolutionary Computation, vol. 3, no. 2, pp. 124-141, July 1999, DOI: 10.1109/4235.771166.
  4. G. Friedman, Selective Feedback Computers for Engineering Synthesis and Nervous System Analogy. University of California, Los Angeles–Engineering, 1956.
  5. H. Bremermann, The Evolution of Intelligence: The Nervous System as a Model of Its Environment. University of Washington, Department of Mathematics, 1958.
  6. C. Pizzuti, "Evolutionary Computation for Community Detection in Networks: A Review," in IEEE Transactions on Evolutionary Computation, vol. 22, no. 3, pp. 464-483, June 2018, DOI: 10.1109/TEVC.2017.2737600.
  7. J. Triana Madrid, V. Bucheli Guerrero, y Ángel. García Banos, “Sistema de control para computación evolutiva basado en redes complejas”, Investigación e Innovación en Ingenierías, vol. 8, n.º 2, pp. 169 – 183, ago. 2020.
  8. J. Triana, A. Redondo and V. Bucheli, "Analysis of Complex Networks in optimization Algorithms," 2019 IEEE CHILEAN Conference on Electrical, Electronics Engineering, Information and Communication Technologies (CHILECON), Valparaiso, Chile, 2019, pp. 1-7, DOI: 10.1109/CHILECON47746.2019.8987591.
  9. I. Zelinka, D. Davendra, V. Snasel, R. Jasek, R. Senkerık, and Z. Oplatkova, “Preliminary investigation on relations between complex networks and evolutionary algorithms dynamics”, 2010 International Conference on Computer Information Systems and Industrial Management Applications, CISIM, pp. 148–153, 2010.
  10. I. Zelinka, D. Davendra, S. Roman, and J. Roman, “Do Evolutionary Algorithm Dynamics Create Complex Network Structures?”, Complex Systems, vol. 20, n°. 2, pp. 127–140, 2011.
  11. I. Zelinka, D. Davendra, J. Lampinen, R. Senkerik and M. Pluhacek, "Evolutionary algorithms dynamics and its hidden complex network structures," 2014 IEEE Congress on Evolutionary Computation (CEC), Beijing, China, 2014, pp. 3246-3251, DOI: 10.1109/CEC.2014.6900441.
  12. I. Zelinka, “Investigation on Relationship between Complex Networks and Evolutionary Algorithms Dynamics,” AIP Conference Proceedings, vol. 1389, no. 1, pp. 1011–1014, 09 2011. DOI: https://doi.org/10.1063/1.3637781
  13. S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW (Physics). USA: Oxford University Press, Inc., 2003
  14. I. Zelinka, D. Davendra, V. Snášel, R. Jašek, R. Šenkeřik and Z. Oplatková, "Preliminary investigation on relations between complex networks and evolutionary algorithms dynamics," 2010 International Conference on Computer Information Systems and Industrial Management Applications (CISIM), Krakow, Poland, 2010, pp. 148-153, doi: 10.1109/CISIM.2010.5643674.
  15. J.-M. Llanos-Mosquera, G.-L. Muriel-López, J.-D. Triana-Madrid, y V.-A. Bucheli-Guerrero, “Algoritmos evolutivos guiados por redes complejas libres de escala”, Rev. Cient., vol. 44, n.º 2, pp. 228–241, may 2022.
  16. J. Triana, V. Bucheli and A. Garcia, “Traveling Salesman Problem Solving Using Evolutionary Algorithms Guided by Complex Networks”, International Journal of Artificial Intelligence, vol. 18, no. 2, pp. 101-112, 2020.
  17. J. Triana, V. Bucheli and O. Solarte, “Knapsack Problem Solving Using Evolutionary Algorithms Guided by Complex Networks”, International Journal of Artificial Intelligence, vol. 20, no. 1, pp. 136-146, 2022.
  18. L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. DOI: https://www.science.org/doi/10.1126/science.286.5439.509
  19. T. Back, Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford university press, 1996
  20. J. H. Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, 1992.
  21. D. I. K. H. Kellermayer, “Numerische optimierung von computer modellen mittels der evolutionsstrategie hans-paul schwefel birkh ̈auser, basel and stuttgart, 1977 370 pages hardback sf/48 isbn 3-7643-0876-1,” Cybernetics and System, vol. 7, no. 3-4, pp. 319–320, 1977.
  22. A. Huning, "Evolutionsstrategie optimierung technischer systeme nach prinzipien der biologischen evolution”. Problemata, 15, Frommann-Holzboog. 1976
  23. D. B. Fogel, “Unearthing a fossil from the history of evolutionary computation,” Fundamenta Informaticae, vol. 35, no. 1-4, pp. 1–16, 1998
  24. P. A. Vikhar, "Evolutionary algorithms: A critical review and its future prospects," 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC), Jalgaon, India, 2016, pp. 261-265, doi: 10.1109/ICGTSPICC.2016.7955308.
  25. F. -F. Wei, W. -N. Chen, X. -M. Hu and J. Zhang, "An Empirical Study on Evolutionary Algorithms for Traveling Salesman Problem," 2019 9th International Conference on Information Science and Technology (ICIST), Hulunbuir, China, 2019, pp. 273-280, doi: 10.1109/ICIST.2019.8836906.
  26. C. Purcaru, R.-E. Precup, D. Iercan, L.-O. Fedorovici, R.-C. David, and F. Dragan, “Optimal robot path planning using gravitational search algorithm,” Int. J. Artif. Intell, vol. 10, no. 13, pp. 1–20, 2013
  27. R. P. Alvarez Gil, Z. C. Johanyák and T. Kovács, Surrogate Model based Optimization of Traffic Lights Cycles and Green Period Ratios using Microscopic Simulation and Fuzzy Rule Interpolation, International Journal of Artificial Intelligence, vol. 16, no. 1, pp. 20-40, 2018
  28. R.-E. Precup and R.-C. David, Nature-inspired optimization algorithms for fuzzy controlled servo systems. Butterworth-Heinemann, 2019.
  29. E. Osaba, J. Del Ser, A. Sadollah, M. N. Bilbao, and D. Camacho, “A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem,” Applied Soft Computing, vol. 71, pp. 277–290, 2018.
  30. Z. Jiang, J. Liu, and S. Wang, “Traveling salesman problems with pagerank distance on complex networks reveal community structure,” Physica A: Statistical Mechanics and its Applications, vol. 463, pp. 293–302, 2016
  31. A. L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. DOI: https://www.science.org/doi/abs/10.1126/science.286.5439.509
  32. D. J. Watts and S. H. Strogatz, “Collective dynamics of small-world networks ” Nature, vol. 393, no. 6684, pp. 440–442, 1998
  33. L. A. N. Amaral, A. Scala, M. Barthelemy, and H. E. Stanley, “Classes of small-world networks,” Proceedings of the national academy of sciences, vol. 97, no. 21, pp. 11 149–11 152, 2000.
  34. C. A. Ruíz Ramírez, D. M. Montoya Quintero, y J. A. Jimenez Builes, "Un Ambiente visual integrado de desarrollo para el aprendizaje de programación en robótica", Investigación e Innovación en Ingenierías, vol. 9, n.º 1, pp. 7–21, 2021. DOI: https://doi.org/10.17081/invinno.9.1.3957
Cómo citar
[1]
V. A. Bucheli, O. Solarte Pabón, L. L. Diaz Molano, y H. A. Ordoñez, «Algoritmos Evolutivos Guiados por Redes Barabási–Albert: El Problema del Agente Viajero», Investigación e Innovación en Ingenierías, vol. 11, n.º 2, pp. 146–158, nov. 2023.

Send mail to Author

Send Cancel

Custom technologies based on your needs

  • MongoDB
  • ElasticSearch
  • Redis
  • Solr
  • Memcached