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

Krawiec, Krzysztof; Liskowski, Paweł

doi:10.1515/fcds-2017-0017

Abstract

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.

References

[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.10.1145/1281192.1281206
Search in Google Scholar Back to article
[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 Back to article
[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 Back to article
[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.942536
Open DOI Search in Google Scholar Back to article
[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.2051673
Open DOI Search in Google Scholar Back to article
[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 Back to article
[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.996017
Open DOI Search in Google Scholar Back to article
[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.10.1007/3-540-44811-X_34
Search in Google Scholar Back to article
[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 Back to article
[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.10.1007/978-3-642-29139-5_19
Search in Google Scholar Back to article
[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.10.1109/TEVC.2014.2362729
Search in Google Scholar Back to article
[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.10.1145/860435.860483
Search in Google Scholar Back to article
[13] Hollander M., Wolfe D. A., and Chicken E. Nonparametric statistical methods, volume 751. John Wiley & Sons, 2013.
Search in Google Scholar Back to article
[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.10.1109/TEVC.2002.800884
Search in Google Scholar Back to article
[15] Kanji G. K. 100 statistical tests. Sage, 2006.10.4135/9781849208499
Search in Google Scholar Back to article
[16] Koren Y., Bell R., and Volinsky C. Matrix factorization techniques for recommender systems. Computer, (8):30-37, 2009.10.1109/MC.2009.263
Search in Google Scholar Back to article
[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.10.1007/978-3-642-15871-1_50
Search in Google Scholar Back to article
[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.10.1007/978-3-319-16501-1_5
Search in Google Scholar Back to article
[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 Back to article
[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.10.1145/3071178.3071320
Search in Google Scholar Back to article
[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.10.1007/978-3-319-10762-2_60
Search in Google Scholar Back to article
[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.10.1145/2908812.2908888
Search in Google Scholar Back to article
[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.10.1007/978-3-319-30668-1_5
Search in Google Scholar Back to article
[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.10.1145/3071178.3071344
Search in Google Scholar Back to article
[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_00179
Open DOI Search in Google Scholar Back to article
[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.10.1145/2739482.2768505
Search in Google Scholar Back to article
[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 Back to article
[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.40110021765
Open DOI Search in Google Scholar Back to article
[29] Ricci F., Rokach L., and Shapira B. Introduction to recommender systems handbook. Springer, 2011.10.1007/978-0-387-85820-3
Search in Google Scholar Back to article
[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.919006
Open DOI Search in Google Scholar Back to article
[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.10.1162/evco.1993.1.2.127
Search in Google Scholar Back to article
[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.10.1145/1389095.1389343
Search in Google Scholar Back to article
[33] Stanley K. O. and Miikkulainen R. Competitive coevolution through evolutionary complexification. J. Artif. Intell. Res.(JAIR), 21:63-100, 2004.10.1613/jair.1338
Search in Google Scholar Back to article

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

Abstract

Paradigm

My account