Many nonstationary time series exhibit changes in the trend and seasonality structure, that may be modeled by splitting the time axis into different regimes. We propose multi-regime models where, inside each regime, the trend is linear and seasonality is explained by a Periodic Autoregressive model. In addition, for achieving parsimony, we allow season grouping, i.e. seasons may consists of one, two, or more consecutive observations. Since the set of possible solutions is very large, the choice of number of regimes, change times and order and structure of the Autoregressive models is obtained by means of a Genetic Algorithm, and the evaluation of each possible solution is left to an identification criterion such as AIC, BIC or MDL. The comparison and performance of the proposed methods are illustrated by a real data analysis. The results suggest that the proposed procedure is useful for analyzing complex phenomena with structural breaks, changes in trend and unstable seasonality.