The GA heuristic generically has hyperbolic fixed points

Author

Mary Vann Eberlein

Date of Award

8-1996

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Computer Science

Major Professor

Michael D. Vose

Committee Members

Charles Collins, Bruce MacLennan, Michael Thomason

Abstract

A continuously differentiable function 𝒢 models the behavior of a simple genetic algorithm, incorporating the genetic operators selec-tion, mutation and crossover. In this model, populations are repre-sented by points in ℜⁿ. (Typically, in genetic search the populations correspond to points in Λ = {x ∈ ℜⁿ: ∀i.x_i ≥ 0, ∑x_i = 1}). Given population p the expected next population of the GA is Gp). Sev-eral facts are known about the relationship between the GA and 𝒢. In particular, the GA spends much of its time near fixed points of 𝒢 in the large population case. Consequently, it is desirable to understand the behavior of 𝒢 near its fixed points. A fixed point x of 𝒢 is called hyperbolic if the differential d𝒢_x of 𝒢 at x has no eigenvalues of modulus one. If x is a hyperbolic fixed point of 𝒢, then d𝒢_x sheds light on the behavior of the sequence p, 𝒢(p), 𝒢²(p), in a neighborhood of x. Therefore, the differential of 𝒢 can be used to explain the behavior of 𝒢 near its hyperbolic fixed points. This report shows that in the positive mutation case, there is a dense open set in (ℜ+)ⁿ such that if the fitness parameter of 𝒢 belongs to this set, then all fixed points of 𝒢 in Λ are hyperbolic.

Recommended Citation

Eberlein, Mary Vann, "The GA heuristic generically has hyperbolic fixed points. " PhD diss., University of Tennessee, 1996.
https://trace.tennessee.edu/utk_graddiss/9729