Travel Sales Problem: Evolutionary Algorithms and Complex Networks

This article examines the impact of network degree distribution on the performance of evolutionary algorithms, specifically in solving the Traveling Salesperson Problem (TSP). It evaluates the integration of various network types to regulate population crossovers, enhancing candidate solutions and their refinement over generations. The experimental analysis includes complex networks like Erdős–Rényi and Barabási–Albert, along with regular graphs such as Balanced trees and Harary graphs. The study focuses on how different network structures influence exploration, convergence, and computational efficiency, particularly in terms of CPU time. Results show that highly connected networks, like Barabási–Albert, facilitate faster convergence and improved solution quality by guiding the search process more effectively. The Harary graph with k=2 demonstrated superior performance, reducing execution times by up to sevenfold compared to traditional approaches. This improvement highlights the advantages of specific degree distributions in balancing exploration and exploitation. Networks with hubs, such as Barabási–Albert, accelerate information flow and the evolutionary process, while more regular networks, like Harary graphs, provide controlled structures that maintain high solution quality. These findings emphasize the importance of network topology in evolutionary algorithms and suggest further exploration of hybrid models and other network types to optimize NP-hard problems.