Abstract
We propose a genetic algorithm that evolves families of rules from a set of examples. Inputs and outputs of the problem are discrete and nominal values which makes it difficult to use alternative learning methods that implicitly regard a metric space. A way how to encode sets of rules is presented together with special variants of genetic operators suitable for this encoding. The solution found by means of this process can be used as a core of a rule-based expert system.
Introduction: The Metric Trap
Traditional machine learning methods, such as neural networks and many statistical classifiers, typically operate within a "metric space." These models rely on calculating distances or neighborhoods between data points to determine classification boundaries. However, many real-world datasets contain nominal attributes—variables like "Color" (Red, Blue, Green) or "Profession" (Doctor, Engineer, Artist)—where no inherent mathematical distance exists.
Forcing these categories into a metric space by encoding them as integers (e.g., Red=1, Blue=2) introduces arbitrary bias, as it implies that Red is "closer" to Blue than to Green. Roman Neruda's 1995 technical report from Los Alamos National Laboratory addresses this by proposing a genetic algorithm (GA) that evolves logical "if-then" rules directly on the original discrete data format.
Methodology
Rule Representation and Encoding
The proposed GA treats an "individual" in the population not as a single rule, but as a complete set of rules. Each rule is structured in Disjunctive Normal Form (DNF), taking the form:
IF (Variable 1 is in {Set A}) AND (Variable 2 is in {Set B}) THEN Conclusion
To represent these rules for the GA, Neruda utilizes a bit-map encoding. For each variable, a bit string is created where the length corresponds to the number of possible values for that variable. A bit set to 1 indicates that the corresponding value is included in the rule's condition.
An individual is represented as a 2D array where rows correspond to individual rules and columns represent the bit-mapped "building blocks" for each variable.
Genetic Operators
The algorithm employs a hierarchical approach to evolution to optimize both the composition of the rule set and the logic of individual rules:
- Selection: Fitness is determined by three criteria: "catches" (correct classifications), "misses" (incorrect classifications), and "don't knows" (cases where the rule does not apply).
- High-level Crossover: This operator exchanges entire rules between two parent sets, exploring the most effective combinations of existing rules.
- Low-level Crossover: This operator exchanges specific variable blocks between rules, creating entirely new rules by mixing conditions.
- Mutation: Bits in the bit-map are randomly flipped, effectively adding or removing possible values from a rule's condition.
Key Insights
The primary advantage of this approach is its ability to navigate the "jumpy" landscape of discrete symbolic logic, which is difficult for gradient-based methods. By explicitly accounting for "don't know" cases, the fitness function encourages the evolution of "crisp," highly specific rules that only fire when certain, rather than forcing a classification on every data point.
Furthermore, the hierarchical operators respect the logical boundaries of the rules. Unlike standard GAs that might splice a binary string at any point, this method ensures that the underlying logic of a rule block remains intact during crossover.
Conclusion
While the 1995 report focuses on the theoretical framework, it provides a robust foundation for rule extraction in non-metric domains. By evolving rule sets that are inherently human-readable, the algorithm serves as a bridge between raw data and the creation of expert systems, bypassing the biases introduced by artificial metric mappings.
Summary updated