Link: ‘Hello World’ genetic algorithm

I enjoyed a post today at Hidden Clause talking about an attempt to generate the string ‘hello, world!’ using a genetic algorithm.

In the first chapter of the documentation for the Watchmaker Framework Daniel W. Dyer presents an interesting genetic algorithm example: what if we wanted to evolve the string “HELLO WORLD”? … My first thought: implementing this in JGAP shouldn’t be that hard.

The setup reminds me of the game ‘Mastermind’ — we’re dealing with a fixed-length string and scoring based on how many of the correct characters occur in the string and if they are in the right position. You combine some better strings and sometimes mutate them to generate new strings, and repeat that process until, hopefully, you arrive at the target string, ‘hello, world!’.

Did it work? Well, almost. The first result, “‘!ello, or!d!”,  was reached after 1 million iterations on a population size of a thousand — and, it used a limited alphabet containing only the letters and punctuation in the target string (and not, for example, ‘z’).

The reason the solution was not reached, the post’s author notes, is that the algorithm doesn’t have the breadth or the convergent ability to match the statistical odds involved. Recalling the old problem of monkeys on typewriters producing Shakespeare , the author notes how unlikely it is to produce the desired result.

Of course, we’re not simply monkeying at typewriters. We’re making random changes and mutations, but we’re intelligently selecting the parents. Apparently, the method first tried wasn’t intelligent enough to arrive at the desired solution within that number of iterations, and increasing iterations or population size, apparently, isn’t going to be practical.  So we need to use a better way of selecting the parents.

We could improve the fitness function. Let’s say we take the whole alphabet and the punctuation and number them (for instance: A=1… Z=26 and space and comma and exclamation could be 27, 28, and 29, respectively). Now, assign fitness based on the difference between actual and target values of each character. Is this cheating? Well, no. Our new fitness function requires no a priori knowledge of the solution and will work equally well for a different target string. This is providing our GA with a lot more information per epoch, and therefore we should see a much faster convergence.

(Aside: there are much better way of numbering the letters and punctuation to encourage faster convergence, based on the frequency the characters are used in the English language. In fact, one could develop a system that took advantage of commonly grouped letters like ‘th’ and ‘ing’, and if dealing with sentences, commonly grouped words…  Is that cheating? Well, we must remember that the more such information we encode, the more pre-disposed or biased our output will be. Also, the point of a using a genetic algorithm is to substitute computation time for programming complexity. In a contrived problem, it’s up to us where that line lies. )

There are a number of other ways to improve the fitness function, but my instinct is that this suggestion or a similar modification would be sufficient. I hope the Hidden Clause crew reports the result of another attempt.

August 13, 2009. Tags: , , , . Emergence. Leave a comment.

Queen Problems

Can you place three white queens and five black queens on a 5×5 chessboard so that no queen of one color attacks a queen of the other? The solution is unique, except rotations and reflections.

It took me longer than I first expected to solve this problem. The solution is: Puzzle-5BQ-3WQ

Since a queen attacks along rank, file, and diagonal, it leaving triangles between them unattacked, with a knight-move as the closest vertex of each triangle. While that is immediately obvious to anyone familiar with chess, I was able to solve the problem by thinking about placing white queens in such a way as to allow the largest triangles. Before searching for a solution in that manner, I tried other methods unsuccessfully: hit-and-miss attempts (having at first underestimated the problem); placing queens at knight-moves as one might do for the classic eight-queen problem (see below); utilizing symmetry by placing queens at, say, each corner and at the center; and so on.

How would a computer solve the problem? Well, a wikipedia article suggests, among other methods, a genetic algorithm, which struck my fancy.  So I started writing one.

After the skeleton of the algorithm was written and I started tinkering with parameters and the fitness function, I realized this problem would make a great introduction to genetic algorithms and also provide a simple platform for various discussions about the nuances of GAs.

July 17, 2009. Tags: , , , , . General. Leave a comment.

Yann Le Cun

Yann Le Cun was recently featured on NYAS’s Science and the City podcast. He spoke about visual processing using Artificial Neural Networks (ANNs) and in particular his work on the system that reads the amounts on your cheques at the ATM.  The host, Alana Range, notes that her ATM has never gotten her cheque amounts wrong. I myself no longer bother to check.

