Genetic Network Programming with Rule Accumulation and its Application to Tile-World Problem
Lutao Wang*,**,1, Shingo Mabu*,2, Fengming Ye*,3, Shinji Eto*,4, Xuefeng Fan**,5, and Kotaro Hirasawa*,6
*Graduate School of Information, Production and Systems, Waseda University, Japan
**School of Electronics and Information Engineering, Tongji University,
Siping Road 1239, 200092, Shanghai, China
Genetic Network Programming (GNP) is an evolutionary algorithm derived from GA and GP. Directed graph structure, reusability of nodes, and implicit memory function enable GNP to deal with complex problems in dynamic environments efficiently and effectively, as many paper demonstrated. This paper proposed a new method to optimize GNP by extracting and using rules. The basic idea of GNP with Rule Accumulation (GNP with RA) is to extract rules with higher fitness values from the elite individuals and store them in the pool every generation. A rule is defined as a sequence of successive judgment results and a processing node, which represent the good experiences of the past behavior. As a result, the rule pool serves as an experience set of GNP obtained in the evolutionary process. By extracting the rules during the evolutionary period and then matching them with the situations of the environment, we could, for example, guide agents’ behavior properly and get better performance of the agents. In this paper, we apply GNP with RA to the problem of determining agents’ behaviors in the Tile-world environment in order to evaluate its effectiveness. The simulation results demonstrate that GNP with RA could have better performances than the conventional GNP both in the average fitness value and its stability.
-  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 Transactions on Neural Networks, 5(1), pp. 3-14, 1994.
-  S. Mabu, K. Hirasawa, and J. Hu, “A Graph-Based Evolutionary Algorithm: Genetic Network Programming (GNP) and Its extension Using Reinforcement Learning,” Evolutionary Computation, Vol.15, No.3, pp. 369-398, 2007.
-  T. Eguchi, K. Hirasawa, J. Hu, and N.Ota, “A study of Evolutionary Multiagent Models Based on Symbiosis,” IEEE Trans. on Systems, Man and Cybernetics, Part B, Vol.35, No.1, pp. 179-193, 2006.
-  K. Hirasawa, M. Okubo, J. Hu, and J. Murata, “Comparison between Genetice Network Programming (GNP) and Genetic Programming (GP),” In Proc. of the IEEE Congress on Evolutionary Computation (CEC2001), pp. 1276-1282, 2001.
-  H. Katagiri, K. Hirasawa, J. Hu, and J. Murata, “Genetice Network Programming and Its Application to the Multiagent System,” Trans. IEE of Japan, Vol.122-C, No.12, pp. 2149-2156, 2002 (in Japanese).
-  K. Hirasawa, T. Eguchi, J. Zhou, L. Yu, J. Hu, and S. Markon, “A Double-Deck Elevator Group Supervisory Control System Using Genetic Network Programming,” IEEE Transactions on Systems, Man, And Cybernetics Part C, Vol.38, No.4, pp. 535-550, 2008.
-  Y. Chen, S. Mabu, K. Shimada, and K. Hirasawa, “Trading Rules on Stock Markets Using Genetic Network Programming with Sarsa Learning,” Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol.12, No.4, pp. 383-392, 2008.
-  W. Wei, H. Zhou, S. Mabu, K. Shimada, and K. Hirasawa, “Comparative Association Rules Mining Using Genetic Network Programming (GNP) with Attributes Accumulation Mechanism and its Application to Traffic Systems,” Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol.12, No.4, pp. 393-403, 2008.
-  C. Yue, Y. Wang, S. Mabu, K. Shimada, and K. Hirasawa, “Multiple Round English Auction based on Genetic Network Programming,” In Proc. of the symposium of FAN 2008, Hiroshima, 2008.
-  G. Yang, K. Shimada, S. Mabu, K. Hirasawa, and J. Hu, “Mining equalized association rules from multi concept layers of ontology using Genetic Network Programming ,” In Proc. of the IEEE Congress on Evolutionary Computation, pp. 705-712, 2007.
-  F. Ye, S. Mabu, K. Shimada, and K. Hirasawa, “Genetic Network Programming with Rule Chains,” In Proc. of the SICE Annual Conf. 2008, Tokyo, Japan, 2008.
-  L. Yu, J. Zhou, F. Ye, S. Mabu, K. Shimada, and K. Hirasawa, “Double-deck Elevator System using Genetic Network Programming with Genetic Operators based on Pheromone Information,” In Proc. of the 2008 GECCO Conf., pp. 2239-2244, 2008.
-  L. Wang, C. Chen, S. Mabu, K. Shimada, X. Fan, and K. Hirasawa, “Genetic Network Programming with Rule Accumulation,” In Proc. of the SICE SSI Conf. 2008, Himeji, Japan, 2008.
-  L. Wang, F. Ye, S. Mabu, S. Eto, and K. Hirasawa, “Genetic Network Programming with Rule Accumulation Considering Judgment Order,” In Proc. of the IEEE Congress on Evolution Computation (CEC2009), Norway, 2009 (submitted).
-  M. E. Pollack and M. Ringuette, “Introducing the tile-world: Experimentally evaluating agent architectures,” In T. Dietterich, and W. Swartout, (Eds.), In Proc. of the Conf. of the American Association for Artificial Intelligence, pp. 183-189, AAAI Press, 1990.