Unsupervised Problem Decomposition Using Genetic Programming

Kattan A., Agapitos A., Poli R.

13th European Conference on Genetic Programming, İstanbul, Turkey, 7 - 09 April 2010, vol.6021, pp.122-133 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 6021
  • City: İstanbul
  • Country: Turkey
  • Page Numbers: pp.122-133
  • Istanbul Technical University Affiliated: No


We propose a new framework based on Genetic Programming (GP) to automatically decompose problems into smaller and simpler tasks. The framework uses GP at two levels. At the top level GP evolves ways of splitting the fitness cases into subsets. At the lower level GP evolves programs that solve the fitness cases in each subset. The top level GP programs include two components. Each component receives a training case as the input. The components' outputs act as coordinates to project training examples onto a 2-D Euclidean space. When an individual is evaluated, K-means clustering is applied to group the fitness cases of the problem. The number of clusters is decided based on the density of the projected samples. Each cluster then invokes an independent GP run to solve its member fitness cases. The fitness of the lower level GP individuals is evaluated as usual. The fitness of the high-level GP individuals is a combination of the fitness of the best evolved programs in each of the lower level GP runs. The proposed framework has been tested on several symbolic regression problems and has been seen to significantly outperforming standard GP systems.