An Explicit Memory Scheme of Genetic Network Programming
Shingo Mabu, Fengming Ye, and Kotaro Hirasawa
Graduate School of Information, Production and Systems, Waseda University, 2-7 Hibikino, Wakamatsu-ku, Kitakyushu, Fukuoka 808-0135, Japan
Many classical methods such as Genetic Algorithm (GA), Genetic Programming (GP), Evolutionary Strategies (ES), etc. have made significant contribution to the study of evolutionary computation. And recently, a new approach named Genetic Network Programming (GNP) has been proposed especially for solving complex problems in dynamic environments. It is based on the algorithms of classical evolutionary computation techniques and uses data structures of directed graphs which are the unique feature of GNP. Focusing on GNP’s distinguished expression ability of the graph structure, this paper proposes an enhanced architecture for standard GNP in order to improve the performance of GNP by adopting an explicit memory scheme which records and utilizes the exploited information flexibly and extensively during the evolution process of GNP. In the enhanced architecture, the important gene information of the elite individuals is extracted and accumulated in the memory during evolution. Among the accumulated information, some of them are selected and used to guide the agents. In this paper, the proposed architecture is applied to the tileworld which is an excellent benchmark for evaluating the architecture demonstrating its superiority.
-  J. H. Holland, “Adaptation in natural and artificial systems,” University of Michigan Press, Ann Arbor, 1975.
-  D. E. Goldberg, “Genetic algorithm in search optimization and machine learning,” Reading, MA: Addison-Wesley, 1989.
-  J. R. Koza, “Genetic programming, on the programming of computers by means of natural selection,” MIT Press, Cambridge, MA, 1992.
-  J. R. Koza, “Genetic programming II, automatic discovery of reusable programs,” MIT Press, Cambridge, MA, 1994.
-  D. B. Fogel, “An introduction to simulated evolutionary optimization,” IEEE Trans. on Neural Networks, Vol.5, No.1, pp. 3-14, 1994.
-  L. J. Fogel, J. M. Zurada, R. J. Marks II, and C. Goldberg, “Evolutionary programming in perspective: the top-down view, Computational Intelligence: Imitating Life,” Piscataway (Eds.), NJ: IEEE Press, 1994.
-  I. Rechenberg, J.M. Zurada, R. J.Marks II, and C. Goldberg, “Evolution strategy, Computational Intelligence: Imitating Life,” Piscataway (Eds.), NJ: IEEE Press, 1994.
-  K. Hirasawa, M. Okubo, H. Katagiri, J. Hu, and J. Murata, “Comparison between genetic network programming (GNP) and genetic programming (GP),” In Proc. of the Congress on Evolutionary Computation, pp. 1276-1282, 2001.
-  H. Katagiri, K. Hirasawa, J. Hu, and J. Murata, “Network structure oriented evolutionary model – genetic network programming – and its comparison with genetic programming,” In Proc. of the 2001 Genetic and Evolutionary Computation Conference Late Breaking Papers, pp. 219-226, 2001.
-  S. Mabu, K. Hirasawa, and J. Hu, “A graph-based evolutionary algorithm: genetic network programming (GNP) and its extension using reinforcement learning,” Evolutionary Computation, MIT Press, Vol.15, No.3, pp. 369-398, 2007.
-  S. Mabu, K. Hirasawa, and J. Hu, “Genetic network programming with learning and evolution for adapting to dynamical environments,” In Proc. of the 2003 Congress on Evolutionary Computation, pp. 69-76, 2003.
-  S. Mabu, K. Hirasawa, J. Hu, and J. Murata, “Online learning of genetic network programming and its application to prisoner���s dilemma game,” Trans. of IEE Japan, Vol.123-c, No.3, pp. 535-543, 2003.
-  K. Taboada, E. Gonzales, K. Shimada, S. Mabu, K. Hirasawa, and J. Hu, “Association Rule Mining for Continuous Attributes using Genetic Network Programming,” IEEJ Trans. on Electrical and Electronic Engineering, Vol.3, No.2, pp. 199-211, 2008.
-  Y. Chen, S. Mabu, K. Shimada, and K. Hirasawa, “A genetic network programming with learning approach for enhanced stock trading model,” Expert Systems with Applications, No.36, No.10, pp. 12537-12546, 2009.
-  K. Hirasawa, T. Eguchi, J. Zhou, L. Yu, and S. Markon, “A doubledeck elevator group supervisory control system using genetic network programming,” IEEE Trans. on Systems, Man and Cybernetics, Part C, Vol.38, No.4, pp. 535-550, 2008.
-  J. Zhou, L. Yu, S. Mabu, K. Shimada, K. Hirasawa, and S. Markon, “A Traffic Flow-Adaptive Controller of Double-Deck Elevator Systems using Genetic Network Programming,” IEEJ Trans. on Electrical and Electronic Engineering, Vol.3, No.6, pp. 703-714, 2008.
-  J. Branke, “Memory enhanced evolutionary algorithms for changing optimization problems,” In Proc. of the 1999 Congress on Evolutionary Computation, pp. 1875-1882, 1999.
-  A. Simoes and E. Costa, “An immune system-based genetic algorithm to deal with dynamic environments: Diversity and memory,” In Proc. of the 6th Int. Conf. on Neural Networks and Genetic Algorithms, pp. 168-174, 2003.
-  S. Yang, “Memory-based immigrants for genetic algorithms in dynamic environments,” In Proc. of the 2005 Genetic Evolutionary Computation Conf., pp. 1115-1122, 2005.
-  D. E. Goldberg and R. E. Smith, “Nonstationary function optimization using genetic algorithms with dominance and diploidy,” In Proc. of the 2nd Int. Conf. on Genetic Algorithms, pp. 59-68, 1987.
-  K. P. Ng and K. C. Wong, “A new diploid scheme and dominance change mechanism for non-stationary function optimisation,” In Proc. of the 6th Int. Conf. on Genetic Algorithms, pp. 159-166, 1995.
-  J. Lewis, E. Hart, and G. Ritchie, “A comparison of dominance mechanisms and simple mutation on non-stationary problems,” In Proc. of the 4th Int. Conf. on Parallel Problem Solving From Nature, pp. 139-148, 1998.
-  D. Dasgupta and D. McGregor, “Nonstationary function optimization using the structured genetic algorithm,” In Proc. of the 2nd Int. Conf. on Parallel Problem Solving From Nature, pp. 145-154, 1992.
-  S. J. Louis and Z. Xu, “Genetic algorithms for open shop scheduling and re-scheduling,” In Proc. of the 11th ISCA Int. Conf. on Computation and Their Application, pp. 99-102, 1996.
-  C. L. Ramsey and J. J. Grefenstette, “Case-based initialization of genetic algorithms,” In Proc. of the 5th Int. Conf. on Genetic Algorithms, pp. 84-91, 1993.
-  S. Yang, “Explicit Memory Schemes for Evolutionary Algorithms in Dynamic Environments,” Evolutionary Computation in Dynamic and Uncertain Environments, Vol.51, pp. 3-28, 2007.
-  Y. Cao and W. Luo, “Novel Associative Memory Retrieving Strategies for Evolutionary Algorithms in Dynamic Environments,” Lecture Notes in Computer Science, No.5821, pp. 258-268, 2009.
-  S. Yang, “Associative Memory Scheme for Genetic Algorithms in Dynamic Environments,” Lecture notes in Computer Science, No.5821, pp. 258-268, 2009.
-  X. Cai, Z. Cui, J. Zeng, and Y. Tan, “Dispersed Particle Swarm Optimization,” Information Processing Letters, Vol.105, Issue 6, pp. 231-235, 2008.
-  A. Acan and A. Gunay, “Enhanced particle swarm optimization through external memory support,” in Proc. of the 2005 IEEE Congress on Evolutionary Computation, pp. 1875-1882, 2005.
-  A. Acan, “An External Memory Implementation in Ant Colony Optimization,” Lecture notes in Computer Science, No.3172, pp. 247-269, 2004.
-  R. Poli, N. F. McPhee, L. Citi, and E. Crane, “Memory with Memory in Genetic Programming,” J. of Artificial Evolution and Applications, Vol.2009, Article ID: 570606, 2009.
-  K. Bearpark and A. Keane, “Short term memory in genetic programming,” in Proc. of the 4th Int. Conf. on Adaptive Computing in Design and Manufacture, pp. 309-320, 2000.
-  B. Andersson, P. Svensson, P. Nordin, and M. Nordahl, “Reactive and Memory-Based Genetic Programming for Robot Control,” in Proc. of the 2nd European Conf. on Genetic Programming, pp. 121-129, 2010.
-  F. Ye, S. Mabu, L. Wang, S. Eto, and K. Hirasawa, “Genetic Network Programming with Reconstructed Individuals,” SICE J. of Control, Measurement and System Integration, Vol.3, No.2, pp. 121-129, 2010.
-  M. E. Pollack and M. Ringuette, “Introducing the tile-world: experimentally evaluating agent architectures,” In Proc. of the Conf. of the American Association for Artificial Intelligence, pp. 183-189, AAAI Press, 1990.