Opening the Black Box: Alternative Search Drivers for Genetic Programming and Test-based Problems
Abstract
Test-based problems are search and optimization problems in which candidate solutions interact with multiple tests (examples, fitness cases, environments) in order to be evaluated. The approach conventionally adopted in most search and optimization algorithms involves aggregating the interaction outcomes into a scalar objective. However, passing different tests may require unrelated `skills' that candidate solutions may vary on.
Scalar tness is inherently incapable of capturing such di erences and leaves a search algorithm largely uninformed about the diverse qualities of individual candidate solutions. In this paper, we discuss the implications of this fact and present a range of methods that avoid scalarization by turning the outcomes of interactions between programs and tests into 'search drivers' - partial, heuristic, transient pseudo-objectives that form multifaceted characterizations of candidate solutions. We demonstrate the feasibility of this approach by reviewing the experimental evidence from past work, confront it with related research endeavors, and embed it into a broader context of behavioral program synthesis.
References
Bucci, A., Pollack, J.B., de Jong, E.: Automated extraction of problem structure. In: K.D. et al. (ed.) Genetic and Evolutionary Computation – GECCO-2004, Part I, Lecture Notes in Computer Science, vol. 3102, pp. 501–512. Springer-Verlag, Seattle, WA, USA (2004). DOI doi:10.1007/b98643. URL http://link.springer.de/link/service/series/0558/bibs/3102/31020501.htm
Burke, E., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., Woodward, J.R.: A Classification of Hyperheuristic Approaches, chap. Handbook of Meta-Heuristics, pp. 449–468. Kluwer (2010). DOI 10.1007/978-1-4419-1665-5 15. URL http://dx.doi.org/10.1007/978-1-4419-1665-5
de Jong, E.D., Pollack, J.B.: Ideal Evaluation from Coevolution. Evolutionary Computation 12(2), 159–192 (2004)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGAII. Evolutionary Computation, IEEE Transactions on 6(2), 182 –197 (2002). DOI 10.1109/4235.996017
Genesereth, M.R., Love, N., Pell, B.: General game playing: Overview of the AAAI competition. AI Magazine 26(2), 62–72 (2005)
Knowles, J.D., Watson, R.A., Corne, D.: Reducing local optima in single-objective problems by multiobjectivization. In: EMO ’01: Proceedings of the First International Conference on Evolutionary MultiCriterion Optimization, pp. 269–283. Springer-Verlag, London, UK (2001)
Koren, Y., Bell, R., Volinsky, C.: Matrix factorization techniques for recommender systems. Computer (8), 30–37 (2009)
Krawiec, K.: Behavioral Program Synthesis with Genetic Programming, Studies in Computational Intelligence, vol. 618. Springer International Publishing (2015). DOI doi:10.1007/978-3-319-27565-9. URL http://www.cs.put.poznan.pl/kkrawiec/wiki/?n=Site.BPS
Krawiec, K., Liskowski, P.: Automatic derivation of search objectives for test-based genetic programming. In: P. Machado, M.I. Heywood, J. McDermott, M. Castelli, P. Garcia-Sanchez, P. Burelli, S. Risi, K. Sim (eds.) 18th European Conference on Genetic Programming, LNCS, vol. 9025, pp. 53–65. Springer, Copenhagen (2015). DOI doi:10.1007/978-3-319-16501-1 5
Krawiec, K., O’Reilly, U.M.: Behavioral programming: a broader and more detailed take on semantic GP. In: C. Igel, D.V. Arnold, C. Gagne, E. Popovici, A. Auger, J. Bacardit, D. Brockhoff, S. Cagnoni, K. Deb, B. Doerr, J. Foster, T. Glasmachers, E. Hart, M.I. Heywood, H. Iba, C. Jacob, T. Jansen, Y. Jin, M. Kessentini, J.D. Knowles, W.B. Langdon, P. Larranaga, S. Luke, G. Luque, J.A.W. McCall, M.A. Montes de Oca, A. Motsinger-Reif, Y.S. Ong, M. Palmer, K.E. Parsopoulos, G. Raidl, S. Risi, G. Ruhe,
T. Schaul, T. Schmickl, B. Sendhoff, K.O. Stanley, T. Stuetzle, D. Thierens, J. Togelius, C. Witt, C. Zarges (eds.) GECCO ’14: Proceedings of the 2014 conference on Genetic and evolutionary computation, pp. 935– 942. ACM, Vancouver, BC, Canada (2014). DOI doi:10.1145/2576768.2598288. URL http://doi.acm.org/10.1145/2576768.2598288. Best paper
Krawiec, K., Swan, J., O’Reilly, U.M.: Behavioral program synthesis: Insights and prospects. In: R. Riolo, W.P. Worzel, M. Kotanchek, A. Kordon (eds.) Genetic Programming Theory and Practice XIII, Genetic and Evolutionary Computation. Springer, Ann Arbor, USA (2015). URL http://www.cs.put.poznan.pl/kkrawiec/wiki/uploads/Research/2015GPTP.pdf
Liskowski, P., Krawiec, K.: Discovery of implicit objectives by compression of interaction matrix in testbased problems. In: T. Bartz-Beielstein, J. Branke, B. Filipiˇc, J. Smith (eds.) Parallel Problem Solving from Nature – PPSN XIII, Lecture Notes in Computer Science, vol. 8672, pp. 611–620. Springer (2014). DOI 10.1007/978-3-319-10762-2 60
Liskowski, P., Krawiec, K.: Non-negative matrix factorization for unsupervised derivation of search objectives in genetic programming. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO ’16, pp. 749–756. ACM, New York, NY, USA (2016). DOI 10.1145/2908812.2908888. URL http://doi.acm.org/10.1145/2908812.2908888
Liskowski, P., Krawiec, K.: Non-negative matrix factorization for unsupervised derivation of search objectives in genetic programming. In: T. Friedrich (ed.) GECCO ’16: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, pp. 749–756. ACM, Denver, USA (2016). DOI doi:10.1145/2908812.2908888
Liskowski, P., Krawiec, K.: Online discovery of search objectives for test-based problems. Evolutionary Computation pp. 1–32 (2016). DOI 10.1162/EVCO a 00179. URL http://dx.doi.org/10.1162/EVCO_a_00179. PMID: 26953882
Popovici, E., Bucci, A., Wiegand, R.P., de Jong, E.D.: Handbook of Natural Computing, chap. Coevolutionary Principles. Springer-Verlag (2011)
Swan, J., Adriaensen, S., Bishr, M., Burke, E.K., Clark, J.A., Causmaecker, P.D., Durillo, J., Hammond, K., Hart, E., Johnson, C.G., Kocsis, Z.A., Kovitz, B., Krawiec, K., Martin, S., Merelo, J., Minku, L.L., Ozcan, E., Pappa, G.L., Pesch, E., Garcıa-S´anchez, P., Schaerf, A., Sim, K., Smith, J.E., St¨utzle, T., Voß, S., Wagner, S., Yao, X.: A research agenda for metaheuristic standardization. In: MIC 2015: The XI Metaheuristics International Conference (2015)
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.
