COMPUTACIONAL PERFORMANCE COMPARISON OF GENETIC ALGORITHM OF CHU-BEASLEY AND ANT COLONY ALGORITHM IN THE SOLUTION OF P-CENTDIAN PROBLEM
COMPARACIÓN DEL DESEMPEÑO COMPUTACIONAL DE LOS ALGORIMTOS GENÉTICO DE CHU-BEASLEY Y COLONIA DE HORMIGAS EN LA SOLUCIÓN DEL PROBLEMA DE P-CENTDIANA
Ing. César Adrian Muñoz.
PhD. Ramón A. Gallego.
MSc. Eliana Mirledy Toro.
Abstract: The P-centdian is a location problem with large application in daily life and also an important line of research. Some of its applications are: location of service entities, telecommunication repeater antennas, power distribution system transformers, communications equipment for the command remote control and switching devices, among others. In this paper the general problem of the P-centdian is presented as well as its mathematical model and the coding used in its solution. It also describes the implemented combinatorial optimization techniques (Genetic Algorithm of Chu-Beasley and Ant Colony Algorithm) that are used to solve the mentioned problem. Finally, the performance of these methods is assessed through the evaluation of a test case with low and high mathematical complexity.
Keywords: Ant Colony Algorithm, Genetic Algorithm of Chu-Beasley, combinatorial optimization, metaheuristics, P-centdian.
Resumen: La P-centdiana es un problema de localización de gran aplicabilidad en la vida diaria que constituye una importante línea de investigación. Entre las aplicaciones se tienen: localización de entidades de servicio, antenas repetidoras de telecomunicaciones, transformadores en sistemas de distribución de energía eléctrica, equipos de comunicaciones para el comando a distancia de dispositivos de control y maniobra, entre otros. En este trabajo se presenta el problema general de la P-centdiana así como el modelo matemático que lo representa y la codificación empleada en su solución. También se describen las técnicas de optimización combinatorial implementadas (Algoritmo Genético de Chu-Beasley y Algoritmo Colonia de Hormigas) a partir de las cuales se resuelve dicho problema. Finalmente, a través de la evaluación de un caso de prueba de baja y alta complejidad matemática se analiza el desempeño de dichos métodos.
Palabras clave: Algoritmo Colonia de Hormigas, Algoritmo Genético de Chu-Beasley, metaheurísticas, optimización combinatorial, P-centdiana.