2010.01.08 - genetic algorithms resurrected

during my M.Sc. studies i had a lot of courses in artificial intelligence, along which there was one semester of genetic algorithms (aka: GA). yesterday, when i was at my friend's place he asked me to search for some materials we were presenting during that course, since he was asked to prepare a GA overview seminar.

after doing some digging on the hard drive i've found lectures, seminars we were presenting and project that we implemented. the application was called 'sciezka' (ang. 'path') and it used GA to find 'cheap' (in terms of length and up/down complexity) path from one point to another, on a given map. maps were gray-scaled, where black was the lowest height, while white was the highest part – it gave us 256 levels. crossing level up/down (going up/down the hill) was more 'expensive' than walking on the same height all the time, so the best path should be as short as possible, but also should not go up/down a lot.

example path found by our algorithm on 'the warehouse' map means staying on the ground and not climbing to the top of the package. just to go straight ahead to the destination.

another examples are quite obvious – paths find by GA are easy to spot straight ahead.

there were though some of them, that were not exactly “the expected results”. paths were fine, but the trick was, that when map has been created we were thinking about other solution, that would go through as little lines as possible. in few cases we haven't spotted the most obvious solution…

when following map has been prepared we though about path similar to one of the previous – we though GA will go ahead, but it will stay on the top of the map for the whole trip and then go down to the destination. it appeared though that going through such a high hill is very expensive and GA decided… to walk it around! would you cross 10[m] high wall? GA either. :)

the last, but not least, was 'entering the castle' map. there were 2 walls around destination point and to make things a bit more difficult of GA, we painted few more lines, that would make simple “go ahead” tactic sub-optimal (it would require crossing extra lines). again it appeared that map had a little trick – while painting these lines we were already focused on the solution of crossing two walls we haven't spotted that some of the newly added lines make our original solution outdated. see for your selves.

i must say it is a very pleasant moment in life when your program exceeds your initial expectations… :)