Graph-Based Crossover: A Case Study with the Busy Beaver Problem



The success of the application of evolutionary approaches depends, to a large extent, on problem representation and on the used genetic operators. In this paper we introduce a new graph based crossover operator and compare it with classical two?point crossover. The study was carried out using a theoretical hard problem known as Busy Beaver. This problem involves the search for the Turing Machine that produces the maximum number of ones when started on a blank tape. Experimental results show that, in this domain, the new graph-based operator provides a clear advantage over two?point crossover.

PDF File

Cited by

Year 2015 : 1 citations

 A semantic network-based evolutionary algorithm for computational creativity
AG Baydin, RL de Mántaras, S Ontañón - Evolutionary Intelligence, 2015 - Springer

Year 2012 : 1 citations

 AG Baydin, RL de Mántaras. Evolution of ideas: A novel memetic algorithm based on semantic networks
IEEE Congress on Evolutionary Computation (CEC), 2012.

Year 2009 : 1 citations

 Shalaby, M., Saitou, K. (2009). High-Stifness, Lock-and-Key Heat-Reversible Locator-Snap Systems for the Design for Disassembly. Journal of Mechanical Design, Volume 131, Issue 4, 041005 (9 pages). April 2009

Year 2008 : 3 citations

 Shalaby, Mohammed Mounir, High-Stiffness, Lock-and-Key Heat-Reversible Locator-Snap Systems for the Design for Disassembly, Ph.D. Thesis, University of Michigan, 2008.

 Stonedahl, F., Rand, W., and Wilensky, U. 2008. CrossNet: a framework for crossover with network-based chromosomal representations. In Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation (Atlanta, GA, USA, July 12 - 16, 2008). M. Keijzer, Ed. GECCO '08. ACM, New York, NY, 1057-1064. DOI=

 Naidoo A., Pillay N., Using Genetic Programming for Turing Machine Induction, in M. O'Neill et al. (eds.), EuroGP 2008, Lecture Notes in Computer Science 4971, pp. 350 - 361, Springer-Verlag Berlin Heidelberg, 2008.

Year 2007 : 1 citations

 Naidoo A., Pillay N., Evolving Finite Acceptors for Regular Languages, in Neves et al., New Trends in Artificial Intelligence, pp. 193 -206, APPIA, 2007

Year 2006 : 2 citations

 N. Lyu, B. Lee, and K. Saitou. Partitioning of space frame structures for in-process dimensional adjustability and stiffness. Journal of Mechanical Design, 128(May):527–535, 2006;

 N. Lyu and K. Saitou. Decomposition-based assembly synthesis of space frame structures using joint library. Journal of Mechanical Design, 128(1):57–65, 2006;

Year 2005 : 3 citations

 Lyu, N., Saitou, K. (2005). Decomposition-Based Assembly Synthesis of a Three-Dimensional Body in White Model for Structural Stiffness. Journal of Mechanical Design, Vol. 127, No.1, pp. 34-48, January 2005

 M Shalaby, K Saitou "Design of Heat Reversible Snap Joints for Space Frame Bodies", Proceedings of IDETC/CIE 2005 ASME 2005 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference September 24-28, 2005, Long Beach, California USA

 N. Lyu and K. Saitou. Topology optimization of multicomponent beam structure via decomposition- based assembly synthesis. Journal of Mechanical Design, 127(2):170–183, 2005;

Year 2004 : 4 citations

 Niehaus, Jens, "Graphbasierte Genetische Programmierung", University of Dortmund, PhD Thesis, 2004.

 Lyu, N., Saitou, K. (2004). Decomposition-Based Assembly Synthesis of Space Frame Structures using Joint Library. In Proceedings of the International Design Engineering Technical Conferences & Computers and Information in Engineering Conference (DECT"2004), ASME International

 Lyu, N., Lee, B., Saitou, K. (2004). Decomposition-Based Assembly Synthesis for Structural Stiffness and Dimensional Integrity. In Proceedings of the 2004 ASME International Mechanical Engineering Congress and Exposition (IMECE04), ASME International

 HA Montes, JL Wyatt, Graph Representation for Program Evolution: an Overview, 2004.

Year 2003 : 3 citations

 Hironobu Katagiri, Pyeongtaek Taro Hiroshi, Takashi Hu reactor, Zyuniti Murata, "Genetic Network Programming Genetic Network Programming accepted variant on the number of nodes", Journal of electricity C (Electronics and Information Systems Division Magazine)
Vol. 123 (2003) , No. 1 pp.57-66 Vol. 123 (2003), No. 1 pp.57-66.

 Yahja, A., Carley, K. (2003). WIZER: What-if Analyzer for Automated Social Model Space Exploration and Validation. In Proceedings of the 2003 North American Association for Computational Society and Organizational Science Conference (NAACSOS 2003).

 Lyu, N., Saitou, K. (2003). Topology Optimization of Multi-Component Structures Via Decomposition-Based Assembly Synthesis. In Proceedings of the International Design Engineering Technical Conferences & Computers and Information in Engineering Conference (DECT"2003), ASME International.

Year 2002 : 4 citations

 Nattee Niparnan, A Genetic Algorithm for Finite State Machine Inference, PhD Thesis, Chulalongkorn University, 2002.

 Ben-Amram, A., Petersen, H. (2002). Improved Bounds for Functions Related to Busy Beavers. Theory of Computing Systems, Vol. 35, No. 1, pp. 1-11, Springer-Verlag

 Katagiri, H., Hirasawa, K., Jinglu, H., Murata, J. (2002). Comparing some Graph Crossover in Genetic Network Programming. In Proceedings of the 41st SICE Annual Conference, Volume 2, pp. 1263-1268, IEEE

 Dopico, J. R. R, Metodología para el desarrollo de sistemas de extracción de conocimento en RNA. PhD Thesis, University of A Coruña, 2002