1
早稲田大学大学院情報生産システム研究科
博士論文審査結果報告書
論 文 題 目
Study on Intelligent Negotiation using Genetic Network Programming Evolving based on
Agreement Conditions
申 請 者 Tofazzal HOSSAIN
情報生産システム工学専攻 ニューロコンピューティング研究
2013 年 6 月
2
有向グラフ構造をもつGenetic Network Programming(GNP)は、2000年に平 澤が提案した進化論的計算アルゴリズムであり、①部分観測マルコフプロセスを 容易に実現できる、②判定ノードおよび処理ノードの重複利用が可能なためコン パクトな解を生成できる、③ノード遷移を活用するためメモリ機構を有している などの特徴をもっている。そのため、データマイニング、株式売買のタイミング の決定、エレベータ群管理、道路交通流の予測などに展開されている。
本論文は、GNPの交渉モデルへの展開に関するものである。具体的には、商品 の買い手と売り手が買値・売値を入札により決定する典型的な交渉システムを取 り上げ、GNPで構成した買い手エージェント、あるいは、売り手エージェントが GNPを使用しない交渉戦略に比較し、どのような知的交渉戦略を獲得できるのか を検討している。このような交渉モデルについては、従来、Monotonic Concession Protocol(MCP), Genetic Algorithm(GA), Learning Classifier System(LCS)およ びReinforcement Learning(RL)を活用したモデルなどが研究されてきた。しかし、
これらは、譲歩戦略を中心としたモデルであり、また、これらのモデルの進化・
学習アルゴリズムも柔軟で最適な戦略を構築するには不十分であった。
本論文では、初めに、買い手エージェントと売り手エージェントが GNP を使 用して買値・売値を入札するBasic Negotiation Model を提案し、このモデルの 基本特性を明らかにしている。次に、Basic Negotiation Modelを発展させ、複数 の買い手が複数の売り手と交渉するMultilateral Negotiation Model、商品の価 格 の み な ら ず 、 商 品 の 配 送 時 間 と 保 険 に 関 す る 項 目 も 考 慮 し て 進 化 す る Multi-Issue Negotiation Model、および、生態系の共生現象を活用したMasbiole Negotiation Modelを提案し評価している。
第1章では、交渉モデルと進化論的計算アルゴリズムの進展について述べ、交 渉成立時にのみ、エージェント個体の適合度を計算する新しい進化論的計算手法 が交渉モデルの実現にとって有効であるという着想に至った経緯および期待でき る効果を従来方式と比較しながら述べ、本論文の内容を要約している。
第 2 章では、GNP で構成した買い手エージェントと売り手エージェントが買 値・売値を入札により決定するBasic Negotiation Modelにおいて、買い値が売 値より高くなる(交渉成立)場合にのみ、交渉価格であるエージェント個体の適合 度を計算する新しい進化論的計算手法を提案し、買い手エージェントと売り手エ ージェントがどのように進化するのかを解析している。初めに、GNPの判定ノー ドで相手エージェントの入札状況を判定し、処理ノードで入札額を決定するGNP 方式では、従来のMCP、GA、LCSおよびRL方式に比較し、譲歩や非譲歩など の多様な入札を柔軟に構成できることを明らかにしている。次に、各世代の各エ ージェント個体間で交渉が成立した場合のみ各エージェント個体の適合度を計算 する方式を具体的に説明している。
3
シミュレーションでは、交渉が成立した場合のみ適合度を計算する交渉成立付 き進化の検証を行うため、世代ごとの交渉成立率を計算したところ最終500世代 内にほぼすべてのエージェント個体間で交渉が成立することを明らかにしている。
また、通常の進化と異なり、適合度曲線は初期世代に最適に近い値に急接近する が振動している、しかし、世代とともに適合度曲線は最適解に安定に収束してい くことを示している。
第 3 章では、複数の買い手が複数の売り手と交渉する GNP を利用した Multilateral Negotiation Modelを提案し評価している。初めに、１対１対応の 交渉を基本とするMultilateral Negotiation Model はｎ対ｎ対応のContinuous Double Auction(CDA)などと異なり、エージェント間のプライバシーが守られる、
譲歩や非譲歩などの多様な入札が可能である、および、買い手（売り手）が自分 にとって最適な売り手（買い手）を決定できるなどの特徴があることを示してい る。また、より現実的な交渉モデルを実現するため、売り手エージェントおよび 買い手エージェントにそれぞれの価格許容限界を示す目標価格を導入しエージェ ントの適合度を計算している。
シミュレーションでは、GNPで構成した買い手エージェントとMCPで構成し た買い手エージェントが、それぞれ、MCPで構成した売り手エージェントと交渉 した場合のGNP買い手エージェントとMCP買い手エージェントの比較評価を行 っている。その結果、GNP買い手エージェントの適合度がMCP買い手エージェ ントの適合度より約2.5倍高くなることを明らかにしている。また、GNPで構成 した買い手エージェントと売り手エージェントの交渉では、交渉成立までの入札 回数が18回であるのに対して、MCPで構成したエージェントとの交渉では、入 札回数が23回となることを示している。その結果、GNPエージェントの入札回 数がMCPエージェントの入札回数より約22%減少し, GNPの進化により知的な エージェントを構築できることを明らかにしている。
第 4 章では, 商品の価格のみならず、商品の配送時間と保険に関する項目も考 慮して進化するGNPを利用したMulti-Issue Negotiation Modelを提案し評価し ている。従来のMulti-Issue Negotiation Modelでは、複数の項目をまとめて交 渉する結合方式や項目ごとの交渉をそれぞれ個別に行う個別方式が主流であり更 なる方式の改善が求められていた。提案方式は、GNPの判定ノードで個々の項目 を判定する柔軟な方式であるため、価格、配送時間および保険の多彩な組み合わ せで交渉が成立する特徴があることを示している。また、交渉は入札により買い 手エージェントのオファーが売り手エージェントのオファーより高くなる場合に 成立し、オファーは商品の価格、配送時間および保険の各オファーの線形結合で 計算している。
シミュレーションでは、GNPで構成した買い手エージェントとMCPで構成し
4
た買い手エージェントが、それぞれ, GNPで構成した売り手エージェントと交渉 した場合のGNP買い手エージェントとMCP買い手エージェントの比較評価を行 っている。その結果、GNP買い手エージェントの適合度がMCP買い手エージェ ントの適合度より約3倍高くなることを明らかにしている。これは、GNPの進化 によりGNPで構成したエージェントがMCPで構成したエージェントより優れた 交渉能力を持つことが可能になることを示している。
第5章では、GNPを利用したMasbiole Negotiation Modelを提案し評価して いる。Masbiole(Multi Agent Systems with Symbiotic Learning and Evolution) は生態系の共生現象をモデル化した進化論的計算アルゴリズムで、自分エージェ ントのみならず相手エージェントの適合度を考慮した自分エージェントの進化が 可能であり、買い手GNPエージェントと売り手GNPエージェントの交渉に、相 手を搾取する戦略、あるいは、相手と共栄する戦略が可能になることを示してい る。
シミュレーションでは、売り手エージェントに対して搾取戦略をとる買い手エ ージェントと売り手エージェントに対して共栄戦略をとる買い手エージェントの 比較評価を行っている。その結果、搾取戦略をとる買い手エージェントの適合度 が共栄戦略をとる買い手エージェントの適合度より約 17％高くなることを明ら かにしている。
第6章では、GNPで構成した買い手エージェント、あるいは、売り手エージェ ントが入札により交渉を行う各種モデルの研究成果を総括している。
以上、本論文では、GNPで構成した商品の買い手エージェントと売り手エージ ェントの交渉システムを取り上げ、交渉成立時にのみエージェント個体の適合度 を計算する新しい進化論的計算アルゴリズムを提案している。さらに、提案方式 を各種の交渉モデルに展開しモデルの有効性を明らかにしている。従って、交渉 システムに適した進化論的計算アルゴリズムの確立とその応用拡大に寄与すると ころが大である。よって、本論文は博士（工学）の学位論文として価値あるもの と認める。
2013年5月30日
主査 早稲田大学 教授 博士（情報工学）（九州工業大学） 古月敬之 早稲田大学 教授 工学博士 （早稲田大学） 吉江修 早稲田大学 教授 博士（工学） （早稲田大学） 藤村茂 早稲田大学 教授 博士（工学） （グルノーブル大学）Lepage Yves
早稲田大学 名誉教授 工学博士 （九州大学） 平澤宏太郎
