Opening the Black Box: Alternative Search Drivers for Genetic Programming and Test-based Problems

  • Krzysztof Krawiec
Keywords: Evolutionary computation, test-based problems, genetic programming, search drivers, coevolutionary algorithms, surrogate fitness

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)

Published
2017-06-01
How to Cite
[1]
Krawiec, K. 2017. Opening the Black Box: Alternative Search Drivers for Genetic Programming and Test-based Problems. MENDEL. 23, 1 (Jun. 2017), 1-6. DOI:https://doi.org/10.13164/mendel.2017.1.001.
Section
Research articles