This is an example from my generative design class of the digi-pro project.
Note: these processing sketches are based on java, the execution in your browser may be restricted or even blocked completely. Please review the security settings of your browser and your java installation if you don’t see the sketches. You need to include “http://download.j-raedler.de/” in the exception site list.
Genetic or evolutionary approaches are used to solve a wide range of problems with the computer. Many algorithms try to reproduce the mechanism of natural evolution as close as possible. They produce generations of slightly mutated information (DNA), combine the attributes of individuals, select the fittest and produce new generations.
This approach may solve many complex problems. But to get it working you have to do some serious programming and to tune a lot of parameters. In many cases a much simpler approach may be sufficient.
The next examples show a “poor man’s evolution” to optimize a configuration. It just starts with a random configuration. One small change is made (random). If the result is better than before, the new configuration is used. If not, the change will be revoked. This process will continue in a loop. Thats all!
In the following example we want to place some elements on a plane. The only condition is that no overlapping happens and an additional distance between the element borders will be maintained. It starts with a random configuration (with overlapping). In every step one (randomly chosen) element is moved to a new random position. If the overall sum of overlapping is smaller than before, the new configuration is used. When a configuration is found that satisfies the condition, the background turns from blue to green and the search is turned off. Press “ALT-H” to toggle the visbility of the controls. By using the controls yout may start again and/or change the parameters.
[iframe http://download.j-raedler.de/Processing/EvoCircle/applet/index.html 100% 580px]
You will see that the algorithm finds a solution with the default parameters within some seconds. But the result doesn’t look nice in all cases. In a next step we will modify the criterion for the selection. Instead of summing up all overlappings we look at the minimum distance between two element borders. A new configuration is used only if this value is larger or equal to the old value. The decision to prefer the “‘mutated” configuration even if its “fitness value” is the same brings some more noise to the process. This may help to find a better solution (recover from local optimums). The elements in this example will not move more than an allowed value. Use “ALT-H” again to toggle the controls.
[iframe http://download.j-raedler.de/Processing/EvoCircle3/applet/index.html 100% 580px]
You will see that after some time a configuration with a very constant distribution of the elements will be found. If may not be the optimal distribution but a good one.
For special cases like 12 elements of the same size it will very often find the well-known analytical solution:
This “poor man’s evolution” is very easy to implement and may lead to good results in many cases. When you have an optimization problem you should consider using this super-simple approach first. If the results are not good enough you may switch to a full-fledged genetic algorithm.