Some features about the convergence process of a Genetic Algorithm
M. T. Iglesias, M. R ́ ios, Concepción Vidal · 2005
Genetic Algorithms (GA) are inspired by nature, by the principle of evolution, i.e., survival of the fittest. GA are applicable to many hard optimization problems. The importance of these evolution programming techniques is growing since evolution processes are parallel in nature and parallelism is one promising direction in Computer Science. The underlying idea of GA is extremely simple. Consider a population P of prey, with characteristics making them more or less likely to be eaten by predators and let us suppose that we can describe these features that permits an individual p to survive by some fitness function f i.e.: the higher the value of f(p), the higher the probability of survival of p -the population, of course, evolves in time-. For obvious reasons, one expects the prey with high fitness to eventually dominate the population. This is exactly how a basic GA works. Formally, one may thus think of an optimization problem. In this review of Genetic Algorithms -and their convergence processwe do not aim at completeness. Our wish is to provide a brief overview that is broad enough to show the richness of this field (only occasionally fill in details but refer amply to existing literature): we will describe in a intuitive way what GA are about and we will briefly sketch some of the mathematics behind this (such that the schema theorem by Holland ([3]) and concepts like deception ([2]), (high) epistasis ([1], [4]) and (high) order ([4]) of the fitness function). Moreover, we give the main ideas of Contractive Genetic Algorithms (CGA). The Banach fix point theorem has an intuitive application to the case of GA. In fact, it may be proved the convergence of CGA to the same fix point independently of the choice of initial population. The fix point is achieved when all individuals in the population have the same -global maximumvalue (see [5] for details).