論文の概要: A Distribution Evolutionary Algorithm for the Graph Coloring Problem
- arxiv url: http://arxiv.org/abs/2203.15162v3
- Date: Tue, 2 May 2023 13:50:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-03 18:22:57.849559
- Title: A Distribution Evolutionary Algorithm for the Graph Coloring Problem
- Title（参考訳）: グラフ彩色問題に対する分布進化アルゴリズム
- Authors: Yongjian Xu and Huabin Cheng and Ning Xu and Yu Chen and Chengwang Xie
- Abstract要約: 確率モデル (DEA-PPM) に基づく分布進化アルゴリズムを開発し, グラフカラー化の問題に対処する。
DEA-PPMは、新しい確率モデルに基づく分布人口を採用し、分布空間を探索するための探索戦略を導入する。
数値的な結果から,小集団のDEA-PPMは最先端のメタヒューリスティックスと競合することが示された。
- 参考スコア（独自算出の注目度）: 9.258122432690556
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Graph coloring is a challenging combinatorial optimization problem with a
wide range of applications. In this paper, a distribution evolutionary
algorithm based on a population of probability model (DEA-PPM) is developed to
address it efficiently. Unlike existing estimation of distribution algorithms
where a probability model is updated by generated solutions, DEA-PPM employs a
distribution population based on a novel probability model, and an orthogonal
exploration strategy is introduced to search the distribution space with the
assistance of an refinement strategy. By sampling the distribution population,
efficient search in the solution space is realized based on a tabu search
process. Meanwhile, DEA-PPM introduces an iterative vertex removal strategy to
improve the efficiency of $k$-coloring, and an inherited initialization
strategy is implemented to address the chromatic problem well. The cooperative
evolution of the distribution population and the solution population leads to a
good balance between exploration and exploitation. Numerical results
demonstrate that the DEA-PPM of small population size is competitive to the
state-of-the-art metaheuristics.utes to its competitiveness to the
state-of-the-art metaheuristics.
- Abstract（参考訳）: グラフカラー化は、広範囲のアプリケーションにおいて難しい組合せ最適化問題である。
本稿では,確率分布モデル(dea-ppm)に基づく分布進化アルゴリズムを開発し,効率的な解法を提案する。
生成した解によって確率モデルを更新する既存の分布アルゴリズムとは異なり、DEA-PPMは新しい確率モデルに基づく分布人口を採用し、改良戦略の助けを借りて分布空間を探索する直交探索戦略を導入する。
分布人口をサンプリングすることにより、タブ探索プロセスに基づいて解空間の効率的な探索を実現する。
一方、DEA-PPMは、$k$-coloringの効率を改善するために反復頂点除去戦略を導入し、色調問題に対処するために継承初期化戦略を実装した。
流通人口と解決人口の協調進化は、探検と搾取のバランスを良好に保っている。
数値的な結果は、人口の少ないDEA-PPMは、最先端のメタヒューリスティックスと競合することを示している。
関連論文リスト
- Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳（メタデータ） (2024-01-29T02:08:40Z) - Ensemble-Based Annealed Importance Sampling [12.59962335240209]
本稿では,Annealed Importance Smpling (AIS) のアンサンブルに基づくバージョンを提案する。
我々はアンサンブル内の相互作用を利用して、未発見モードの探索を奨励する。
本稿では,提案アルゴリズムをどのように実装し,アンサンブルの進化を規定する偏微分方程式を導出する方法について論じる。
論文 参考訳（メタデータ） (2024-01-28T12:47:39Z) - Strategic Distribution Shift of Interacting Agents via Coupled Gradient
Flows [6.064702468344376]
実世界のシステムにおける分散シフトのダイナミクスを解析するための新しいフレームワークを提案する。
より単純なモデルでは捉えられない偏極や異なる影響といった、よく文書化された形態の分布シフトを捉える手法を示す。
論文 参考訳（メタデータ） (2023-07-03T17:18:50Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳（メタデータ） (2023-07-01T18:35:21Z) - Scalable Multiple Patterning Layout Decomposition Implemented by a
Distribution Evolutionary Algorithm [11.366935475887239]
一般化グラフ着色問題として MPL のレイアウト分解をモデル化する。
DEA-PPMは、分解結果と実行時間のバランスをとることができる。
論文 参考訳（メタデータ） (2023-04-09T10:23:30Z) - End-to-End Pareto Set Prediction with Graph Neural Networks for
Multi-objective Facility Location [10.130342722193204]
施設配置問題(FLP)は、サプライチェーンやロジスティクスで広く見られるNPハード最適化問題の典型的なクラスである。
本稿では,システム全体のコストを同時に最小化し,システム信頼性を最大化する多目的施設配置問題(MO-FLP)について考察する。
ノードとエッジの暗黙グラフ表現を学習するために、2つのグラフニューラルネットワークを構築した。
論文 参考訳（メタデータ） (2022-10-27T07:15:55Z) - Distributed Evolution Strategies for Black-box Stochastic Optimization [42.90600124972943]
この研究は、分散ブラックボックス最適化への進化的アプローチに関するものである。
各作業者は、アルゴリズムによる問題の近似を個別に解くことができる。
問題のロバスト性を大幅に改善する2つの代替シミュレーション手法を提案する。
論文 参考訳（メタデータ） (2022-04-09T11:18:41Z) - Score-based Generative Modeling of Graphs via the System of Stochastic
Differential Equations [57.15855198512551]
本稿では,連続時間フレームワークを用いたグラフのスコアベース生成モデルを提案する。
本手法は, トレーニング分布に近い分子を生成できるが, 化学価数則に違反しないことを示す。
論文 参考訳（メタデータ） (2022-02-05T08:21:04Z) - Implicit Distributional Reinforcement Learning [61.166030238490634]
2つのディープジェネレータネットワーク(DGN)上に構築された暗黙の分布型アクター批判(IDAC)
半単純アクター (SIA) は、フレキシブルなポリシー分布を利用する。
我々は,代表的OpenAI Gym環境において,IDACが最先端のアルゴリズムより優れていることを観察する。
論文 参考訳（メタデータ） (2020-07-13T02:52:18Z) - MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
本稿では,マイニングパターンを用いて問題サイズの削減を行うMineReduceという手法を提案する。
異種車両ルーティング問題に対するMineReduceの適用について述べる。
論文 参考訳（メタデータ） (2020-05-15T08:49:50Z) - Decentralized MCTS via Learned Teammate Models [89.24858306636816]
本稿では,モンテカルロ木探索に基づくトレーニング可能なオンライン分散計画アルゴリズムを提案する。
深層学習と畳み込みニューラルネットワークを用いて正確なポリシー近似を作成可能であることを示す。
論文 参考訳（メタデータ） (2020-03-19T13:10:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。