Introduction
In the field of heuristic search, the performance of a solver depends critically on its evaluation function—a mathematical rule that estimates the distance from a given state to the goal. Larry A. Rendell's 1983 paper introduces PLS2, a "doubly layered" learning system designed to automate the discovery of these functions by combining state-space exploration with genetic algorithms. Building on the earlier PLS1 system, PLS2 addresses fundamental issues of instability and complex feature interactions that previously hindered automated heuristic learning.
The Problem of Heuristic Learning
In the early 1980s, creating effective evaluation functions for puzzles like the 15-puzzle was a manual and error-prone process. Rendell's previous system, PLS1, attempted to learn these functions by measuring "penetrance"—the density of solution paths within specific regions of a feature space. However, PLS1 suffered from two primary flaws: it was highly sensitive to noisy training data (instability) and struggled to account for non-independent feature interactions.
As shown in the conceptual mapping above, the goal is to partition the feature space into regions that provide reliable estimates of success. PLS2 seeks to move beyond simple linear weight optimization to a system that can discover global optima in these complex, non-linear search spaces.
The PLS2 Architecture
PLS2 introduces a two-layered architecture to manage the learning process more robustly. The first layer, the Performance Element (PE), performs the standard tasks of exploring the state space and collecting statistics on feature success. The second layer, the Genetic Supervisor, treats the knowledge gathered by the PE as a "genotype" to be evolved.
This architecture allows the system to maintain a population of solvers, each with different feature space partitions. A "Critic" component assigns utility to specific regions within the feature space, enabling "credit localization." Instead of judging a solver as a whole, the system can identify and preserve high-quality "genes" (specific feature regions) even if they originate from an overall underperforming solver.
Genetic Optimization and Results
Unlike standard genetic algorithms that use binary crossover, PLS2 employs a "K-sexual" reproduction strategy. It merges regions from the entire population and stochastically selects the most useful ones to form the next generation. This approach exploits the relative independence of feature regions, making the genetic search highly efficient.
Experimental results on the 15-puzzle demonstrated that PLS2 significantly improved stability over its predecessor. By evolving the way feature space is partitioned, the system effectively handles non-linear interactions and is capable of locating global optima in the weight space. The author notes that the system's ability to dismiss aberrant information—data that would have previously led the learner astray—is a key factor in its superior performance.
Conclusion
PLS2 represents a foundational step in combining evolutionary computing with symbolic AI. By layering a genetic supervisor over a statistical performance element, Rendell created a robust framework for automated heuristic discovery. While the system still requires human-defined initial features, its ability to optimize their use through regionalization and population-based learning marked a significant advancement in machine learning for state-space search.
Summary updated