Average crossover operator to produce offspring for AMOC problem

Description

In this crossover operator designed for AMOC problem, the new child is produced by taking the average of the changepoint locations from dad and mom and round to an integer. Note, every chromosome has at most one candidate changepoint location.

Usage

AMOCcrossover(mom, dad, p.range = NULL, minDist, lmax, N)

Arguments

Value

The child chromosome that produced from mom and dad for next generation.

Jump mutation operator to produce offspring for AMOC problem

Description

In a certain probability, the mutation genetic operator can be applied to generate a new child. In this AMOC mutation operator, the new child changepoint location can be down via a "jump" method. The child changepoint location will jump minDist time units either to the left or right to produce the changepoint location for the mutated child. The jump direction is randomly decided with 0.5 probability.

Usage

AMOCmutation(
  child,
  p.range = NULL,
  minDist,
  Pchangepoint = NULL,
  lmax = NULL,
  mmax = NULL,
  N = NULL
)

Arguments

Value

The resulting child chromosome representation.

Random population initialization for AMOC problem

Description

Randomly generate the individuals' chromosomes (changepoint configurations) to construct the first generation population for the at most one changepoint (AMOC) problem.

Usage

AMOCpopulation(popsize, p.range, N, minDist, Pchangepoint, mmax, lmax)

Arguments

Details

Given the possible candidate changepoint location set, each chromosome in the first generation population can be obtained by randomly sampling one location from the candidate set. The first element of every chromosome represent the number of changepoints and the last non-zero element always equal to the length of time series plus one (N+1).

Value

A matrix that contains each individual's chromosome.

The parents selection genetic algorithm operator for AMOC problem

Description

The genetic algorithm require to select a pair of chromosomes, representing dad and mom, for the crossover operator to produce offspring (individual for next generation). Here, the same linear ranking method in selection_linearrank is used to select a pair of chromosomes for dad and mom in the at most one changepoint (AMOC) problem. By default, the dad has better fit/smaller fitness function value/larger rank than mom.

Usage

AMOCselection(pop, popFit)

Arguments

Value

A list contains the chromosomes for dad and mom.

Example function: Calculating BIC for AR(1) model

Description

The objective function for changepoint search in Autoregressive moving average with model order selection via Bayesian Information Criterion (BIC).

Usage

ARIMA.BIC(chromosome, plen = 0, XMat, Xt)

Arguments

Value

The BIC value of the objective function.

Examples

Ts = 1000
betaT = c(0.5) # intercept
XMatT = matrix(1, nrow=Ts, ncol=1)
colnames(XMatT) = "intercept"
sigmaT = 1
phiT = c(0.5)
thetaT = NULL
DeltaT = c(2, -2)
Cp.prop = c(1/4, 3/4)
CpLocT = floor(Ts*Cp.prop)

myts = ts.sim(beta=betaT, XMat=XMatT, sigma=sigmaT, phi=phiT, theta=thetaT,
              Delta=DeltaT, CpLoc=CpLocT, seed=1234)

# candidate changepoint configuration
chromosome = c(2, 250, 750, 1001)
ARIMA.BIC(chromosome, XMat=XMatT, Xt=myts)

Calculating BIC for Multiple changepoint detection with model order selection

Description

The objective function for changepoint search in Autoregressive moving average with model order selection via Bayesian Information Criterion (BIC).

Usage

ARIMA.BIC.Order(chromosome, plen = 2, XMat, Xt)

Arguments

Value

The BIC value of the objective function.

Examples

N = 1000
XMatT = matrix(1, nrow=N, ncol=1)
Xt = ts.sim(beta=0.5, XMat=XMatT, sigma=1, phi=0.5, theta=0.8,
            Delta=c(2, -2), CpLoc=c(250, 750), seed=1234)

# one chromosome representation
chromosome = c(2, 1, 1, 250, 750, 1001)
ARIMA.BIC.Order(chromosome, plen=2, XMat=XMatT, Xt=Xt)

Genetic algorithm

Description

Perform the modified genetic algorithm for changepoint detection. This involves the minimization of an objective function using a genetic algorithm (GA). The algorithm can be run sequentially or with explicit parallelization.

Usage

GA(
  ObjFunc,
  N,
  GA_param = .default.GA_param,
  GA_operators = .default.operators,
  p.range = NULL,
  ...
)

Arguments

Value

Returns a list that has components:

Examples

N = 1000
XMatT = matrix(1, nrow=N, ncol=1)
Xt = ts.sim(beta=0.5, XMat=XMatT, sigma=1, phi=0.5, theta=NULL,
            Delta=c(2, -2), CpLoc=c(250, 750), seed=1234)
TsPlotCheck(X=1:N, Xat=seq(from=1, to=N, length=10), Y=Xt, tau=c(250, 750))

