Friday, March 27, 2009

Genetic Programming

Computer Scientists like to borrow ideas from other disciplines! I already reviewed Simulated Annealing which has been inspired by Physic and atom movements. Now a quick discussion about Genetic Programming (and Evolutionary Computing), which has been inspired by Biological evolution and Genetics.

Genetic Programmig is another meta-heuristic for Optimization. The key idea is to find a (local) optimal solution by starting with a feasible population (a collection of non-optimal solutions). The initial population evolves in different iterations. Two key steps are used to evolve: a solution can mutated or crossovered. The best solution is selected among the evolutions of the initial population.

If you want to know more about Genetic programming and Evolutionary computing, there are thousands of books and papers. Personally, I like they unified approach presented in Evolutionary Computation by Kenneth A. De Jong, 2002. For those interested in Web search, let me point out that Genetic programming has been successfully used for Learning to rank (see this "optimizing evaluation measures in learning to rank" and the references within)

Here you have the code for Genetic Programming in C++

No comments:

Post a Comment