Acceleration of Evolutionary Image Filter Design Using Coevolution in Cartesian GP

Cartesian genetic programming, coevolution, fitness modeling, image filter design.

This contribution is based on the paper Acceleration of Evolutionary Image Filter Design Using Coevolution in Cartesian GP, that has been pubished in  The 12th International Conference on Parallel Problem Solving from Nature,  LNCS 7491, Berlin, DE, Springer, 2012, p. 163-172, ISBN 978-3-642-32936-4.

Evolutionary design based on genetic programming is a very computationally intensive design method. It also holds for the evolutionary design of image filters which has been performed by Cartesian Genetic Programming (CGP). The most time consuming procedure is the fitness calculation where tens of thousands of pixels in training set (the so-called set of target objective vectors, TOVs) have to be evaluated in order to obtain a single fitness value. A single run is typically finished after 200 thousands candidate filter evaluations.

In this work, we propose to employ a coevolutionary algorithm based on coevolution of candidate filters and TOVs subsets running on  an ordinary processor to accelerate the image filter evolution. We use two populations: (1) population of candidate filters evolved on principles of CGP and (2) population of TOVs subsets evolved using a simple genetic algorithm (GA); each population is running in one thread (i.e. we use a two-thread model). The aim of this type of coevolution is to allow both candidate programs and TOVs subsets to improve each other automatically until a satisfactory problem solution is found. We compared two approaches to fitness calculation of TOVs subset - the first one is based on the fitness predictor concept (CFP) and the second approach exploits the competitive coevolution scheme (CC). The salt-and-pepper noise filters are designed using standard CGP and coevoltuionary CGP.

Experimental results show that only 15-20% of original training vectors are needed to find an image filter which provides the same quality of filtering as the best filter evolved using the standard CGP which utilizes the whole training set. Moreover, the median time of evolution was reduced 2.99 times (the execution time is the sum for both threads) in comparison to the standard CGP running in one thread.