Computing Optimal Populations for Binary Problems using Logic Minimization

Area of Science:

• Machine Learning
• Artificial Intelligence
• Computational Intelligence

Background:

• Generalization in eXternal Classifier System (XCS) has primarily focused on single-step binary problems.
• Multi-step binary problems in XCS have been studied mainly for performance, with optimal solutions remaining unknown.
• Existing research lacks a method to determine optimal generalization for multi-step environments.

Purpose of the Study:

• To present a novel approach for computing optimal solutions in both single-step and multi-step binary problems.
• To establish a method for deriving optimal solutions starting from a tabular solution.
• To analyze and compare these optimal solutions with those evolved by XCS.

Main Methods:

• Developed an approach to compute optimal solutions for binary problems from their tabular representations.
• Illustrated the method using Boolean functions with known optimal solutions.
• Applied the approach to compute optimal solutions for the Woods problems, a multi-step testbed for XCS.

Main Results:

• Successfully computed optimal solutions for single-step and multi-step binary problems, including the Woods problems.
• Confirmed initial hypotheses in simple environments and provided new understanding for complex scenarios.
• Demonstrated that XCS evolves minimal solutions, with their number increasing alongside the number of learning problems.

Conclusions:

• The developed approach provides a way to compute optimal solutions for multi-step XCS problems.
• Findings validate early intuitions and offer new perspectives on generalization in complex learning tasks.
• The study also addresses the minimal representation of evolving classifier populations and the impact of condensation.