Machine-Code Program Evolution by Genetic Programming Using Asynchronous Reference-Based Evaluation Through Single-Event Upset in On-Board Computer
Tomohiro Harada* and Keiki Takadama**
*College of Information Science and Engineering, Ritsumeikan University
1-1-1 Noji-Higashi, Kusatsu, Shiga 525-8577, Japan
**Department of Informatics, The University of Electro-Communications
1-5-1 Chofugaoka, Chofu, Tokyo 182-8585, Japan
This study proposes a novel genetic programming method using asynchronous reference-based evaluation (called AREGP) to evolve computer programs through single-event upsets (SEUs) in the on-board computer in space missions. AREGP is an extension of Tierra-based asynchronous genetic programming (TAGP), which was proposed in our previous study. It is based on the idea of the biological simulator, Tierra, where digital creatures are evolved through bit inversions in a program. AREGP not only inherits the advantages of TAGP but also overcomes its limitation, i.e., TAGP cannot select good programs for evolution without an appropriate threshold. Specifically, AREGP introduces an archive mechanism to maintain good programs and a reference-based evaluation by using the archive for appropriate threshold selection and removal. To investigate the effectiveness of the proposed AREGP, simulation experiments are performed to evolve the assembly language program in the SEU environment. In these experiments, the PIC instruction set, which is carried on many types of spacecraft, is used as the evolved assembly program. The experimental results revealed that AREGP cannot only maintain the correct program through SEU with high occurrence rate, but is also better at reducing the size of programs in comparison with TAGP. Additionally, AREGP can achieve a shorter execution step and smaller size of programs, which cannot be achieved by TAGP.
-  S. Buchner, D. McMorrow, J. Melinger, and A. Camdbell, “Laboratory tests for single-event effects,” IEEE Trans. on Nuclear Science, Vol.43, No.2, pp. 678-686, Apr. 1996.
-  N. Kuznetsov, “The Rate of Single Event Upsets in Electronic Circuits onboard Spacecraft,” Cosmic Research, Vol.43, pp. 423-431, 2005.
-  Reed Business Information, “EDN Japan February issue,” EDN Japan, 2005.
-  G. Swift and S. Guertin, “In-flight observations of multiple-bit upset in DRAMs,” IEEE Trans. on Nuclear Science, Vol.47, No.6, pp. 2386-2391, Dec. 2000.
-  N. Ikeda, H. Shindou, Y. Iide, H. Asai, S. Kuboyama, and S. Matsuda, “Evaluation of the Errors of Commercial Semiconductor Devices in a Space Radiation Environment,” The Trans. of the Institute of Electronics, Information and Communication Engineers, B, Vol.88, No.1, pp. 108-116, 2005.
-  J. Justesen and T. Hoholdt, “A Course In Error-Correcting Codes,” European Mathematical Society, 2004.
-  T. Harada, M. Otani, H. Matsushima, K. Hattori, H. Sato, and K. Takadama, “Robustness to Bit Inversion in Registers and Acceleration of Program Evolution in On-Board Computer,” J. of Advanced Computational Intelligence and Intelligent Informatics (JACIII), Vol.15, No.8, pp. 1175-1185, Oct. 2011.
-  T. Harada, M. Otani, H. Matsushima, K. Hattori, and K. Takadama, “Evolving Complex Programs in Tierra-based On-Board Computer on UNITEC-1,” 2010 61st World Congress on Int. Astronautical Congress (IAC), 2010.
-  K. Nonami and K. Takadama, “Tierra-based Space System for Robustness of Bit Inversion and Program Evolution,” SICE 2007 Annual Conf., pp. 1155-1160, 2007.
-  T. Kimezawa and T. S. Ray, “Artificial Life System Tierra,” Technical Report TR-H-268, ATR Human Information Processing Research Laboratories, 1999.
-  C. G. Langton, “Artificial Life,” Addison-Wesley, 1989.
-  T. S. Ray, “An approach to the synthesis of life,” Artificial Life II, Vol.XI, pp. 371-408, 1991.
-  J. Koza, “Genetic Programming On the Programming of Computers by Means of Natural Selection,” MIT Press, 1992.
-  T. Harada and K. Takadama, “Asynchronous Evaluation Based Genetic Programming: Comparison of Asynchronous and Synchronous Evaluation and Its Analysis,” K. Krawiec, A. Moraglio, T. Hu, A. Etaner-Uyar, and B. Hu (Eds.), Genetic Programming, Lecture Notes in Computer Science, Vol.7831, pp. 241-252, Springer Berlin Heidelberg, 2013.
-  T. Harada, K. Takadama, and H. Sato, “Promoting Machine-Code Program Evolution in Asynchronous Genetic Programming,” SICE J. of Control, Measurement, and System Integration, Vol.9, No.2, pp. 93-102, 2016.
-  “PIC10F200/202/204/206 Data Sheet 6-Pin, 8-bit Flash Microcontrollers,” Microchip Technology Inc., 2007.
-  D. E. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” 1st edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1989.
-  D. Jong and K. Alan, “An Analysis of the Behavior of a Class of Genetic Adaptive Systems,” Ph.D. thesis, Department of Computer and Communications Sciences, University of Michigan, 1975.
-  S. Nakasuka, “UNITEC-1 and Onboard Computer Survival Competition in Interplanetary Environment,” Proc. of 27th Int. Symposium on Space Technology and Science, 2009.
-  T. Harada and K. Takadama, “Maintaining, Minimizing, and Recovering Machine Language Program through SEU in On-Board Computer,” Proc. of the 12th Int. Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS 2014), 2014.