Ant Colony Sampling with GFlowNets for Combinatorial Optimization
<|reference_start|>Ant Colony Sampling with GFlowNets for Combinatorial Optimization: This paper introduces the Generative Flow Ant Colony Sampler (GFACS), a neural-guided probabilistic search algorithm for solving combinatorial optimization (CO). GFACS integrates generative flow networks (GFlowNets), an emerging amortized inference method, with ant colony optimization (ACO), a promising probabilistic search algorithm. Specifically, we use GFlowNets to learn a constructive policy in combinatorial spaces for enhancing ACO by providing an informed prior distribution over decision variables conditioned on input graph instances. Furthermore, we introduce a novel off-policy training algorithm for scaling conditional GFlowNets into large-scale combinatorial spaces by leveraging local search and shared energy normalization. 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.<|reference_end|>
@article{kim2024ant,
    title={Ant Colony Sampling with GFlowNets for Combinatorial Optimization},
    author={Minsu Kim, Sanghyeok Choi, Hyeonah Kim, Jiwoo Son, Jinkyoo Park,
  Yoshua Bengio},
    journal={arXiv preprint arXiv:2403.07041},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.07041},
    primaryClass={cs.LG cs.NE}
}