Addressing Combinatorial Optimization with Estimation of Distribution Algorithms Based on Diffusion Models

Abstract

Diffusion models have demonstrated remarkable success in modeling high-dimensional probability distributions within machine learning. Their potential for modeling search distributions in combinatorial optimization, however, remains largely unexplored. This paper bridges this gap by integrating diffusion models into Estimation of Distribution Algorithms (EDAs). We propose two novel EDAs: a diffusion-by-denoising EDA (Diff-EDA) and a diffusion-by-deblending EDA (DbD-EDA), both adapted for discrete optimization. Key adaptations include the use of Gumbel-Softmax for discrete variables, fitness-guided sampling, and tailored loss functions. Through extensive experiments on benchmark additive functions and combinatorial problem instances (SAT, Ising, UBQP), we validate the effectiveness of the proposed algorithms. Our results show that diffusion-based EDAs can outperform classical EDAs based on probabilistic graphical models and contemporary neural-network-based EDAs, particularly on problems with complex variable interactions. This work establishes a new direction for EDAs, demonstrating that diffusion models can provide a powerful and flexible framework for learning and sampling from search distributions in evolutionary optimization.