Abstract
Detecting changepoints in a time series of length $N$ entails evaluating up to $2^{N-1}$ possible changepoint models, making exhaustive enumeration computationally infeasible. Genetic algorithms (GAs) provide a stochastic way to identify the structural changes: a population of candidate models evolves via selection, crossover, and mutation operators until it converges on one changepoint model that balances the goodness-of-fit with parsimony. The R package changepointGA encodes each candidate model as an integer chromosome vector and supports both the basic single-population model GA and the island model GA. Parallel computing is implemented on multi-core hardware to further accelerate computation. Users may supply custom fitness functions or genetic operators, while a user-friendly wrapper streamlines routine analyses. Extensive simulations demonstrate that our package runs significantly faster than binary-encoded GA alternatives. Additionally, this package can simultaneously locate changepoints and estimate their effects, as well as other model parameters and any integer-valued hyperparameters. Applications to array-based comparative genomic hybridization data and a century-long temperature series further highlight the package's value in biological and climate research.
Introduction
Identifying "changepoints"—moments when the underlying statistical properties of a time series shift—is a classic but computationally brutal problem. For a series of length $N$, there are $2^{N-1}$ possible configurations of changepoints. Even for moderate $N$, an exhaustive search is impossible.
While Genetic Algorithms (GAs) have been used to navigate this search space stochastically, most existing implementations rely on binary encoding (a string of 0s and 1s of length $N$). This approach suffers from high dimensionality, potential for invalid configurations (e.g., changepoints placed too close together), and a lack of support for joint parameter estimation. The changepointGA package addresses these issues through a novel integer-based representation.
Methodology: Integer Encoding and the Island Model
The core innovation of changepointGA is its compact integer representation. Instead of a long binary string, a "chromosome" is a vector containing the number of changepoints ($m$), model hyperparameters ($s$) such as AR or MA orders, and the specific integer locations of the changepoints ($\tau$). This drastically reduces the dimensionality of the search space, turning a problem that scales with the length of the time series into one that scales with the number of changepoints.
The package implements two types of GAs: a basic single-population model and a more robust Island Model. The Island Model maintains separate subpopulations ("islands") that evolve independently and occasionally swap individuals through a "migration" process. This prevents the algorithm from getting stuck in local optima and allows for efficient parallelization across multi-core hardware.
To find the best model, the package uses the Bayesian Information Criterion (BIC) as a fitness function, balancing goodness-of-fit with model parsimony. It also allows users to set a minDist parameter to ensure changepoints are not placed too close together, avoiding computational singularities.
Performance and Real-World Applications
The authors benchmarked changepointGA against standard binary-encoded GA packages using simulated ARMA(p, q) data. The results were stark: for a series of 1,000 observations, changepointGA achieved an approximately 3,500-fold speedup, reducing a nearly hour-long task to just one second. Accuracy remained high, with the package correctly identifying the true number of changepoints in over 94% of simulations when model orders were known.
Beyond simulations, the package was applied to diverse real-world datasets:
- Glioblastoma aCGH data: Successfully identifying DNA copy number variations where changepoints indicate genetic gains or deletions.
- Atlanta Airport Temperature Series: Detecting five significant climate shifts in a century-long dataset (1879–2013), outperforming previous studies using simpler models.
Conclusion
By shifting from binary to integer encoding, changepointGA transforms changepoint detection from a high-dimensional struggle into a computationally efficient process. The ability to simultaneously estimate model orders and changepoint locations makes it a versatile tool for biological, climate, and financial time series analysis. Future work may involve expanding the library of built-in fitness functions and exploring GPU-based acceleration for even larger datasets.
Summary updated