I've been working on a linear genetic programming system that evolves bytecode for a simple register machine. I've been having trouble getting the solutions to converge if the target output is anything other than the same character output multiple times, and I think the fitness functions I've been trying are the main problem.
The register machine is almost Turing complete except for being bound to a maximum number of operations. Its input and output functions input or output one character at a time. The selection algorithm I'm using can handle multiple fitness functions so that each exerts the same selection pressure without any need for fine-tuning the balance. All the fitness functions return integers, with lower numbers being better.
I'm using these two fitness functions at the moment:
The first one compares the output and the target bit by bit from the beginning and stops when it reaches a bit that isn't the same, then returns the number of bits remaining on whichever is longer.
The second one also compares bit by bit, and returns the total number of bits that are different.
--edit
After trying a few things, I've found out what was preventing it from converging: as well as the two fitness functions I'm also been using program length and execution time as fitness functions. The selection algorithm I'm using gives them all the same selection pressure but mutations are much more likely to be beneficial with regard to those functions than the functions that measure the quality of the output. The solution was to run the selection algorithm twice for each generation: the first time ignores program size and runtime and eliminates 90% of the surplus programs, then run it again using all the criteria to remove the remaining 10% surplus.
Now it converges although very slowly, so I'd still like to know if there are any string comparison metrics that might work better as fitness functions.