CONVERGENCE ANALYSIS OF CANONICAL GENETIC ALGORITHMS

被引：934

作者：

RUDOLPH, G

机构：

[1] Department of Computer Science, LS XI, University of Dortmund, Dortmund

来源：

IEEE TRANSACTIONS ON NEURAL NETWORKS | 1994年 / 5卷 / 01期

关键词：

Canonical genetic algorithm - Convergence analysis - Crossover reproduction - Finite Markov chain analysis - Global optimum - Mutation - Proportional reproduction - Schema theorem;

D O I：

10.1109/72.265964

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper analyzes the convergence properties of the canonical genetic algorithm (CGA) with mutation, crossover and proportional reproduction applied to static optimization problems. It is proved by means of homogeneous finite Markov chain analysis that a CGA will never converge to the global optimum regardless of the initialization, crossover, operator and objective function. But variants of CGA's that always maintain the best solution in the population, either before or after selection, are shown to converge to the global optimum due to the irreducibility property of the underlying original nonconvergent CGA. These results are discussed with respect to the schema theorem.

引用

页码：96 / 101

页数：6