| 講演名 | 2003/7/24 遺伝的ネットワークプログラミングを応用した状態遷移グラフの獲得(「21世紀の知識情報科学に向けて」,及び一般) 上田 祐彰, 岩根 典之, 高橋 健一, 宮原 哲浩, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 未知の有限状態機械(FSM)の入出力系列(訓練系列)から,そのFSMの状態遷移グラフ(STG))を獲得する手法を提示する.本手法は遺伝的ネットワークプログラミング(GNP)の枠組みに基づいている.個体群は有向グラフであるSTGの集合であり,これらに対して交叉,突然変異などの遺伝的操作を繰り返し適用することにより,訓練系列に対して無矛盾なSTGの獲得を試みる.訓練系列に対して無矛盾,かつ状態数が少ないSGを獲得するため,適合度は,訓練系列を個体に印可するととによっそ得られる出力系列と訓練系列における出力系列との差およびSTGの状態数に基づいて評価している.また突然変異を実施する部分構造をヒューリスティクスを用いて選択し,探索の高速化を試みている.さらに遺伝的操作では,意味のない状態,有向辺を削除するガベージコレクションを確率的に実施している.本手法を実装しMCNSベンチマークを用いた評価実験を行った結果,ほとんどFSMに対して,訓練系列に無矛盾なSTGを獲得できることが示された.最後に,実際のエージェント環境に本手法を適用するために必要となる,改良の指針についても言及する. |
| 抄録(英) | We present the method that acquires a state transition graph(STG) from input/output sequences (training sequences) of an unknown finite state machine(FSM). Our method is based on the Genetic Network Programming(GNP) framework. Here, STGs as individuals are evolved by applying genetic operations such as crossover and mutation. The goal of our method is acquisition of an STG that is consistent with training sequences, and the number of states is as small as possible. Thus, the fitness function is consists both of the accuracy and the number of states of an STG, where the accuracy of the STG is evaluated as the difference between the output sequences of the training sequences and those from the STG. For mutation, an edge is heuristically selected from a mutated STG to find a feasible solution quickly, and the destination states of the edge is changed. Moreover, an operation which removes states and edges which have no effect on state transitions is applied to some STGs which undergo the operation with low probability. The method has been implemented and some experimental results for MCNC benchmark examples have been shown. For almost examples, we can obtain STGs that are consistent with training sequences. Finally, we discuss our plan to apply our method to agent systems. |
| キーワード(和) | 遺伝的ネッキワークプログラミング / 状態遷移グラフ / 有限状態機械 / 機械学習 |
| キーワード(英) | Genetic Network Programming / State Transition Graphs / Finite State Machine / Machine Learning |
| 資料番号 | AI2003-11 |
| 発行日 |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 2003/7/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 遺伝的ネットワークプログラミングを応用した状態遷移グラフの獲得(「21世紀の知識情報科学に向けて」,及び一般) |
| サブタイトル（和） | |
| タイトル（英） | Acquisition of a State Transition Graphs using Genetic Network Programming Techniques |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 遺伝的ネッキワークプログラミング / Genetic Network Programming |
| キーワード(2)（和/英） | 状態遷移グラフ / State Transition Graphs |
| キーワード(3)（和/英） | 有限状態機械 / Finite State Machine |
| キーワード(4)（和/英） | 機械学習 / Machine Learning |
| 第 1 著者 氏名（和/英） | 上田 祐彰 / Hiroaki UEDA |
| 第 1 著者 所属（和/英） | 広島市立大学情報科学部 Faculty of Information Sciences, Hiroshima City University |
| 第 2 著者 氏名（和/英） | 岩根 典之 / Noriyuki IWANE |
| 第 2 著者 所属（和/英） | 広島市立大学情報科学部 Faculty of Information Sciences, Hiroshima City University |
| 第 3 著者 氏名（和/英） | 高橋 健一 / Kenichi TAKAHASHI |
| 第 3 著者 所属（和/英） | 広島市立大学情報科学部 Faculty of Information Sciences, Hiroshima City University |
| 第 4 著者 氏名（和/英） | 宮原 哲浩 / Tetsuhiro MIYAHARA |
| 第 4 著者 所属（和/英） | 広島市立大学情報科学部 Faculty of Information Sciences, Hiroshima City University |
| 発表年月日 | 2003/7/24 |
| 資料番号 | AI2003-11 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 243 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |