USING GENETIC PROGRAMMING TECHNIQUES FOR INERTIA-FREE SYSTEM IDENTIFICATION TASKS

Full Text

Introduction. The identification of many stochastic objects is often limited to the identification of static systems. The most common pattern of the discrete-continuous variables, xi is the object’s output variables, n is number of sample units. Genetic programming reconstructs parametric strucprocess is shown in fig. 1 [1-4]. А is unknown object’s operator, uuur uuur x(t) is the vector of ture, describing the process based on the available sample. Since genetic programming is based on the optimiza- tion method (genetic algorithm), the process of finding the object’s output variables; uuur u(t) is the vector of the the most optimal structure is iterative. The criterions of object’s input variables; m(t) is the vector of the object’s uuur controlled but unmeasurable input variables; l(t) is the vector of the object’s and controlled but unmeasurable input variables; x(t) is the random action, optimality are mean error, mean-square error, mean rela- tive error and other characteristics that reflect structure accurateness. The process of genetic programming is divided into the following stages [14; 15]: wi(t) : i = 1, 2, ..., k are the variables in the process; (t) is 1) the first genetic trees are created randomly; 2) receiving descendants from trees, obtaining descenthe continuous time; H m , Hu , H x , H z , H q , H w dants, can be performed using the following actions: measuring devices; mt , ut , и(t) , x(t) , w(t) ; hm (t) , xt , wt hu (t) , are measures of m(t) , hx (t) , hw(t) are the - Replication; - Reproduction; - Mutation; random effects. Levels of a priori information. Let’s consider the different levels of priori information [5-7]: 1. Systems with parametric uncertainty. Parametric level of priori information assumes that there is a para- metric structure with unknown parameters. Iterative prob- abilistic procedures are used for parameter estimation. The problem of identification in the narrow sense is solved in this case; 2. Systems with nonparametric uncertainty. A nonpara- metric level of priori information does not have the para- metric structure, but it has some qualitative information about the process. For example it has uniqueness, or am- biguity of its characteristics, linearity for dynamic proc- esses or the nature of its nonlinearity. Nonparametric statistics methods are used to solve problems of identifi- cation at this level (it is identification in a “broad” sense); 3. Systems with parametric and nonparametric uncer- tainty. System that does not correspond to any types described above is very important from the practical point of view. For example, for individual characteristics of a multiply connected process, on the basis of physico- chemical laws, energy laws, the law of mass conservation, balance relationships, parametric patterns can be derived. However, for others it is not possible. Thus, we are in a situation where the task of identifi- cation is formulated in terms of both parametric and non- parametric priori information. Then the models are an interconnected system of parametric and non-parametric ratios. Genetic programming. Genetic programming algo- rithm is based on the same optimization algorithm [8-13]. r r This algorithm is applied when parametric structure of process is not known, but there is a sample where (ui , xi ) ,i = 1...n , ui is the vector of the object’s input 3) the trees that least satisfy the conditions of the optimum are destroyed; 4) verification of compliance with the conditions. It is noticeable that the genetic programming process is very similar to genetic algorithms. Let’s describe central concepts of the genetic pro- gramming: The concept of “genetic tree” is used as a description of the structure of an object in genetic programming. A genetic tree is a connected graph, where nodes represent actions, and finite elements (leaves) are variables (fig. 2). We suggest the genetic tree of the following expres- sion, as an example: f(x1, x2) = x1*(x2 - 7) * (2/sin(x1)). The restoration of the structure from the represented tree begins with the leaves. It is also important to describe the terms replication, reproduction and mutation. Replication is the action towards the tree that results in an exact copy of the parent tree (fig. 3). Reproduction is receiving descendants by replacing the branches of parent trees with each other (fig. 4). Mutation is receiving a descendant by changing the parent tree branch to randomly created one (fig. 5). The last step in genetic programming is verification of result. If the verification confirms to the conditions, then the researcher uses the resulting tree for object modeling. If the conditions have not been achieved, the genetic programming process is repeated, beginning with step 2. Computational experiment. Object modeling proc- ess is demonstrated in different conditions. In the process of computational experiments, the relationship between the dimension of the process under investigation and the speed of finding the parametric structure using genetic programming will be demonstrated. For genetic programming, the following settings have been introduced: - the number of trees = 10; - prediction: average forecast error < 0.1; - the maximum recovery time = 240 second. The maximum time given for recovery is necessary to accelerate the experiment. The structure will be restored for the following func- tions: f(x) = x1 + x2 + 5, x1 Î(0,3) , x2 Î(0,3) . We will this algorithm more depends on “successfulness” of the original tree choice. It is worth mentioning that during experiments the genetic algorithm was completely restored, resulting in: f(x) = (x2 + 5) + x1, where the restored structure does not copy the original, for example: f(x) = x1 + x1 + cos(x1) + + x2 + 3 + sin(x2), however, when x1 Î(0,3) , x2 Î(0,3) , structure is close to the original. The structure will be restored for the following funccheck the dependence of the time of finding the structure from the value of the training sample for this example. The dependence of the time of finding the structure from the value of the training sample example is not observed (fig. 6). This can be explained by the fact that tions: f(x) = sin(x1)*x1 + 6*cos(x2), x1 Î(0,3) , x2 Î(0,3) . We will check the dependence of the time of finding the structure on the value of the training sample for this example. Fig. 1. Common pattern of the discrete-continuous process Рис. 1. Общая схема исследуемого процесса Fig. 2. Genetic tree example Рис. 2. Пример генетического дерева Generation t + Generation t + 1 / + x1 4 x2 - x1 6 Fig. 3. Replication’s example 767 Рис. 3. Пример репликации Generation t Fig. 4. Reproduction’s example 768 Рис. 4. Пример размножения Fig. 5. Mutation’s example Рис. 5. Пример мутации The dependence of the time of finding the structure on the value of the training sample example is not observed either (fig. 7). The genetic algorithm restore the function: f(x) = = cos(x2) + cos(x2) + cos(x2) + cos(x2) + сos(x2) + + cos(x2) + (x1*sin(x1)), but the restored structure does not copy the original, for example: f(x) = ((3*x1)/4) + Then more units (nodes and leaves) the genetic tree requires to restore the parametric form of the original function, the more “complicated” this function is. The value of input parameters also has dependence on the “complexity”. In the next experiment, we restore the function with 5 ( ) input variables: f(x) = x1 + x2 + x3 + x4 + x5, x1 Î(0,3) , + cos(x2)*6, but, when x1 Î(0,3) , x2 Î(0,3) , this struc- x2 Î 0,3 . Let’s check the dependence of the modeling ture is close to the original. When comparing fig. 6 and fig. 7, we can see that the average time to restore the structure is greater in example 2. It’s the reason to suppose that the time of modeling depends on the “complexity” of the modeling object. time on the value of the training sample. As can be seen from fig. 8, there is no dependence of the time of finding the structure on the size of the training sample. The genetic algorithm restores the function: f(x) = = (x5 + x3) + (x1 + (x4 + x2)), but the restored structure does not copy the original, for example: (x3 + (5 + + (((x5/4) * x3) + ((x1/(5 - x2)) * (x4 - sin(x1 + x5)))))), but, when x1 Î(0,3) , x2 Î(0,3) , this structure is close to the original. The modeling time depends on the “complexity” of the modeling function shown in the fig. 9. You can see that in some cases the modeling process is fast. This happens in those cases when the algorithm choses the close to the desired function original tree. As we can see in fig. 9, there is strong correlation between the modeling’s time and the value of input variables. Fig. 6. Dependence of the time of finding the structure from the value of the training sample, example 1 Рис. 6. Зависимость времени нахождения структуры от величины обучающей выборки, пример 1 Fig. 7. Dependence of the time of finding the structure on the value of the training sample, example 2 Рис. 7. Зависимость времени нахождения структуры от величины обучающей выборки, пример 2 770 Fig. 8. Dependence of the time of finding the structure on the value of the training sample, example 3 Рис. 8. Зависимость времени нахождения структуры от величины обучающей выборки, пример 3 Fig. 9. Dependence of the time of finding the structure on the number of input variables, example 4 Рис. 9. Зависимость времени нахождения структуры от количества входных переменных, пример 4 Conclusion. The method of genetic programming for finding the parametric structure of the inertial-free object has been presented. It has been shown that the time of finding the parametric structure depends on train sample value. Also, the time of finding the parametric structure is dependent on the number of input variables.

About the authors

E. D. Mihov

Siberian Federal University

Email: edmihov@mail.ru
79, Svobodny Av., Krasnoyarsk, 660041, Russian Federation

References

Supplementary files