On Synchronized Evolution of the Network of Automata
IEEE Transactions on Evolutionary Computation, 6 (2):
147--158 (April 2002)Abstract
One of the tasks in machine learning is to build a
device that predicts 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 (GAs), which let these automata
evolve to predict each next input symbol of the
sequence. Moreover, we studied how to combine these
highly fit automata so that a network of them would
compensate for each others weaknesses and predict
better than any single automaton.We studied the
simplest approaches to combine automata: building trees
of automata with special-purpose automata, which may be
called switchboards. These switchboard automata are
located on the internal nodes of the tree, take an
input symbol from the input sequence just as do other
automata, and predict which subtree will make a correct
prediction on each next input symbol. GAs again play a
crucial role in searching for switchboard 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 IX. The test results show that DFAs together with
GAs seem to be very effective for this type of pattern
learning task.