An Ant Colony to solve a word problem

I have modified my ant colony to solve 4 letter word problems of the type:
Starting with the word "leaf", changing 1 letter per step end with the work "loan" e.g.
leaf -> lean -> loan

I also have versions that solve 5, 6 and 7 letter problems, although for 6 and 7 letter words (and probably 5 too) there are so few connections between words, you might as well brute force your way through it.

The problem with the following characteristics seem ideally suited to an Ant Colonies:

1. definite routes between points
   
2. required to optimise for shortest route
3. large problem area - for small problems, just brute force it.
   

Again, code available on request.

Linux on an OLD laptop

I have just been given a laptop (IBM Thinkpad 240 running windows 2k) and spent a few days trying to load linux on it.

The 240 I was given does not have a floppy, CD-ROM or built in network and it won't boot off the USB, but I managed to install Ubuntu Intrepid Alterrnate install like this:

1. Remove the hard disk, and install it in an old laptop (in my case a 365x) with a CD-ROM and floppy drive, boot off a downwloaded MS-DOS 6.22 floppy, format C: and sys C:
2. Copy loadlin 1.6 and dsl linux to a CD. Copy the CD to the local hard disk
3. Put the hard disk back into the 240, and boot MS-DOS
4. Use loadlin to boot DSL (from /boot/isolinux on the CD): loadlin linux24 initrd=initrd.gz root=/dev/ramdisk
   
5. Use DSL to mount a USB disk containing the linux distro you want to install (Ubuntu Intrepid in my case), and copy it to the hard disk
6. Reboot into MS-DOS
7. Use loadlin to boot Ubuntu - I used the network install as Intrepid detected the PCMCIA card I had: loadlin vmlinuz initrd=initrd.gz root=/dev/linux
8. Once Intrepid was installed, a standard wireless USB worked beautifully!

Note for the 240, DSL needs vga=789 and xmodule=fbdev to start the GUI

I am currently running JWM and XDM on the 240 with the kazehakase browser (firefox is too heavy for a 300Mhz laptop!)

An Ant Colony Optimisation Algorithm

I have been playing with an ant colony algorithm to solve a traveling salesman problem, and have always had inconsistent results (once ants decide on a route the route is strengthened and they are less likely to explore other options - they hit a local minima and reinforce it)

A few weeks back I tried to inject a little entropy back into a colony that was getting lazy, by using a "black sheep" ant that bucks the trend and randomly picks one these algorithms instead:

1. Random - ignores distances between towns, and just randomly chooses a town
   
2. Closest Town - chooses the closest town regardless of the prefered route
   
3. Least Followed - chooses the town that other ants are avoiding

This simple change drastically improved the algorithm to such an extent that I thought it might actually be able to compete with a brute force algorithm.

So, the tests.... I ran 2 of them.

In both cases there was a 10 minute cut off for the colony and 10 colonies were run against each brute force solution. Also, the colony had to get to the optimum solution - not a "close enough" answer.

To provide some degree of confidence that it was working, the best solution was rendered in 3 space by visual python to provide a quick, visual sanity check. (Also, its fun to watch the ants trying different routes)

The first test: 10 towns, 3,628,800 possible routes ,146 different solutions. Brute force was solved in an average of 2 minutes 8 seconds. The colony did it in 13 seconds average, with 81% of tests solved in under a second.

The second test: 11 towns, 39,916,800 possible routes for each solutions, 16 different solutions
Brute force was solved in an average of 23 minutes 55 seconds. The colony did it in 18 seconds average, with 83% of tests solved in under a second.

I tried with 12 towns, but I wasn't patient enough to wait 3 hours for the brute force algorithm to finish.

Anyway, its clear that the ant colony beats the brute force algorithm hands down!

Now what's the problem that this solution solves.....

(Code available on request)