Genetic Algorithm for Variable Knot Spline Fitting via Least Squares

摘要

In this report, we describe a method for fitting variable knot spline models to noisy univariate data which uses a genetic algorithm to optimize over the number and location of the knots. For a fixed number of knots, the location of the knots is chosen to minimize the sum of squares error; the appropriate number of knots is determined by the adjusted GCV criterion of Luo and Wahba (1997). The objective is to find the model which minimizes RSS/df, where the degrees of freedom are inflated to reflect the adaptive nature of the knot search (i.e., selection of basis functions). We justify theoretically that our algorithm will converge to the variable knot model which optimizes the model fitting criterion, given that this model is contained in the search space. A modified bootstrap technique is used to obtain pointwise standard errors for models obtained by the GA method. Experimental results comparing the performance of the proposed algorithm to those obtained using the non-linear optimization technique of Schwetlick and Schuetze (1995), the genetic algorithm proposed by Manela et. al. (1993), and the method of Luo and Wahba (1997) are presented. We also discuss the extension our technique to related problems.