Adaptive test selection for factorization-based surrogate fitness in genetic programming

• Autorzy: Krawiec K. , Liskowski P.

Identyfikatory

DOI

10.1515/fcds-2017-0017

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

genetic programming; matrix factorization; surrogate fitness; test-based problems; recommender systems

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2017
• Tom: Vol. 42, No. 4
• Strony: 339--358
• Opis fizyczny: Bibliogr. 33 poz., fig., tab.

Twórcy

autor

Krawiec K.

• Institute of Computing Science, Poznan University of Technology, Poland

autor

Liskowski P.

• Institute of Computing Science, Poznan University of Technology, Poland

Bibliografia

• [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.
• [2] Bongard J. and Lipson H. Active coevolutionary learning of deterministic finite automata. Journal of Machine Learning Research, 6(Oct):1651-1678, 2005.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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 information retrieval, pages 259-266. ACM, 2003.
• [13] Hollander M., Wolfe D.A., and Chicken E. Nonparametric statistical methods, volume 751. John Wiley & Sons, 2013.
• [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.
• [15] Kanji G.K. 100 statistical tests. Sage, 2006.
• [16] Koren Y., Bell R., and Volinsky C. Matrix factorization techniques for recommender systems. Computer, (8):30-37, 2009.
• [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.
• [18] Krawiec K. and Liskowski P. Automatic derivation of search objectives for test based 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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [25] Liskowski P. and Krawiec K. Online discovery of search objectives for test-based problems. Evolutionary Computation, 25(3):375-406, 2017.
• [26] Liskowski P., Krawiec K., Helmuth T., and Spector L. Comparison of semantic aware 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.
• [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.
• [28] Pagie L. and Hogeweg P. Evolutionary consequences of coevolving targets. Evolutionary Computation, 5(4):401-418, Winter 1997.
• [29] Ricci F., Rokach L., and Shapira B. Introduction to recommender systems handbook. Springer, 2011.
• [30] Schmidt M.D. and Lipson H. Coevolution of fitness predictors. IEEE Transactions on Evolutionary Computation, 12(6):736-749, Dec. 2008.
• [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.
• [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.
• [33] Stanley K.O. and Miikkulainen R. Competitive coevolution through evolutionary complexification. J. Artif. Intell. Res.(JAIR), 21:63-100, 2004.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).