Study of the impact of genotype compression for Genetic programming, an application to data compression.

Student thesis: Doctoral Thesis

Abstract

This dissertation presents two contributions which combine the domains
of data compression and evolutionary search. The first contribution is
the development of a new approach where genetic programming (GP) is used
to improve the compressibility of the data. A genetic programming system
is used to generate a transformation which reduces the entropy of the
data. Applying this transformation to the data, prior to its compression
by a standard compression algorithm, will allow it to be compressed to a
smaller size. The advantage of this approach is that it automates the
process where human design would otherwise be required. This
automatization allows us to generate a transformation for each
individual input file.

A second contribution of this work is a modification to a standard
genetic algorithm (GA) which introduces low level modularization. This
modularization is obtained by using a data compression technique to
shorten the length of the genotype, hence the name compressing GA
(c-GA). By compressing the genotype of the individuals we protect the
genetic material and make the reuse of combinations of features
possible. The validity of our assumptions has been tested with a series
of reference GA and GP problems. Results indicate that genotype
compression is beneficial to the search process and performs best for
problems which feature repetition in the solution representation.
Date of Award24 Nov 2006
Original languageEnglish
SupervisorKris Steenhaut (Promotor) & Ann Nowe (Promotor)

Keywords

  • data compression

Cite this

'