This section is a checklist which you can follow to solve a different problem using the component framework described in this article. In short this checklist reads:
You may also want to create new functionality for the TKiller and/or TParentSelector components to kill and select individuals based on other criteria.
The first task is to get a clear understanding of the problem at hand and to devise a representation of its solution. Evolutionary Algorithms have been applied to a huge number of problems using many different representation techniques. Here are a pair of examples...
Genetic Programming uses evolutionary techniques to manipulate statements in interpreted language. Selection and iteration constructs (if statements and for/while loops) are literally written, edited and moved around by mutations and crossover to give functionality.
Genetic Algorithms, the first form of evolutionary computation to be developed, uses a strict encoding technique in which solutions are translated to binary strings, to which genetic operations are applied. These genetic operations are the closest to those found in nature - we can apply them on the lowest possible level. Individual bits can be swapped, toggled and deleted and strings of bits can be moved around, reversed or otherwise manipulated.
In practice though, to get the best results from evolutionary computation, we generally find ourselves adapting the algorithms to fit the problem. If we go back to our timetabling example, we might choose to represent the timetable as a series of lesson names, room numbers and times...
maths, 12.1, Mon 09:00 english, 01.6, Wed 10:00 ...
Developing the representation is probably the hardest task we must complete before we use EAs. Practically speaking, what we must do is create a descendant of the TIndividual class which implements the representation we decide upon.
The second task is to create a descendant of the TExaminer class which will give us a measure of the fitness of an individual.
For the timetabling example this might mean calculating a weighted sum of the number of students and staff who have clashing lessons and the number of double bookings for rooms. The lower the number the fitter the individual, so the EA will seek to minimise clashes and double bookings.
Next we must implement the natural selection process which will allow individuals to breed and be mutated. This is done by creating a descendant of the TParentSelector, TBreeder and TExaminer components.
The parent selector is, by far, the easiest to implement as we can more or less copy the tournament selection process we used for the TSP. Other selection methods do exist though and you may find that these give you better results.
The breeder is a little more difficult - it is the job of the breeder to create a new individual based on some of the features of the individuals which exist in the population. We use the parent selector to ensure that the parent individuals we use are fit, then we use some form of crossover to copy features of each parent to the offspring. We do this by copying subsets of the parents to the offspring at random. It might be worth noting that we are not limited to two parents, we could have any number (including 1). For the timetabling example we might implement crossover by taking the time and location of lessons from each parent in turn, swapping the donor parent at random.
The mutator must alter the structure of the individual using the genetic operations we discussed in section 2. The most important thing to remember is that we must ensure that the mutations do not cause the individual to become invalid - as single point mutation would in the travelling salesman problem. We might implement a mutation for the timetable problem by swapping the times of two lessons, for example.
The last step is to link the components together and write a nice user interface to allow you to control the EA. Just as we did for the TSP.
| Back |
|
|
| Contents | ||
| Next | ||