Improving System Performance in Case-Based Iterative Optimization through Knowledge Filtering

TL;DR

Adding knowledge to AI systems isn't always beneficial; it can actually slow them down. This paper introduces "knowledge filtering" strategies for a case-based system (CABINS) that learns to optimize job-shop schedules. By intelligently using past failures, these filters significantly improve efficiency without sacrificing solution quality.

What Problem Does This Paper Address?

The prevailing wisdom in AI has often been that more knowledge equals better performance. However, this paper challenges that assumption, particularly in the context of knowledge-based systems that learn over time. They highlight that acquired knowledge, especially from machine learning systems, can be of low quality (incorrect, irrelevant, or redundant). This "unfiltered" knowledge can degrade performance by increasing computational costs (e.g., longer search times) without a corresponding improvement in solution quality. The authors specifically address this in the domain of job-shop scheduling, a notoriously complex and "ill-structured" optimization problem where it's hard to predict the outcome of any given action due to intricate interdependencies. Their goal is to find ways to make learned knowledge beneficial by filtering out the harmful parts.

Methods

The core of this paper is the introduction and evaluation of knowledge filtering strategies within their case-based reasoning (CBR) system, CABINS. CABINS learns control knowledge for iterative repair of job-shop schedules.

Here's a breakdown of their approach:

  • CABINS System: It works by iteratively revising an initially suboptimal schedule. It uses "repair tactics" (like moving an activity on a timeline) to improve the schedule. The system learns which repair tactics to use and how to evaluate their outcomes by storing past repair experiences as "cases."
  • The Problem with Unfiltered Knowledge: In their experiments, they found that CABINS, when using all learned cases without any filtering, became "greedy" and "stubborn." This meant it would try the most similar repair tactic regardless of how weak the similarity was, and it would persist in trying to repair an activity even when the likelihood of success was low. This led to excessive tactic applications and reduced efficiency.
  • Knowledge Filtering Strategies: To combat this, they developed three filtering strategies that leverage failure information from past cases:
  • Validated Filtering: Before applying a repair tactic, CABINS checks if it's likely to fail based on past failures with similar situations. If a tactic has a low probability of failure (validated), it's considered.
  • Interruptive Filtering: If CABINS estimates that repairing a particular activity is too difficult (based on a high number of past failures in similar situations), it "gives up" on that activity and moves to another, saving wasted effort.
  • Hybrid Filtering: This strategy combines both validated and interruptive filtering. It first checks if it should give up on an activity (interruptive) and, if not, then proceeds to validate the chosen repair tactics (validated).

Datasets

The paper does not introduce new datasets. Instead, they use a benchmark suite of job-shop scheduling problems. These problems are variations of those used in prior work by the authors, with each problem consisting of 10 orders, each with 5 activities. They generated these problems by considering different parameter values for range and bottleneck configurations.

Key Insights and Ideas

  • Knowledge is Not Always Good: The most significant insight is the empirical demonstration that learned knowledge, when unfiltered, can actively harm system performance by increasing computational cost without improving solution quality. This is a crucial counterpoint to the common assumption that more knowledge is always better.
  • Failure is Informative: The paper strongly advocates for the utility of failure information. Instead of just discarding failures, they show how to proactively use them to guide future decisions, either by validating potential actions or by knowing when to stop trying.
  • Context Matters for Filtering: The effectiveness of filtering depends on the domain. For ill-structured problems like job-shop scheduling, where domain models are hard to build, failure-based filtering becomes a powerful alternative.
  • Synergistic Effects of Hybridization: Combining different filtering strategies (validated and interruptive) leads to a synergistic effect, yielding better efficiency improvements than either strategy alone.

Key Results

The experimental results are quite compelling:

  • Efficiency Gains:
    • Validated Filtering: Improved efficiency by about 58% compared to the unfiltered condition.
  • Interruptive Filtering: Improved efficiency by about 46%.
  • Hybrid Filtering: Achieved the highest efficiency improvement at about 65%.
  • Solution Quality Maintained: Crucially, these efficiency gains were achieved without sacrificing solution quality. In fact, the filtered versions often produced solutions of similar or even slightly better quality than the unfiltered version.
  • Faster than Baseline: The filtering strategies also made CABINS faster than a rule-based optimizer (RBR) that served as their baseline.
  • Reduced Tactic Applications: The primary driver for efficiency improvement was a significant reduction in the number of repair tactic applications, which are computationally expensive. For example, hybrid filtering reduced tactic applications from 2206.2 (unfiltered) to 776.6.

Limitations and Future Work

  • Parameter Tuning: The authors acknowledge that the filtering strategies involve parameters (like k for nearest neighbors and threshold values). They mention that they heuristically decided on these values for their experiments.
  • Future Work: They are currently exploring automated adaptation of the filtering control parameters. This suggests that finding optimal values for k and thresholds could be learned or adjusted dynamically, further enhancing the system's performance.

Summary updated

BibTeX
@inproceedings{1995improving,
  title = {{Improving System Performance in Case-Based Iterative Optimization through Knowledge Filtering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure