Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
This seems closer to a meta-question than a question: you are really asking for a good mathematical question to ask about genetic algorithms. It is not clear to me whether such "questions asking for good questions" are appropriate for this site, but I find your meta-question interesting enough so that I will not vote to close it. Let's see what people have to say... –  Pete L. Clark Sep 25 '11 at 20:45
1  
@PeteL.Clark I agree, it is absolutely vague. Maybe I could edit it and reformulate it as a "big-list question", as other questions I've seen here asking "the most beautiful theorem in that area" and such things; If "senior members" of this site (like you) think is not appropriate I will try to formulate it as something like "what are the most mathematically deep facts you can see in the theory of Genetic Algorithms?", or something similar. –  Emanuele Natale Sep 25 '11 at 22:08
1  
Definitely on the mathematical side of the study of EA are this paper and this other paper. –  Did Sep 26 '11 at 1:58

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you very much, this is the kind of answer I was hoping to get. –  Emanuele Natale Sep 25 '11 at 22:28
    
sigma.z.1980 do you have any reference also for schemata thoery? –  Emanuele Natale Sep 26 '11 at 9:33
    
try oldschool stuff, John Holland's 'Adaptation in Artificial Systems'(1975), Goldberg's 'Genetic Algorithms' (1989) and Mitchell's 'Introduction to GA' (1996). Also, as an antidote try Reeves, Rowe (2003) and Nix, Vose(1992). –  sigma.z.1980 Sep 26 '11 at 20:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.