How do Genetic Algorithms Work?
Genetic Algorithms basically imitate evolution. Once a problem is identified, a Genetic Algorithm can be implemented. First, a fitness ranking is created, depending on certain attributes of the "candidates", or the animals that are evolving. Then, a random set of candidates, with various values for their attributes, is created, and called the first generation. Each generation, the Genetic Algorithm has a specific way of mating (combining attributes) and mutating(random changes to attributes), as well as killing off some of the candidates. After many generations, the "fittest" candidates, as well as the population as a whole, will approach a certain, most effective solution to the problem.
To help clarify exactly what this means, an explanation of how our demonstration genetic algorithm works is provided below
Color Reducing Genetic Algorithm
The goal of the demo is to use a genetic algorithm to reduce the number of colors used in an image. The algorithm starts by generating nine random "palettes" of 32 colors each using the HSL color space . This colorspace was chosen because of the "simple" color spaces, it best represents the way humans perceive color. Each palette corresponds to one image in the 3x3 tiled layout.
The program starts by replacing each color in the base image with the closest color from the associated palette. Then the user sorts the resulting images by how "good" each image looks. This not only adds user interaction to the process, but it lets the user make choices based on how the human eye perceives an image. For example, in the "Castle" image, the human eye tends to focus more on the castle than the sky, which can result in a very accurate foreground at the expense of a one or two color sky. In the "Lights" example image, the human eye values high-contrast, vivid distinctions between background and foreground more than the exact tone of each light streak. Although computers do a very admirable job reducing an image to very few colors using dithering and related technologies, it is very hard for computers to accurately discern what's important in a given image.
Next comes the genetic algorithm part. When the user clicks the "Next Generation" button, each palette generates "offspring," each "child" randomly choosing colors from its two parents until it has 32 "genes." The top three images are pre-scripted to reproduce with each other, but much of the reproduction is done randomly, with more "fit" (i.e., higher ranked) images more likely to reproduce. We also introduced a few concepts borrowed from other genetic algorithm demos. To make sure the best image always remained in the gene pool, we introduced the concept of "Elitism." We also mated a "newcomer" with position #1 to constantly add new genes into the gene pool.
The last step in the process was the mutations. We randomly added or subtracted a small amount to the hue, saturation and luminance of each color in the palette to simulate random mutations of genes. The process repeats as many times as the user's patience allows, or until the image gets good enough.About The Authors
The three authors of this website are all sophomores, hailing from both Massachusetts and California.