A NEW GENETIC ALGORITHM

• 成果类型: Article
• 署名作者: Cerf, Raphael
• 署名单位: Universite Paris Saclay; Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/aoap/1034968228
• 发表日期: 1996
• 页码: 778-817
• 关键词: convergence

摘要

Here is a new genetic algorithm. It is built by randomly perturbing a two operator crossover-selection scheme. Three conditions of biological relevance are imposed on the crossover. A new selection mechanism is used, which has the decisive advantage of preserving the diversity of the individuals in the population. The attractors of the unperturbed process are particular equi fitness subsets of populations endowed with a rich structure. The random vanishing perturbations are twofold: local perturbations of the individuals (mutations) and loosening of the selection pressure. When the population size is greater than a critical value which depends strongly on the optimization problem, their delicate asymptotic interaction ensures the convergence (possibly in finite time) of the population to the ideal attractor whose populations contain all the maxima of the fitness function. The process explores without respite the neighborhoods of the best points found so far (instead of focusing on a particular point) and finds simultaneously all the global maxima of the fitness function; it seems to be the first cooperative search procedure of this kind.