分散制約最適化問題近似解法の多重実行の効果
スポンサーリンク
概要
- 論文の詳細を見る
分散制約最適化問題は,マルチエージェント環境における分散問題解法として注目を集めている.しかし提案されている解法は,最適解を保証するために非常に長い処理時間を要するか,あるいは確率的解法により短い時間で粗い近似解を得るのが限界であった.現実世界の複雑な問題への適用を考えた場合,短い時間で品質の高い近似解が得られる効率的手法が求められる.本論文では,分散制約最適化問題のための分散非決定性近似アルゴリズムの効率化を目指した多重化手法を提案する.分散アルゴリズムの計算時間の多くはメッセージ通信に費やされること,よって個々のノードの計算量やメッセージ長の少しの増加はアルゴリズム全体の効率に直接大きな影響を及ぼさないという前提のもとでは,分散近似アルゴリズムを多重実行することで効率を上げることが可能である.本論文ではその効果について極値分布理論を用いた理論的解析を行うとともに,シンプルなアルゴリズムの多重化実験により検証を行った.その結果,計算時間の大幅な短縮や解の品質の向上とともに,計算結果の分散を小さくできる効果を確認した.
- 2009-12-15
著者
-
竹内 郁雄
東京大学大学院情報理工学系研究科創造情報学専攻
-
竹内 郁雄
電通大
-
竹内 郁雄
電気通信大学情報工学科
-
飯塚 泰樹
東京大学大学院情報理工学系研究科
-
竹内 郁雄
東京大学理学部
-
竹内 郁雄
日本光電工業(株)
-
竹内 郁雄
東京大学大学院情報理工学系研究科
-
竹内 郁雄
早稲田大学理工学術院
関連論文
- 全国大会は社会の窓(特別インタビュー,写真で綴る情報処理学会全国大会50年史,50周年記念特集号)
- WebVDIのためのVNC Proxy(OS-4:仮想化,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- ソフトウェア科学会第3回大会
- 八卦的予言としてのデザイン
- 日本の風土と21世紀のソフトウェア
- オブジェクト指向計算特集の編集にあたって
- 曖昧な文法を扱うコンパイラ・コンパイラ
- 実時間記号処理システムTAO/SILENTにおける軽量プロセスの実現
- エレガントな解答をもとむ 解答--出題 2010年9月号
- 全国大会は社会の窓
- ロボカップレスキュープロジェクト
- 松原仁,野田五十樹,松野文俊,稲見昌彦,大須賀公一編, ロボット情報学ハンドブック(CD-ROM付), ナノオプトニクス・エナジー発行, 近代科学社発売, 2010年3月19日, 初版第1刷発行, B5判, 函入, 960頁
- ロボカップレスキュー・シミュレーションにおける分散協調
- スケーラビリティとユーザビリティに優れた分散ファイルシステム向けのアクセス制御機構(データアクセス・移動体,インターネットセキュリティ,一般)
- 分散制約最適化問題近似解法の多重実行の効果
- パネル討論会 : 明日のソフトウェア工学 (<特集>ソフトウェア工学の現状と動向)
- パネル討論会 : 理輪は実践を導けるか,実践は理論を生かせるか? : 第1回プログラミング : 言語・基礎・実践 研究会報告
- セミリフレクション機能を持ったエージェントの開発
- 図表的文書の記述モデルAFAL
- 次のDeep Blueはいつできるか : 2匹目のDeep Blueはいるか? : コンピュータはいつ将棋・囲碁・サッカーで人間を超えられるか
- 「AIとゲーミング」
- 要求の粒度が調節可能な遅延評価機構
- スケーラビリティとユーザビリティに優れた分散ファイルシステム向けのアクセス制御機構(データアクセス・移動体,インターネットセキュリティ,一般)
- IT防災の展開
- 複合パラダイム言語TAOにおけるオブジェクト指向プログラミングとその実現
- 複合パラダイム言語TAOにおけるオブジェクト指向プログラミングとその実現
- No-method-foundハンドラとその応用
- 会話形LispシステムTAO/60
- パネル討論会 : 第5世代コンピュータ・スーパコンピュータが商用コンピュータに与えるインパクトについて
- 枝刈り機構とメモ化機構をもつ言語
- RoboCupシミュレーションエージェントの能力とワールドモデル
- atomic-Ruby:世界でたった 1 つだけの Ruby
- パネル討論会 : Common Lisp
- VMMでWebVDIを実現するシステムの実装と評価
- 「世紀末討論会 : 20世紀, コンピュータ・サイエンスは何の役に立ったか? : 」
- ロボカップレスキュープロジェクト : マルチエージェントシステム研究の大規模災害救助への応用を目指して(特集●社会・経済におけるマルチエージェント)
- 座談会 : ロボカップレスキュー:緊急大規模災害救助への挑戦
- RoboCup-Rescue : 情報科学の緊急災害対応問題への挑戦
- エレガントな解答をもとむ(解答) 出題 2004年8月号
- エレガントな解答をもとむ 解答--出題 2009年9月号
- yass: yet another simple storage
- 融合と結合
- 融合と結合
- エレガントな解答をもとむ 解答--出題 2008年10月号
- 分散制約充足問題のためのMulti-agent Tabu Search手法の効果(モデル/理論,ソフトウェアエージェントとその応用論文)
- エレガントな解答をもとむ 解答 出題 2007年9月号
- RoboCupRescue Simulationにおける大域的行動判断
- エレガントな解答をもとむ 解答 2006年8月号
- ¬
- ¬
- Lispへのオブジェクト指向の自然な導入
- 融合型言語TAOにおける構造データと未定義値の扱い
- マルチパラダイム言語TAOにおける論理型プログラム処理系の実装
- 実行機構の類似性に着目した関数型言語と論理型言語の融合 (新しいシステムソフトウェア)
- あるマシン工房の事例 : TAO/SILENTの開発
- 記号処理カーネルSILENTのハードウェア構成
- 実時間記号処理のためのイベントボックス
- 実時間記号処理のためのイベントボックス
- TAOのパッケージシステム
- TAOのコンカレンシ・コントロール
- 逆ア・ラ・カルト逆理風 (逆の発想)
- パラドックスのパラドックス
- ウエアラブルコンピューター (知能のミステリー) -- (人工知能)
- コンピューター,ゲーム,現実世界 (知能のミステリー) -- (人工知能)
- 人工知能のゴールを見直す (知能のミステリー) -- (人工知能)
- チューリングの忘れられた研究
- レクリエ-ション数学の楽しみ
- ブ-ルの夢よ,さらば (ホフスタッタ- コンピュ-タ・エイジの魔術師)
- 亀からアキレスを見れば (ホフスタッタ- コンピュ-タ・エイジの魔術師)
- 特集「記号処理と計算機アーキテクチャ」の編集にあたって
- リスクコミニュケーションに向けた地理情報共有システム(アウェアネス,コミュニケーション支援)
- リスクコミニュケーションに向けた地理情報共有システム
- プログラミングシンポジウムGPCCのゲームとパズル
- ヒュ-マンフレンドリィなシステムとは? (機械がとらえることば)
- ビジネス・チャンスとして最近の規制整合の変革期を捉える(医科器械の国際的整合性)
- 人工知能とフォルマリズムの臨界 (情報としての世界--人工知能と心の哲学)
- 大学の人材育成--東京大学から見た人材育成の課題と対応策 (特集 日本のソフトウェア産業--人材,競争力,未来)
- RoboCupRescueヒューマンリーグの設計
- かけ声によるチームプレイの実現 : RoboCupシミュレーションにおける協調動作の考察
- 我輩はコラムである 名前はまだない
- エレガントな解答をもとむ 出題2005年8月号
- ノイマンと非ノイマン (フォン・ノイマン生誕100年)
- エレガントな解答をもとむ--解答(出題 2003年1月号)
- 未踏ソフトウェア創造事業 : 組織力から個人の才能へ
- IPA-1 未踏ソフトウェア創造事業とは(大型プロジェクト紹介,学術系企画)
- エレガントな解答をもとむ
- 複数のシミュレータを統合する大規模分散シミュレーションカーネル
- 記号処理システムLispの展望
- 未踏ユースから育ったタレントたち:0.編集にあたって
- リスト処理言語LIPQとその処理系
- エレガントな解答をもとむ 解答--出題 2011年8・9月号
- エレガントな解答をもとむ
- 〔2000年〕7月号「解いてみよう」懸賞問題・優秀者発表
- プログラミングのゆくえ
- エレガントな解答をもとむ
- 「宣言型」って何?
- やっぱり,Lispだね
- 電子メールで原稿を修正する方法--真鵺道(マヌエド)
- 銅の蓋(インタラクティブ・エッセイ)
- 日本語, 好きですか?(インタラクティブ・エッセイ)