1. bookVolume 42 (2017): Issue 4 (December 2017)
Journal Details
License
Format
Journal
First Published
24 Oct 2012
Publication timeframe
4 times per year
Languages
English
access type Open Access

Adaptive Test Selection for Factorization-based Surrogate Fitness in Genetic Programming

Published Online: 09 Dec 2017
Page range: 339 - 358
Received: 12 Apr 2017
Accepted: 23 Aug 2017
Journal Details
License
Format
Journal
First Published
24 Oct 2012
Publication timeframe
4 times per year
Languages
English

Genetic programming (GP) is a variant of evolutionary algorithm where the entities undergoing simulated evolution are computer programs. A fitness function in GP is usually based on a set of tests, each of which defines the desired output a correct program should return for an exemplary input. The outcomes of interactions between programs and tests in GP can be represented as an interaction matrix, with rows corresponding to programs in the current population and columns corresponding to tests. In previous work, we proposed SFIMX, a method that performs only a fraction of interactions and employs non-negative matrix factorization to estimate the outcomes of remaining ones, shortening GP’s runtime. In this paper, we build upon that work and propose three extensions of SFIMX, in which the subset of tests drawn to perform interactions is selected with respect to test difficulty. The conducted experiment indicates that the proposed extensions surpass the original SFIMX on a suite of discrete GP benchmarks.

Keywords

[1] Bell R., Koren Y., and Volinsky C. Modeling relationships at multiple scales to improve accuracy of large recommender systems. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 95-104. ACM, 2007.Search in Google Scholar

[2] Bongard J. and Lipson H. Active coevolutionary learning of deterministic finite automata. Journal of Machine Learning Research, 6(Oct):1651-1678, 2005.Search in Google Scholar

[3] Breese J. S., Heckerman D., and Kadie C. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence, pages 43-52. Morgan Kaufmann Publishers Inc., 1998.Search in Google Scholar

[4] Chellapilla K. and Fogel D. B. Evolving an expert checkers playing program without using human expertise. IEEE Transactions on Evolutionary Computation, 5(4):422-428, 2001.10.1109/4235.942536Open DOISearch in Google Scholar

[5] Chong S. Y., Tino P., Ku D. C., and Xin Y. Improving Generalization Performance in Co-Evolutionary Learning. IEEE Transactions on Evolutionary Computation, 16(1):70-85, 2012.10.1109/TEVC.2010.2051673Open DOISearch in Google Scholar

[6] Clark D. M. Evolution of algebraic terms 1: term to term operation continuity. International Journal of Algebra and Computation, 23(05):1175-1205, 2013.Search in Google Scholar

[7] Deb K., Pratap A., Agarwal S., and Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182-197, April 2002.10.1109/4235.996017Open DOISearch in Google Scholar

[8] Ficici S. G. and Pollack J. B. Pareto optimality in coevolutionary learning. In Kelemen J. and Sosík P., editors, Advances in Artificial Life, 6th European Conference, ECAL 2001, volume 2159 of Lecture Notes in Computer Science, pages 316-325, Prague, Czech Republic, 2001. Springer.Search in Google Scholar

[9] Fortin F.-A., De Rainville F.-M., Gardner M.-A., Parizeau M., and Gagné C. DEAP: Evolutionary algorithms made easy. Journal of Machine Learning Research, 13:2171-2175, jul 2012.Search in Google Scholar

[10] Gonçalves I., Silva S., Melo J. B., and Carreiras J. M. Random sampling technique for overfitting control in genetic programming. In Genetic Programming, pages 218-229. Springer, 2012.Search in Google Scholar

[11] Helmuth T., Spector L., and Matheson J. Solving uncompromising problems with lexicase selection. IEEE Transactions on Evolutionary Computation, 19(5):630-643, Oct. 2015.Search in Google Scholar

[12] Hofmann T. Collaborative filtering via gaussian probabilistic latent semantic analysis. In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pages 259-266. ACM, 2003.Search in Google Scholar

[13] Hollander M., Wolfe D. A., and Chicken E. Nonparametric statistical methods, volume 751. John Wiley & Sons, 2013.Search in Google Scholar

[14] Jin Y., Olhofer M., and Sendhoff B. A framework for evolutionary optimization with approximate fitness functions. IEEE Transactions on Evolutionary Computation, 6:481-494, 2002.Search in Google Scholar

[15] Kanji G. K. 100 statistical tests. Sage, 2006.Search in Google Scholar

[16] Koren Y., Bell R., and Volinsky C. Matrix factorization techniques for recommender systems. Computer, (8):30-37, 2009.Search in Google Scholar

