A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problem

AI summary

Overview

• Research area: Machine learning for combinatorial optimization (CO), specifically the hybridization of denoising diffusion models (DDMs) with evolutionary algorithms (EAs). The concrete application studied is the Maximum Independent Set Problem (MISP) on Erdős-Rényi graphs.
• Technical level: Advanced. The paper assumes familiarity with evolutionary computation, denoising diffusion models, graph neural networks, and integer linear programming.
• Scope: The paper introduces the Denoising Diffusion-based Evolutionary Algorithm (DDEA) framework, in which a pre-trained diffusion model supplies both population initialization and a learned recombination operator, and evaluates it against DIFUSCO, Gurobi and KaMIS on MISP instances ranging from 50–100 up to 1300–1400 nodes.

What This Paper Is About

Diffusion-based neural solvers such as DIFUSCO can generate many candidate solutions for combinatorial problems in parallel, but they typically lack the structured exploration that classical metaheuristics like evolutionary algorithms provide, and they often depend on problem-specific post-processing to reach competitive quality. The authors propose embedding a pre-trained diffusion model directly into the EA loop — using it to create the initial population and to perform recombination — rather than treating it merely as a generator followed by a separate refinement stage. The goal is a problem-agnostic hybrid framework that keeps the search capabilities of an EA while inheriting the high-quality, structure-aware sampling of a diffusion model.

Key Contributions

1. The DDEA framework. A hybrid architecture that keeps a standard EA loop (binary tournament selection, recombination, mutation, elitism replacement, no duplicate solutions) but replaces initialization and recombination with diffusion-based counterparts. Only two problem-specific components are required: a decoding strategy that turns probability vectors into feasible solutions, and a source of training labels.

2. Diffusion-based recombination trained by imitation learning. A conditional diffusion model is trained to generate offspring conditioned on two parent solutions and the graph, using an Integer Linear Program "optimized recombination" operator as an expert demonstrator. The ILP maximizes offspring size subject to a local-branching-style constraint that limits the combined Hamming distance to the parents to a threshold k = λ · h(x, y).

3. Diffusion-based population initialization. A pre-trained DIFUSCO model samples node probability heatmaps in parallel, which are decoded via a greedy feasibility-preserving heuristic, giving a diverse, high-quality initial population.

4. An experimental study on the MISP. Comparisons against DIFUSCO, Gurobi, KaMIS, classical crossover (CDX), randomized-greedy initialization, and the full ILP expert operator, including ablation and out-of-distribution generalization tests.

Main Findings

• Recombination approximates the expert operator. The diffusion recombination operator was trained on approximately 160,000 examples from expert ILP recombination across all three datasets. Measured by gap to the optimized recombination label, it achieved 1.28 (± 3.34) on ER-50-100, 6.10 (± 8.53) on ER-300-400 and 5.18 (± 8.48) on ER-700-800 with EA parents, outperforming CDX recombination (6.38 ± 7.25, 20.52 ± 7.61, 24.13 ± 6.03) and DIFUSCO (6.36 ± 5.54 and 8.51 ± 7.17 and 5.44 ± 4.89 on the respective datasets).

• Performance degrades with parent quality, as expected. Using heuristic parents, the diffusion recombination gap rose to 2.86 (± 4.40), 12.18 (± 6.86) and 16.81 (± 6.38); using random parents it rose to 3.10 (± 5.09), 26.28 (± 5.90) and 26.60 (± 4.15). The authors describe this as cost monotonicity, validating the operator's design.

• Both components matter, recombination more than initialization. Within the full EA framework, full DDEA (P=16, G=20) achieved gaps of 0.11 (± 0.53) on ER-50-100, 0.90 (± 1.37) on ER-300-400 and 2.95 (± 2.02) on ER-700-800. Removing diffusion recombination (DI/CDX) gave 0.55 (± 1.52), 3.57 (± 2.27) and 5.75 (± 2.66); removing diffusion initialization (RG/Diffusion) gave 0.11 (± 0.69), 1.39 (± 2.09) and 4.52 (± 2.33); the naïve EA (RG/CDX) gave 0.25 (± 1.15), 8.58 (± 2.98) and 13.36 (± 3.48). The paper quotes the DDEA-versus-DI/CDX comparison as 2.81% versus 5.75% gap on ER-700-800, and the DDEA-versus-RG/DR comparison as 0.94% versus 1.39% gap on ER-300-400 (Table 2 lists 2.95 and 0.90 respectively for full DDEA).

• The learned operator is far cheaper than the expert. ILP-based optimized recombination required 88.3 (± 12.9) seconds per generation on ER-300-400 and 104.8 (± 9.1) on ER-700-800, against 9.4 (± 0.8) and 23.9 (± 0.5) for the diffusion recombination in Table 2; the text cites an example of 5 s versus 88 s per generation on ER-300-400.

• DDEA beats DIFUSCO on primal integral. Solving the MISP to optimality on ER-50-100, DDEA (P=24) reached primal integral 0.00 versus DIFUSCO's 0.19. On ER-300-400 the best DDEA configurations (P=32 and P=48) both reached 0.70 versus DIFUSCO's 1.21, and on ER-700-800 DDEA (P=48) reached 2.27 versus DIFUSCO's 3.07.

