Non-negative Matrix Factorization for Unsupervised Derivation of Search Objectives in Genetic Programming
Paweł Liskowski, Krzysztof Krawiec · 2016
In genetic programming (GP), the outcomes of the evaluation phase in an evolutionary loop can be represented as an interaction matrix, with rows corresponding to programs in a population, columns corresponding to tests that define a program synthesis task, and ones and zeroes signaling respectively passing a test and failing to do so. The conventional fitness, equivalent to a row sum in that matrix, only crudely reflects program's compliance with desired output, and recent contributions in semantic and behavioral GP point to alternative, multifaceted characterizations that facilitate navigation in the search space. In this paper, we propose DOF, a method that uses the popular machine learning technique of non-negative matrix factorization to heuristically derive a low number of underlying objectives from an interaction matrix. The resulting objectives redefine the original single-objective synthesis problem as a multiobjective optimization problem, and we posit that such characterization fosters diversification of search directions while maintaining useful search gradient. The comparative experiment conducted on 15 problems from discrete domains confirms this claim: DOF outperforms the conventional GP and GP equipped with an alternative method of derivation of search objectives on success rate and convergence speed.