Dynamic System Control Using Rule Learning and Genetic Algorithms

David E. GoldbergIJCAI 1985

Introduction

Traditional automation is highly effective for repetitive, deterministic tasks. However, real-world environments often present "perpetual novelty"—unforeseen scenarios that rigid, hard-coded algorithms cannot handle. David Goldberg's research addresses this by proposing an adaptive control framework based on Learning Classifier Systems (LCS). Unlike traditional controllers that require pre-programmed laws, the LCS starts with a "random state of mind" and evolves its own rules for system stability and emergency response.

The Learning Classifier System Architecture

The core of this approach is the LCS, a hybrid system that integrates three distinct mechanisms to facilitate autonomous learning.

Schematic of the Learning Classifier System (LCS) architecture, showing the interaction between detectors, the message list, the classifier store, and the genetic algorithm.
  1. Rule and Message System: This serves as the system's cognitive engine. Detectors translate environmental states into messages, which are processed by a set of rules (classifiers) represented as ternary strings (0, 1, and the '#' wildcard). The wildcard allows the system to generalize across different environmental states.
  2. Apportionment of Credit (AOC): Modeled after a competitive service economy, this system manages the "fitness" of rules. Classifiers bid for the opportunity to act; successful actions result in rewards (income), while poor decisions lead to "bankruptcy." This ensures that only useful rules persist in the system.
  3. Genetic Algorithm (GA): The GA acts as the innovation engine. It periodically selects high-performing rules to serve as "parents" for new rules, using crossover and mutation to explore new strategies that the AOC system can then evaluate.

Experimental Environments

The system was tested in two simulated environments:

  • 1-D Inertial Object: A mass governed by Newtonian physics. The goal is to maintain the object's position at the center of a track despite external disturbances.
  • Natural Gas Pipeline Simulator: A complex simulation involving friction, storage (linepack), seasonal demand fluctuations, and unpredictable leak events. This environment tests the system's ability to balance supply and demand while identifying critical failures.

Key Results and Insights

The inclusion of a Genetic Algorithm proved critical for long-term performance and sophisticated strategy discovery. In the inertial control task, the GA-enabled system independently discovered "braking rules"—applying counter-force to prevent overshoot—a behavior typically requiring manual engineering in traditional control theory.

In the more complex pipeline management task, the GA-enabled system demonstrated superior efficiency and accuracy.

Performance comparison (Total Evaluation over Time) for the natural gas pipeline simulator, showing the GA-enabled system (POLCS.6) significantly outperforming the non-GA version (POLCS.5) and a random walk.

A significant finding was the resolution of the "False Alarm Paradox." While a system without a GA could achieve high raw leak detection rates, it suffered from an extremely high false alarm rate (approximately 75%). The GA-enabled system learned to distinguish between pressure drops caused by normal demand shifts and those caused by actual leaks, significantly improving the economic viability of the control strategy.

Conclusion

The research demonstrates that the "ruthlessly spartan syntax" of LCS, when combined with evolutionary heuristics, allows for the creation of self-programming control systems. By treating rules as economic agents and using GAs for innovation, these systems can master complex, dynamic environments without human intervention. Future work will focus on scaling these simulations to real-world complexities and improving the resolution of environmental sensors.

Summary updated

BibTeX
@inproceedings{goldberg1985dynamic,
  author = {David E. Goldberg},
  title = {{Dynamic System Control Using Rule Learning and Genetic Algorithms}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1985},
}
Figure