I have tinkered with this myself. Have you tried a fitness function that doesn't just compare the source pixels, but also compares the source and approximation

I have tinkered with this myself. Have you tried a fitness function that doesn't just compare the source pixels, but also compares the source and approximation after each has been run through various convolution kernels, and adding the result to the overall score? it takes a little longer but it can let you fine tune things like giving a higher score to images whose edges line up.