論文の概要: On Population-Based Algorithms for Distributed Constraint Optimization
Problems
- arxiv url: http://arxiv.org/abs/2009.01625v1
- Date: Wed, 2 Sep 2020 06:39:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-22 19:47:25.631709
- Title: On Population-Based Algorithms for Distributed Constraint Optimization
Problems
- Title（参考訳）: 分散制約最適化問題に対する集団ベースアルゴリズムについて
- Authors: Saaduddin Mahmud, Md. Mosaddek Khan, Nicholas R. Jennings
- Abstract要約: 我々は、人口ベースのアルゴリズムとして広く呼ばれる、新しい不完全アルゴリズムのクラスについて研究する。
最初のアプローチであるAnytime Evolutionary DCOP(AED)は、進化最適化メタヒューリスティックを利用してDCOPを解く。
第2のコントリビューションでは、人口ベースのアプローチと局所的な検索アプローチを組み合わせることができることを示す。
- 参考スコア（独自算出の注目度）: 12.21350091202884
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Distributed Constraint Optimization Problems (DCOPs) are a widely studied
class of optimization problems in which interaction between a set of
cooperative agents are modeled as a set of constraints. DCOPs are NP-hard and
significant effort has been devoted to developing methods for finding
incomplete solutions. In this paper, we study an emerging class of such
incomplete algorithms that are broadly termed as population-based algorithms.
The main characteristic of these algorithms is that they maintain a population
of candidate solutions of a given problem and use this population to cover a
large area of the search space and to avoid local-optima. In recent years, this
class of algorithms has gained significant attention due to their ability to
produce high-quality incomplete solutions. With the primary goal of further
improving the quality of solutions compared to the state-of-the-art incomplete
DCOP algorithms, we present two new population-based algorithms in this paper.
Our first approach, Anytime Evolutionary DCOP or AED, exploits evolutionary
optimization meta-heuristics to solve DCOPs. We also present a novel anytime
update mechanism that gives AED its anytime property. While in our second
contribution, we show that population-based approaches can be combined with
local search approaches. Specifically, we develop an algorithm called DPSA
based on the Simulated Annealing meta-heuristic. We empirically evaluate these
two algorithms to illustrate their respective effectiveness in different
settings against the state-of-the-art incomplete DCOP algorithms including all
existing population-based algorithms in a wide variety of benchmarks. Our
evaluation shows AED and DPSA markedly outperform the state-of-the-art and
produce up to 75% improved solutions.
- Abstract（参考訳）: 分散制約最適化問題(Distributed Constraint Optimization Problems, DCOP)は、協調エージェントの集合間の相互作用を制約の集合としてモデル化する最適化問題である。
DCOPはNPハードであり、不完全解を見つける方法の開発に多大な努力が注がれている。
本稿では,人口ベースアルゴリズムと広く呼ばれる不完全なアルゴリズムの新たなクラスについて検討する。
これらのアルゴリズムの主な特徴は、与えられた問題の候補解の集団を維持し、この集団を用いて探索空間の広い領域をカバーし、局所オプティマを避けることである。
近年,高品質な不完全解を生成する能力によって,このようなアルゴリズムが注目されている。
本稿では,最新の不完全DCOPアルゴリズムと比較して,解の質をさらに向上することを目的として,2つの新しい集団ベースアルゴリズムを提案する。
最初のアプローチであるAnytime Evolutionary DCOP(AED)は、進化最適化メタヒューリスティックを利用してDCOPを解く。
また、AEDをいつでも利用できる新しいリアルタイム更新機構も提示する。
第2のコントリビューションでは、人口ベースのアプローチと局所的な検索アプローチを組み合わせることができることを示す。
具体的には,Simulated Annealingメタヒューリスティックに基づくDPSAと呼ばれるアルゴリズムを開発した。
我々はこれらの2つのアルゴリズムを実験的に評価し、様々なベンチマークで既存の人口ベースアルゴリズムを含む最先端の不完全DCOPアルゴリズムに対して異なる設定でそれぞれの効果を示す。
AEDとDPSAは最先端を著しく上回り,最大75%の改善ソリューションが得られた。
関連論文リスト
- Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。
これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。
我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
論文 参考訳（メタデータ） (2024-07-22T23:24:03Z) - Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。
本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
論文 参考訳（メタデータ） (2024-01-19T07:40:24Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳（メタデータ） (2023-07-01T18:35:21Z) - A Simple Evolutionary Algorithm for Multi-modal Multi-objective
Optimization [0.0]
マルチモーダル・多目的最適化問題(MMOP)を解くための定常進化アルゴリズムを提案する。
本報告では,1000関数評価の低計算予算を用いて,様々なテストスイートから得られた21個のMMOPの性能について報告する。
論文 参考訳（メタデータ） (2022-01-18T03:31:11Z) - A survey on multi-objective hyperparameter optimization algorithms for
Machine Learning [62.997667081978825]
本稿では,多目的HPOアルゴリズムに関する2014年から2020年にかけての文献を体系的に調査する。
メタヒューリスティック・ベース・アルゴリズムとメタモデル・ベース・アルゴリズム,および両者を混合したアプローチを区別する。
また,多目的HPO法と今後の研究方向性を比較するための品質指標についても論じる。
論文 参考訳（メタデータ） (2021-11-23T10:22:30Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - PAMELI: A Meta-Algorithm for Computationally Expensive Multi-Objective
Optimization Problems [0.0]
提案アルゴリズムは,実モデルのモデルによって定義される一連の代理問題の解法に基づく。
また,最適化ランドスケープのための最適なサロゲートモデルとナビゲーション戦略のメタ検索を行う。
論文 参考訳（メタデータ） (2021-03-19T11:18:03Z) - A Particle Swarm Inspired Approach for Continuous Distributed Constraint
Optimization Problems [7.512486812178571]
連続DCOPは連続変数で問題を明示的にモデル化することができる。
C-DCOPを解くための最先端のアプローチは、面倒なメモリか計算オーバーヘッドのいずれかを経験する。
そこで我々は,Particle Swarm Optimization(PSO)にインスパイアされた新しいC-DCOPアルゴリズム,すなわちParticle Swarm Optimization Based C-DCOP(PCD)を提案する。
論文 参考訳（メタデータ） (2020-10-20T11:04:47Z) - Deep Reinforcement Learning for Field Development Optimization [0.0]
本研究の目的は,畳み込みニューラルネットワーク(CNN)深部強化学習(DRL)アルゴリズムをフィールド開発最適化問題に適用することである。
近似ポリシー最適化 (PPO) アルゴリズムは2つのCNNアーキテクチャで様々な層と構成を持つ。
両ネットワークは、ハイブリッド粒子群最適化(PSO-MADS)アルゴリズムと比較して満足な結果をもたらすポリシーを得た。
論文 参考訳（メタデータ） (2020-08-05T06:26:13Z) - Resource Allocation via Model-Free Deep Learning in Free Space Optical
Communications [119.81868223344173]
本稿では,自由空間光学(FSO)通信におけるチャネルフェージング効果の緩和のための資源配分の一般的な問題について検討する。
本フレームワークでは,FSO資源割り当て問題を解決する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-07-27T17:38:51Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。