Genetic Programming Approach for Predicting Surface Subsidence Induced by Mining

INTRODUCTION

The study of surface subsidence resulting from underground mining holds significance in view of beneficial effects on national economy and people's living conditions. As is known, a large quantity of minerals need to be exploited for modernization construction. Mining leads to surface subsidence, some underground engineering and production facilities are destroyed accordingly, which blocks the development of production and retards people's living standard. To solve this contradiction, subsidence due to mining must be deeply researched and reasonable control technique must be devised to reduce its harmful effects to minimum level.

Surface subsidence induced by mining is a complex problem, which is related with several factors. Genetic programming has a good ability to deal with complex and nonlinear problems, and therefore genetic programming approach is proposed to predict mining induced surface subsidence in this article. Genetic programming (Li and Kou, 2001; yun, 2000; Yun and Wang, 1997) is a novel global, random searched, and optimized technique, which is based on the principle of biology and evolution. It is imitative of chromosomes to express problems, and it is based on the Darwinian principle of "survival of the fittest" through the operation of selection, crossover and mutation, therefore the random generated initial population can approach the optimized solution step by step. Genetic programming is an interdisciplinary subject, which is formed by the intercrossing of biology and engineering, at present, it is becoming the third research point followed by the system of Expert and ANN. The details of the genetic programming and the implementation for the prediction of surface subsidence are the subject of this article.

BASIC TECHNIQUE OF GENETIC PROGRAMMING

Description of Individual

Genetic programming is a symbolic regression technique developed by Koza (schwefel, 1995; Koza, 1994, 1992). It is an evolutionary computational technique (like genetic algorithm, evolutionary strategy and evolutionary programming, etc.). Each generation is composed of several individuals, and it becomes a population, as usual, binary trees are used to represent its structures, that is to say, a population member in GP is a hierarchically structured tree consisting of functions and terminals. The functions and terminals are selected from a set of functions (operators) and a set of terminals. For example, the set of operators F can contain such functions expressed by

where f_i can be: (1) plus, minus, times, divide; (2) sin, cos, log, exp; (3) and, or, not; (4) ceil, floor; (5) min, max; (6) eq (equal), gt (greater than), le (less than or equal).

The set of terminals T contain the arguments for the functions. For example, T={t₁, t₂, ……t_m}, where t₁ can be the variables of x, y, and z or the constants a, b or π. Now, a potential solution may be depicted as a rooted, labeled tree with ordered branches, using operations from the function set and arguments from the terminal set.

Generation of Initial Population

The initial population of GP is generated by choosing random functions and terminals from F sets and T sets. There are three different methods available in GP to create the initial population.

(1) "Fullinit". This is the Full method. In the standard procedure, the new tree receives non-terminal (internal) nodes until the initial tree depth (D_max, the initial maximum depth/size of the new tree) is reached. The last depth level is limited to terminal nodes. As a result, trees initialized using this method will be perfectly balanced with all the branches of the same length.

If size is used instead of depth, internal nodes are chosen until the size of the new tree is close to the specified size (D_max), and only then terminals are chosen. Unlike the standard procedure, the size variation may not be able to create trees with the exact size specified, but only close (never exceeding).

(2) "Growinit". This is the Grow method. In the standard procedure, each new node is randomly chosen between the terminals and non-terminals, except the nodes at the initial tree depth level, which must be the terminals. Trees created using this method may be unbalanced, with some branches much longer than others, and their depth may range from 1 to the value of the D_max parameter. If the size variation is used, nodes will be chosen randomly. Before reaching the size specified in D_max, care is taken on the choice of the internal nodes based on their arity, to make sure that theD_max will not be exceeded by the respective arguments (which now have to be terminals).

(3) "Rampedinit". This is the Ramped Half-and-Half method. In the standard procedure, an equal number of individuals are initialized for each depth between 2 and the initial tree depth value. For each depth level considered, half of the individuals are initialized using the Full method, and the other half using the Grow method. The population of trees resulting from this initialization method is very diverse with balanced and unbalanced trees of several different depths. In the size variation, an equal number of individuals are initialized with sizes ranging from 2 to D_max. As in the standard procedure, for each size, half of the trees are initialized using the Full method, and the other half using the Grow method.

Fitness of the Individual

The fitness of individuals is major measure to evaluate the individual; fitness means the optimized results to approximate the true solution. Different problems have different fitness. In this article, the sum of the absolute difference is between expected output value and the value returned by the individual on all fitness cases. The best individuals are the ones that return values less different than the expected values, that are the ones with lower fitness.

