Abstract
Model checking is a way of analysing programs and program-like structures to decide whether they satisfy a list of temporal logic statements describing desired behaviour. In this paper we apply this to the fitness checking stage in an evolution strategy for learning finite state machines. We give experimental results consisting of learning the control program for a vending machine.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Acras, R.N., Vergilio, S.R.: Splinter: A generic framework for evolving modular finite state machines. In: Bazzan, A.L.C., Labidi, S. (eds.) SBIA 2004. LNCS (LNAI), vol. 3171, pp. 356–365. Springer, Heidelberg (2004)
Banzhaf, W., Nordin, P., Keller, R.E., Francone, F.D.: Genetic Programming: An Introduction. Morgan Kaufmann, Seattle (1998)
Burch, J.R., Clarke, E.M., McMillan, K.L., Dill, D.L., Hwang, L.J.: Symbolic model checking: 1020 states and beyond. In: Proceedings of the Fifth Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, Los Alamitos (1990)
Casavant, T.L., Kuhl, J.G.: A communicating finite automata approach to modeling distributed computation and its application to distributed decision-making. IEEE Trans. Computers 39(5), 628–639 (1990)
Chellapilla, K., Czarnecki, D.: A preliminary investigation into evolving modular finite state machines. In: Proceedings of the 1999 IEEE Congress on Evolutionary Computation, IEEE Press, New York (1999)
Clark, J., et al.: Reformulating software engineering as a search problem. IEE Proceedings - Software 150(3), 161–175 (2003)
Clark, J.A., Jacob, J.L.: Protocols are programs too: the meta-heuristic search for security protocols. Information and Software Technology 43(14), 891–904 (2001)
Clarke Jr., E.M., Grumberg, O., Peled, D.A.: Model Checking. MIT Press, Cambridge (1999)
Emerson, E.A.: Temporal and modal logic. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. B, pp. 955–1072. MIT Press, Cambridge (1990)
Fogel, D.B.: Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. IEEE Press, New York (1995)
Fogel, L.J., Owens, A.J., Walsh, M.J.: Artificial Intelligence through Simulated Evolution. Academic Press, San Diego (1966)
Harman, M., Clark, J.A.: Metrics are fitness functions too. In: Proceedings of the Tenth IEEE International Symposium on Software Metrics, pp. 58–69. IEEE Press, New York (2004)
Harman, M., Jones, B.F.: Search-based software engineering. Information and Software Technology 43(14), 833–839 (2001)
Hinton, A., Kwiatkowska, M., Norman, G., Parker, D., PRISM,: a tool for automatic verification of probabilistic systems. In: Hermanns, H., Palsberg, J. (eds.) TACAS 2006 and ETAPS 2006. LNCS, vol. 3920, pp. 441–444. Springer, Heidelberg (2006)
Huelsbergen, L.: Abstract program evaluation and its application to sorter evolution. In: Proceedings of the 2000 Congress on Evolutionary Computation, pp. 1407–1414. IEEE Press, New York (2000)
Huth, M., Ryan, M.: Logic in Computer Science: Modelling and Reasoning about Systems. Cambridge University Press, Cambridge (2000)
Johnson, C.G.: Deriving genetic programming fitness properties by static analysis. In: Foster, J.A., et al. (eds.) EuroGP 2002. LNCS, vol. 2278, Springer, Heidelberg (2002)
Johnson, C.G.: Genetic programming with guaranteed constraints. In: Lotfi, A., Garibaldi, J.M. (eds.) Applications and Science in Soft Computing, pp. 95–100. Springer, Heidelberg (2004)
Keijzer, M.: Improving symbolic regression with interval arithmetic. In: Ryan, C., et al. (eds.) EuroGP 2003. LNCS, vol. 2610, pp. 70–82. Springer, Heidelberg (2003)
Koza, J.R.: Genetic Programming: On the Programming of Computers by means of Natural Selection. Series in Complex Adaptive Systems. MIT Press, Cambridge (1992)
O’Neill, M., Ryan, C.: Grammatical evolution. IEEE Transactions on Evolutionary Computation 5(4), 349–358 (2001)
O’Neill, M., Ryan, C.: Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Kluwer, Dordrecht (2003)
Partridge, D., Galton, A.: The specification of ‘specification’. Minds and Machines 5(2), 243–255 (1995)
Partridge, D., Yates, W.B.: Data-defined problems and multiversion neural-net systems. Journal of Intelligent Systems 7(1–2), 19–32 (1997)
Petrovic, P.: Comparing finite-state automata representation with gp-trees. IDI Technical report 05/2006, Norwegian University of Science and Technology (2006)
Ryan, C.: Pygmies and civil servants. In: Kinnear Jr., K.E. (ed.) Advances in Genetic Programming, pp. 243–263. MIT Press, Cambridge (1994)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Johnson, C.G. (2007). Genetic Programming with Fitness Based on Model Checking. In: Ebner, M., O’Neill, M., Ekárt, A., Vanneschi, L., Esparcia-Alcázar, A.I. (eds) Genetic Programming. EuroGP 2007. Lecture Notes in Computer Science, vol 4445. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71605-1_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-71605-1_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-71602-0
Online ISBN: 978-3-540-71605-1
eBook Packages: Computer ScienceComputer Science (R0)