GA.res = GA(ObjFunc=ARIMA.BIC, N=N, XMat=XMatT, Xt=Xt)
GA.res$overbestfit
GA.res$overbestchrom

GA_param

Description

A list object contains the hyperparameters for GA running.

Arguments

Author(s)

Mo Li

Examples

# time series length
N = 1000

GA_param = list(
  popsize      = 40,
  Pcrossover   = 0.95,
  Pmutation    = 0.1,
  Pchangepoint = 0.06,
  minDist      = 3,
  mmax         = N/2 - 1,
  lmax         = 2 + N/2 - 1,
  maxgen       = 50000,
  maxconv      = 5000,
  option       = "cp",
  monitoring   = FALSE,
  parallel     = FALSE,
  nCore        = NULL,
  tol          = 1e-5,
  seed         = NULL
)

Island model based genetic algorithm

Description

Perform the modified island-based genetic algorithm (IslandGA) for multiple changepoint detection. Minimization of an objective function using genetic algorithm (GA). The algorithm can be run sequentially or in explicit parallelisation.

Usage

IslandGA(
  ObjFunc,
  N,
  IslandGA_param = .default.IslandGA_param,
  IslandGA_operators = .default.operators,
  p.range = NULL,
  ...
)

Arguments

Value

Returns a list that has the following components.

Examples

N = 1000
XMatT = matrix(1, nrow=N, ncol=1)
Xt = ts.sim(beta=0.5, XMat=XMatT, sigma=1, phi=0.5, theta=NULL,
            Delta=c(2, -2), CpLoc=c(250, 750), seed=1234)
TsPlotCheck(X=1:N, Xat=seq(from=1, to=N, length=10), Y=Xt, tau=c(250, 750))

IslandGA.res = IslandGA(ObjFunc=ARIMA.BIC, N=N, XMat=XMatT, Xt=Xt)
IslandGA.res$overbestfit
IslandGA.res$overbestchrom

IslandGA_param

Description

A list object contains the hyperparameters for island-based GA running.

Arguments

Author(s)

Mo Li

Examples

# time series length
N = 1000

IslandGA_param = list(
  subpopsize   = 40,
  Islandsize   = 5,
  Pcrossover   = 0.95,
  Pmutation    = 0.15,
  Pchangepoint = 0.1,
  minDist      = 2,
  mmax         = N/2 - 1,
  lmax         = 2 + N/2 - 1,
  maxMig       = 1000,
  maxgen       = 50,
  maxconv      = 100,
  option       = "cp",
  monitoring   = FALSE,
  parallel     = FALSE, ###
  nCore        = NULL,
  tol          = 1e-5,
  seed         = NULL
)

Plot the simulated time series

Description

This is a function to plot the simulated time series with segmentation visualization by provided changepoint locations.

Usage

TsPlotCheck(
  X = NULL,
  Xat = NULL,
  Y,
  tau = NULL,
  mu = NULL,
  XLAB = NULL,
  YLAB = NULL
)

Arguments

Value

No return value, called for side effects

Examples

Ts = 1000
betaT = c(0.5) # intercept
XMatT = matrix(1, nrow=Ts, ncol=1)
colnames(XMatT) = "intercept"
sigmaT = 1
DeltaT = c(2, -2)
Cp.prop = c(1/4, 3/4)
CpLocT = floor(Ts*Cp.prop)

myts = ts.sim(beta=betaT, XMat=XMatT, sigma=sigmaT, Delta=DeltaT, CpLoc=CpLocT, seed=1234)
TsPlotCheck(X=1:Ts, Xat=seq(from=1, to=Ts, length=10), Y=myts, tau=CpLocT)

Comparing multiple changepoint configurations by pairwise distance

Description

This function is to calculate the distance metric (Shi et al., 2022) between two changepoint configurations, C_{1}=\{\tau_{1}, \ldots, \tau_{m}\} and C_{2}=\{\eta_{1}, \ldots, \eta_{k}\}, where \tau's are the changepoint locations.

Usage

cptDist(tau1, tau2, N)

Arguments

Details

The pairwise distance was proposed by Shi et al. (2022),

d(C_{1}, C_{2})=|m-k|+ \min(A(C_{1}, C_{2})),

where m is the number of changepoints in configuration C_{1} and k is the number of changepoints in configuration C_{2}. The term \min(A(C_{1}, C_{2})) reflects the cost of matching changepoint locations between C_{1} and C_{2} and can be calculated using the linear assignment method. Details can be found in Shi et al. (2022). Note: if one configuration doesn't contain any changepoints (valued NULL), the distance is defined as |m-k|. The function can also be used to examine changepoint detection performance in simulation studies. Given the true changepoint configuration, C_{true}, used in generating the time series, the calculated distance between the estimated multiple changepoint configuration, C_{est}=\{\eta_{1}, \ldots, \eta_{k}\}, and C_{true} can be used to evaluate the performance of the detection algorithm.

