Enhancing island model genetic programming by controlling frequent trees

• Autorzy: Ono Keiko , Hanada Yoshiko , Kumano Masahito , Kimura Masahiro

Identyfikatory

DOI

10.2478/jaiscr-2018-0024

• Języki publikacji: EN

Abstrakty

EN

In evolutionary computation approaches such as genetic programming (GP), preventing premature convergence to local minima is known to improve performance. As with other evolutionary computation methods, it can be difficult to construct an effective search bias in GP that avoids local minima. In particular, it is difficult to determine which features are the most suitable for the search bias, because GP solutions are expressed in terms of trees and have multiple features. A common approach intended to local minima is known as the Island Model. This model generates multiple populations to encourage a global search and enhance genetic diversity. To improve the Island Model in the framework of GP, we propose a novel technique using a migration strategy based on textit frequent trees and a local search, where the frequent trees refer to subtrees that appear multiple times among the individuals in the island. The proposed method evaluates each island by measuring its activation level in terms of the fitness value and how many types of frequent trees have been created. Several individuals are then migrated from an island with a high activation level to an island with a low activation level, and vice versa. The proposed method also combines strong partial solutions given by a local search. Using six kinds of benchmark problems widely adopted in the literature, we demonstrate that the incorporation of frequent tree information into a migration strategy and local search effectively improves performance. The proposed method is shown to significantly outperform both a typical Island Model GP and the aged layered population structure method.

Słowa kluczowe

EN

genetic programming; island model; frequent tree-based migration strategy

• Wydawca: University of Social Sciences
• Czasopismo: Journal of Artificial Intelligence and Soft Computing Research
• Rocznik: 2019
• Tom: Vol. 9, No. 1
• Strony: 51--65
• Opis fizyczny: Bibliogr. 34 poz., rys.

Twórcy

autor

Ono Keiko

• Department of Computer Engineering, Ryukoku University, Shiga 5202194, Japan

autor

Hanada Yoshiko

• Faculty of Engineering Science, Kansai University, Japan

autor

Kumano Masahito

• Department of Electronics and Informatics, Ryukoku University, Shiga 5202194, Japan

autor

Kimura Masahiro

• Department of Electronics and Informatics, Ryukoku University, Shiga 5202194, Japan

Bibliografia

