Adaptive Test Selection for Factorization-based Surrogate Fitness in Genetic Programming
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 o...
Main Authors: | , |
---|---|
Format: | Article |
Language: | English |
Published: |
Sciendo
2017-12-01
|
Series: | Foundations of Computing and Decision Sciences |
Subjects: | |
Online Access: | https://doi.org/10.1515/fcds-2017-0017 |
_version_ | 1811321210492944384 |
---|---|
author | Krawiec Krzysztof Liskowski Paweł |
author_facet | Krawiec Krzysztof Liskowski Paweł |
author_sort | Krawiec Krzysztof |
collection | DOAJ |
description | 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. |
first_indexed | 2024-04-13T13:12:49Z |
format | Article |
id | doaj.art-638e03619636485082d59c69127c34dc |
institution | Directory Open Access Journal |
issn | 2300-3405 |
language | English |
last_indexed | 2024-04-13T13:12:49Z |
publishDate | 2017-12-01 |
publisher | Sciendo |
record_format | Article |
series | Foundations of Computing and Decision Sciences |
spelling | doaj.art-638e03619636485082d59c69127c34dc2022-12-22T02:45:33ZengSciendoFoundations of Computing and Decision Sciences2300-34052017-12-0142433935810.1515/fcds-2017-0017fcds-2017-0017Adaptive Test Selection for Factorization-based Surrogate Fitness in Genetic ProgrammingKrawiec Krzysztof0Liskowski Paweł1Institute of Computing Science, Poznan University of Technology, PolandInstitute of Computing Science, Poznan University of Technology, PolandGenetic 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.https://doi.org/10.1515/fcds-2017-0017genetic programmingmatrix factorizationsurrogate fitnesstestbased problemsrecommender systems |
spellingShingle | Krawiec Krzysztof Liskowski Paweł Adaptive Test Selection for Factorization-based Surrogate Fitness in Genetic Programming Foundations of Computing and Decision Sciences genetic programming matrix factorization surrogate fitness testbased problems recommender systems |
title | Adaptive Test Selection for Factorization-based Surrogate Fitness in Genetic Programming |
title_full | Adaptive Test Selection for Factorization-based Surrogate Fitness in Genetic Programming |
title_fullStr | Adaptive Test Selection for Factorization-based Surrogate Fitness in Genetic Programming |
title_full_unstemmed | Adaptive Test Selection for Factorization-based Surrogate Fitness in Genetic Programming |
title_short | Adaptive Test Selection for Factorization-based Surrogate Fitness in Genetic Programming |
title_sort | adaptive test selection for factorization based surrogate fitness in genetic programming |
topic | genetic programming matrix factorization surrogate fitness testbased problems recommender systems |
url | https://doi.org/10.1515/fcds-2017-0017 |
work_keys_str_mv | AT krawieckrzysztof adaptivetestselectionforfactorizationbasedsurrogatefitnessingeneticprogramming AT liskowskipaweł adaptivetestselectionforfactorizationbasedsurrogatefitnessingeneticprogramming |