Presentation | 2003/7/24 Acquisition of a State Transition Graphs using Genetic Network Programming Techniques Hiroaki UEDA, Noriyuki IWANE, Kenichi TAKAHASHI, Tetsuhiro MIYAHARA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Genetic Network Programming / State Transition Graphs / Finite State Machine / Machine Learning |
Paper # | AI2003-11 |
Date of Issue |
Conference Information | |
Committee | AI |
---|---|
Conference Date | 2003/7/24(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Artificial Intelligence and Knowledge-Based Processing (AI) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Acquisition of a State Transition Graphs using Genetic Network Programming Techniques |
Sub Title (in English) | |
Keyword(1) | Genetic Network Programming |
Keyword(2) | State Transition Graphs |
Keyword(3) | Finite State Machine |
Keyword(4) | Machine Learning |
1st Author's Name | Hiroaki UEDA |
1st Author's Affiliation | Faculty of Information Sciences, Hiroshima City University() |
2nd Author's Name | Noriyuki IWANE |
2nd Author's Affiliation | Faculty of Information Sciences, Hiroshima City University |
3rd Author's Name | Kenichi TAKAHASHI |
3rd Author's Affiliation | Faculty of Information Sciences, Hiroshima City University |
4th Author's Name | Tetsuhiro MIYAHARA |
4th Author's Affiliation | Faculty of Information Sciences, Hiroshima City University |
Date | 2003/7/24 |
Paper # | AI2003-11 |
Volume (vol) | vol.103 |
Number (no) | 243 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |