On the Topology of Genetic Algorithms

Abstract

Genetic algorithms are stochastic search heuristics which are popular for their broad applicability, especially in combinatorial search problems. The search mechanism relies on an abstraction of genetic evolution and selection as seen in nature. This paper introduces a topological structure for the search space which is consistent with existing theory and practice for genetic algorithms, namely forma analysis. A notion of convexity is defined within this context and connections between this definition and forma analysis are established. This framework provides an alternative perspective on the exploitation/exploration dilemma as well as population convergence, which relates directly to the genetic operators employed to drive the evolution process. It also provides a different interpretation of design constraints associated with genetic algorithm implementations. The intention is to provide a new analytical perspective for genetic algorithms, and to establish a connection with exact search methods through the concept of convexity. Genetic algorithms are stochastic search heuristics which are popular for their broad applicability, especially in combinatorial search problems. The search mechanism relies on an abstraction of genetic evolution and selection as seen in nature. This paper introduces a topological structure for the search space which is consistent with existing theory and practice for genetic algorithms, namely forma analysis. A notion of convexity is defined within this context and connections between this definition and forma analysis are established. This framework provides an alternative perspective on the exploitation/exploration dilemma as well as population convergence, which relates directly to the genetic operators employed to drive the evolution process. It also provides a different interpretation of design constraints associated with genetic algorithm implementations. The intention is to provide a new analytical perspective for genetic algorithms, and to establish a connection with exact search methods through the concept of convexity.