Unsupervised Problem Decomposition using GP

This paper proposes a new framework based on the Genetic Programming (GP) to automatically decompose problems into smaller and simpler tasks. GP evolves programs with two components. Each component receive a training case as an input and return a single number as output. The two components act as a coordinate to project training examples onto a two-dimensional Euclidean space. K-means clustering is applied to group similar instances. The number of clusters is decided based on the density of the projected samples. Each cluster is then invokes an independent GP run to solve the cases for its members. Once a program that finds good decomposition for the training examples is evolved, it can be used on unseen data without requiring any further evolution. During normal operation of the system the data are again projected onto a two-dimensional Euclidean space. Finally, unseen testing cases are solved using the solver of the closest cluster’s centeriod. The proposed framework has been tested with several symbolic regression problems. Experimentation reveals that performance of systems employing this framework is significantly outperforming standard GP.



Here you can download the Target functions that have been testing the performance of system and compare them with other methods.

· Target functions

· Experiments results



Unsupervised Problem Decomposition using Genetic Programming


Computing and Electronic Engineering

Ahmed Kattan