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

Previous | Table of Contents | Next

RESULTS

The hybrid scheme described in the previous section has been used to solve the systems of nonlinear equations that arise in the development of N-point Gauss-Legendre quadrature formulae. The goal here is to solve the system of nonlinear equations, not to determine values of quadrature nodes and their associated weights that allow for accurate integral approximations. Thus, results will focus on the values of the quadrature nodes and the weights, not on the accuracy of an approximation to any given integral. The quadrature nodes and their associated weights for various Gauss-Legendre quadrature formulae resulting from the solution of the system of equations depicted in Equation (12.2) are shown in Table 12.1. Notice that the given values are accurate to the tenth decimal place [2].

Table 12.1 The quadrature nodes and the associated weights for four-, five-, six-, seven-, and eight-point Gauss-Legendre quadrature formulae are provided below.
| Quadrature nodes, xi | weights, wI
2 | -0.5773502692 0.5773502692 | 1.0000000000 1.0000000000
3 | ±0.7745966692 0.0000000000 | 0.5555555556 0.8888888888
4 | ±0.8611363116 ±0.3399810436 | 0.3478548451 0.6521451549
5 | ±0.9061798459 ±0.5384693101 0.0000000000 | 0.2369268851 0.4786286705 0.5688888888
6 | ±0.9324695142 ±0.6612093865 ±0.2386191861 | 0.1713244924 0.3607615730 0.4679139346
7 | ±0.9491079123 ±0.7415311856 ±0.4058451514 0.0000000000 | 0.1294849662 0.2797053915 0.3818300505 0.4179591837
8 | ±0.9602898565 ±0.7966664774 ±0.5255324099 ±0.1834346425 | 0.1012285363 0.2223810345 0.3137066459 0.3626837834

As a point of comparison for gauging the effectiveness of the hybrid scheme, a Newton method was provided with randomly generated initial guesses for the systems of equations. The results of this exercise are shown in Figures 12.4 and 12.5. Figure 12.4 shows the number of successes in 100,000 randomly generated guesses. Here, a “success” means convergence to the correct solution to the system of equations. Figure 12.5 shows the number of random initial guesses required before the initial success. Thus, when determining the coefficients for the seven-point formula (which involves solving a system of fourteen nonlinear equations), the Newton method converged only 4 times for the 100,000 initial guesses provided. The expected success rate of randomly guessing is 4/100,000 = 4* 10-5.

Figure 12.4 As can be seen above, the number of “successes” in 100,000 randomly generated initial guesses decreases exponentially with N for the Newton method.

Figure 12.5 The number of guesses required before the initial successful convergence by the Newton method increases exponentially with N for the Newton method.

So that statistics suitable for comparison could be computed, the hybrid scheme was implemented in the following way. In the course of the GA’s operation, the best solution existing at the end of each generation was sent as an initial guess to a Newton method. The Newton method used this initial guess in an attempt to solve the system of equations. The results are shown in Figure 12.6. When considering this figure, recall that a fitness function evaluation consisted only of computing the numerical value of 2N individual equations and taking the maximum of these values. Thus, a fitness function evaluation is actually quite inexpensive computationally. The number of fitness function evaluations shown in Figure 12.6 are the number of evaluations required such that the Newton method would converge to the solution of the system of nonlinear equations on this first guess. Notice in this figure that the number of function evaluations required by the GA increases polynomially with N as opposed to the exponential behavior depicted by the Newton method acting independently.

Figure 12.6 The success rate of the hybrid scheme shows that the number of function evaluations increases polynomially as opposed to the exponential increase required by the Newton method.

To summarize the results presented in this section: when the hybrid scheme is used, a GA can effectively locate an initial guess that allows the Newton method to converge to an accurate solution much more quickly than when random initial guesses are supplied. It is also important to note that there is some computational overhead associated with the operation of the GA. The standard genetic operators require the generation of random numbers and the combining and copying of bit strings. Additionally, the fitness function values must be computed. However, this computational overhead is negligible when compared to the computation involved with computing the inverse of the Jacobian matrix.

Previous | Table of Contents | Next

Copyright © CRC Press LLC