Ant Colony Sampling with GFlowNets for Combinatorial Optimization
Minsu Kim Sanghyeok Choi Jiwoo Son Hyeonah Kim Jinkyoo Park Yoshua Bengio
This paper introduces the Generative Flow Ant Colony Sampler (GFACS), a novel
neural-guided meta-heuristic algorithm for combinatorial optimization. GFACS
integrates generative flow networks (GFlowNets) with the ant colony
optimization (ACO) methodology. GFlowNets, a generative model that learns a
constructive policy in combinatorial spaces, enhance ACO by providing an
informed prior distribution of decision variables conditioned on input graph
instances. Furthermore, we introduce a novel combination of training tricks,
including search-guided local exploration, energy normalization, and energy
shaping to improve GFACS. Our experimental results demonstrate that GFACS
outperforms baseline ACO algorithms in seven CO tasks and is competitive with
problem-specific heuristics for vehicle routing problems. The source code is
available at \url{https://github.com/ai4co/gfacs}.