The technology behind the ATMs was developed by Le Cun and others almost 10 years ago, at AT&T Bell Labs [which, tragically, has been closed down]. The algorithm they developed [now] goes under the name LeNet, and is a multi-layer backpropagation Neural network called a Convolution Neural Network.  I will explain this terminology in my next post. [Update: explanation now posted.]

In the object recognition demonstration, Yann Le Cun describes four output interpretations in the LeNet algorithm: 1) edges and contours, 2) motifs, 3) categories, and finally 4) objects. By narrowing down options in several steps LeNet can arrive at the final outputn (identifying the object) far more rapidly — the demonstration on the podcast proceses 4-5 pictures each second, and can recognize five different objects.  There are also demonstrations online on Yann Le Cun’s website.

I wondered as I listened to this podcast about the comparisons drawn between mammalian visual processing and Le Cun’s algorithm. There were some very pronounced differences that suggest that our brains utilize a totally different technique, not simply a more complex version of LeNet, as was implied in the interview. These differences were:

  1. LeNet utilizes supervised learning. Our learning is largely unsupervised.
  2. We extrapolate, not just interpolate. So while LeNet needs tens of thousands of samples before it starts recognizing an object, babies might see a few toy planes and recognize the one in the sky. In interview, Le Cun notes that his algorithm, when used for letter recognition, needs to be trained with both printed and handwritten samples and is unable to extrapolate from one to the other.

I think there were some other differences that I do not now recall.  I got flashbacks of the TED-talk in which Handspring founder Jeff Hawkins cracked some jokes about the fundamental differences between computer and human visual processing. I’ll try to post about that; it was pretty entertaining.

[Update: check out a Matlab class for CNN implementation on the Matlab file exchange, by Mihail Sirotenko.]

June 13, 2009. Tags: , , , , , , . Neural Networks. 1 comment.

Surprising Results from Emergent Systems

One of my favorite examples of a surprising result from an emergent system is an experiment that utilized a genetic algorithm to solve a sorting problem on a FPGA chip. The hope was to arrive at the best (minimal) solution to the sorting problem faster and with more confidence than a human could. The actual result was that the genetic algorithm found a solution that was better than what theory said was even possible!

How did that happen? It turned out that the models humans used and programmed into computer simulations were not in fact complete. They are based in theoretical simplifications that do not fully describe the physical world, in which nature is not limited to the ‘1’s and ‘0’s of electrical theory, in which nature could take advantage of the minute electromagnetic coupling of electrical components packed tightly into a silicon ship, in which higher order effects not considered by models could be utilized to solve the problem. 

By physically wiring an infinitely reprogrammable Xilinx XC6216 FPGA chip to allow the genetic algorithm to use a physical board — instead of a computer simulation of the board — the algorithm arrived at a solution that used fewer steps and fewer gates than the best solution previously offered by theory. 

“What is downright scary is this: the FPGA only used 32 of its 100 available logic gates to achieve its task, and when scientists attempted to back-engineer the algorithm of the circuit, they found that some of the working gates were not even connected to the rest through normal wiring. Yet these gates were still crucial to the functionality of the circuit. This means, according to Thompson, that either electromagnetic coupling or the radio waves between components made them affect each other in ways which the scientists could not discern (Taubes 1997).”

The structure of the genetic solution discarded the need for models or theory and was allowed to experiment with actual physical properties.  All that was needed were rules that allowed better solutions to survive in each generation until the optimal result was achieved. 

Read more: http://www.cs.bgu.ac.il/~jasminme/ECAL071/Exe3/koza_evolving.pdf [PDF] 

Not all problems are suitable for such an evolutionary approach; it is often impractical even when it does work. But what appeals to me is the idea that we can  do what nature does. We can use simple rules to find an amazingly efficient solutions to a problem, without understanding how that solution really works. Not far in the future, the world might be full of algorithmic solutions as diverse and amazing to a computer scientist as the animals of the world are to a zoologist.

December 15, 2008. Tags: , , , . Emergence. 1 comment.