論文の概要: A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problem

• arxiv url: http://arxiv.org/abs/2510.08627v1
• Date: Wed, 08 Oct 2025 11:41:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 04:53:46.901051
• Title: A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problem
• Title（参考訳）: 拡散に基づく進化的アルゴリズムフレームワーク:最大独立集合問題への応用
• Authors: Joan Salvà Soler, Günther R. Raidl,
• Abstract要約: 進化的アルゴリズム(EA)を相乗的に統合する解法拡散に基づく進化的アルゴリズム(DDEA)フレームワークを提案する。 DDEAは、同じ時間予算でDIFUSCOを常に上回り、同じ時間制限で大きなグラフ上でGurobiを上回ります。 我々の研究は、DDMとEAのハイブリッド化の可能性を強調し、強力な機械学習ソルバの開発に有望な方向性を提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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\H{o}s-R\'enyi 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.
• Abstract（参考訳）: 拡散モデル(DDM)は組合せ最適化に有望な生成的アプローチを提供するが、進化アルゴリズム(EA)のような伝統的なメタヒューリスティックな探索能力に欠けることが多い。 本稿では,これらのパラダイムを相乗的に統合したDDEA(Denoising Diffusion-based Evolutionary Algorithm)フレームワークを提案する。 訓練済みのDDMを用いて、高品質で多様な集団の初期化と、最適な実証者に対する模倣学習を通じて訓練された新しい拡散ベースの組換え演算子を訓練する。 Erd\H{o}s-R\'enyi グラフ上の最大独立集合問題における DDEA の評価を行い、主要な DDM 解法 DIFUSCO に対する顕著な改善を示す。 DDEAのソリューションサイズはER-300-400とER-700-800のデータセットでそれぞれ3.9%と7.5%である。 ディストリビューション以外の実験では、DDEAは同じ時間制限下でDIFUSCOよりも11.6%高い品質のソリューションを提供する。 アブレーション研究は拡散初期化と組換えの両方が重要であることを証明している。 我々の研究は、DDMとEAのハイブリッド化の可能性を強調し、複雑な組合せ最適化問題に対する強力な機械学習ソルバの開発に有望な方向性を提供する。

関連論文リスト

• Adversarial Distribution Matching for Diffusion Distillation Towards Efficient Image and Video Synthesis [65.77083310980896]
  本稿では, 実測値と偽測値の間に潜時予測を整列させる適応分布マッチング (ADM) を提案する。 提案手法は,DMD2と比較してSDXLの1ステップ性能に優れ,GPU時間が少ない。 SD3-Medium, SD3.5-Large, CogVideoX に多段階の ADM 蒸留を適用した実験では, 画像と映像の効率的な合成に向けた新しいベンチマークが設定された。
  論文  参考訳（メタデータ） (2025-07-24T16:45:05Z)
• Integrating Intermediate Layer Optimization and Projected Gradient Descent for Solving Inverse Problems with Diffusion Models [19.445391508424667]
  逆問題(IP)はノイズの観測から信号を再構成する。 DMはIPを解くための強力なフレームワークとして登場し、優れた再構築性能を実現している。 既存のDMベースの手法は、重い計算要求や準最適収束といった問題に頻繁に遭遇する。 これらの課題に対処するために,DMILOとDMILO-PGDという2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2025-05-27T06:49:02Z)
• Variational Autoencoding Discrete Diffusion with Enhanced Dimensional Correlations Modeling [48.96034602889216]
  Variencoding Discrete Diffusion (VADD) は、潜在変数モデリングによる離散拡散を強化する新しいフレームワークである。 補助的認識モデルを導入することにより、VADDはトレーニングセット上の変分下界と償却推論を介して安定したトレーニングを可能にする。 2Dトイデータ、画素レベルの画像生成、テキスト生成に関する実証結果は、VADDがMDMベースラインを一貫して上回ることを示す。
  論文  参考訳（メタデータ） (2025-05-23T01:45:47Z)
• Deep Data Consistency: a Fast and Robust Diffusion Model-based Solver for Inverse Problems [0.0]
  本研究では,拡散モデルを用いた逆問題解法において,データ一貫性ステップをディープラーニングモデルで更新するディープデータ一貫性(DDC)を提案する。 線形および非線形タスクにおける最先端手法と比較して、DDCは類似度と実性の両方の指標の優れた性能を示す。
  論文  参考訳（メタデータ） (2024-05-17T12:54:43Z)
• Fast Diffusion Model [122.36693015093041]
  拡散モデル(DM)は、複雑なデータ分布を捉える能力を持つ様々な分野に採用されている。 本稿では,DM最適化の観点から,高速拡散モデル (FDM) を提案する。
  論文  参考訳（メタデータ） (2023-06-12T09:38:04Z)
• DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization [51.517956081644186]
  グラフベースの拡散フレームワークであるDIFUSCOを導入する。 本フレームワークは, NPC問題を離散0, 1ベクトル最適化問題とみなす。 MIS問題に対して、DIFUSCOは、挑戦的なSATLIBベンチマークにおいて、以前の最先端のニューラルソルバよりも優れている。
  論文  参考訳（メタデータ） (2023-02-16T11:13:36Z)
• Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexity [77.78624443410216]
  異種胸部データ検出のための改良型FDAMアルゴリズムを提案する。 本研究は,提案アルゴリズムの通信が機械数に強く依存し,精度レベルにも強く依存していることを示す。 FDAMアルゴリズムのベンチマークデータセットと、異なる組織の医療用胸部X線画像に対する効果を実験により実証した。
  論文  参考訳（メタデータ） (2021-02-09T04:05:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。