• [1] J. Koza, in Genetic Programming and Evolvable Machines, vol. 11 (2010), vol. 11, pp. 251–284
• [2] Y. Shichel, E. Ziserman, M. Sipper, in Proceedings of 8th European Conference on Genetic Programming (Eurogp2005). (to appear). xxx.tex; 12/06/2005; 9:07; p.24 Genetically Programming Backgammon Players, Draft 25 (SpringerVerlag, 2005), pp. 143–154
• [3] B. Samie, G. Dragffy, A. Pipe, Y. Liu, in Proceedings of the Third European Conference on Genetic Programming EuroGP’00 (2011), pp. 73–84
• [4] V.S. Gordon, D. Whitley, D. Whitley, in Proceedings of the 5th International Conference on Genetic Algorithms (1993), pp. 177–183
• [5] D. Whitley, Statistics and Computing 4, 65 (1994)
• [6] J.J.G. Chrisila B. Pettey, Michael R. Leuze, in Proceeding Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application (1987), pp. 155–161
• [7] D. Andre, J.R. Koza, in Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications PDPTA’96, Volume III (1996), pp. 1163–1174
• [8] W.F. Punch, in Proceedings of the Third Annual Conference Genetic Programming (1998), pp. 308–313
• [9] F. Fernandez, M. Tomassini, W.F. Punch III, J.M. Sanchez, in Proceedings of the Third European Conference on Genetic Programming EuroGP’00 (2000), pp. 283–293
• [10] F. Fernandez, G. Galeano, J.A. G ´ omez, in Proceedings of the 5th European Conference on Genetic Programming EuroGP’02 (2002), pp. 326–336
• [11] J. Hu, E.D. Goodman, K. Seo, in Genetic Programming Theory and Practice, ed. by R.L. Riolo, B. Worzel (Kluwer, 2003), chap. 6, pp. 81–98
• [12] J. Hu, E.D. Goodman, K. Seo, M. Pei, in GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, ed. by W.B. Langdon, E. Cantu-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, . Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M.A. Potter, A.C. Schultz, J.F. Miller,E. Burke, N. Jonoska (Morgan Kaufmann Publishers, New York, 2002), pp. 772–779
• [13] J. Hu, E. Goodman, K. Seo, Z. Fan, in Evolutionary Computation, vol. 13 (2005), vol. 13, pp. 241–277
• [14] G.S. Hornby, in In Proceedings of the 11th Annual conference on Genetic and evolutionary computation (ACM, 2009), pp. 795–802
• [15] G.S. Hornby, in Genetic Programming Theory and Practice VII, ed. by R.L. Riolo, U.M. O’Reilly, T. McConaghy (Springer, 2009), Genetic and Evolutionary Computation, pp. 87–102
• [16] G. Hornby, in GECCO (2006), pp. 815–822
• [17] M.F. Korns, in Genetic Programming Theory and Practice IX, ed. by R. Riolo, E. Vladislavleva, J.H. Moore (Springer, Ann Arbor, USA, 2011), Genetic and Evolutionary Computation, pp. 129–151
• [18] R. Poli, N.F. McPhee, Evolutionary Computation 11(2), 169 (2003)
• [19] N.F. McPhee, B. Ohs, T. Hutchison, in Proceedings of the 11th European conference on Genetic programming EuroGP’08 (2008), pp. 134–145
• [20] S.C. Roberts, D. Howard, J.R. Koza, in Proceedings of the 4th European conference on Genetic programming EuroGP’01 (2001), pp. 160–175
• [21] K. Ono, Y. Hanada, M. Kumano, M. Kimura, in IEEE Congress on Evolutionary Computation (IEEE, 2013), pp. 2988–2995
• [22] T. Asai, K. Abe, S. Kawasoe, H. Sakamoto, S. Arikawa, in Proceedings of SIAM International Conference on Data Mining SDM’02 (2002), pp. 158–174
• [23] T. Asai, H. Arimura, T. Uno, S. ichi Nakano, in Proc. of the 6th Intl. Conf. on Discovery Science (Springer-Verlag, 2003), pp. 47–61
• [24] C. Fillon, A. Bartoli, in Proceedings of the 9th European conference on Genetic Programming EuroGP’06 (2006), pp. 13–23
• [25] S. Luke, G.C. Balan, L. Panait, in Proceedings of the 2003 international conference on Genetic and evolutionary computation GECCO’03: Part II (2003), pp. 1729–1739
• [26] K. Yanai, H. Iba, in Proceedings of the 2003 Congress on Evolutionary Computation CEC’03, vol. 3 (2003), vol. 3, pp. 1618–1625
• [27] W.B. Langdon, R. Poli, Foundations of genetic programming (Springer, 2002)
• [28] W. Langdon, R. Poli, in Proceedings of the Third Annual Conference Genetic Programming GP’98 (1998), pp. 193–201
• [29] A. In, K. Kinnear, B. Punch, D. Zongker, E. Goodman, in Advances in Genetic Programming II, MIT Press (1996)
• [30] C. Tuite, M. O’Neill, A. Brabazon, in GECCO (Companion) (ACM, 2013), pp. 151–152
• [31] H. Majeed, in Proceedings of the 2005 workshops on Genetic and evolutionary computation GECCO’05 (2005), pp. 378–381
• [32] H. Majeed, C. Ryan, in Proceedings of the 9th European conference on Genetic Programming EuroGP’06 (2006), pp. 36–48
• [33] J. McDermott, U.M. O’Reilly, L. Vanneschi, K. Veeramachaneni, in Proceedings of the 14th European conference on Genetic programming EuroGP’11 (2011), pp. 190–202
• [34] E. Burke, S. Gustafson, G. Kendall, IEEE Transactions on Evolutionary Computation 8(1), 47 (2004)

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).