集団的意思決定支援法の実験環境に関する研究

Slides:



Advertisements
Similar presentations
●母集団と標本 母集団 標本 母数 母平均、母分散 無作為抽出 標本データの分析(記述統計学) 母集団における状態の推測(推測統計学)
Advertisements

MPIを用いたグラフの並列計算 情報論理工学研究室 藤本 涼一.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
公共経済学(06,06,02) 投票のパラドックスと中位投票者モデル1.
最大エントロピーモデルに基づく形態素解析と辞書による影響
点対応の外れ値除去の最適化によるカメラの動的校正手法の精度向上
3.2.3~3.3 D3 川原 純.
セキュアネットワーク符号化構成法に関する研究
Bipartite Permutation Graphの ランダム生成と列挙
Data Clustering: A Review
ヒープソートの演習 第13回.
多様性を実現する群知能の振舞いのモデル 木下研究室 内山 竜佑.
第11回 整列 ~ バケットソート,基数ソート,ヒープソート~
ファジィ論理と ファジィ構造モデリング 北海道工業大学 情報デザイン学科 三田村 保.
群論とルービックキューブ 白柳研究室  水野貴裕.
神奈川大学大学院工学研究科 電気電子情報工学専攻
シミュレーション論 Ⅱ 第12回 強化学習.
上坂吉則 尾関和彦 文一総合出版 宮崎大輔2003年6月28日(土)
社会心理学のStudy -集団を媒介とする適応- (仮)
先端論文紹介ゼミ Role-based Context-specific Multiagent Q-learning
プログラムの動作を理解するための技術として
1章前半.
ベイジアンネットワーク概説 3.6 構造の探索アルゴリズム
高山建志 五十嵐健夫 テクスチャ合成の新たな応用と展開 k 情報処理 vol.53 No.6 June 2012 pp
第Ⅱ部 協力ゲームの理論 第9章 シャープレイ値.
プログラム実行履歴を用いたトランザクションファンクション抽出手法
シミュレーション論 Ⅱ 第12回 様々なシミュレーション手法(3) 強化学習.
MPIを用いた並列処理 ~GAによるTSPの解法~
遺伝的アルゴリズムへの 統計力学的アプローチ 大阪大学 大学院理学研究科 鈴木譲 CISJ2005 於早稲田大学理工学部
ベイジアンネット混合モデルによる 強化学習エージェントの方策改善
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
動的依存グラフの3-gramを用いた 実行トレースの比較手法
アルゴリズムとデータ構造 2013年7月16日
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
関係 (relation) 集合Aの要素aとBの要素bとが、ある条件Rを満たすとき「Rの関係にある」といい、aRb と書く。
社会シミュレーションのための モデル作成環境
東京大学人間環境学専攻 奥田・橋本研究室 修士1年 相良 光志
補遺:質問への解答(1) 順序対と非順序対(1回目の授業)
トーリックイデアルの グレブナ基底を求める アルゴリズム – F4およびF5 –
Introduction to Soft Computing (第11回目)
早わかりアントコロニー最適化 (Ant Colony Optimization)
第9回 優先度つき待ち行列,ヒープ,二分探索木
25. Randomized Algorithms
2. 関係 五島 正裕.
2. 関係 五島 正裕.
モバイルエージェントネットワークの拡張とシミュレーション
Webコミュニティ概念を用いた Webマイニングについての研究 A study on Web Mining Based on Web Communities 清水 洋志.
所属集団の変更できる社会的ジレンマ実験について2
計算の理論 II 前期の復習 -有限オートマトン-
バイトコードを単位とするJavaスライスシステムの試作
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
第4章 識別部の設計 4-5 識別部の最適化 発表日:2003年5月16日 発表者:時田 陽一
情報知能学科「アルゴリズムとデータ構造」
第16章 動的計画法 アルゴリズムイントロダクション.
第9回 優先度つき待ち行列,ヒープ,二分探索木
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
アルゴリズムとデータ構造 2011年7月11日
Max Cut and the Smallest Eigenvalue 論文紹介
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
アルゴリズムとプログラミング (Algorithms and Programming)
メソッドの同時更新履歴を用いたクラスの機能別分類法
ヒープソート.
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
計算の理論 I 反復補題 火曜3校時 大月 美佳 平成16年7月13日 佐賀大学知能情報システム学科.
割り当て問題(assignment problem)
2008年 電気学会 全国大会 平成20年3月19日 福岡工業大学 放電基礎(1)
マルチエージェントシステムにおける 通信コストの構造依存性に関する解析
市松模様を使用した カメラキャリブレーション
2008年 7月17日 応用数理工学特論 期末発表 鈴木綾華,程飛
P2Pによる協調学習システム 唐澤 信介   北海道工業大学 電気工学専攻.
Presentation transcript:

集団的意思決定支援法の実験環境に関する研究 北海道工業大学 情報デザイン学科 大崎友之、三田村 保、大堀隆文

研究背景 マルチエージェント研究 集団的意思決定支援法の研究 エージェント=環境(environment)の状態を知覚し,行動を行うことによって環境に影響を与えることのできる自律的主体 マルチエージェント=複数のエージェントが相互作用を行う環境 集団的意思決定支援法の研究 マルチエージェントの合意形成 各エージェントが自分の意思を持ち、一つの意思にまとめる

合意形成 合意された意思 (前順序関係、半順序関係) まとめて一つの意思に 2の意思 ・・・ nの意思 エージェント1 エージェント2 1の意思 (前順序関係、半順序関係) 2の意思 ・・・ nの意思 エージェント1 エージェント2 ・・・ エージェントn

