I started to write about the difficulties of creating a system that is ‘evolveable’, or, seen another way, the problem of converting a problem into one in which a solution can be evolved. However, I got slightly sidetracked into discussing the limits of what images can be evolved in my genetic algorithm to evolve and image of Darwin. I’ll continue writing about evolving solutions to a problem in a later post.
It may well be that not all the possible solutions to a problem can be encoded into a particular scheme, though this is not necessarily a problem. In the case of life, there may be many solutions to the problem of self-replication that do not involved proteins. It is also conceivable that there are some groups of proteins that cannot be encoded into DNA (though I’ll have to think further about this to come up with a convincing example – perhaps a restriction enzymes that digests its own gene). In the case of my genetic algorithm to evolve an image of Darwin, I’m is almost certain that it is impossible to evolve a perfect likeness using 384 or fewer circles.
Clearly, if one were to use one circle per pixel (30400 for my image), then a perfect image could be generated. It would be interesting to know (but very difficult to calculate) the smallest number of circles required to generate any image of 30400 pixels. Since there are 256^30400 (2^243200 or ~10^73000, where “^” means “to the power of”) possible 8-bit grayscale image of this size, and there are ~1.3 x 10^11 possible circles in this size and shape of an image (choosing from 152 x-coordinates, 200 y-coordinates, 67 diameters, 256 shades of grey and 256 transparency), then at least 6300 or so circles would be needed. However, of the possible images made of 6300 circles, a huge number would be pure white (if the transparency of each circle was 100% or colour was 100% white, then any combination of sizes and x, y and z coordinates would be white. In addition, if a few large white opaque circles were drawn last, it wouldn’t matter what the first circles were like).
If I wanted, instead of encoding an image as a list of properties of circles, I could have simply encoded it as a list of the colour of every pixel (which is how digital images are normally encoded). It might have been of some interest to evolve an image based on this encoding, pixel-by-pixel, but not much. In this case, the solution to the problem of creating an image of Darwin is obvious – just copy the image you’re aiming at. In contrast, I think it’s far from obvious how to create that same image using overlapping circles. In this case, the limitation of the encoding system is what makes the problem worth evolving.In fact, there may even be a practical application of an image-evolution scheme to compress image data: encoding a 152 x 200 pixel, 8-bit, grayscale image normally requires 30400 x 8 bits, but using 256 circles, it would require about 9200 bits. However, as I showed above, this is likely to be a very lossy compression. However, a similar system has been discussed.