An Analysis of a Simple Genetic Algorithm.
Yuri G. Rabinovich, Avi Wigderson · 1991
The rate of convergence and the structure of stable populations are studied for a simple, and yet nontrivial, family of genetic algorithms. 1 INTRODUCTION This paper originates in an attempt to use genetic algorithms as an alternative approach to theoretical problems of combinatorial optimization. In Holland's [1] pioneering work it is suggested that genetic algorithms are likely to work well in those cases where some short schemata have fitness exceeding the average and where these schemata combine well by the crossover operator. In this case the crossing-over of two well fitted structures usually results in a well fitted structure. In the context of combinatorial optimization this means that a genetic algorithm (with a genetic operator that is tailor-made for the problem) is likely to be effective when this operator usually merges two given structures of high fitness into a third good structure. Consider for example the classical problem of finding large matchings in a given graph G...