# Data-Driven Identification of Crane Dynamics Using Regularized Genetic Programming
## 2 Materials and Methods  
Genetic programming has been applied successfully in several difficult problems such as symbolic regression, pattern recognition, and automatic design. A survey and taxonomy of existing GP-based methods can be found in [36]. Symbolic regression seeks to identify a mathematical expression over a space of searchable functions that best fits a data set of input-output pairs \(T=\{(\mathbf{x}_{i},y_{i})\}_{i=1}^{N}\) with inputs \(\mathbf{x}_{i}\in\mathbb{R}^{n}\) and an output variable \(y\in\mathbb{R}\). In the G3P-SR algorithm proposed in this paper, an individual \(\phi^{P_{i}}\) in a population \(P\) is composed of \(q\) transformations (represented by trees), which, in the context of identification, we shall call model terms, of the input \(\mathbf{x}\) so that \(\phi^{P_{i}}(\mathbf{x})\ :\mathbb{R}^{n}\rightarrow\mathbb{R}^{q}\)  
\[\phi^{P_{i}}=\begin{bmatrix}\phi_{1}^{P_{i}}&\phi_{2}^{P_{i}}&\ldots&\phi_{q} ^{P_{i}}\end{bmatrix}\]  
where \(\phi_{j}^{P_{i}}\) are the semantics of tree \(j\) in individual \(P_{i}\), and the output \(\hat{y}^{P_{i}}\) is a linear combination of the columns of \(\phi^{P_{i}}\) as follows:  
\[\hat{y}=\sum_{j=1}^{q}\!\theta_{j}\phi_{j} \tag{1}\]  
In order to avoid redundant model terms, duplicate model terms are eliminated from the individual, and the search space is constrained by implementing a set of production rules that prevent the model terms in \(\phi^{P_{i}}\) from being composed of linear combinations of other model terms in the same individual. This can be achieved by allowing the addition or subtraction operator to only be used inside a nonlinear function, e.g., the model term \(\phi_{j}^{P_{i}}=(x_{1}+x_{2})\) is not allowed, as it could be composed as a linear combination of two model terms \(\phi_{j+1}^{P_{i}}=x_{1}\) and \(\phi_{j+2}^{P_{i}}=x_{2}\), but the model term \(\phi_{j}^{P_{i}}=\tanh(x_{1}+x_{2})\) is allowed. The coefficients \(\theta_{j}\) of the model terms are found using a deterministic numerical optimization algorithm that usually results in increased accuracy as opposed to traditional genetic programming. Every individual in the population has a fixed number of model terms \(q\), which is a hyperparameter of the G3P-SR algorithm. The library of model terms is assumed to be redundant and only a subset of the model terms in the library is required to model the output \(y\). The model term selection and parameter optimization are performed simultaneously using sparse regression by adding an \(l_{0}\) pseudo-norm penalty. This reduces both the model complexity and the chances of overfitting while training on set \(T\). The sparse solution of (1) means that there are model terms in the individual \(\phi^{P_{i}}\) that have no effect on the model output \(\hat{y}\); however, these model terms, called introns, produce different offsprings when subject to genetic operators.  
Several approaches to the input-output modeling of nonlinear dynamical systems have been developed, including the nonlinear autoregressive moving average model with exogenous input (NARMAX) model structure that was introduced in the early 1980s to describe a wide class of models. The NARMAX model is a nonlinear function of lagged outputs, inputs, and error terms. When the model does not contain lagged error terms, the NARMAX model simplifies into a nonlinear autoregressive model with an exogenous input (NARX), and its structure is described in  
\[y_{k}=F\begin{bmatrix}y_{k-1},\ldots,y_{k-n_{q}},u_{k-1},\ldots,u_{k-n_{q}} \end{bmatrix}+e_{k} \tag{2}\]where the nonlinear function \(F[\cdot]\) is linear in the parameters, and the NARX model has the same form of (1), where the model terms \(\phi_{j}\) are possibly nonlinear functions of the lagged input and output variables. This makes the NARX model structure a natural candidate for the structure input-output dynamic model that will be used in this study for G3P-SR for the identification of dynamical systems.