Overview
Genetic Algorithms are one paradigma dedicated to the field of Evolutionary Algorithms (EA). In a previous blog post, I described EA's in general. Now I want to get more concrete and give the thing a name. As the reactions to the previous weblog entry showed me EA's are not seen as a cure for anyone's problems, fortunately. If this were the case we would live in a quite naive world.
Also see my article in Javamagazin 08/2004 (only in German) for further information on the subject of GA's.
Building Blocks
As a GA is a subclass of an EA, the main idea is the same. What distinguishes a GA from other subclasses of EA's is the representation choosen for the individuals. As with biology, an individual following Darwin's idea is a chromosome. Chromosomes are carrying the genetic material on the desoxyribonucleic acid (DNA). A gene is carrying the information of a certain attribute. The specific characteristic of a gene is called an allel.
Now what we need to do is encode each individual within a technical entity capable of representing an allel. Easiest, we could use a simple string, one for each individual. A string is best because of its genericity. For problems related to numbers you would perhaps use an integer or a double. Then collect all your individuals and put them into a data container, i.e. a collection.
Getting Darwinian
Important elements of a GA are the genetic operations applied to individuals of the current population. As we know from school, these are crossing over, mutation and replication. There are different terms for replication, we mean copying an individual to the next generation without changing its internal state (genotype). All three operations could be outlined by the term reproduction.
Applicability of Genetic Algorithms
Not every problem can be solved with help of a GA, that would be too easy and if this were the case - believe me - I would not type in this text with my own hands (reminds me sort of the movie "Secretary", but that's another issue...).
It is essential with a GA to be able to define a fitness function. A fitness function is one of the fundamental principles within the concept of EA's. It's a measure of how good a current individual is representing a solution to the given problem.
That means: If you cannot provide a fitness function, you cannot use a GA to help solve your problem. Period. In this case, use another algorithm, but not a GA or related stuff.
So, best is to have a simulator which can be fed and evaluated. This, then, could be your out-of-the-box fitness function. Ready you go. Most popular example I know is electrical engineering with P-SPICE. P-SPICE is a very powerful tool able to simulate electrical circuitry.
Other applications include problems where you know a formula or a axiomatic system allowing to evaluating the deviation of an optimal solution. If, for example, you have 16 meters of fence, you know by taking the square root that the maximum area to fence is 4 square meters. Then, for a problem that forces you to have an arbitrary shaped fence, your fitness function would be quite easiy. Could you tell me what the idea shape of a pentagon shaped fence with length of 16 meters is to cover the maximum area? Well, this should not too difficult, although there could be some constraints, like the prohibition to have a symmetry within the shape...
Conclusion
In the next weblog entry, we will introduce the GA framework JGAP which helps in concretely implementing a GA for a given problem. With JGAP (and other frameworks as well, like ECJ), one will be able to easily set up the code for a GA and let the system run until it finds a proper solution to a given problem.
