Denoising Diffusion-Based Evolutionary Algorithms: Exploring Hybridizations of Evolutionary Algorithms with Denoising Diffusion Models

Abstract

In dieser Arbeit wird die Integration von entrauschenden Diffusionsmodellen mit evolutionären Algorithmen (EAs) zur Verbesserung der maschinellen lernbasierten kombinatorischen Optimierung untersucht. Während Diffusionsmodelle vielversprechende generative Ansätze zur Lösung von NP-schweren Problemen bieten, sind sie häufig auf problemspezifische Heuristiken angewiesen und verfügen nicht über die robuste Explorationsfähigkeit klassischer Suchverfahren.Um diese Einschränkungen zu überwinden, schlagen wir einen neuartigen diffusionsbasierten evolutionären Algorithmus (DEA) vor. Dieser Lösungsanstz nutzt vortrainierte Diffusionsmodelle sowohl zur Initialisierung der Population als auch für die Rekombination, wodurch der durch Diffusionsmodelle erfasste multimodale Lösungsraum gezielt in die explorative Suchstruktur eines EAs eingebettet wird. Wir fokussieren uns auf das Maximum-Independent-Set-Problem (MIS) und erweitern einen Basis-EA um eine diffusionsgestützte Initialisierung sowie einen neuartigen Rekombinationsoperator. Letzterer wird mittels Imitationslernens aus einem optimalen Rekombinationsdemonstrator trainiert, der als Integer Linear Program formuliert ist.Numerische Experimente auf Erdős-Rényi-Graphen unterschiedlicher Größe zeigen, dass DEA die Leistung von Difusco, einem hochmodernen diffusionsbasierten Optimierer für kombinatorische Optimierungsprobleme, signifikant übertrifft, indem es sowohl eine höhere Lösungsqualität als auch eine bessere Generalisierungsfähigkeit auf größere Graphinstanzen erzielt. Insbesondere schlägt DEA die führende Software zur Lösung gemischt-ganzzahligen linearen Problemen, Gurobi, bei größeren Instanzen unter gleichen Zeitbudgets, bleibt jedoch hinter hochspezialisierten klassischen Lösern wie KaMIS zurück.Ablationsstudien belegen den entscheidenden Einfluss der diffusionsbasierten Initialisierung und Rekombination auf die Gesamtleistung des DEA-Frameworks. Diese Arbeit liefert empirische Evidenz für das synergetische Potenzial der Kombination von Diffusionsmodellen mit evolutionären Algorithmen und eröffnet neue Perspektiven für die Entwicklung robuster hybrider ML-metaheuristischer Ansätze zur Lösung komplexer kombinatorischer Optimierungsprobleme.

This thesis explores the integration of denoising diffusion models with evolutionary algorithms (EAs) to enhance machine learning-based combinatorial optimization. While diffusion models have shown promise as generative solvers for NP-hard problems, they often rely on problem-specific heuristics and lack the robust exploration capabilities of traditional search methods. To address these limitations, we propose a novel Diffusion-based Evolutionary Algorithm (DEA) framework. This approach leverages pre-trained diffusion models for both population initialization and recombination, effectively exploiting the multimodal solution space captured by diffusion models within the exploratory structure of an EA. We focus on the Maximum Independent Set (MIS) problem, developing a baseline EA and then introducing diffusion-based initialization and a diffusion recombination operator trained via imitation learning from an optimal recombination demonstrator formulated as an Integer Linear Program.Computational experiments on Erdős-Rényi graph datasets of varying sizes demonstrate that DEA significantly outperforms standalone Difusco, a state-of-the-art diffusion-based solver for combinatorial optimization, achieving improved solution quality and better out-of-distribution generalization to larger graph instances. Notably, DEA outperforms the MIP solver Gurobi on larger instances when considering the same time limit, while still falling short of highly specialized classical solvers like KaMIS.Our ablation studies highlight the crucial contributions of both diffusion-based initialization and recombination to the DEA framework's success. This work provides empirical evidence for the synergistic potential of combining diffusion models and EAs, offering a promising direction for developing more robust and effective machine learning approaches to complex combinatorial optimization problems and paving the way for future research into hybrid ML-metaheuristic methods.