ABSTRACT
Robert Goldberg Natalie Hammerman Dept of Computer Science Dept of Math and Computer Science Queens College Molloy College 65-30 Kissena Blvd. PO Box 5002 Flushing, NY 11367 Rockville Centre, NY 11571-5002
Goldberg@qcunix1.acc.qc.edu nhammerman@fsmail.pace.edu
Abstract The co-authors (1998) previously introduced two reorganization operators (MTF and SFS) that facilitated the convergence of a genetic algorithm which uses a bitstring genome to represent a finite state machine. Smaller solutions were obtained with a faster convergence than the standard (benchmark) approaches. The current research applies this technology to a different problem area, designing automata that can recognize languages given a list of representative words in the language and a list of other words not in the language. The experimentation carried out indicates that in this problem domain also, smaller machine solutions were obtained by the MTF operator than the benchmark. Due to the small variation of machine sizes in the solution spaces of the languages tested (obtained empirically by Monte Carlo methods), MTF is expected to find solutions in a similar number of iterations as the other methods. While SFS obtained faster convergence on more languages than any other method, MTF has the overall best performance based on a more comprehensive set of evaluation criteria.