Value

References

Shi, X., Gallagher, C., Lund, R., & Killick, R. (2022). A comparison of single and multiple changepoint techniques for time series data. Computational Statistics & Data Analysis, 170, 107433.

Examples

N = 100

# both tau1 and tau2 has detected changepoints
tau2 = c(25, 50, 75)
tau1 = c(20, 35, 70, 80, 90)
cptDist(tau1=tau1, tau2=tau2, N=N)

# either tau1 or tau2 has zero detected changepoints
cptDist(tau1=tau1, tau2=NULL, N=N)
cptDist(tau1=NULL, tau2=tau2, N=N)

# both tau1 and tau2 has zero detected changepoints
cptDist(tau1=NULL, tau2=NULL, N=N)

The default mutation operator in genetic algorithm

Description

In a certain probability, the mutation genetic operator can be applied to generate a new child. By default, the new child selection can be down by the similar individual selection method in population initialization, selectTau.

Usage

mutation(child, p.range = NULL, minDist, Pb, lmax, mmax, N)

Arguments

Details

A function can apply mutation to the produced child with the specified probability Pmutation in GA_param and IslandGA_param. If order selection is not requested (option = "cp" in GA_param and Island_GA), the default mutation operator function uses selectTau to select a completely new individual with a new chromosome as the mutated child. For details, see selectTau. If order selection is needed (option = "both" in GA_param and Island_GA), we first decide whether to keep the produced child's model order with a probability of 0.5. If the child's model order is retained, the selectTau function is used to select a completely new individual with a new chromosome as the mutated child. If a new model order is selected from the candidate model order set, there is a 0.5 probability to either select a completely new individual with new changepoint locations or retain the original child's changepoint locations for the mutated child. Note that the current model orders in the child's chromosome are excluded from the set to avoid redundant objective function evaluation. Finally, the function returns a vector containing the modified chromosomes for mutated child.

Value

The resulting child chromosome representation.

operators

Description

A list object contains the GA or IslandGA operators function names.

Arguments

References

Lu, Q., Lund, R., & Lee, T. C. (2010). An MDL approach to the climate segmentation problem. Ann. Appl. Stat. 4 (1) 299 - 319.

See Also

See Also as GA.

Examples

operators = list(population = "random_population",
                 selection  = "selection_linearrank",
                 crossover  = "uniformcrossover",
                 mutation   = "mutation")

Random population initialization

Description

Randomly generate the individuals' chromosomes (changepoint confirgurations) to construct the first generation population.

Usage

random_population(popsize, prange, N, minDist, Pb, mmax, lmax)

Arguments

Details

The default population initialization uses selectTau to select the chromosome for the first generation population. Each column from the produced population matrix represent an chromosome of an individual. The first element of every chromosome represent the number of changepoints and the last non-zero element always equal to the length of time series plus one (N+1).

Value

A matrix that contains each individual's chromosome.

Randomly select the chromosome

Description

Randomly select the changepoint configuration for population initialization. The selected changepoint configuration represents a changepoint chromosome. The first element of the chromosome represent the number of changepoints and the last non-zero element always equal to the length of time series + 1.

Usage

selectTau(N, prange, minDist, Pb, mmax, lmax)

Arguments

Value

A single changepoint configuration format as above.

The default parents selection genetic algorithm operator

Description

The genetic algorithm require to select a pair of chromosomes, representing dad and mom, for the crossover operator to produce offspring (individual for next generation). The parents chromosomes are randomly selectd from the initialized population by a linear ranking method according to each individual's fittness in the input argument popFit. By default, the dad has better fit/smaller fitness function value/larger rank than mom.

Usage

selection_linearrank(pop, popFit)

Arguments

Value

A list contains the chromosomes for dad and mom.

Time series simulation with changepoint effects

Description

This is a function to simulate time series with changepoint effects. See details below.

Usage

ts.sim(
  beta,
  XMat,
  sigma,
  phi = NULL,
  theta = NULL,
  Delta = NULL,
  CpLoc = NULL,
  seed = NULL
)

Arguments

Details

The simulated time series Z_{t}, t=1,\ldots,T_{s} is from a class of models,

Z_{t}=\mu_{t}+e_{t}.

• Time series observations are IID
  \mu_{t} is a constant and e_{t}'s are independent and identically distributed as N(0,\sigma).

• ARMA(p,q) model with constant mean
  \mu_{t} is a constant, and e_{t} follows an ARMA(p,q) process.

