October 14, 2011
Ever since version 0.8.0051 of Grasshopper, there is a second solver available from within Galapagos which implements the Simulated Annealing algorithm. Like the existing Evolutionary solver, Simulated Annealing is also a meta-heuristic technique, but works in a fundamentally different fashion. Having access to both solvers makes it easier to circumvent some of the shortcomings of each. Ironically, Simulated Annealing is a much simpler process than Simulated Evolution but may be harder to understand since the real-world analogy is more abstract and based on a less well known process.
In metallurgy, annealing is the process of controlled heating and cooling of metal to achieve certain material properties. At first, the metal is heated up to melting point so it can be cast or formed. At an atomic level, heat is nothing more than particle velocity. The particles (atoms & molecules alike) in a hot substrate move faster than the same particles in a cold substrate. At some point the velocity of two particles will be so high that they cannot succeed in forming a persistent bond between them. When this happens the substrate loses internal structure and turns liquid.
March 9, 2011
This is the second post on how to define your own Fitness Functions. In the first post we discussed how to combine Fitness variables with different units and ranges. Today we’ll talk about how we can write a Fitness Function that always points the solver in the right direction. I’ll use a simpler example this time, where all the Fitness Variables are of the same type as well as the same range.
March 7, 2011
Often the most difficult thing whilst setting up an Evolutionary Solver run is the definition of the Fitness Function. The sort of problem that is most suited for Evolutionary Solvers typically has a number (sometimes a very large number) of different variables that need to be solved. Sometimes these variables cooperate, in that improving one will also improve the other, sometimes they oppose and sometimes they are completely unconnected.
March 5, 2011
This is the sixth post in a series on Evolutionary Solvers.
All the mechanisms we have discussed so far (Selection, Coupling and Coalescence) are designed to improve the quality of solutions on a generation by generation basis. However all of them have a tendency to reduce the bio-diversity in a population. The only mechanism which can introduce diversity is mutation. Several types of mutation are available in the Galapagos core, though the nature of the implementation in Grasshopper at the moment restricts the possible mutation to only Point mutations.
March 5, 2011
This is the fifth post in a series on Evolutionary Solvers.
Once a mate has been selected from a population, offspring needs to be generated. On the genetic level this is anything but fun and games. The biological process of gene recombination is horrendously complicated and itself subject to evolution (meiotic drive for example, where genes evolve to affect the random process of meiosis and thus improve their chances of ending up in offspring). The digital variant is much simpler. This is partially because genes in evolutionary algorithms are not very similar to biological genes. Ironically, biological genes are far more digital than programmatic genes. As Mendel discovered in the 1860′s, genes are not continuously variable qualities. Instead they behave like on-off switches. Genes in evolutionary solvers like Galapagos behave like floating point numbers, that can assume all the values between two numerical extremes. When Mendel crossed wrinkly and smooth peas, he ended up with specific frequencies of each in the subsequent generations, but never with a pea that was somewhat wrinkly and somewhat smooth. With Evolutionary Algorithms there’s no reason why we couldn’t interpolate genes this way.
March 4, 2011
This is the fourth post in a series on Evolutionary Solvers.
Coupling is the process of finding mates. Once a genome has been elected to mate by the active Selection Algorithm, it has to pick a mate from the population to complete the act. There are of course many ways in which mate selection could occur, but Galapagos at the moment only allows one; selection by genomic distance. In order to explain this in detail, I should first tell you how a Genome Map works. This
is a Genome Map. It displays all the genomes (individuals) in a certain population as dots on a grid. The distance between two genomes on the grid is roughly analogous with the distance between the genomes in gene-space. I say roughly because it is in fact impossible to draw a map with exact distances. A single genome is defined by a number of genes. We assume that all the genomes in a species have the same number of genes (this is not technically a limitation of Evolutionary Algorithms, even though it is currently a limitation of Galapagos). Therefore the distance between two genomes is an N-Dimensional value, where N equals the number of genes. It is not possible to accurately display an N-Dimensional point cloud on a 2-Dimensional screen so the Genome Map is only a coarse approximation. It also follows that the axes of this graph have no meaning whatsoever, the only information a Genome Map conveys is which genomes are more or less similar (close together) and which genomes are more or less different (far apart).
March 4, 2011
This is the third post in a series on Evolutionary Solvers.
Biological Evolution proceeds by Natural Selection. The ruthless force identified by Darwin as the arbiter of progress. Put simply, Natural Selection affects the direction of the gene-pool over time by regulating who gets to mate. In extreme cases mating is prevented because a specific genome is so unfit that the bearer cannot survive until reproductive age. Another rather extreme case would be sterility. However, there’s a myriad ways in which Natural Selection can make it difficult or impossible for certain individuals to pass on their genetic footprint.
March 4, 2011
This is the second post in a series on Evolutionary Solvers.
In biological evolution, the quality known as “Fitness” is actually something of a stumbling block. Usually it is very difficult to say exactly what it means to be fit. It certainly has little or nothing to do with being the strongest, or the fastest, or the most vicious. The reason there are no flying dogs isn’t that evolution hasn’t gotten around to making any yet, it is that the dog lifestyle is supremely incompatible with flying and the sacrifices required to equip a dog with flight would certainly detract more from the overall fitness than flight would add to it. Fitness is the result of a million conflicting forces. Evolutionary Fitness is the ultimate compromise.
March 4, 2011
This series of blog posts is a rough approximation of the lecture I gave at the AAG10 conference in Vienna on September 21st 2010. Naturally it will be a rather different experience as the medium is different, but it my hope the basic premise of the lecture remains intact. These posts deals with Evolutionary Solvers in general, but I use Rhino, Grasshopper and Galapagos to demonstrate the topics.