合意形成 合意された意見 (前順序関係、半順序関係) まとめて一つに nの意思 2の意思 ・・・ エージェント1 エージェント2 ・・・ 1の意思 (前順序関係、半順序関係) nの意思 2の意思 ・・・ b c e a d e a c d b a b e c d a b c d e a 1 1 1 0 0 b 0 1 1 1 1 c 0 0 1 0 0 d 0 0 1 1 0 e 0 0 1 0 1 a b c d e a 1 0 0 0 0 b 0 1 1 0 0 c 0 0 1 1 0 d 0 0 0 1 1 e 1 0 0 0 1 a b c d e a 1 0 0 0 0 b 0 0 1 0 0 c 0 1 1 0 0 d 0 0 1 1 0 e 1 0 0 1 1 エージェント1 エージェント2 ・・・ エージェントn

研究内容 集団的意思決定支援法の実験環境の整備 エージェントの意思自動生成 合意形成シミュレーション エージェントの意思を表す行列を生成実験 FISMを利用した合意形成 合意形成のシミュレーションの実行および結果

エージェントの意思自動生成 エージェントの意思を自動的に生成 自動生成実験 作成する行列数(各方法共通) エージェントの意思を表す行列 前順序関係=反射性、推移性 半順序関係=反射性、推移性、反対称性 自動生成実験 方法1 ランダム生成 方法2 Warshallのアルゴリズム 方法3 FISMを利用(前順序) 方法4 FISMを利用(半順序) 作成する行列数(各方法共通) n = 3・・・50個 n = 4・・・1,000個 n≧5・・・10,000個 前順序、半順序ともに作成した行列の平均生成率

方法1 ランダム生成 処理手順 反射性をみたす行列Mをランダムで作成 重複がないかチェックし、なければMを決定 方法1 ランダム生成 処理手順 反射性をみたす行列Mをランダムで作成 重複がないかチェックし、なければMを決定 前順序、半順序の関係を満たしているかをチェック

方法1の結果 この方法では、前順序、半順序ともにほとんど作成できない。

方法2 推移的閉包を利用 処理手順 反射性を満たす行列Mをランダムで作成 MをWarshallのアルゴリズムを利用し修正 方法2 推移的閉包を利用 処理手順 反射性を満たす行列Mをランダムで作成 MをWarshallのアルゴリズムを利用し修正 重複がないかチェックし、なければMを決定 b a c グラフの各頂点から経路で到達できる他のすべての頂点に辺をつないだグラフを、元のグラフの推移的閉包(transitive closure)と呼ぶ。 今回はそのアルゴリズムの1つである動的Blocked Warshall法のアルゴリズムを使用した。

方法2の結果 前順序は方法1より若干作成できる量は増えたが前順序、半順序ともに全体的には少ない。

FISM(Flexible Interpretive Structural Modeling) 部分可到達行列 Mii=1(反射性)   以下の条件を満たしていない Mij= x,Mik= 1,Mkj= 1 Mij= x,Mik= 0,Mkj= 1 Mij= x,Mkj= 1,Mki= 1 含意規則 以下の3種類の含意が存在する 1⇒1含意とは、xijに1を与えたとき、他の未知要素xpqを1とする含意である。 1⇒0含意とは、xijに1を与えたとき、他の未知要素xpqを0とする含意である。 0⇒0含意とは、xijに0を与えたとき、他の未知要素xpqを0とする含意である。

方法3 FISMを利用(前順序) 処理手順 反射性で他が未知の初期行列Mを作成 未知要素数が0になるまで以下を繰り返す 重複がないかチェック 未知要素(Mij= x)をランダムで選出 Mijに{0,1}をランダムでセット Mijの値から含意規則を適用してMを更新 重複がないかチェック 半順序のチェック

方法3の結果 前順序においては100%作成することが可能になった。 生成された行列のほとんどが前順序であり、半順序行列は少ない。

方法4 FISMを利用(半順序) 処理手順 反射性で他が未知の初期行列Mを作成 未知要素数が0になるまで以下を繰り返す 重複がないかチェック 未知要素(Mij= x)をランダムで選出 Mijに{0,1}をランダムでセット Mij が1のときMjiを0にする Mijの値から含意規則を適用してMを更新 重複がないかチェック

方法4の結果 半順序、前順序ともに100%作成することができるようになった。

合意形成シミュレーション 1. 集団G に所属するエージェントMK を作成 2. 比較行列Cを作成 未知要素(cij=x)を選出(今回はランダム) cijの値を{0,1}に決定(今回は多数決) 決定したcijの値から含意規則を適用してCを更新

合意形成シミュレーション 集団G = { Ak :k = 1,2,・・・,K } 選択肢W = { O1,O2,・・・,ON } Mk = [mkij] 実験条件 集団数 G=10 エージェント数 K=10 選択肢数 N=5~10,20,30 未知要素(cij=x)を選出(ランダム) cijの値を{0,1}に決定(多数決)

合意形成シミュレーション(1) 1. 集団G に所属するエージェントMK を作成 (MKは重複なく、半順序) 2. 比較行列Cを作成 C = [cij] mij , (if m(1)ij = m(2)ij = ・・・ = m(k)ij) cij = x

合意形成シミュレーション(2) 3. Cが既知行列になるまで以下を繰り返す 未知要素(cij=x)を選出(今回はランダム) cijの値から含意規則を適用してCを更新

合意形成の評価 一致度FIを以下のようにして求める

シミュレーション結果 選択肢が増加していくと一致度FIの最大値が減少し最小値が増加していることから選択肢が増えるほどばらつきが少なくなる

今後の課題 cijの決定方法 M(i,j)の決定方法 エージェントの重み付けを行う 合意方法 集団で決定 個別にエージェント同士で決定し、全体の合意を得る方法

集団的意思決定支援法の実験環境に関する研究 北海道工業大学 情報デザイン学科 大崎友之、三田村 保、大堀隆文