On synchronized evolution of the network of automata

Created by W.Langdon from gp-bibliography.bib Revision:1.4394

  title =        "On synchronized evolution of the network of automata",
  author =       "Yoshiyuki Inagaki",
  year =         "1999",
  description =  "Thesis (Ph. D., Social Science)--University of
                 California, Irvine, 1999.; Includes bibliographical
                 references (leaves 97-98).",
  oai =          "oai:xtcat.oclc.org:OCLCNo/ocm43628471",
  school =       "University of California, Irvine",
  address =      "USA",
  keywords =     "genetic algorithms, genetic programming, Computer
                 science, Sequential machine theory, Artificial
  URL =          "http://search.proquest.com/docview/304498722",
  size =         "112 pages",
  abstract =     "One of the tasks in machine learning is to build a
                 device which guesses each next input symbol of a
                 sequence as it takes one input symbol from the
                 sequence. We studied new approaches to this task. We
                 suggest that deterministic finite automata, DFA , are
                 good building blocks for this device together with
                 genetic algorithms, GA , which let these automata
                 {"}evolve{"} to guess each next input symbol of the
                 sequence. Moreover, we studied the way to combine these
                 highly fit automata so that the network of them would
                 compensate for each other's weakness and guess better
                 than any single automaton can. We studied the simplest
                 approaches to combine automata: building trees of
                 automata with special purpose automata, which may be
                 called switch-boards . These switch-board automata are
                 located on the internal nodes of the tree, take an
                 input symbol from the input sequence just like other
                 automata do, and guess which subtree will make a right
                 guess on each next input symbol. Genetic algorithms
                 again play a crucial role in searching for switch-board
                 automata. We studied various ways of growing trees of
                 automata and tested them on sample input sequences,
                 mainly note pitches, note duration, and up/down notes
                 of Bach's Fugue. The test results show that DFAs
                 together with GAs seem to be very effective for this
                 type of pattern learning task. Besides this main
                 finding, the tests revealed several interesting things.
                 For example, the sequence of the note pitches is more
                 predictable than the sequence of up/down notes. This is
                 counter intuitive. Larger alphabets mean larger numbers
                 of possible configurations of automata. This implies a
                 larger search space for genetic algorithms; therefore,
                 the algorithms should have difficulty finding automata
                 which fit the tasks. However, the tree devices built to
                 predict the note pitches often outperform those built
                 to predict the up/down notes even though the size of
                 the input alphabet for the former is 8 and that for the
                 latter is 2. This suggests the following: The genetic
                 search is so powerful and effective that if there are
                 good solutions in its search space, it will find one
                 when it works with a large enough population for a
                 large enough number of generations. Therefore, if the
                 search fails to find a good solution, the search space
                 almost certainly does not contain one.",
  notes =        "UMI 9940706 Supervisor Louis Narens

                 See also \cite{inagaki:2002:TEC}",

Genetic Programming entries for Yoshiyuki Inagaki