A Proposal of Memory and Prediction Based Genetic Algorithm Using Speciation in Dynamic Multimodal Function Optimization
Takumi Ichimura*, Hiroshi Inoue**, Akira Hara**,
Tetsuyuki Takahama**, and Kenneth J. Mackin***
*Faculty of Management and Information Systems, Prefectural University of Hiroshima, 1-1-71 Ujina-Higashi, Minami-ku, Hiroshima 734-8559, Japan
**Graduate School of Information Sciences, Hiroshima City University, 3-4-1 Ozuka-higashi, Asaminami-ku, Hiroshima 731-3194, Japan
***Department of Information Systems, Tokyo University of Information Sciences, 4-1 Onaridai, Wakaba-ku, Chiba 265-8501, Japan
It is a difficult problem for evolutionary algorithms to search an optimal solution in multimodal functions with dynamic environments, where individuals searchmore than one optimum and their fitness values change over time. In this paper, we propose a method of Memory and Prediction Based Genetic Algorithm Using Speciation. This method is extended with a case based memory and a meta learner for precise prediction of environmental change. Especially, the individuals in a memory consist of 4 kinds of predictors and they can adjust to the change of dynamic environment adaptively. Speciation has shown to be an effective technique for multimodal optimization. A niching method based on speciation can be used to classify a population into groups according to their similarity measured by a distance. In this paper, each group by speciation has a memory and the individuals stored in the memory can respond to the situation according to the dynamic environment. In order to verify the effectiveness, the method is examined to search for an optimal solutions in multimodal functions.
-  J. J. Grefenstette, “Genetic algorithms for changing environments,” Proc. of the 2nd Int. Conf. on Parallel Problem Solving from Nature, pp. 137-144, 1992.
-  F. Vavak and T. C. Fogarty, “comparative study of steady state and generational genetic algorithms for use in nonstationary environments,” AISB Workshop on Evolutionary Computing, LNCS, Vol.1143, Springer, pp. 297-304, 1996.
-  H. G. Cobb and J. J. Grefenstette, “Genetic algorithms for tracking changing environments,” Proc. of the 5th Int. Conf. on Genetic Algorithms, pp. 523-530, 1993.
-  J. Branke, “Memory enhanced evolutionary algorithms for changing optimization problems,” Proc. of the 1999 Congress on Evolutionary Computation, Vol.3, pp. 1875-1882, 1999.
-  J. Branke, T. Kaußler, C. Schmidth, and H. Schmeck, “A multipopulation approach to dynamic optimization problems,” Proc. of the Adaptive Computing in Design and Manufacturing, pp. 299-308, 2000.
-  J. Eggermont, T. Lenaerts, S. Poyhonen, and A. Termier, “Raising the Dead; Extending Evolutionary Algorithms with a Case-based Memory,” Proc. of the Second European Conf. on Genetic Programming (EuroGP’01), Springer-Verlag, Vol.2038 of LNCS., pp. 280-290, 2001.
-  J. Eggermont and T. Lenaerts, “Non-stationary Function Optimization using Evolutionary Algorithms with a Case-based Memory,” TechnicalReport TR2001-11, Leiden Institute of Advanced Computer Science, Leiden University, Leiden, The Netherlands, pp. 59-68, 2001.
-  J. Eggermont and T. Lenaerts, “Dynamic Optimization using Evolutionary Algorithms with a Case-based Memory,” Proc. of the 14th Belgium Netherlands Artificial Intelligence Conf. (BNAIC’02), 2002.
-  X. Li, “Efficient Differential Evolution using Speciation for Multimodal Function Optimization,” Proc. of Genetic and Evolutionary Computation Conference (GECCO05), pp. 873-880, 2005.
-  J. Branke, “Memory Enhanced Evolutionary Algorithms for Changing Optimization Problems,” Proc. of 1999 Congress on Evolutionary Computation (CEC99), Vol.3, pp.1875-1882, 1999.
-  J.-P. Li, M. E. Balazs, G. T. Parks, and P. J. Clarkson, “A species conserving genetic algorithm for multimodal function optimization,” Evolutionary Computation, Vol.10, No.3, pp. 207-234, 2002.
-  X. Li, “Adaptively choosing neighborhood bests using species in a particle swarm optimizer for multimodal function optimization,” Proc. of Genetic and Evolutionary Computation Conference 2004 (GECCO’04) (LNCS 3102), pp. 105-116, 2004.