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)

uinput jni interface

I needed to build a Java interface to the uinput kernel device, and as this was my first non-trivial jni code, I'll document it here. (This ties in with the wiigee library)

Note this requires the uipnut kernel mode to be loaded, and the running user to have write access to the uinput device.

First, write the Java code containing the native library references:

public class X11Input {
//Singleton
private static X11Input u;
public static X11Input getInstance() {
if(u == null) {
u = new X11Input();
}
return u;
}

//native methods
//private - called to destroy, and init native interface
private native void destroy();
private native void init();
//public functions
public native void mouseMove(int x, int y);
public native void keyPress(int key);
public native void keyRelease(int key);

//Load native library
static {
System.loadLibrary("X11Input");
}

//We add the Shutdown hook, and init the uinput interface in the contructor
public X11Input() {
init();
Runtime.getRuntime().addShutdownHook(new Thread() {
public void run() {
X11Input.getInstance().destroy();
System.out.println("Destroying the X11Input singleton jni");
}
});
}
}
Note the use of the addShutdownHook to ensure* the uinput device is correctly closed.

Next, using the compiled class and javah, generate a c header file:
javah -jni org.wiiboard.x11.X11Input

This is executed at the root of the bin directory, and will generate the file:
org_wiiboard_x11_X11Input.h

Next, write the c code that adds the workings behind the the functions:
#include
#include
#include
#include
#include
#include
#include
#include
#include

#include
#include
#include "UinputTest.h"

/* Globals */
static int uinp_fd = -1;
struct uinput_user_dev uinp; // uInput device structure
struct input_event event; // Input device structure
/* Setup the uinput device */
int setup_uinput_device()
{
// Temporary variable
int i=0;
// Open the input device
uinp_fd = open("/dev/input/uinput", O_WRONLY | O_NDELAY);
if (uinp_fd == 0)
{
printf("Unable to open /dev/input/uinput\n");
return -1;
}
memset(&uinp,0,sizeof(uinp)); // Intialize the uInput device to NULL
strncpy(uinp.name, "PolyVision Touch Screen", UINPUT_MAX_NAME_SIZE);
uinp.id.version = 4;
uinp.id.bustype = BUS_USB;
// Setup the uinput device
ioctl(uinp_fd, UI_SET_EVBIT, EV_KEY);
ioctl(uinp_fd, UI_SET_EVBIT, EV_REP);
ioctl(uinp_fd, UI_SET_EVBIT, EV_REL);
ioctl(uinp_fd, UI_SET_RELBIT, REL_X);
ioctl(uinp_fd, UI_SET_RELBIT, REL_Y);
for (i=0; i <> 0 && ( x != 0 || y != 0 )) {

if(x != 0) {
memset(&event, 0, sizeof(event));
gettimeofday(&event.time, NULL);
event.type = EV_REL;
event.code = REL_X;
event.value = x;
write(uinp_fd, &event, sizeof(event));
}
if(y!=0) {
memset(&event, 0, sizeof(event));
gettimeofday(&event.time, NULL);
event.type = EV_REL;
event.code = REL_Y;
event.value = y;
write(uinp_fd, &event, sizeof(event));
}

memset(&event, 0, sizeof(event));
gettimeofday(&event.time, NULL);
event.type = EV_SYN;
event.code = SYN_REPORT;
event.value = 0;
write(uinp_fd, &event, sizeof(event));
}
}

JNIEXPORT void JNICALL
Java_org_wiiboard_x11_X11Input_keyPress(JNIEnv *env, jobject obj, jint key)
{
memset(&event, 0, sizeof(event));
gettimeofday(&event.time, NULL);
event.type = EV_KEY;
event.code = key;
event.value = 1;
write(uinp_fd, &event, sizeof(event));

memset(&event, 0, sizeof(event));
gettimeofday(&event.time, NULL);
event.type = EV_SYN;
event.code = SYN_REPORT;
event.value = 0;
write(uinp_fd, &event, sizeof(event));
}

JNIEXPORT void JNICALL
Java_org_wiiboard_x11_X11Input_keyRelease(JNIEnv *env, jobject obj, jint key)
{
memset(&event, 0, sizeof(event));
gettimeofday(&event.time, NULL);
event.type = EV_KEY;
event.code = key;
event.value = 0;
write(uinp_fd, &event, sizeof(event));

memset(&event, 0, sizeof(event));
gettimeofday(&event.time, NULL);
event.type = EV_SYN;
event.code = SYN_REPORT;
event.value = 0;
write(uinp_fd, &event, sizeof(event));
}

JNIEXPORT void JNICALL
Java_org_wiiboard_x11_X11Input_init(JNIEnv *env, jobject obj)
{
setup_uinput_device();
}

JNIEXPORT void JNICALL
Java_org_wiiboard_x11_X11Input_destroy(JNIEnv *env, jobject obj)
{
destroy_uinput_device();
}
Now compile:
gcc --share -o libX11Input.so -I/include/ -I/include/linux org_wiiboard_x11_X11Input.c /jre/lib/i386/server/libjvm.so

That will generate the libX11Input.so library.

Now you can run the java code with the java.lirary.path pointing to your new .so file's directory:
java -Djava.library.path=. X11InputTest

Wiigee on linux

Wiigee is a wiimote library written in Java that can learn and identify gestures. A demo application is available for download, and source is included in the jar file.

I have used wiigee under linux (ubuntu i386 and Kubuntu x64), and this is what I had to do to get it running.

First, to get it running, download the the bluecove libraries (I used version 2.1.0), and maven2.
Make sure libbluetooth and libbluetooth-dev are installed (and libstdc++.so.6 is linked too libstdc++.so on Kubuntu)

The bluecove MicroeditionConnector.java needs to have the L2CAP validation removed (apparently the wii mote uses non-standard ports)

export the JAVA_HOME variable (if its not alerady set), and execute:
mvn -Dmaven.test.skip=true -e
That will generate all the bluetooth libraries

Make the bluecove, and bluecove-gpl jars, and the libbluecove native binary lib avaiable to the wiigee library, and you're set.

Useful Commands

For network troubles getting files:
wget -c -t 0 -T 1
-> continue download with infinite re-tries and a 1 second timeout.

To allow ssh users to launch apps into the logged in users X sessoion:
netcat -l -s 127.0.0.1 -p 2020
-> start net cat in listen mode on the lo interface on port 2020
Ensure this is called in the gdm PreSession config script

Putty authorized keys

1. Install Putty
2. Generate the key
3. Enter a pass phrase
4. Select the generated public key and copy to the clipboard
5. Save the private and public keys somehwere sensible
   
6. ssh into the server that will hold the public key
7. Make a .ssh directory in ~: mkdir .ssh
   
8. Set access to .ssh : chmod 700 .ssh
9. Enter the command: cat > .ssh/authorized_keys
10. Paste the test from the clipboard
11. Hit CTRL-D to exit
12. Set the access on the authorized_keys file: chmod 644 .ssh/authorized_keys
13. Start Pagent and add the new private key (passphrase entered above will be required)
    

Check that it worked by using putty to ssh in to the server.