Understanding Genetic Algorithm Dynamics Using Harvesting Strategies

摘要

The genetic algorithm (GA) finds optimal solutions over complex fitness landscapes using a method developed in analogy to genetic laws and natural selection. The method essentially operates by optimizing the tradeoff between exploring new points in the search space and exploiting previous information discovered thus far. In this tradeoff, an understanding of the internal GA dynamics, how exactly the GA arrives at an optimum solution, remains somewhat mysterious. Harvesting strategies are introduced here to parameterize the GA's dynamical behavior of elevating sub-threshold solutions toward optimum. The method of harvesting balances the competing aims of population diversity counterweighted against rapid convergence toward the optimum solution. The work establishes that: (1) an upper bound on the fitness ratio exists, above which harvesting becomes too disruptive to the population diversity; (2) analytical conditions for considering elevation within the genetic algorithm are a specific case of logistic growth; and (3) explicit relations exist for the maximum yield and maximum harvestable fraction for 2-stage, 3-stage and finally n-stage harvesting strategies as a function of fitness ratio. Simple expressions for GA time complexity between harvesting steps are presented.