An Analysis of Genetic-Based Pattern Tracking and Cognitive-Based Component Tracking Models of Adaptation

Elaine Pettit, Kathleen M. SwiggerAAAI 1983

Introduction

In the early 1980s, the field of evolutionary computation was in its infancy, driven largely by John Holland’s pioneering work on genetic algorithms (GAs). A central question of the time was how biological systems adapt so effectively to complex, shifting environments. This paper, originally presented at AAAI-83, explores this question by pitting Holland’s genetic models against a more traditional "cognitive" statistical approach. The goal was to determine whether adaptation is better served by tracking individual components of an environment or by utilizing the structured, "blind" operators of evolution to capture complex patterns.

The Models of Adaptation

The researchers evaluated four distinct models to compare their adaptive capabilities:

  1. BETA (The Genetic Model): This model implemented Holland’s fundamental genetic operators, including fitness-proportionate selection, mutation, inversion, and crossover. Crossover, in particular, allows the population to swap segments between strings, facilitating the exploration of new solution spaces.
  2. MEMPOP (The Cognitive Model): This model functioned as a bit-wise statistical tracker. It maintained a memory of failure frequencies for each bit position and adjusted the probability of "flipping" bits based on that history.
  3. RANDPOP: A baseline model that relied solely on random point mutations without any structured selection or recombination.
  4. CONTROLPOP: A control group with no adaptive mechanism, representing a static response to the environment.

Mechanism of the Genetic Model

The BETA model's strength lies in its ability to manipulate entire structures rather than individual bits. By using crossover, the model can combine successful sub-patterns (schemata) from different individuals in the population.

Illustration of the crossover mechanism in the BETA (genetic) model, showing how segments are swapped between two parent structures to create offspring.

Experimental Methodology

The study utilized synthetic environments represented by 12-bit binary strings. To simulate environmental change, the authors employed Markov-chain transition matrices, allowing for precise control over the volatility of the environment. Three specific profiles were tested:

  • Frequent Perturbations: A highly volatile environment with rapid bit changes.
  • Rare Perturbations: A steady-state environment with infrequent shifts.
  • Absorbing State: A perfectly stable environment.

Results and Statistical Analysis

The performance of the models varied significantly depending on the environmental profile. In volatile environments, the cognitive model (MEMPOP) demonstrated a clear advantage. Its ability to track individual bit-wise statistics allowed it to respond more quickly to rapid fluctuations than the genetic model, which requires time for successful traits to propagate through a population.

Statistical analysis using Kruskal-Wallis and Duncan's Multiple Range Test (MRT), showing MEMPOP's superior mean performance in a volatile environment.

However, the results shifted in stable environments. In "absorbing state" tests, the genetic model (BETA) eventually surpassed the cognitive model in fitness. While the cognitive model is an excellent "component tracker," the genetic model proved to be a superior "pattern tracker," capable of locking onto complex, stable configurations that bit-wise statistics might miss.

Discussion

Computational Complexity

A major finding of the study was the difference in computational efficiency. The cognitive model (MEMPOP) requires $O(n^2)$ operations, as it must update and query every bit of every structure in the population. In contrast, the genetic model operates at $O(n)$, manipulating whole structures based on a single fitness score. This makes GAs significantly more scalable for complex problems.

Punctuated Equilibrium and Local Optima

The data for the genetic model showed "jumps" in performance—sudden bursts of adaptation followed by plateaus. This mirrors the biological theory of punctuated equilibrium. Furthermore, while cognitive models can become trapped in local optima by locking too tightly into a current state, GAs maintain a diverse "pool of schemata," allowing for faster recovery when a long-stable environment finally shifts.

Conclusion

The researchers concluded that while bit-wise statistical tracking is effective for volatile, independent components, genetic algorithms provide a more robust and efficient abstraction for tracking complex patterns. The study provides empirical support for Holland’s theories of "intrinsic parallelism," suggesting that the structure of genetic operators—not just random change—is the primary driver of effective adaptation in stable or correlated environments.

Summary updated

BibTeX
@inproceedings{pettit1983analysis,
  author = {Elaine Pettit and Kathleen M. Swigger},
  title = {{An Analysis of Genetic-Based Pattern Tracking and Cognitive-Based Component Tracking Models of Adaptation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}

Loading related content...

Figure