• ARMA(p,q) model with seasonality
  \mu_{t} is not a constant,

  \mu_{t} = ASin(\frac{2\pi t}{S})+BSin(\frac{2\pi t}{S}),

  and e_{t} follows an ARMA(p,q) process.

• ARMA(p,q) model with seasonality and trend
  \mu_{t} is not a constant,

  \mu_{t} = ASin(\frac{2\pi t}{S})+BSin(\frac{2\pi t}{S}) + \alpha t,

  and e_{t} follows an ARMA(p,q) process. The changepoint effects could be introduced through the \mu_{t} as

  \mu_{t} = \Delta_{1}I_{t>\tau_{1}} + \ldots + \Delta_{m}I_{t>\tau_{m}},

  where 1\leq\tau_{1}<\ldots<\tau_{m}\leq T_{s} are the changepoint locations and \Delta_{1},\ldots,\Delta_{m} are the changepoint parameter that need to be estimated.

Value

The simulated time series with attributes:

Examples

##### M1: Time series observations are IID
Ts = 1000
betaT = c(0.5) # intercept
XMatT = matrix(1, nrow=Ts, ncol=1)
colnames(XMatT) = "intercept"
sigmaT = 1
DeltaT = c(2, -2)
Cp.prop = c(1/4, 3/4)
CpLocT = floor(Ts*Cp.prop)

myts = ts.sim(beta=betaT, XMat=XMatT, sigma=sigmaT,
              Delta=DeltaT, CpLoc=CpLocT, seed=1234)
TsPlotCheck(Y=myts, tau=CpLocT)

##### M2: ARMA(2,1) model with constant mean
Ts = 1000
betaT = c(0.5) # intercept
XMatT = matrix(1, nrow=Ts, ncol=1)
colnames(XMatT) = "intercept"
sigmaT = 1
phiT = c(0.5, -0.5)
thetaT = c(0.8)
DeltaT = c(2, -2)
Cp.prop = c(1/4, 3/4)
CpLocT = floor(Ts*Cp.prop)

myts = ts.sim(beta=betaT, XMat=XMatT, sigma=sigmaT,
              phi=phiT, theta=thetaT, Delta=DeltaT, CpLoc=CpLocT, seed=1234)
TsPlotCheck(Y=myts, tau=CpLocT)

##### M3: ARMA(2,1) model with seasonality
Ts = 1000
betaT = c(0.5, -0.5, 0.3) # intercept, B, D
period = 30
XMatT = cbind(rep(1, Ts), cos(2*pi*(1:Ts)/period), sin(2*pi*(1:Ts)/period))
colnames(XMatT) = c("intercept", "Bvalue", "DValue")
sigmaT = 1
phiT = c(0.5, -0.5)
thetaT = c(0.8)
DeltaT = c(2, -2)
Cp.prop = c(1/4, 3/4)
CpLocT = floor(Ts*Cp.prop)

myts = ts.sim(beta=betaT, XMat=XMatT, sigma=sigmaT,
              phi=phiT, theta=thetaT, Delta=DeltaT, CpLoc=CpLocT, seed=1234)
TsPlotCheck(Y=myts, tau=CpLocT)


##### M4: ARMA(2,1) model with seasonality and trend
# scaled trend if large number of sample size
Ts = 1000
betaT = c(0.5, -0.5, 0.3, 0.01) # intercept, B, D, alpha
period = 30
XMatT = cbind(rep(1, Ts), cos(2*pi*(1:Ts)/period), sin(2*pi*(1:Ts)/period), 1:Ts)
colnames(XMatT) = c("intercept", "Bvalue", "DValue", "trend")
sigmaT = 1
phiT = c(0.5, -0.5)
thetaT = c(0.8)
DeltaT = c(2, -2)
Cp.prop = c(1/4, 3/4)
CpLocT = floor(Ts*Cp.prop)

myts = ts.sim(beta=betaT, XMat=XMatT, sigma=sigmaT,
              phi=phiT, theta=thetaT, Delta=DeltaT, CpLoc=CpLocT, seed=1234)
TsPlotCheck(Y=myts, tau=CpLocT)

Uniform crossover to produce offsprings

Description

In uniform crossover, typically, each bit is chosen from either parent with equal probability. Other mixing ratios are sometimes used, resulting in offspring which inherit more genetic information from one parent than the other. In a uniform crossover, we don’t divide the chromosome into segments, rather we treat each gene separately. In this, we essentially flip a coin for each chromosome to decide whether or not it will be included in the off-spring. If model order selection is requested, each child's model order has the equal probability (0.5) from dad and mom.

Usage

uniformcrossover(mom, dad, prange, minDist, lmax, N)

Arguments

Value

The child chromosome that produced from mom and dad for next generation.