What about Genetic Algorithms from a mathematical point of view?

Question

Last year I've attended an Artificial Intelligence course (it was very simple, just a summary of the main ideas); we've seen what a genetic algorithm is and the idea seems very interesting to me. Now I must plan what courses will I attend during my "master" (I'm italian, here we have 3 year of bachelor degree, plus 2 year of "Magistrale", that I don't know if could be translated better than it is with "master"). I would like to know how much interesting Genetic Algorithm are from a mathematical point of view, I mean if it is reasonable for a mathematics student to start to study them as a possible field where to do research in the future.

Answer 1

Yes, a genetic/evolutionary algorithm (EA) is a very sensible mathematical topic. In short, there are a lot of applications but not too much theory, so less advanced people, such as myself, actually have a chance.

There are two things you can look at: schemata theory that concerns mostly with $\textit{why}$ an EA works and is quite hard and algebraic, and runtime/convergence analysis, which answers the question $\textit{how}$ it works. It is more probabilistic, combinatorial and analytical, and therefore I find it more interesting.

Since most EAs are binary-encoded, most people look at convergence on binary-encoded problems (OneMax, OneMax with weights, BinaryValues, etc) and combinatorial problems (Shortest Path, Eulerian cycles, etc). In the past few years the amount of research increased substantially, but still concerns test problems, not real-life problems. It is also focused on $(1+1)$ EA, i.e. elitist algorithm with population and recombination pool size 1 using some form of mutation operator. Population and recombination-based algorithms are fairly rare.

What I suggest you go and have a look at are:

Rudolph(1994a,1994b,1997)

Nix,Vose(1992) - quite hard

Droste et al(2002) - the most popular paper so far

He,Yao(2002,2003,2004)

Chen et at(2009,2011)

Doerr et all (lots of papers written in the past 2 years, esp. on drift analysis)

This will give you a good intro on what's going on in the area. Also, if you are good with complex analysis, have a look at Analytic COmbinatorics by Flajolet, Sedgewick(2007) and Flajolet et al (2005,2006). And Concrete MAthematics is a very good book, of course :)

Once again, the more math you use the more we find out about EA. Good luck.