Optimizing the traveling salesman problem with hybrid GFlowNets and genetic algorithms

In tackling the complexities of the Traveling Salesman Problem (TSP), where the goal is for a salesman to visit a set of cities exactly once and return to the starting city while minimizing the total travel distance, the problem grows exponentially more difficult as the number of cities increases. The brute force approach, which examines every possible sequence of city visits, has a time complexity of [Formula: see text], making it unfeasible for large-scale datasets. To address this challenge, we propose a novel hybrid approach that integrates Genetic Algorithms (GAs) with Generative Flow Networks (GFlowNets) to achieve more efficient and scalable solutions. GFlowNets are effective in generating high-quality solutions for NP-hard problems but often face limitations in efficiently navigating large solution spaces. Our hybrid model, termed Hybrid GFlowNet, combines the exploration capabilities of GFlowNets with GA’s robust optimization techniques. This hybrid approach incorporates local search strategies to refine promising solutions and prevent the algorithm from getting trapped in local optima, a common issue with standalone GA methods. By leveraging both global exploration and local refinement, the model enhances the efficiency of the search for optimal or near-optimal solutions. We tested the Hybrid GFlowNet on benchmark TSP datasets, including TSPLIB, and real-world datasets like Djibouti, demonstrating its ability to significantly outperform traditional methods. The experimental results showed that our hybrid model achieved near-optimal solutions with faster convergence rates, reducing the computational overhead while improving the quality of the solutions. Furthermore, the method proves to be both robust and scalable, making it well-suited for solving larger and more complex TSP instances encountered in practical scenarios.