Regression-based estimators are used for several surveys conducted by the Governments Division of the U.S. Census Bureau. One assumption of this style of estimator is that the auxiliary variable has a roughly linear relationship with the estimated variables. Estimation procedures for 2009 through 2013 of finance and employment surveys will take this into consideration, but the original stratifications of the samples still do not. In this paper we propose using concepts from genetic algorithms to stratify a frame with auxiliary data such that the data fit a linear relationship in each stratum. To do this, we make the assumption that we know the maximum number of partitions for a piecewise linear fit. In particular, we consider the case of dividing an interval into at most three piecewise linear segments, with concepts that generalize naturally to any arbitrary maximum. One goal is to determine a minimal spanning set of the interval to partition. We first explore two families of piecewise linear functions with different levels of perturbation. We then consider this method on simulated data that does not fit the model well. Finally, we consider the method on actual data. The method is applied with a fixed number of iterations.