Classification Using an Online Genetic Algorithm

AAAI 1998

TL;DR

This paper introduces an "online genetic algorithm" (OLGA) for classification tasks. Unlike traditional genetic algorithms that rely on a fixed dataset, OLGA learns incrementally from a stream of examples, making it suitable for dynamic environments and large datasets where storing all data is impractical.

What Problem Does This Paper Address?

Traditional genetic algorithms (GAs) are powerful optimization tools, but they typically require a static, fixed dataset for evaluating the "fitness" of potential solutions. This approach is problematic in scenarios where the data distribution changes over time (concept drift) or when the dataset is too massive to be held in memory for repeated evaluations. The authors address this by proposing an "online" GA that can learn and adapt continuously as new data arrives, mimicking natural selection in dynamic environments.

Methods

The core innovation is the Online Genetic Algorithm (OLGA). Key features include:

  • Incremental Learning: Instead of evaluating against a full training set, OLGA processes examples one at a time.
  • Dynamic Fitness: An individual's fitness is not fixed but evolves as it encounters more examples. The fitness is calculated based on the number of correctly classified examples seen so far for each class, weighted by the class itself.
  • Support for New Individuals: The fitness function is designed to prevent newly created individuals from being immediately discarded before they have a chance to learn from a reasonable number of examples.
  • Classification Mechanism: For classification tasks, individuals can represent complete solutions or contribute as part of a group. The final classification is determined by a majority vote among contributing individuals.
  • Standard GA Components: OLGA still utilizes a population, recombination (e.g., multi-point crossover), and mutation operators.

Datasets

The paper describes experiments conducted on a set of 6 boolean attributes with a classification target that is true only when all attributes are 1. The value of one attribute (a1) was set to 1 with a fixed probability. The authors also varied the probability of this attribute, which in turn varied the overall class distribution (ranging from 22% to 64% positive examples). This constitutes a newly introduced benchmark designed to test the OLGA's adaptability to varying class distributions and the learnability of different classification functions.

Key Insights and Ideas

  • Adaptability is Key: The OLGA's ability to adapt to changing data distributions and learn incrementally is its most significant advantage over static GAs.
  • Fitness as a Moving Target: The concept of a dynamic fitness function that updates with each new example is crucial for online learning. It allows the algorithm to continuously refine its understanding of the data.
  • Mimicking Natural Selection: By processing examples sequentially and adapting, the OLGA more closely resembles how real organisms learn and adapt in dynamic environments.
  • Robustness to Unusual Scenarios: The OLGA demonstrated effectiveness even when faced with challenges like combining conflicting classifiers or abrupt shifts in data distribution.

Key Results

The OLGA achieved high classification performance, with accuracies ranging from 86% to 98% across various configurations of the synthetic boolean attribute problem. Even when tested on more complex scenarios, such as combining multiple conflicting classifiers or handling sharp changes in data distribution, the OLGA maintained strong cumulative classification accuracies.

Limitations and Future Work

The authors acknowledge that the current work is based on one artificial domain. While the results are promising, they are considered "initial, albeit weak, evidence" for the OLGA's applicability.

Future work suggested includes:

  • Applying the OLGA architecture to non-artificial problems.
  • Comparing the OLGA to other online algorithms to benchmark its performance against existing state-of-the-art methods in online learning.

Summary updated

BibTeX
@inproceedings{1998classification,
  title = {{Classification Using an Online Genetic Algorithm}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}
Figure