- Set up a random population modelling the problem
- Select two of the fittest specimens to reproduce
- Optionally cross parents to breed offspring
- Mutate parents optionally
- The new population consists of the selected parents and their descendants
As the population is nearing the optimal, it stands to reason that improved, rather than random, mutations and offspring should be promoted. During the next stage in the evolution, though, survival of the fittest should have a similar effect.
The specific problem chosen for illustration is allocating exactly one resource to every task. (This seems to have been proposed in the early 80's while presenting a new type of Neural network.) The goal is to maximise performance, though it could equally well have been the minimisation of a cost function. Here is the performance table:
| Task | 1 | 2 | 3 | 4 | 5 | 6 |
| Resource | ||||||
| 1 | 10 | 5 | 4 | 6 | 5 | 1 |
| 2 | 6 | 4 | 9 | 7 | 3 | 2 |
| 3 | 1 | 8 | 3 | 6 | 4 | 6 |
| 4 | 5 | 3 | 7 | 2 | 1 | 4 |
| 5 | 3 | 2 | 5 | 6 | 8 | 7 |
| 6 | 7 | 6 | 4 | 1 | 3 | 2 |
Within a few generations (for this size of problem), the optimal of 44 is found, given a random initial population of 52. The average population score is about 40 for random offspring and mutations, while it reached a peak of 43.88 for improved descendants and mutations. The few extra lines of code required to promote improved population characteristics are therefore well worthwhile, since it it harder to breed better children near the optimal.
In this context, a mutation involves swapping the resources allocated to two tasks. Breeding also entails swapping, so that the resource takes the place it had in the first parent in the second parent, and vice versa.
The gatask program at another site solves the same problem. If you understand programming, but are not mainly a programmer, though, you may not be very fond of C.- Site map
- 8051 logic analyser
For my own code: Valid XHTML 1.0!