[17] Krawiec K. and Lichocki P. Using co-solvability to model and exploit synergetic effects in evolution. In Schaefer R., Cotta C., Kolodziej J., and Rudolph G., editors, PPSN 2010 11th International Conference on Parallel Problem Solving From Nature, volume 6239 of Lecture Notes in Computer Science, pages 492-501, Krakow, Poland, 11-15 Sept. 2010. Springer.Search in Google Scholar

[18] Krawiec K. and Liskowski P. Automatic derivation of search objectives for testbased genetic programming. In Machado P., Heywood M. I., McDermott J., Castelli M., Garcia-Sanchez P., Burelli P., Risi S., and Sim K., editors, 18th European Conference on Genetic Programming, volume 9025 of LNCS, pages 53-65, Copenhagen, 8-10 Apr. 2015. Springer.Search in Google Scholar

[19] Lee D. D. and Seung H. S. Algorithms for non-negative matrix factorization. In Advances in neural information processing systems, pages 556-562, 2001.Search in Google Scholar

[20] Liskowski P. and Jaskowski W. Accelerating coevolution with adaptive matrix factorization. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’17, pages 457-464, New York, NY, USA, 2017. ACM.Search in Google Scholar

[21] Liskowski P. and Krawiec K. Discovery of implicit objectives by compression of interaction matrix in test-based problems. In Parallel Problem Solving from Nature-PPSN XIII, pages 611-620. Springer, 2014.Search in Google Scholar

[22] Liskowski P. and Krawiec K. Non-negative matrix factorization for unsupervised derivation of search objectives in genetic programming. In Friedrich T., editor, GECCO ’16: Proceedings of the 2016 Annual Conference on Genetic and Evolutionary Computation, pages 749-756, Denver, USA, 20-24 July 2016. ACM.Search in Google Scholar

[23] Liskowski P. and Krawiec K. Surrogate fitness via factorization of interaction matrix. In Heywood M. I., McDermott J., Castelli M., Costa E., and Sim K., editors, EuroGP 2016: Proceedings of the 19th European Conference on Genetic Programming, volume 9594 of LNCS, pages 68-82, Porto, Portugal, 30 Mar.-1 Apr. 2016. Springer Verlag.Search in Google Scholar

[24] Liskowski P. and Krawiec K. Discovery of search objectives in continuous domains. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’17, pages 969-976, New York, NY, USA, 2017. ACM.Search in Google Scholar

[25] Liskowski P. and Krawiec K. Online discovery of search objectives for test-based problems. Evolutionary Computation, 25(3):375-406, 2017.10.1162/evco_a_00179Open DOISearch in Google Scholar

[26] Liskowski P., Krawiec K., Helmuth T., and Spector L. Comparison of semanticaware selection methods in genetic programming. In Johnson C., Krawiec K., Moraglio A., and O’Neill M., editors, GECCO 2015 Semantic Methods in Genetic Programming (SMGP’15) Workshop, pages 1301-1307, Madrid, Spain, 11-15 July 2015. ACM.Search in Google Scholar

[27] McKay R. I. B. Fitness sharing in genetic programming. In Whitley D., Goldberg D., Cantu-Paz E., Spector L., Parmee I., and Beyer H.-G., editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), pages 435-442, Las Vegas, Nevada, USA, 10-12 July 2000. Morgan Kaufmann.Search in Google Scholar

[28] Pagie L. and Hogeweg P. Evolutionary consequences of coevolving targets. Evolutionary Computation, 5(4):401-418, Winter 1997.10.1162/evco.1997.5.4.401Open DOISearch in Google Scholar

[29] Ricci F., Rokach L., and Shapira B. Introduction to recommender systems handbook. Springer, 2011.Search in Google Scholar

[30] Schmidt M. D. and Lipson H. Coevolution of fitness predictors. IEEE Transactions on Evolutionary Computation, 12(6):736-749, Dec. 2008.10.1109/TEVC.2008.919006Open DOISearch in Google Scholar

[31] Smith R. E., Forrest S., and Perelson A. S. Searching for diverse, cooperative populations with genetic algorithms. Evolutionary computation, 1(2):127-149, 1993.Search in Google Scholar

[32] Spector L., Clark D. M., Lindsay I., Barr B., and Klein J. Genetic programming for finite algebras. In Keijzer M., editor, GECCO ’08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 1291-1298, Atlanta, GA, USA, 12-16 July 2008. ACM.Search in Google Scholar

[33] Stanley K. O. and Miikkulainen R. Competitive coevolution through evolutionary complexification. J. Artif. Intell. Res.(JAIR), 21:63-100, 2004.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo