It's been observed that evolution works remarkably well both in the real world and as a software optimization method. It's been somewhat of a mystery as to why this is the case. In both cases, evolution produces very efficient results in sometimes unexpected ways, but there is no mathematic proof as to why genetic algorithms seem bound for success. A new paper by Marek W. Gutowski of the Institute of Physics at the Polish Academy of Sciences in Poland offers some insights into the problem. The paper titled, Amazing Geometry of Genetic Space or Are Genetic Algorithms Convergent? (PDF format) offers this conclusion:
"The chances of improvement are always higher than for lack of it, if the selection of parents is performed either in soft, or hard but adaptive, manner. This is a very general result, completely independent of the optimization problem under study. It applies equally well to discrete, continuous and mixed optimization problems."Ultimately, Gutowski offers a proof that soft selection is superior to other methods.
Tags: Genetics, Evolution, Algorithms.
in fact, prooves about convergence of genetical algorithms have been obtained by Raphael Cerf (see for instance Asymptotic convergence of genetic algorithms, 1998).
ReplyDelete