Nothing Special   »   [go: up one dir, main page]

skip to main content
10.5555/1763756.1763768guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

Genetic programming with fitness based on model checking

Published: 11 April 2007 Publication History

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.

References

[1]
Ricardo Nastas Acras and Silvia Regina Vergilio. Splinter: A generic framework for evolving modular finite state machines. In Proceedings of SBIA 2004, pages 356-365. Springer, 2004.
[2]
Wolfgang Banzhaf, Peter Nordin, Robert E. Keller, and Frank D. Francone. Genetic Programming: An Introduction. Morgan Kaufmann, 1998.
[3]
J.R. Burch, E.M. Clarke, K.L. McMillan, D.L. Dill, and L. J. Hwang. Symbolic model checking: 1020 states and beyond. In Proceedings of the Fifth Annual IEEE Symposium on Logic in Computer Science, 1990.
[4]
Thomas L. Casavant and Jon G. Kuhl. A communicating finite automata approach to modeling distributed computation and its application to distributed decision-making. IEEE Trans. Computers, 39(5):628-639, 1990.
[5]
Kumar Chellapilla and David Czarnecki. A preliminary investigation into evolving modular finite state machines. In Proceedings of the 1999 IEEE Congress on Evolutionary Computation. IEEE Press, 1999.
[6]
John Clark, Jose Javier Dolado, Mark Harman, Rob Hierons, Mary Lumkin Bryan Jones, Brian Mitchell, Spiros Mancoridis, Kearton Rees, Marc Roper, and Martin Shepperd. Reformulating software engineering as a search problem. IEE Proceedings - Software, 150(3):161-175, 2003.
[7]
John A. Clark and Jeremy L. Jacob. Protocols are programs too: the meta-heuristic search for security protocols. Information and Software Technology, 43(14):891- 904, 2001.
[8]
Edmund M. Clarke Jr., Orna Grumberg, and Doron A. Peled. Model Checking. MIT Press, 1999.
[9]
E.A. Emerson. Temporal and modal logic. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume B, pages 955-1072. MIT Press, 1990.
[10]
D.B. Fogel. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. IEEE Press, 1995.
[11]
Lawrence J. Fogel, Alvin J. Owens, and Michael J. Walsh. Artificial Intelligence through Simulated Evolution. Academic Press, 1966.
[12]
Mark Harman and John A Clark. Metrics are fitness functions too. In Proceedings of the Tenth IEEE International Symposium on Software Metrics, pages 58-69. IEEE Press, 2004.
[13]
Mark Harman and Bryan F. Jones. Search-based software engineering. Information and Software Technology, 43(14):833-839, 2001.
[14]
A. Hinton, M. Kwiatkowska, G. Norman, and D. Parker. PRISM: a tool for automatic verification of probabilistic systems. In H. Hermanns and J. Palsberg, editors, Proceedings 12th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'06), pages 441-444, 2006. LNCS Volume 3920.
[15]
Lorenz Huelsbergen. Abstract program evaluation and its application to sorter evolution. In Proceedings of the 2000 Congress on Evolutionary Computation, pages 1407-1414. IEEE Press, 2000.
[16]
Michael Huth and Mark Ryan. Logic in Computer Science: Modelling and Reasoning about Systems. Cambridge University Press, 2000.
[17]
Colin G. Johnson. Deriving genetic programming fitness properties by static analysis. In James Foster, Evelyne Lutton, Conor Ryan, and Andrea Tettamanzi, editors, Proceedings of the 2002 European Conference on Genetic Programming. Springer, 2002.
[18]
Colin G. Johnson. Genetic programming with guaranteed constraints. In Ahmad Lotfi and Jonathan M. Garibaldi, editors, Applications and Science in Soft Computing, pages 95-100. Springer, 2004.
[19]
Maarten Keijzer. Improving symbolic regression with interval arithmetic. In Conor Ryan et al., editor, Proceedings of the 6th European Conference on Genetic Programming, pages 70-82, 2003.
[20]
John R. Koza. Genetic Programming : On the Programming of Computers by means of Natural Selection. Series in Complex Adaptive Systems. MIT Press, 1992.
[21]
Michael O'Neill and Conor Ryan. Grammatical evolution. IEEE Transactions on Evolutionary Computation, 5(4):349-358, August 2001.
[22]
Michael O'Neill and Conor Ryan. Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Kluwer, 2003.
[23]
D. Partridge and A. Galton. The specification of 'specification'. Minds and Machines, 5(2):243-255, 1995.
[24]
D. Partridge and W.B. Yates. Data-defined problems and multiversion neural-net systems. Journal of Intelligent Systems, 7(1-2):19-32, 1997.
[25]
Pavel Petrovic. Comparing finite-state automata representation with gp-trees. IDI Technical report 05/2006, Norwegian University of Science and Technology, 2006.
[26]
Conor Ryan. Pygmies and civil servants. In Kenneth E. Kinnear, Jr., editor, Advances in Genetic Programming, pages 243-263. MIT Press, 1994.

Cited By

View all
  • (2019)Solving symbolic regression problems with formal constraintsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321743(977-984)Online publication date: 13-Jul-2019
  • (2017)A hot method for synthesising cool controllersProceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software10.1145/3092282.3092299(122-131)Online publication date: 13-Jul-2017
  • (2017)Counterexample-driven genetic programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071224(953-960)Online publication date: 1-Jul-2017
  • Show More Cited By

Index Terms

  1. Genetic programming with fitness based on model checking
      Index terms have been assigned to the content through auto-classification.

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image Guide Proceedings
      EuroGP'07: Proceedings of the 10th European conference on Genetic programming
      April 2007
      382 pages
      ISBN:9783540716020

      Publisher

      Springer-Verlag

      Berlin, Heidelberg

      Publication History

      Published: 11 April 2007

      Qualifiers

      • Article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 14 Dec 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2019)Solving symbolic regression problems with formal constraintsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321743(977-984)Online publication date: 13-Jul-2019
      • (2017)A hot method for synthesising cool controllersProceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software10.1145/3092282.3092299(122-131)Online publication date: 13-Jul-2017
      • (2017)Counterexample-driven genetic programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071224(953-960)Online publication date: 1-Jul-2017
      • (2017)Synthesizing, correcting and improving code, using model checking-based genetic programmingInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-016-0418-119:4(449-464)Online publication date: 1-Aug-2017
      • (2016)Subtree semantic geometric crossover for genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-015-9253-517:1(25-53)Online publication date: 1-Mar-2016
      • (2015)Using Model Checking Techniques For Evaluating the Effectiveness of Evolutionary Computing in Synthesis of Distributed Fault-Tolerant ProgramsProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754779(1119-1126)Online publication date: 11-Jul-2015
      • (2015)Search-based synthesis of probabilistic models for quality-of-service software engineeringProceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2015.22(319-330)Online publication date: 9-Nov-2015
      • (2014)Runtime verification of microcontroller binary codeScience of Computer Programming10.1016/j.scico.2012.10.01580(109-129)Online publication date: 1-Feb-2014
      • (2014)Security analysis of an identity-based strongly unforgeable signature schemeInformation Sciences: an International Journal10.1016/j.ins.2014.07.022286(29-34)Online publication date: 1-Dec-2014
      • (2013)An interpolation based crossover operator for genetic programmingProceedings of the 15th annual conference companion on Genetic and evolutionary computation10.1145/2464576.2482689(1107-1112)Online publication date: 6-Jul-2013
      • Show More Cited By

      View Options

      View options

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media