分散breakout : 反復改善型分散制約充足アルゴリズム(<特集>並列処理)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では分散制約充足問題を解くための新しいアルゴリズムである分散breakoutアルゴリズムを提案する.本アルゴリズムは集中型の制約充足問題を解くための反復改善型のアルゴリズムであるbreakoutアルゴリズムに触発されたものであり, 各エージェントは近傍のエージェントと現在の変数の値の割当, 可能な改善方法を交換し, エージェント全体として制約条件違反の個数が減少するように値の変更を行う.また, エージェント全体として局所最適に陥ったことを検出するのではなく, 近傍との通信のみで検出できる, より弱い条件である準局所最適を検出し, 制約の重みを変更することにより準局所最適から脱出する.実験的な評価により, 本アルゴリズムはグラフの色塗り問題の非常に難しい問題のインスタンスに関して既存のアルゴリズムより効率的であることを示す.
- 一般社団法人情報処理学会の論文
- 1998-06-15
著者
関連論文
- *-SAT:SATの拡張(最近のSAT技術の発展)
- セキュアキーワード広告オークションプロトコルの提案(メカニズムデザイン,ソフトウェアエージェントとその応用論文)
- 匿名の開環境下における協力ゲームについて(参加型シミュレーション,マルチエージェントの理論と応用)
- 1-D-6 特性関数の簡略記述法を用いた提携構造の形成(離散・組合せ最適化(2))
- 架空名義操作不可能な組合せオークションの割当規則の特性(メカニズムデザイン,ソフトウェアエージェントとその応用論文)
- Multi-MaxSAT : ラグランジュ分解・調整法を用いたWeighted Max-SAT問題の解法(分散協調とエージェント)
- 摂動完全均衡に基づくマルチエージェント部分観測可能マルコフ決定過程のプラン構築(モデル/理論,ソフトウェアエージェントとその応用論文)
- キーワード広告におけるゲーム理論・オークション理論(Web技術,ビジネスモデルとAI)
- Take-it-or-Leave-it方式の再配分オークションメカニズムの提案(メカニズムデザイン,ソフトウェアエージェントとその応用論文)
- 開環境での協力ゲームにおける公平な配分を実現する解概念の提案(PhDセッション)
- 分散制約最適化問題へのソフトアーク整合の適用
- 2-E-9 匿名の開環境における協力ゲームについて(ゲーム理論(2))
- 開放型プロダクションシステムにおけるデータ依存関係の管理
- 適切な掲載数を決定するキーワード広告オークションプロトコルの提案(エージェント)
- 組合せオークションのための架空名義操作不可能なメカニズムの特性(メカニズムデザインと電子市場(1))
- クラーク税を用いた戦略的操作不可能な費用分担メカニズムの提案(メカニズムデザインと電子市場(1))
- Take-It-or-Leave-Itに基づく再配分オークションメカニズムの提案(メカニズムデザインと電子市場(1))
- セキュアキーワード広告オークションプロトコルの提案(メカニズムデザインと電子市場(2))
- 自動メカニズムデザインによる架空名義入札に頑健な組合せオークションメカニズムの構築(メカニズムデザインと電子市場(2))
- 非準線形効用を対象とした架空名義入札に頑健な複数ユニットオークションプロトコルの提案(「エージェント基礎」及び一般)
- 適切な掲載数を決定するキーワード広告オークションの提案(オークションとメカニズムデザイン)
- 任意の評価値に対する架空名義入札に頑健なダブルオークションプロトコル
- 平均的に予算非負なダブルオークションプロトコル
- 架空名義入札に頑健な組合せオークションプロトコルにおけるバンドルの設計方法
- AAMAS 2002(会議報告)
- 架空名義入札に頑健な複数ユニットオークションプロトコル
- 逐次型オークションの入札戦略決定手法 : 準線形効用と予算制約の導入
- 架空名義入札に頑健な組合せオークションプロトコル
- インターネットオークションの理論
- 架空名義入札に頑健なダブルオークションプロトコル
- 2-D-1 数理計画法を用いたメカニズムデザインの自動化 : 架空名義入札に頑健な組合せオークションメカニズムの設計(離散・組合せ最適化(5))
- 描画用制約プログラミング言語 : CLDの設計
- 再構成可能なハードウェアを用いた充足可能性問題の解法
- 開環境での協力ゲームにおける解の簡略記述法
- 再構成可能なハードウェアを用いた充足可能性問題の解法
- 再構成可能なハードウェアを用いた充足可能性問題の解法
- 再構成可能なハードウェアを用いた充足可能性問題の解法
- 分散制約最適化問題に基づく提携構造形成問題
- 敵対者に対応する協調問題解決：限量記号付き分散制約充足問題
- 分散ラグランジュ緩和プロトコルにおける適応的な価格更新
- JAWSの発展とエージェント分野への寄与(エージェント)
- Eighteenth International Joint Conference on Artificial Intelligence(IJCAI-2003)(会議報告)
- 全米人工知能会議AAAI-94報告
- 8.パネル討論:エージェントの社会的インパクト(社会に向き合うエージェントシステム)
- 会議報告 IJCAI-01
- 特集「エージェント技術とその応用」の編集にあたって(特集・エージェント技術とその応用)
- 多状態コミットメント探索とその評価
- 多状態コミットメント実時間A^*アルゴリズムの性能解析
- 多状態コミットメント探索の性能評価
- ヒューリスティック探索へのn-状態コミットメントの導入
- ヒューリスティック探索への n-状態コミットメントの導入
- 一般化相互割当問題の上界値を求める分散ラグランジュ緩和プロトコル(マルチエージェントの理論,マルチエージェントの理論と応用)
- 一般化相互割当問題のための分散ラグランジュ緩和プロトコル(モデル/理論, ソフトウェアエージェントとその応用論文)
- An Easy-Hard-Easy Cost Profile in Distributed Constraint Satisfaction(Knowledge Processing)
- 情報収集のための分散タスク割り当て
- 情報収集のための分散タスク割り当て(「アクティブマイニング」及び一般 : 文部科学省科学研究費特定領域研究「情報洪水時代におけるアクティブマイニングの実現」公開シンポジウム)
- 情報収集のための分散タスク割り当て (知識ベースシステム研究会(第60回) 人工知能基礎論研究会(第52回) 小特集:「データマイニング」および一般) -- (文部科学省科学研究費特定領域研究 情報洪水時代におけるアクティブマイニングの実現)
- アクティブ情報統合のための動的分散制約充足プロトコル
- アクティブ情報統合のための動的分散制約充足プロトコル (テーマ:「アクティブマイニング」および一般)
- 制約充足テクニックを用いた移動体通信の周波数割当問題の解法
- 分散制約充足におけるnogood学習の効果
- 複雑な局所問題に対応する分散制約充足アルゴリズム
- 分散不完全制約充足問題
- 制約充足テクニックを用いた移動体通信の周波数割当問題の解法
- 分散breakout : 反復改善型分散制約充足アルゴリズム(並列処理)
- 環境設定ウォッチャーシステムの開発
- CSPの新しい展開 : 分散/動的/不完全CSP ( 制約充足問題の基礎と応用)
- ICMAS'95報告
- 分散制約充足におけるエージェントの非集中的組織化
- 山登り法を用いた分散制約充足における組織化
- 分散制約充足における組織化の負荷分散
- 山登り法を用いた分散制約充足における組織化
- 山登り法を用いた分散制約充足における組織化
- Greedyな割当手法に基づくStrategy-proofな組合せオークションプロトコルと公開競上げ式プロトコルへの拡張(分散協調とエージェント)
- 多様な興味を持つ専門家と素人が存在する場合の組み合わせオークション
- 専門家と素人が存在する場合の組合せオークション : 専門家が単一財にのみ専門知識をもつ場合(分散協調とエージェント)
- 専門家と素人が存在する場合の組合せオークション : 専門家が単一財にのみ専門知識を持つ場合
- 自然の選択の情報に非対称性が存在する場合のオークションプロトコルの設計(マルチエージェント)
- 専門家と素人が存在する場合の組合せオークション : 専門家が単一財にのみ専門知識を持つ場合
- 自然の選択に関する情報の非対称性のある場合のオークションプロトコルの設計
- 特集「マルチエージェント」の編集にあたって(マルチエージェント)
- 架空名義入札に頑健な公開競上げ式複数同一財オークションプロトコル
- 留保価格設定が不要な耐架空名義人札マルチユニットオークションプロトコル(ソフトウェアエージェントとその応用論文)
- 情報収集のための分散タスク割り当て (知識ベースシステム研究会(第60回) 人工知能基礎論研究会(第52回) 小特集:「データマイニング」および一般) -- (文部科学省科学研究費特定領域研究 情報洪水時代におけるアクティブマイニングの実現)
- 平均的に予算非負なダブルオークションプロトコル
- AAAI-99参加報告
- (1)マルチエージェントシステム(会議報告)
- 座談会 : AIと電子商取引の展望(AIの観点から見た電子商取引の将来像)
- マルチエージェントシステム
- 特集「マルチエージェント」の編集にあたって ( マルチエージェント)
- 分散協調処理
- Forbus, K. D. and de Kleer, J. : Building Problem Solvers, MIT Press (1993).
- 分散制約充足の高速化と通信網回線設定への適用
- 分散制約充足の通信網回線設定への適用
- 分散制約充足による分散協調問題解決の定式化とその解法
- ポアソンSAT過程における節の脆弱度と期待寿命 (特集 「医療及び化学情報マイニング」および一般)
- 過制約な一般化相互割当問題に対する分散ラグランジュ緩和プロトコル
- 制約充足や最適化に関するエージェント研究の最近の動向(エージェント)
- Distributed Search Methods for Quantified Distributed Constraint Optimization Problem
- 制約充足や最適化に関するエージェント研究の最近の動向