Quote:
Originally Posted by Lonewolf MacQuaid
To your knowledge, has anyone ever proven genetic algorithm to converge to a global optimal solution in the limit?
This is outside my expertise, although I have done work with
Freidlin-Wentzell large deviations, which is at the heart of proving convergence in simulated annealing. I cannot offer any concrete answers, but maybe you can find something in one of these:
@article {MR2052865,
AUTHOR = {Stannat, Wilhelm},
TITLE = {On the convergence of genetic algorithms---a variational
approach},
JOURNAL = {Probab. Theory Related Fields},
FJOURNAL = {Probability Theory and Related Fields},
VOLUME = {129},
YEAR = {2004},
NUMBER = {1},
PAGES = {113--132},
ISSN = {0178-8051},
CODEN = {PTRFEU},
MRCLASS = {35J20 (35A15 60J25 92D10 92D15)},
MRNUMBER = {MR2052865 (2005d:35040)},
MRREVIEWER = {Dominique L{\'e}pingle},
}
@article {MR1832784,
AUTHOR = {Schmitt, Lothar M.},
TITLE = {Theory of genetic algorithms},
JOURNAL = {Theoret. Comput. Sci.},
FJOURNAL = {Theoretical Computer Science},
VOLUME = {259},
YEAR = {2001},
NUMBER = {1-2},
PAGES = {1--61},
ISSN = {0304-3975},
CODEN = {TCSDI},
MRCLASS = {90C59 (68T05 90C15)},
MRNUMBER = {MR1832784 (2002j:90117)},
MRREVIEWER = {R. Shonkwiler},
}
@article {MR2020342,
AUTHOR = {Schmitt, Lothar M.},
TITLE = {Theory of genetic algorithms. {II}. {M}odels for genetic
operators over the string-tensor representation of populations
and convergence to global optima for arbitrary fitness
function under scaling},
JOURNAL = {Theoret. Comput. Sci.},
FJOURNAL = {Theoretical Computer Science},
VOLUME = {310},
YEAR = {2004},
NUMBER = {1-3},
PAGES = {181--231},
ISSN = {0304-3975},
CODEN = {TCSDI},
MRCLASS = {68T05},
MRNUMBER = {MR2020342 (2004j:68156)},
}
@article {MR2039188,
AUTHOR = {Zhao, Xiao-yan and Nie, Zan-kan},
TITLE = {The {M}arkov chain analysis of premature convergence of
genetic algorithms},
JOURNAL = {Chinese Quart. J. Math.},
FJOURNAL = {Chinese Quarterly Journal of Mathematics. Shuxue Jikan},
VOLUME = {18},
YEAR = {2003},
NUMBER = {4},
PAGES = {364--368},
ISSN = {1002-0462},
MRCLASS = {60J20 (60J10 92D10)},
MRNUMBER = {MR2039188 (2004k:60201)},
MRREVIEWER = {Ren{\'e} L. Schilling},
}