論文の概要: Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search
- arxiv url: http://arxiv.org/abs/2407.16092v1
- Date: Mon, 22 Jul 2024 23:24:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-24 19:05:22.009780
- Title: Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search
- Title（参考訳）: オフライン連成選択とグラフ検索による高速な最適連成構造生成
- Authors: Redha Taguelmimt, Samir Aknine, Djamila Boukredera, Narayan Changder, Tuomas Sandholm,
- Abstract要約: 本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。
これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。
我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
- 参考スコア（独自算出の注目度）: 61.08720171136229
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Coalition formation is a key capability in multi-agent systems. An important problem in coalition formation is coalition structure generation: partitioning agents into coalitions to optimize the social welfare. This is a challenging problem that has been the subject of active research for the past three decades. In this paper, we present a novel algorithm, SMART, for the problem based on a hybridization of three innovative techniques. Two of these techniques are based on dynamic programming, where we show a powerful connection between the coalitions selected for evaluation and the performance of the algorithms. These algorithms use offline phases to optimize the choice of coalitions to evaluate. The third one uses branch-and-bound and integer partition graph search to explore the solution space. Our techniques bring a new way of approaching the problem and a new level of precision to the field. In experiments over several common value distributions, we show that the hybridization of these techniques in SMART is faster than the fastest prior algorithms (ODP-IP, BOSS) in generating optimal solutions across all the value distributions.
- Abstract（参考訳）: 合体形成はマルチエージェントシステムにおいて重要な機能である。
連立組織形成における重要な問題は連立組織の形成であり、社会福祉を最適化するために連立組織にエージェントを分割することである。
これは過去30年間、活発な研究の対象となっていた挑戦的な問題です。
本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。
これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。
これらのアルゴリズムはオフラインフェーズを使用して、評価のための連立の選択を最適化する。
3つめは、解空間を探索するためにブランチとバウンドおよび整数分割グラフ探索を使用する。
我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
いくつかの共通値分布に関する実験において、SMARTにおけるこれらの手法のハイブリダイゼーションは、全ての値分布に対して最適な解を生成する上で、最も高速な先行アルゴリズム(ODP-IP, BOSS)よりも高速であることを示す。
関連論文リスト
- Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - COMBHelper: A Neural Approach to Reduce Search Space for Graph
Combinatorial Problems [19.442683583536137]
COMBHelperは、ソリューションセットの有望なノードを特定するために、グラフニューラルネットワーク(GNN)を使用している。
また、知識蒸留(KD)モジュールと問題固有のブースティングモジュールを使用して、さらなる効率性と有効性をもたらす。
実験の結果,COMBHelperを用いた従来のCOアルゴリズムは,従来のバージョンに比べて少なくとも2倍高速であることがわかった。
論文 参考訳（メタデータ） (2023-12-14T16:17:20Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - A Hybrid Chimp Optimization Algorithm and Generalized Normal
Distribution Algorithm with Opposition-Based Learning Strategy for Solving
Data Clustering Problems [0.0]
本稿では、類似データと異種データを異なるグループに分類するコネクティビティ原則に基づいて、クラスタを分離するデータクラスタリングについて検討する。
メタヒューリスティック最適化アルゴリズムとインテリジェンスに基づく手法が,最適解を妥当な時間で達成するために導入された。
論文 参考訳（メタデータ） (2023-02-16T23:29:01Z) - A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms [18.075115172621096]
本稿では,Isingソルバを用いた混合二項二次プログラムの解法におけるハイブリッドアルゴリズムの形式解析について述べる。
本稿では,ハイブリッド量子古典的切削平面アルゴリズムを用いてこの問題を解決することを提案する。
論文 参考訳（メタデータ） (2022-07-27T16:47:32Z) - On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network [55.56019538079826]
バイレベル最適化は、幅広い機械学習モデルに適用されている。
既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。
そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-06-30T05:29:52Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - On Population-Based Algorithms for Distributed Constraint Optimization
Problems [12.21350091202884]
我々は、人口ベースのアルゴリズムとして広く呼ばれる、新しい不完全アルゴリズムのクラスについて研究する。
最初のアプローチであるAnytime Evolutionary DCOP(AED)は、進化最適化メタヒューリスティックを利用してDCOPを解く。
第2のコントリビューションでは、人口ベースのアプローチと局所的な検索アプローチを組み合わせることができることを示す。
論文 参考訳（メタデータ） (2020-09-02T06:39:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。