Pattern Evolver

Pattern Evolver is a program I wrote in April, 1997. It is the first genetic algorithm I have ever written and its success in solving the following problem is truly incredible. I wrote Pattern Evolver to help me make smooth gray tile patterns of varying ratios of black to white pixels in a 1-bit deep bitmap. In a pattern of 8 x 8 pixels there are 65 possible "densities" of black pixels, 0 - 64 out of the available 64 pixels in the array. To make a smooth teselating pattern that appears as a neutral gray is only intuitively easy for densities that divide evenly into 64, i.e. 0, 1, 2, 4, 8, 16, 32, and 64. Any other number, 14 for example, is not entirely easy to design. There is no predefined or naturally occurring pattern of pixels that produces a perfectly smooth pattern. To design all the necessary patterns from densities of 0 to 64 took me two days and the results were disappointing.

I wrote Pattern Evolver for the express purpose of evolving smooth gray patterns at any designated density. It works beautifully. It has two methods for solving the problem.

The first method is essentially a version of the famous biomorphs programs originated by Richard Dawkins. The computer generates a family of patterns and you the user pick the pattern you believe is the smoothest gray. That pattern becomes parent to a new family of slightly mutated offspring and you continue the process until you are satified with the results. Similarly you can use this method to evolve any type of pattern you like, lines, circles, whatever you want.

The second method is much more interesting from the computer's point of view. Pattern Evolver analyzes each pattern generated in a family and assigns it a grayness score associated with how smooth the computer thinks the pattern is. The option is then available to the user to let the computer pick the grayest pattern. This works quite well and the time saved is extraordinary.

Below is a lineage of patterns. The upper left pattern was the highest scoring pattern picked from a randomly generated family and the computer chose the best of each family for several generations until the final pattern was settled where the evolution halted due to the pattern's superior fitness. Smoother grays can be obtained for this particular density but the lineage shown below demostrates an adaptive peak from which the evolution of this pattern could not escape. Thus, the final pattern may not be the most fit pattern that could evolve, but within its lineage it could go no further. A different path to the top would have to be found, as it were.

Pattern Evolver is freeware and will run on any Macintosh computer. Extensive documentation is included.

Download Pattern Evolver

Wiley, K. B. 1999. Pattern Evolver, An Evolutionary Algorithm that Solves the Nonintuitive Problem of Black and White Pixel Distribution to Produce Tiled Patterns that Appear Gray. The Handbook of Genetic Algorithms. Chambers, Lance D., editor. CRC Press. 1999.