• Population size interacts with graph size. On ER-300-400 the authors identify P=32 as optimal, since P=48 did not improve results; on ER-700-800 larger populations did improve costs. On ER-50-100, two generations with P=24 were enough to reach an optimal solution, with DDEA outperforming DIFUSCO on a 13-second budget.

• DDEA-long outperforms DIFUSCO-timed, Gurobi and matches KaMIS on small instances. With DDEA-long (P=24, G=15 for ER-50-100; P=32, G=15 for ER-300-400; P=20, G=10 for ER-700-800), DDEA's independent set sizes were 0.25% and 0.31% larger than DIFUSCO-timed on ER-300-400 and ER-700-800 with slightly shorter runtimes and fewer individuals explored. Against Gurobi under the same time limit, DDEA's solution sizes were 3.90% and 7.50% larger on ER-300-400 and ER-700-800 respectively, and it matched both Gurobi and KaMIS on ER-50-100, solving that dataset to optimality.

• Better out-of-distribution generalization. On ER-1300-1400, using diffusion models trained only on graphs up to 800 nodes, DDEA (P=16, G=10) reached cost 43.17 in 909.5 seconds with 240 function evaluations and 21 diffusion calls, versus 38.69 in 947.1 seconds for DIFUSCO-timed (which gained only +1.62 over DIFUSCO x16 despite 839 extra seconds). The abstract reports this as 11.6% higher quality under the same time limit. KaMIS reached 49.91 in its 60-second budget.

Methodology in Plain English

The authors take a pre-trained diffusion model (based on DIFUSCO) and plug it into two places inside a standard evolutionary algorithm.

Initialization. The diffusion model produces many node probability "heatmaps" in parallel. Each heatmap is turned into a valid independent set by a simple greedy rule: sort nodes by probability, take the highest-probability node, then mark all of its neighbors as ineligible, and repeat. Because of this rule, every generated individual is automatically feasible.

Recombination. The interesting part is how a new offspring is created from two parents. Instead of mixing bits, the authors trained a second diffusion model that takes the two parents and the graph as conditioning information and denoises random noise into a new offspring heatmap, which is then decoded with the same greedy rule. Training data for this model was produced by an expensive expert: an Integer Linear Program that searches for the best-possible offspring within a limited Hamming distance of the two parents, with the distance budget controlled by a parameter λ. The diffusion model is trained by imitation learning to reproduce these expert outputs, so it learns a cheap approximation of an expensive exact operator. The model's input features extend DIFUSCO's by adding each node's status in both parents alongside its positional embedding.

Search loop. Otherwise the EA is conventional: binary tournament selection picks parents, the diffusion recombination produces offspring, a mutation operator flips selections with fixed probabilities, and elitism replacement preserves quality while rejecting duplicates.

Evaluation. They benchmark on Erdős-Rényi graphs with edge probability 0.15 in three size ranges ([50,100], [300,400], [700,800], with 40,000 graphs generated per range and 128 held out for testing) using KaMIS with a 60-second limit as ground truth, and an out-of-distribution set of 42 graphs with 1300–1400 nodes. Metrics are gap to best-known solution, mean cost, and a runtime-aware primal integral. Baselines include DIFUSCO x16 and x32, "timed" DIFUSCO run to match DDEA's runtime, Gurobi with a standard MISP ILP solved to the same time budget, and KaMIS at 60 seconds. Configurations used p_m = 0.1, p_d = 0.05, λ = 1.75, hidden dimension d_h = 256, n_l = 12 layers, Gaussian diffusion, a cosine inference schedule with T_inf = 50 steps and a linear training schedule with T_train = 1000 steps.

Why This Matters

Impact on research. The paper argues for embedding generative models inside the search loop rather than using them as standalone solution generators requiring separate, problem-specific post-processing. It also shows that an expensive exact operator can be distilled into a cheap learned one through imitation learning and used as

Authors’ abstract

Denoising diffusion models (DDMs) offer a promising generative approach for combinatorial optimization, yet they often lack the robust exploration capabilities of traditional metaheuristics like evolutionary algorithms (EAs). We propose a Denoising Diffusion-based Evolutionary Algorithm (DDEA) framework that synergistically integrates these paradigms. It utilizes pre-trained DDMs for both high-quality and diverse population initialization and a novel diffusion-based recombination operator, trained via imitation learning against an optimal demonstrator. Evaluating DDEA on the Maximum Independent Set problem on Erdős-Rényi graphs, we demonstrate notable improvements over DIFUSCO, a leading DDM solver. DDEA consistently outperforms it given the same time budget, and surpasses Gurobi on larger graphs under the same time limit, with DDEA's solution sizes being 3.9% and 7.5% larger on the ER-300-400 and ER-700-800 datasets, respectively. In out-of-distribution experiments, DDEA provides solutions of 11.6% higher quality than DIFUSCO under the same time limit. Ablation studies confirm that both diffusion initialization and recombination are crucial. Our work highlights the potential of hybridizing DDMs and EAs, offering a promising direction for the development of powerful machine learning solvers for complex combinatorial optimization problems.