A more bio-plausible approach to the evolutionary inference of finite state machines

ABSTRACT

With resemblance of finite-state machines to some biological mechanisms in cells and numerous applications of finite automata in different fields, this paper uses analogies and metaphors to introduce an element of bio-plausibility to evolutionary grammatical inference. Inference of a finite-state machine that generalizes well over unseen input-output examples is an NP-complete problem. Heuristic algorithms exist to minimize the size of an FSM keeping it consistent with all the input-output sequences. However, their performance dramatically degrades in presence of noise in the training set. Evolutionary algorithms perform better for noisy data sets but they do not scale well and their performance drops as size or complexity of the target machine grows. Here, inspired by a biological perspective, an evolutionary algorithm with a novel representation and a new fitness function for inference of Moore finite-state machines of limited size is proposed and compared with one of the latest evolutionary techniques.

References

1. P. Bentley. From coffee tables to hospitals: Generic evolutionary design. In P. J. Bentley, editor, Evolutionary Design by Computers, pages 405--423. Morgan Kaufmann, San Francisco, CA, 1999.
2. P. Bentley. Digital biology. Simon & Schuster New York, 2002.
3. P. Bentley. Fractal proteins. Genetic Programming and Evolvable Machines, 5(1):71--101, 2004.
4. P. J. Bentley. Evolving beyond perfection: an investigation of the effects of long-term evolution on fractal gene regulatory networks. Biosystems, 76(1-3):291--301, 2004.
5. J. Bongard and H. Lipson. Active coevolutionary learning of deterministic finite automata. Journal of Machine Learning Research, 6:1651--1678, 2005.
6. P. Chongstitvatana and C. Aporntewan. Improving correctness of finite-state machine synthesis from multiple partial input/output sequences. In Evolvable Hardware, page 262. IEEE Computer Society, 1999.
7. C. de la Higuera. A bibliographical study of grammatical inference. Pattern Recognition, 38(9):1332--1348, 2005.
8. L. J. Fogel, A. J. Owens, and M. J. Walsh. Artificial Intelligence through Simulated Evolution. John Wiley & Sons, New York, 1966.
9. E. M. Gold. Complexity of automaton identification from given data. Information and Control, 37:302--320, 1978.
10. J. Gomez. An Incremental Learning Algorithm for Deterministic Finite Automata Using Evolutionary Algorithms (Gecco 2004 Noisy DFA Entry). Proc. Genetic and Evolutionary Computation Conf., 2004.
11. T. G. W. Gordon and P. J. Bentley. Development brings scalability to hardware evolution. In Proceedings of the 2005 NASA/DoD Conference on Evolvable Hardware, pages 272--279. IEEE Press, 2005.
12. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
13. S. A. Kauffman. Metabolic stability and epigenesis in randomly constructed genetic nets. J. Theor. Biol., 22:437--467, 1969.
14. S. Kumar and P. Bentley. On growth, form and computers. Elsevier Academic Press, 2003.
15. K. Lang, B. Pearlmutter, and F. Coste. The gowachin server. URL http://www. irisa. fr/Gowachin/, 2005.
16. K. J. Lang, B. A. Pearlmutter, and R. A. Price. Results of the Abbadingo One DFA learning competition and a new evidence-driven state merging algorithm. In Grammatical Inference; 4th International Colloquium, ICGI-98, volume 1433 of LNCS/LNAI, pages 1--12. Springer, 1998.
17. S. Lucas and T. Reynolds. Learning deterministic finite automata with a smart state labeling evolutionary algorithm. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 27(7):1063--1074, 2005.
18. C. M. Macal and M. J. North. Tutorial on agent-based modeling and simulation. In Winter Simulation Conference, pages 2--15. ACM, 2005.
19. C. Manovit, C. Aporntewan, and P. Chongstitvatana. Synthesis of synchronous sequential logic circuits from partial input/output sequences. Lecture Notes in Computer Science, 1478:98s, 1998.
20. J. F. Miller and W. Banzhaf. Evolving the program for a cell: from french flags to boolean circuits. In S. Kumar and P. J. Bentley, editors, On Growth, Form and Computers. Elsevier Academic Press, Oct. 2003.
21. E. F. Moore. Gedanken-experiments on sequential machines. In C. E. Shannon and J. McCarthy, editors, Automata Studies, number 34 in Annals of Mathematics Studies, pages 129--153. Princeton University Press, Princeton, NJ, 1956.
22. N. Niparnan and P. Chongstitvatana. An improved genetic algorithm for the inference of finite state machine. In Systems, Man and Cybernetics, 2002 IEEE International Conference on, volume 7, pages 5-, 2002.
23. A. Oliveira and J. Silva. Efficient Algorithms for the Inference of Minimum Size DFAs. Machine Learning, 44(1):93--119, 2001.
24. Pitt and Warmuth. The minimum consistent DFA problem cannot be approximated within any polynomial. JACM: Journal of the ACM, 40, 1993.
25. H. Shayani. Towards Evolution of a Digital Spiking Neuron Model for FPGA Implementation. Master's thesis, 2006.
26. T. Smith, P. Husbands, P. J. Layzell, and M. O'Shea. Fitness landscapes and evolvability. Evolutionary Computation, 10(1):1--34, 2002.
27. J. Wakerly. Digital Design: Principles and Practices. Prentice Hall, 2000.

Index Terms

• Hardware

  • Electronic design automation

    • High-level and register-transfer level synthesis