Evolutionary Algorithms: An introduction
The big picture
With the term Adaptive Computing a concise description for systems with the ability to adapt themselves to changes requirements by self-modifying their behaviour was coined. This definition just as an introduction. Don’t include it into your encyclopedia. How to come to Evolutionary Algorithms (EA)? EA’s are a subdivision of the so-called Artifical Intelligence (AI). Evolutionary algorithms develop solutions based on a set of available modifiers (instructions), inputs and constraints. They sort of iterate thru an unknown field of potential solutions and find a near-optimal one. Mostly, the solution is suboptimal, but as close to the theoretical optimum so that the developed solution could be accepted and could be used in practice.
Well known is the god-father of genetics, Charles Darwin. Genetic Algorithms, based on Darwinian ideas, Genetic Programming – which is an offspring of Genetic Algorithms and which has been develop by John Koza, and other evolutionary approaches form the subject of Evolutionary Algorithms.
Not to forget Mendel’s laws of inheritance (one could easily intermingle with object-orientation). They allow for the calculation of new generations based on previously developed genes.
When to use the EA approach?
We could easily answer: Whenever it is possible to identify and implement the basic ingredients of an EA. Most important: You need a fitness function. Next, you need a representation for entities embodying possible solutions. If you are able to do so, proceed with EA’s. It is easier to see the applicability of the approach by picking a family member of EA – like Genetic Algorithms – and do an analysis for that. With that, we avoid the problem of working on a very abstract, because meta layer. Future considerations will be necessary beyond this weblog entry.
The Evolutionary Approach
The term EA is describing a concept, something abstract, on which to found a concrete concept. It could be seen as a meta-description of other concepts. It builds the frame for the family members GA, GP and other evolutionary techniques.
The main ideas are:
- Find a solution within a very huge, perhaps nearly infinite search space.
- Begin with a randomly chosen population, each population consisting of independent individuals.
- Each individual needs to be interpreted regarding to its current state (i.e., its current representation).
- The main point with EA’s is to find a fitness function allowing to measure the quality of an individual with respect to solving the given problem.
- Based on the quality of each individual, new populations, consisting of new individuals, can be generated automatically.
- The way new individuals will be generated can be controlled by means of randomly influenced parameters.
- Genetic operations are mainly based on Darwin’s and Mendel’s research.
Executing an Evolutionary Algorithm
It is straightforward implementing an EA. Just perform the following steps in the given order (also see Evolutionary Algorithm Web Service):
- Initialization: Just generate some individuals with random (but at best valid) states
- Evaluation: Use the fitness function to give each individual a rank.
- Selection: Choose your elite and kick the rest from the population.
- Recombination: Add some controlled randomness by applying genetic operators of your choice.
- Do the above until you are satisfied with the currently best solution or until your hard disk crashes…
This post only described EA’s from a top-point view. Further entries will dig into detail with concrete approaches within EA’s. With the stuff to come the broad variety of applicability of EA’s will be shown and proven. From my point of view, EA’s are a clever way of solving several classes of problems without needing to know the gestalt of the solution exactly.