Selection for Reproduction

Similar to genetic algorithms, genetic operators need individuals to produce their children. These parents are selected according to one of the following sampling methods.

(1) "Roulette". This method acts as if roulette with random pointers is spun, and each individual

owns a portion of the roulette that corresponds to its expected number of children.

(2) "Sus". This method also relies on the roulette, but the pointers are equally spaced.

(3) "Tournament". This method chooses each parent by randomly drawing a number of individuals from the population and selecting only the best of them.

(4) "Lexictour". This method implements lexicographic parsimony pressure. Like in "tournament", a random number of individuals are chosen from the population and the best of them is chosen. The main difference is, if two individuals are equally fit, the shortest one (the tree with less nodes) is chosen as the best. This technique has shown to effectively control bloat in different types of problems.

Crossover

Random nodes are chosen from both parent trees, and the respective branches are swapped, and this creates two offsprings. There is no bias towards choosing internal or terminal nodes as the crossing sites.

Mutation

In tree mutation, a random node is chosen from the parent tree and substituted by a new random tree created with the available terminals and functions. This novel random tree is created using the grow initialization method, and obeys the size/depth restrictions imposed on the trees created for the initial generation. Successive generations are created until very fit individuals are obtained. To assist the visualization of the genetic programming procedure a logic flow diagram is presented in Fig. 1.

Figure  1.  Logic flow diagram of genetic programming procedure.

DownLoad: Full-Size Img PowerPoint

Stop Condition

The genetic programming will run until the stop condition indicated by the user is reached, there are three stop rules available. (1) The maximum generation G. When the generation reaches G, genetic programming will stop immediately. (2) The tolerate error. When the error meets the need, genetic programming will stop. (3) The variation of fitness. The variation tendency of fitness is observed, when fitness varies in small limits, genetic programming can be stopped.

GENETIC PROGRAMMING MODEL FOR PREDICTING MINING-SURFACE-SUBSIDENCE IN MATLAB

MATLAB is a widely used programming environment available for a large number of computer platforms. Its language is simple and easy to learn, yet fast and powerful in mathematical calculus. Furthermore, its extensive and straightforward data visualization tools make it a very appealing programming environment (Silva and Costa, 2004; Yin and Ding, 2002). Therefore genetic programming in MATLAB environment can be versatile and easily operational.

It is proved that main factors affecting surface subsidence are seam thickness, seam depth, seam dip angle, and the stiffness coefficient. First, all the factors mentioned above are selected as input variables, and the maximum surface subsidence is the outputs. Therefore, the target is to find the relational expression between main factors and the maximum surface subsidence, which is used to predict the surface subsidence due to mining. The genetic programming model is trained using learning cases obtained from measured data (Bi and Wang, 2002; Cao and Jiang, 2002; Wang and Ding, 2001). Training samples are shown in Table 1 and the parameters of GP are provided in Table 2, after training of genetic programming, the best trees obtained are shown in Fig. 2, and the comparison of calculated result of GP with the observed values is shown in Table 3.

Table  1.  Learning and training samples

 | Show Table

DownLoad: CSV

Table  2.  Parameters of genetic programming

 | Show Table

DownLoad: CSV

Figure  2.  Best tree found by genetic programming.

DownLoad: Full-Size Img PowerPoint

Table  3.  Comparison of calculated result of GP with observed values

 | Show Table

DownLoad: CSV

Seen from Table 3, the relative error results can meet the need of engineering; and the genetic programming model is of good precision of prediction.

CONCLUSIONS

First, basic knowledge of genetic programming is introduced, and then samples chosen from themain factors that influence surface subsidence are trained to establish genetic programming model for surface subsidence prediction. Predictions are made by the testing of data. Results of comparison show that the proposed approach is valid and applicable in predicting mining induced surface subsidence. When genetic programming is used to solve the problem, input variables should be chosen according to the characteristic of problem, if the main affected factors are selected, then the output results will be much closer to measured data. Genetic programming is also used to predict other queries of geo-engineering, provided targets are given.

Genetic programming is proposed for the first time to predict surface subsidence and it is a recently developing technique. The outputs of genetic programming depend on training samples to some extent; therefore, much experience is necessary to choose the main factors of models. Furthermore, genetic programming is also time-consuming, especially when inputs are multivariable. Therefore, some effective measures must be taken to solve its related shortcomings.