Industrial Applications of Genetic Algorithms:Gauss-Legendre Integration Using Genetic Algorithms

Previous | Table of Contents | Next

There are at least two difficulties associated with the two-dimensional problem represented by Figure 12.3. First, there are four solutions to the problem. Often in nonlinear systems of equations, there are multiple roots. Second, and generally more difficult to overcome, the functions f and g are not necessarily related to one another. There is nothing special about the common points of zero-contour lines from either f’s or g’s perspective. Thus, in order to solve this problem completely, the entire zero-contour lines of each function involved must be mapped out. Furthermore, this is an example of only two functions of two independent variables. When the system of equations is expanded to N-dimensions, the goal is to determine the intersection of N unrelated zero-contour hyperplanes, each of dimension (N-1). Fortunately, there are alternatives to the exhaustive mapping of zero-contour lines. A few of the methods commonly used for determining the roots of single equations are extensible to higher dimensions.

There are a number of effective methods for solving one nonlinear equation. Of the most popular of these, bisection [3], regula falsi [1], and modified regula falsi [1] cannot be extended to systems of nonlinear equations because they depend on patterns of sign changes in the function being driven to zero. These patterns of sign changes do not uniquely identify the location of the zeros of several functions of several variables. The fixed point iteration method [4] is perhaps the simplest of root-finding algorithms and is easily extended to systems of equations. However, the fixed point method is highly susceptible to divergence in one dimension, and the method diverges too frequently in systems of equations to be practical. Both Muller’s method [3] and higher-order Newton methods extend in principle, but the computational effort associated with each of these methods increases rapidly with the number of equations being solved. Thus, these methods are rarely used. The principal method for solving a system of nonlinear equations is the traditional Newton method [2], a derivative-based search, because of its simplicity and efficiency. However, since Newton’s method is driven by derivative information, its performance and convergence characteristics are highly dependent on the initial guess of the solution with which it begins.

Of course, there are alternatives to extending the methods of root-finding in a single dimension. One popular alternative to the one-dimensional root-finding algorithms is to collapse the higher dimensionality of the problem into a single dimension by adding the sums of squares (or the absolute values) of the individual functions fi to get a master function F that is to be minimized where

This master function is positive definite and has a global minimum at each of the roots to the equation, Mi. However, the function is often fraught with local minima that tend to exist at points where the zero-contour lines of two functions approach but do not overlap one another. Such a point is labeled H in Figure 12.3. Unfortunately, another of the most difficult problems in numerical methods is the minimization of functions with numerous local minima.

There are a number of efficient algorithms for minimizing a function of many variables. However, the majority of these methods are not always effective in the minimization of the master function stemming from the problem of solving a system of nonlinear equations. Most are incapable of locating multiple roots, or they tend to converge to local minima. Optimization techniques such as variable metric methods [5], Brent’s method [6], and simplex search [7] prove inadequate in the general N-dimensional nonlinear equation problem.

Genetic algorithms consider multiple solutions to search problems simultaneously due to their population approach. Thus, they are effective in optimization problems with more than one optimum solution [8]. Further, since genetic algorithms do not use derivative information, they do not tend to get caught in local optima. The above two attributes of GAs allow them to overcome some of the shortcomings that prevent more traditional search techniques from effectively solving systems of nonlinear equations. However, genetic algorithms do not always converge to the true minimum in a search problem. Thus, they are not inviting stand-alone tools for minimizing the master function F(x) resulting from the problem of solving a system of nonlinear equations. The strength of genetic algorithms is that they rapidly converge to near-optimal solutions.

In this chapter, a hybrid approach to solving the systems of nonlinear equation resulting from the application of Gauss-Legendre quadrature is presented. The higher dimensionality of the problem is collapsed into a single dimension by adding the absolute values of the individual functions fi, thereby forming a master function F(x) that is to be minimized. A GA is used to rapidly converge to near-optimal solutions of the system of equations. These near-optimal points are then used as the initial guesses employed by a traditional Newton search.

Previous | Table of Contents | Next

Copyright © CRC Press LLC