Another page has already discussed
Genetic Algorithms, which mutate and combine a large number of strings a large number of times, mostly keeping the fittest instances, to obtain a near optimal solution to some task. If, additionally, the strings are of
variable length, you are into
Genetic Programming. Thus, Genetic Programming needs to select some point into the string to insert, remove or modify a substring and, if not removing, decide what the new substring will be.
Some healthy scepticism can be expected when the results need a cluster of 1,000 computers to verify. Only a 1.8 GHz processor is at my disposal, and I use it for other work, too (so do you probably), so I will not be presenting anything spectacular. However, only 1 second will be needed to run the program at level 6. At level 7 (which uses a file rather than a memory array for the benefit of old compilers), you will still probably get a result within half a minute, well within the realms of modern personal computers. Obviously, higher levels will take longer.
A
sorting network was thought important enough to be subject to a patent application in the sixties. It will sort a fixed number of items by
comparison swaps, that is, by exchanging two items if the item of lower index is smaller.
This is easier than general genetic programming, since only mutations will be considered- crossing is unlikely to be helpful in this particular problem. There is also only
one candidate function to consider for every stage: The conditional swap, though the arguments will be different. However, the problem is tougher than those suitable for genetic algorithms: The number of stages needed is not known in advance. Indeed, several numbers are possible if suboptimal solutions are considered, too.
If you have not read about Genetic Programming before, finding any solution at all will seem impressive enough. However, the
program (
second version and
x86 binary) has been primed to reduce the number of conditional swaps required, and obtain optimised solutions: There is more to it, strictly speaking, since comparison swaps of different arguments can be performed in
parallel. This page, though, is more about Genetic Programming than sorting networks, and will not go that far.
1-3 2-4 1-2 3-4 2-3
3-5 1-2 3-4 1-3 3-4 2-5 2-3 3-4 4-5
1-6 2-3 3-6 1-2 4-5 3-5 1-4 5-6 2-4 3-4 2-3 4-5
3-6 2-7 1-2 2-4 6-7 2-5 2-6 3-4 1-3 3-5 5-7 3-6 1-2 5-6 4-6 2-3 6-7 4-5
| Items | Tries | C. swaps | Optimal |
|---|
| 4 | 34 | 5 | 5 |
| 5 | 42 | 9 | 9 |
| 6 | 149 | 12 | 12 |
| 7 | 327 | 18 | 16 |
A totally random process is guided by rewards and penalties to a near optimal solution.
Of course, you should complain, this is an easy problem, as mutations not improving on the score can be discarded immediately: More sophisticated problems will likely be different- a temporary loss must be allowed to increase long term benefits. However, the program mutates a single string only. If the software has to deal with a harder task, it may well mutate 1,000 initially different strings.
Sometimes the solution may contain redundancies; postprocessing can remove them, or the human user if the answer is not too complicated.
Perhaps, it is disappointing, if expected, that a computer needs a lot of tries to find a solution which is obvious to anyone who knows about
Shellsort, for example. Optimisation in other fields, such as
Automatic Control may not be equally obvious, though, and even minor improvements in a plant controller can save a lot of money. The more sophisticated problems can be handled by more powerful computers- which are becoming increasingly inexpensive.
There are now at least
21 results of Genetic Programming which duplicate the functionality of patented material listed at a mainstream GP site. One result of GP in automatic control is said to be subject to a patent application. This field has been probed by experts intensively for more than 50 years.
The
improved version should provide a level 8 result within 25 seconds.
Present random quote:
| A poison is too much of anything. |
For my own code up to this point:
Valid XHTML 1.0!