1. bookVolume 9 (2019): Issue 1 (January 2019)
Journal Details
License
Format
Journal
First Published
30 Dec 2014
Publication timeframe
4 times per year
Languages
English
access type Open Access

Enhancing Island Model Genetic Programming by Controlling Frequent Trees

Published Online: 20 Aug 2018
Page range: 51 - 65
Received: 27 Dec 2017
Accepted: 11 Jan 2018
Journal Details
License
Format
Journal
First Published
30 Dec 2014
Publication timeframe
4 times per year
Languages
English

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 f requent 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.

Keywords

[1] J. Koza, in Genetic Programming and Evolvable Machines, vol. 11 (2010), vol. 11, pp. 251–284Search in Google Scholar

[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–154Search in Google Scholar

[3] B. Samie, G. Dragffy, A. Pipe, Y. Liu, in Proceedings of the Third European Conference on Genetic Programming EuroGP’00 (2011), pp. 73–84Search in Google Scholar

[4] V.S. Gordon, D. Whitley, D. Whitley, in Proceedings of the 5th International Conference on Genetic Algorithms (1993), pp. 177–183Search in Google Scholar

[5] D. Whitley, Statistics and Computing 4, 65 (1994)Search in Google Scholar

[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–161Search in Google Scholar

[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–1174Search in Google Scholar

[8] W.F. Punch, in Proceedings of the Third Annual Conference Genetic Programming (1998), pp. 308–313Search in Google Scholar

[9] F. Fernández, M. Tomassini, W.F. Punch III, J.M. Sanchez, in Proceedings of the Third European Conference on Genetic Programming EuroGP’00 (2000), pp. 283–293Search in Google Scholar

[10] F. Fernández, G. Galeano, J.A. Gómez, in Proceedings of the 5th European Conference on Genetic Programming EuroGP’02 (2002), pp. 326–336Search in Google Scholar

[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–98Search in Google Scholar

[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. Cantú-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. 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–779Search in Google Scholar

[13] J. Hu, E. Goodman, K. Seo, Z. Fan, in Evolutionary Computation, vol. 13 (2005), vol. 13, pp. 241–277Search in Google Scholar

[14] G.S. Hornby, in In Proceedings of the 11th Annual conference on Genetic and evolutionary computation (ACM, 2009), pp. 795–802Search in Google Scholar

[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–102Search in Google Scholar

[16] G. Hornby, in GECCO (2006), pp. 815–822Search in Google Scholar

[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–151Search in Google Scholar

[18] R. Poli, N.F. McPhee, Evolutionary Computation 11(2), 169 (2003)Search in Google Scholar

[19] N.F. McPhee, B. Ohs, T. Hutchison, in Proceedings of the 11th European conference on Genetic programming EuroGP’08 (2008), pp. 134–145Search in Google Scholar

[20] S.C. Roberts, D. Howard, J.R. Koza, in Proceedings of the 4th European conference on Genetic programming EuroGP’01 (2001), pp. 160–175Search in Google Scholar

[21] K. Ono, Y. Hanada, M. Kumano, M. Kimura, in IEEE Congress on Evolutionary Computation (IEEE, 2013), pp. 2988–2995Search in Google Scholar

[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–174Search in Google Scholar

[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–61Search in Google Scholar

[24] C. Fillon, A. Bartoli, in Proceedings of the 9th European conference on Genetic Programming EuroGP’ 06 (2006), pp. 13–23Search in Google Scholar

[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–1739Search in Google Scholar

[26] K. Yanai, H. Iba, in Proceedings of the 2003 Congress on Evolutionary Computation CEC’03, vol. 3 (2003), vol. 3, pp. 1618–1625Search in Google Scholar

[27] W.B. Langdon, R. Poli, Foundations of genetic programming (Springer, 2002)Search in Google Scholar

[28] W. Langdon, R. Poli, in Proceedings of the Third Annual Conference Genetic Programming GP’98 (1998), pp. 193–201Search in Google Scholar

[29] A. In, K. Kinnear, B. Punch, D. Zongker, E. Goodman, in Advances in Genetic Programming II, MIT Press (1996)Search in Google Scholar

[30] C. Tuite, M. O’Neill, A. Brabazon, in GECCO (Companion) (ACM, 2013), pp. 151–152Search in Google Scholar

[31] H. Majeed, in Proceedings of the 2005 workshops on Genetic and evolutionary computation GECCO’05 (2005), pp. 378–381Search in Google Scholar

[32] H. Majeed, C. Ryan, in Proceedings of the 9th European conference on Genetic Programming EuroGP’ 06 (2006), pp. 36–48Search in Google Scholar

[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–202Search in Google Scholar

[34] E. Burke, S. Gustafson, G. Kendall, IEEE Transactions on Evolutionary Computation 8(1), 47 (2004)Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo