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