Friday, Debtember 20, 2002
Evolving answersSo I'm reading the genetic algorithms book I received, An Introduction To Genetic Algorithms by Melanie Mitchell and it's quite interesting. I've known the basics of genetic algorithms but I've never really programmed any. Generally, they work like natual selection: you have a population of possible answers (e.g., a list of cities to visit in a particular order) to a problem (e.g., the Traveling Salesman, where you want to minimize the distance traveled) and you cross breed the current population (by taking two (or more perhaps) answers, selecting a portion of their results, and mixing the two to form one (or more) new answers), and possibly mutating the result a bit (e.g., swapping two random cities in a given answer). You keep doing this over and over until you get an answer, or an answer that is good enough. You don't just select potential answers to breed by random—no, you select them based upon a certain criteria (in this case, those in the population with the shortest answers so far) that drives the results towards your eventual goal.
This can't be applied to every problem though, and for those that it can be, the trick is to pick a representation of the data that can be mixed up and mutated easily.
As I'm reading, I'm also doing certain exercises from the book to help cement my understanding of the processes involved in programming genetic algorithms. It's an enjoyable way to spend a few hours.