Testing of software products (SP) is one of the most important stages of SP lifecycles, when it can be found not only the errors, connected to computational algorithm coding process, but also those ones input at the stages of mathematical model (MM) development. The idea of the proposed software testing algorithm, directed on detection of fatal errors in MM, is based on a global search of several variables functions discontinuity. Moreover, a heuristic characteristic function, that takes into account the peculiarities of the problem, is used, which can significantly increase the efficiency of the error situations search algorithm.
Modern mathematical models (MM) allow to obtain extensive and highly
accurate information about the processes occurring in nature and in technology by
calculation. Computational experiments carried out with the mathematical model
implemented as a computer program provides research shortening and its cost
reduction. MM used in the calculations are finally realized in the form of software
products (SP). Errors (including computational by nature errors) committed during the
development of a mathematical model are directly inherited into correspondent SP [
If we consider a class of programs that are based on numerical analysis and
computational mathematics, i.e., programs that implement some of mathematical
models, the most difficult identifiable errors will be fatal computational errors such as
"division by zero", resulting in exponent overflow and program execution failure [
At the same time, order loss or overflow errors can be efficiently traced when
viewed from the perspective of solving the problem of search of second order
discontinuity points and use of algorithms for global optimization (GO) of several
variables functions [
Formally, the computer module can be interpreted as a vector function that acts from set of current module inputs to set of calculated values
The module domain will be described as the Cartesian product of the domains of each parameter where – the domain of the n-th module parameter. By analogy, the set of admissible values of the function F(X ) is presented by where - the range of the m-th component of the vector function.
We will define the area of error situations as the set wherein when there is a fatal computing error in a software module F(X ) . In this case, if fi (X ) then the function has a second-order discontinuity.
The measure of error situations is zero for second-order
discontinuity points, which creates serious difficulties in finding errors of this type.
These errors are classified as "rare" in [
The idea of the method of the second order discontinuity points searching [
k 1, m
Indeed, the function value at the second-order discontinuity point is designated as . It could be associated for the computer with a large maximum positive or negative number, for example, the global extreme of the function in the broadest sense of the word. Applying the methods of global optimization, we are sure to discover function second-order discontinuity points.
The most effective method among the well-known one-parameter methods of
multiextremal optimization is information-statistical method of R.G. Strongin [
To simplify the situation, we will consider the scalar function f (X ) max fi (X ) .
For optimizable function we assume it to be a Lipschitz function with constant K, that means the condition f (x) f (x) K x x is fulfilled.
In [
2( yi yi1) , where m - the Lipschitz constant estimate, which is calculated during the function extremum search:
1 m rM
M 0, M 0,
M max i yi yi1 , (xi xi1) where r – parameter.
To solve the problem of finding of several variables functions discontinuity irreparable points, we will choose the characteristic function similar to (2).
From the point of solving the problem of finding of second-order discontinuity points the Strongin method didn’t manage to be effective because this method successful for Lipschitz functions, that are continuous by definition, loses its properties being applied to a class of discontinuous functions.
Let us analyze the characteristic function (2), which was deduced during information-statistical approach.
For simplicity, we assume r 1 . Formula (2) is presented in the following form: R(i) mxi
2( yi yi1), xi (xi xi1), yi ( yi yi1).
Using the first two terms of the Taylor expansion of optimizable function at the (2)
Providing that m max
i we have yi xi miax f (xi ) miax fi ,
fi 2 R(i) (max fi fi )
Analysis of the formula (3) shows that the characteristic function "inclined" to post test points in the vicinity of local minima of a function to be optimized, while tending towards the global minimum, or in uncertainty intervals, the dimensions of which are large compared to other intervals of the function.
We modify the characteristic function (3), based on the following assumptions.
Firstly, the algorithm of second-order discontinuity points search, in principle, should not rely on local extrema of the function, it should react to a rapid increase or decrease in the function growth rate.
Secondly, the function itself does not contain any information about its future behavior. The first-order derivative shows the function growth rate, while the secondorder derivative - acceleration of this growth. It is obvious that the second-order derivative is more informative in this sense, therefore, we will choose ( fi )2 as the first component of the characteristic function. Squaring the second-order derivative is due to the fact that we don’t need information about the sign of the function curvature at the point of discontinuity.
As a measure of uncertainty of partial interval, by analogy with the Strongin method, we will choose the length of the interval, improved by certain adjustment parameter r. On this basis we can choose the function R(i) ( f (xi ))2 (xi )r as the characteristic function of the irreparable discontinuity points search method. In a multidimensional case, for example for a function of 2 variables, the second-order differential could be used instead of the second-order derivative, and a characteristic function could be represented in the form:
Let us choose a unit square П [
To calculate the second differential of the function by its values, calculated at the nodal points of the grid, it is easy to build a complete second-order polynomial , then
Summarizing the results, it is possible to construct an algorithm of finitedifferences method (FDM) of second-order discontinuity points search:
Step 1. Regular full interpolation grid {Xij } i, j 0,1, 2 is formed for the current square Values of the function at the vertices of the square and in the center were known while building on the previous step of the algorithm. We should only calculate the function values at the midpoints of the edges of a square. As a result, we have Z (k) zi(,kj) , i, j 0,1, 2 . A source square bounded by regular interpolation grid (3) (4) {Xij} i, j 1, 2,3, is divided into four new squares nodes for Qk Qk1 Qk2 Qk3 Qk4 .
Step 2. Using the matrix
In the centers X kcl of the squares an interpolation polynomial
is constructed
function is calculated R(k l) (d 2 P2(,k2) ( X kcl ))2 (hk )2r . Here hk - the length of the squares side Qk l .
Step 3. Calculated values of the characteristic function are entered in the list R in descending order of the function values, i.e. ( i R(i) R(i 1) .
Step 4. As a "decisive" item from the list R we choose one with a maximum characteristic, i.e., R (1). Thus, it is deleted from the list R.
Step 5. If algorithm stop condition is not fulfilled ( (miax zi Msup) (miin hi ) ), then go to step 1.
Stop condition of the algorithm described in step 5 contributes a conclusion of its work, if the test function is outside the domain of the function, which is tantamount to the appearance of the error.
Test functions shown in Table 1 were considered to evaluate the effectiveness of
the FDM algorithm. The first two test functions were constructed of known functions
by their modifications. For example, the known modification of Rastrigin test
function [
The second test function was constructed using division of one by Griewank function, which gave rise to a large number of second-order discontinuity points. The third Kovartsev test function was formed by the addition of a single second-order discontinuity point to a linear combination of error functions generating smooth function with more than 20 local extrema.
In literature the efficiency of search algorithms is typically evaluated using the
operating characteristics machine [
Since the second-order discontinuity points can be found in any of the global
optimization algorithms the efficiency of the proposed algorithm FDM was compared
with the efficiency of direct method GO, for example, the modified bisection method
(BM) [
Operating characteristics of FDM and BM methods built for test functions 1-3 (table 1) are presented in figure 1. Operating characteristics of the FDM algorithm are denoted by solid line in the figure 1, operating characteristics of the BM algorithm by dashed line.
Modified Rastrigin function: z1 1 (11 20(x1 a 0.55)) / 4; x1, x2 [0; 1] . z2 1 (11 20(x2 b 0.55)) / 4; A set of local extrema. "Slit-shaped" second-order discontinuity.
Modified Griewank function: f (x1, x2 ) 1/((x12 x22 ) / 400 x1, x2 [0; 1]. cos(x1 ) cos(x2 / 2) 1) A set of second-order discontinuity points. 1/(1 e ) 20 local extrema. One second-order discontinuity point. GKLS test functions.
Continuous twice differentiable function. 10 local extrema. One global extremum. No points of discontinuity is observed. x1, x2 [0; 1].
As we can see from the graphs, the efficiency of the proposed FDM algorithm is much greater than the efficiency of the bisection method for functions #1 and #3. It happens as bisection method is focused on the optimization of continuous functions conceptually, which forces it to make more detailed "view" of the function areas with Lipschitz constant evaluation increase. This situation arises whenever the function is calculated at points of its discontinuity. FDM method conversely is looking for areas of rapid growth of the test function.
Function 2 (Griewank) has so many points of irreparable discontinuity that their detection is easily implemented with the same efficiency using FDM and BM methods. According to Fig. 1, the BM method has a slight advantage over the FDM method. The significant advantage of FDM over BM was recorded for all other functions.
Figure 2 shows the operating characteristics of these methods, built for continuous GKLS test function.
It is clear from the figure, the efficiency of FDM algorithm for continuous functions is much lower than efficiency of BM algorithm. The finite difference method is forced to examine more carefully the space of the optimized variables in case of continuous functions when there are no second-order discontinuity points (test software module has no errors). In this connection, there is an idea to use the FDM and BM algorithms for computational modules testing in a combined form and stop the calculation when either the FDM finds an error or BM stops.
The algorithm of global search of second-order discontinuity points, designed to detect fatal errors in mathematical models of computational algorithms, is considered in this paper. The basic idea of the algorithm is the addition of a heuristic original characteristic function to a classical algorithm of global optimization, where the first is based on the analysis of the characteristic Strongin function and considers the peculiarities of the problem. It has significantly increased the efficiency of the error search algorithm. This result allows us to hope on the organization of the error search for the functions of large dimensions. In the future, we plan to develop FDM algorithm using modern supercomputer technologys.
This work was supported by the state Ministry of Education and Science of the Russian Federation as part of the activities of the Program of competitiveness improving of SSAU among the world's leading research and education centers for 2013-2020.