A HYBRID APPROACH

A Newton-Raphson algorithm lies at the heart of the hybrid approach presented here. This method suffers from its sensitivity to the initial guess it is supplied, but it is still the most popular algorithm for solving systems of nonlinear equations. Once the neighborhood of a root has been identified, Newton’s method provides an efficient means of converging to the root, if it exists, or of spectacularly failing to converge, indicating that there is no root in the neighborhood. Thus, the focus of the hybrid scheme is to effectively locate regions in which roots are likely to exist; a problem that proves to be readily solved using a GA.

Newton’s method is driven by derivative information and is derived from Taylor’s series analysis. In the solution of systems of equations, the method employs a linear model to solve the equations. A linear model of f(x) is of the form

where J is a matrix. Usually a₀ = f(x₀), and Equation (12.6) is then the first two terms of the Taylor’s series of f(x) if the model J uses the first derivatives. We want to have f(x) = 0, and so set the model in Equation (12.6) equal to zero and solve for x to obtain

An iteration is formed from Equation (12.7) above in an obvious way. Note that an N by N system of linear equations must be solved at each iteration. Thus, such derivative-based methods can be time consuming.

Newton’s method for systems of nonlinear equations uses the linear model based on the “tangent planes.” Since f(x) = 0 is N equations

y = f_i(x) defines a surface. At x₀, the tangent plane to the surface is

The matrix J is the Jacobian matrix

The linearized model employed by Newton’s method is quite effective if the initial guess of x₀ is reasonably close to a root. However, the development of the coefficients required in Gauss-Legendre quadrature is such a case; after all, if the values of the coefficients are approximately known, then the value of the integral can more than likely be accurately approxmiated. Thus, in the hybrid approach proposed, a GA is employed to locate regions in which roots to the system of equations are likely to exist.

GAs are search algorithms based on the mechanics of natural genetics. Despite the numerous variations to Holland’s basic GA [9], the majority of evolutionary algorithms proceed as follows:

1.  generate a population of strings coded to represent potential solutions to the search problem at hand;

2.  evaluate the effectiveness or quality of the solutions represented by the strings in the current population (compute a fitness function value for each string);

3.  make copies of strings in proportion to the effectiveness of the solutions they represent (in proportion to their fitness function values) and combine portions of these highly fit strings according to genetic operators to produce a new population of strings (a new generation);

4.  repeat steps 2 and 3 until a suitable solution to the search problem has been found.

The different varieties of evolutionary algorithms occur due to the genetic operators, the definition of the coding scheme, and the fitness function. In this chapter, the genetic operators are from the simple genetic algorithm due to Goldberg [8]. Computer code for implementing the algorithm can be found in the reference by Goldberg [8].

The coding scheme for this problem is accomplished using a relatively standard coding scheme. A concatenated, binary, linearly mapped coding scheme is employed [8]. In this scheme, the parameters of the search problem are represented as bit strings. For example, in the two-point Gauss-Legendre problem, there exist four equations in four unknowns. The equations are presented collectively as Equation (12.3) and the unknowns are w₁, w₂, x₁, and x₂. The four parameters are each coded as binary strings according to the formula

where p is the parameter being coded, p_min is the minimum value of the parameter (in the case of x_i, the minimum value is -1, while for w_i, it is 0), p_max is the maximum value of the parameter (in the case of both x_i and w_i, the maximum values are 1), and b is the decimal value associated with a binary string of length l. Each of the parameters in the search problem is represented in this fashion, and then concatenated to form a single string that represents a complete solution to the problem. To achieve the accuracy required in this application, bit strings of length forty were employed.

The fitness function is based on identifying the zero-contours of the individual functions f_i. The fitness function to be minimized by the genetic algorithm is

where g is the fitness function to be minimized, max[abs(f_i)] is the maximum value of the absolute value of individual equations in the system f(x) = 0, and N is the number of equations in the system. This function g is a positive definite function that contains global minimums at each of the roots to the system of equations. Recall that a GA will not guarantee convergence to the roots of the equation, but it will rapidly locate regions in which the fitness function is minimal. For the problem of solving systems of nonlinear equations, these regions will likely contain roots to the equations or points at which the zero-contour lines approach but do not cross (false roots).

The hybrid approach is built around two concepts. First, once regions in which roots are likely to exist have been determined, a Newton method can quickly distinguish between “real roots” and “false roots.” If there are roots in the region, a Newton method will rapidly converge to the roots. Second, a GA can be used to rapidly determine regions in which roots are likely to exist. It does so by minimizing a fitness function that indicates promising regions in the search space. The solutions determined by the GA are used as initial guesses supplied to a Newton-Raphson method. As will be seen in the next section, the result is a hybrid scheme that is far more efficient than a Newton method alone.