Hybrid Genetic Algorithm—Local Search Methods for Solving Groundwater Source Identification Inverse Problems
Publication: Journal of Water Resources Planning and Management
Volume 131, Issue 1
Abstract
Identifying contaminant sources in groundwater is important for developing effective remediation strategies and identifying responsible parties in a contamination incident. Groundwater source identification problems require solution of an inverse problem. Gradient-based local optimization approaches are among the most popular approaches for solving these inverse problems. While these methods are sometimes appropriate, they are not effective for problems that contain several local minima and for problems where the decision space is highly discontinuous or convoluted. For these types of problems, heuristic global search approaches such as genetic algorithms (GAs) are more effective. But methods such as GAs are inefficient for fine-tuning solutions once a near global minimum is found. For problems that contain several local minima, a hybrid approach starting with a global method and then fine-tuning with a local method may be more attractive, especially if the decision space is reasonably well behaved near the solution. In this paper, we compare several popular optimization methods for solving a simple groundwater source identification problem and show that hybrid GA-local search (GA-LS) approaches are generally more effective than using stand alone versions of each method. Some variants of the GA-LS approaches are then implemented on a parallel supercomputer to solve a more complex three-dimensional problem.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This work was partially supported by National Science Foundation (NSF) under Grant No. BES-0238623. The writers also wish to acknowledge North Carolina Supercomputing Center (now closed) and Oak Ridge National Laboratory for providing the supercomputer resources necessary for this work.
References
Anderson, M. P., and Woessner, W. W. (1992). Applied groundwater modeling, Academic, New York, 381.
Aral, M. M., and Guan, J. (1996). “Genetic algorithm in search of groundwater pollution sources.” NATO ASI Series, 2(9), 347–369.
Atmadja, J., and Bagtzoglou, A. C. (2001). “State of the art report on mathematical methods for groundwater pollution source identification.” Environmental Forensics, 2(3), 205–214.
Attaviriyanupap, P., Kita, H., Tanaka, E., and Hasegawa, J. (2002). “A hybrid EP and SQP for dynamic economic dispatch with nonsmooth fuel cost function.” IEEE Trans. Power Appar. Syst., 17(2), 411–416, May 2002.
Bear, J. (1988). Dynamics of fluids in porous media, Dover, N. Y., 764.
Belegundu, A. D., and Chandrupatla, T. R. (1999). Optimization concepts and applications in engineering, Prentice–Hall, Upper Saddle River, N. J., 432.
Borse, G. J.(1997). Numerical methods with MATLAB, PWS, Boston, 640.
Branke, J. (2001). “Reducing the sampling variance when searching robust solutions.” Proc. Genetic and Evolutionary Computation Conf. 2001, 235–242.
Chunduru, R. K., Sen, M. K., and Stoffa, P. L. (1997). “Hybrid optimization methods for geophysical inversion.” Geophysics, 62(4), 1196–1207.
Cieniawski, S. E., Eheart, J. W., and Ranjithan, S. (1995). “Using genetic algorithms to solve a multiobjective groundwater monitoring problem.” Water Resour. Res., 31(2), 399–409.
Crain, T., Bishop, R. H., Fowler, W., and Rock, K. (2000). “Interplanetary flyby mission optimization using a hybrid global-local search method.” J. Spacecr. Rockets, 37(4), 468–474.
Davis, L. (ed). (1991). Handbook of genetic algorithms, Van Nostrand Reinhold, New York.
Dorigo, and Gambardella (1977).
Erickson, M., Mayer, A., and Horn, J. (2002). “Multiobjective optimal design of groundwater remediation systems: Application of the niched Pareto genetic algorithm (NPGA).” Adv. Water Resour., 25(1), 51–65.
Espinoza, F. P., Minsker, B. S., and Goldberg, D. E. (2003). “Performance evaluation and population reduction for a self adaptive hybrid genetic algorithm (SAHGA).” Genetic and Evolutionary Computation-Gecco 2003, Pt I, Proceedings, Lecture Notes In Computer Science, 2723, 922–933.
Ewing, R., Lin, T., and Falk, R. (1987). “Inverse and ill-posed problems in reservoir simulation, in Inverse and ill-posed problems.” H. W. Engl and C. W. Groetsch, eds., Academic, San Diego.
Floudas, C. A., and Pardalos, P. M. (2001). Encyclopedia of optimization, Kluwer Academic, Dordrecht and London, Vol. 1.6.
Freeze, R. A., and Cherry, J. A. (1979). “Groundwater.” Prentice-Hall, Englewood Cliffs, N. J., 604.
Giacobbo, F., Marseguerra, M., and Zio, E. (2002). “Solving the inverse problem of parameter estimation by genetic algorithms: The case of a groundwater contaminant transport model.” Ann. Nucl. Energy, 29(8), 967–981.
Goldberg, D. E., and Sastry, K. (2001). “A practical schema theorem for genetic algorithm design and tuning.” IlliGAL Rep. No. 2001022, Univ. of Illinois at Urbana–Champaign, Ill.
Goldberg, D. (1989). “Genetic algorithms in search, optimization, and machine learning.” Addison-Wesley, Reading, Mass, 412.
Gropp, W., Lusk, W., and Skjellum, A. (1999). Using MPI: Portable parallel programming with the message-passing interface, 2nd Ed., The MIT Press, Cambridge, Mass.
Hartzell, S., and Liu, P. C. (1995). “Determination of earthquake source parameters using a hybrid global search algorithm.” Bull. Seismol. Soc. Am., 85(2), 516–524.
Heidari, M., and Ranjithan, S. (1998). “A hybrid optimization approach to the estimation of distributed parameters in two-dimensional confined aquifers.” J. Am. Water Resour. Assoc., 34(4), 909–920.
Hill, M. C., Cooley, R. L., and Pollock, D. W. (1998). “A controlled experiment in ground water flow model calibration.” Ground Water, 36(3), 520–535.
Hoeksema, R. J., and Kitanidis, P. K. (1984). “Application Of The geostatistical approach to the inverse problem in two-dimensional groundwater modeling.” Water Resour. Res., 20(7), 1003–1020.
Holland, J. H. (1975). Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor, Mich.
Houck, C. R., Joines, J. A., and Kay, M. G. (1995). “A genetic algorithm function optimization: A MATLAB implementation.” Tech. Rep. NCSU-IE TR 95-09, North Carolina State Univ., Raleigh, N.C.
Huang, C. L., and Mayer, A. S. (1997). “Pump-and-treat optimization using well locations and pumping rates as decision variables.” Water Resour. Res., 33(5), 1001–1012.
James, A. I., Graham, W. D., Hatfield, K., Rao, P. S. C., and Annable, M. D. (1997). “Optimal estimation of residual non-aqueos phase liquid saturations using partitioning tracer concentration data.” Water Resour. Res., 33(12), 2621–2636.
Karpouzos, D. K., Delay, F., Katsifarakis, K. L., and de Marsily, G. (2001). “A multipopulation genetic algorithm to solve the inverse problem in hydrogeology.” Water Resour. Res., 37(9), 2291–2302.
Kennedy, J., and Eberhart, R. C. (1995). “Particle swarm optimization.” Proc. IEEE International Conference on Neural Networks, IEEE Service Center, Piscataway, N. J., 1942–1948.
Lee, K. Y., Cho, S., Roh, M. L. (2002). “An efficient global-local hybrid optimization method using design sensitivity analysis.” Int. J. Veh. Des., 28(4), 300–317.
Liu, C., and Ball, W. P. (1999). “Application of inverse methods to contaminant source identification from aquitard diffusion profiles at Dover AFB Delaware.” Water Resour. Res., 35(7), 1975–1985.
Liu, G. R., Han, X., and Lam, K. Y. (2002). “A combined genetic algorithm and nonlinear least squares method for material characterization using elastic waves.” Comput. Methods Appl. Mech. Eng., 191(17–18), 1909–1921.
Lobo, F. G., and Goldberg, D. E. (1997). “Decision making in a hybrid genetic algorithm.” IEEE Evolutionary Computation Conference (GECCO), 121–125.
Lobo, F. G., and Goldberg, D. E. (2001). “The parameter-less genetic algorithm in practice.” IlliGAL Report No. 2001022, Univ. of Illinois at Urbana–Champaign, Ill.
Loughlin, D. H., and Ranjithan, S. (1999). “Chance-constrained genetic algorithms.” Genetic and Evolutionary Computation Conference (GECCO), 369–376.
Mahar, P. S., and Datta, B. (1997). “Optimal monitoring network and ground-water-pollution source identification.” J. Water Resour. Plan. Manage., 123(4), 199–207.
Mahar, P. S., and Datta, B. (2000). “Identification of pollution sources in transient groundwater systems.” Water Resour. Manage., 14(3), 209–227.
Mahar, P. S., and Datta, B. (2001). “Optimal identification of groundwater pollution sources and parameter estimation.” J. Water Resour. Plan. Manage., 27(1), 20–29.
Mahinthakumar, G., Gwo, J. P., Moline, G. R., and Webb, O. F. (1999). “Subsurface biological activity zone detection using genetic search algorithms.” J. Environ. Eng., 125(12), 1103–1112.
Mahinthakumar, G. (1999). “PGREM3D: Massively parallel codes for groundwater flow and transport.” ⟨http://www4.ncsu.edu/∼gmkumar/pgrem3d.pdf⟩.
Mahinthakumar, G., and Saied, F. (2002). “A hybrid MPI-OpenMP implementation of an implicit finite-element code on parallel architectures.” Int. J. High Performance Comput. Appl., 16(4), 371–393.
MATLAB. (2000). MATLAB, The language of technical computing, Users Guide, version 6, release 12, The Mathworks Inc., Natick, MA.
Mckinney, D. C., and Lin, M. D. (1994). “Genetic algorithm solution of groundwater management models.” Water Resour. Res., 30(6), 1897–1906.
McLaughlin, D., and Townley, L. R. (1996). “A reassessment of the groundwater inverse problem.” Water Resour. Res., 32(5), 1131–1161.
Michalewicz, Z. (1996). Genetic programs, 3rd Ed., Springer, New York, 387.
Miller, B. L. (1997). “Noise, sampling, and genetic algorithms.” PhD thesis, Univ. of Illinois at Urbana–Champaign, Ill.
Morrison, R. D. (2000). “Application of forensic techniques for age dating and source identification in environmental litigation.” Environ. Forensics, 1, 131–153.
National Research Council. (1990). Groundwater models—Scientific and regulatory applications. National Academic Press, Washington, D.C.
Neupauer, R. M., Borchers, B., and Wilson, J. L. (2000). “Comparison of inverse methods for reconstructing the release history of a groundwater contaminant source.” Water Resour. Res., 36(9), 2469–2475.
Okamoto, M., Nonaka, T., Ochiai, S., and Tominaga, D. (1998). “Nonlinear numerical optimization with use of a hybrid genetic algorithm incorporating the modified Powell method.” Appl. Math. Comput., 91(1), 63–72.
Pal, K. F. (1995). “Genetic algorithm with local optimization.” Biol. Cybern., 73(4), 335–341.
Pan, L. H., and Wu, L. S. (1998). “A hybrid global optimization method for inverse estimation of hydraulic parameters: Annealing-simplex method.” Water Resour. Res., 34(9), 2261–2269.
Poeter, E. P., and Hill, M. C. (1997). “Inverse models: A necessary next step in groundwater modeling.” Ground Water, 35(2), 250–260.
Porsani, M. J., Stoffa, P. L., Sen, M. K., and Chunduru, R. K. (2000). “Fitness functions, genetic algorithms, and hybrid optimization in seismic waveform inversion.” J. Seism. Explor., 9(2), 143–164.
Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. (1996). Numerical recipes in FORTRAN, 2nd Ed., Cambridge University Press, New York.
Reed, P., Minsker, B., and Valocchi, A. J. (2000a). “Cost-effective long-term groundwater monitoring design using a genetic algorithm and global mass interpolation.” Water Resour. Res., 36(12), 3757–3761.
Reed, P., Minsker, B., and Goldberg, D. E. (2000b). “Designing a competent simple genetic algorithm for search and optimization.” Water Resour. Res., 36(12), 3757–3761.
Saied, F., and Mahinthakumar, G. (1998). “Efficient parallel multigrid based solvers for large scale groundwater flow simulations.” Comput. Math. Appl., 35(7), 45–54.
Sayeed, M., and Mahinthakumar, G. (2002). “A multilevel parallelization scheme based on MPI communicators for solving groundwater inverse problems.” High Performance Computing 2002, Society for Computer Simulation International, 137–144.
Sayeed, M. (2004). “A parallel optimization framework for inverse problems.” PhD dissertation, North Carolina State Univ., Raleigh, N.C.
Sciortino, A., Harmon, T. C., and Yeh, W.-G. (2000). “Inverse modeling for locating dense nonaqueous pools in groundwater under steady flow conditions.” Water Resour. Res., 36(7), 1723–1735.
Skaggs, T. H., and Kabala, Z. J. (1994). “Recovering the release history of a groundwater contaminant.” Water Resour. Res., 3, 71–79.
Smalley, J. B., Minsker, B. S., and Goldberg, D. E. (2000). “Risk-based in situ bioremediation design using a noisy genetic algorithm.” Water Resour. Res., 36(10), 3043–3052.
Sun, N.-Z., and Yeh, W. W. G. (1990a). “Coupled inverse problems in groundwater modeling. I. Sensitivity analysis and parameter-identification.” Water Resour. Res., 26(10), 2507–2525.
Sun, N.-Z., and Yeh, W. W. G. (1990b). “Coupled inverse problems in groundwater modeling. II. Identifiability And experimental design.” Water Resour. Res., 26(10), 2527–2540.
Sun, N.-Z. (1994). “Inverse problems in groundwater modeling.” Theory and applications of transport in porous media J. Bear, ed., Kluwer Academic, Dordrecht, 337.
Thompson, A., et al. (1989).
Wang, M., and Zheng, C. (1997). “Optimal remediation policy selection under general conditions.” Ground Water, 35(5), 757–764.
Woodbury, A., Sudicky, E., Ulrych, T. J., and Ludwig, R. (1998). “Three-dimensional plume source reconstruction using minimum relative entropy inversion.” J. Contam. Hydrol., 32(1–2), 131–158.
Woodbury, A. D., and Ulrych, T. J. (1996). “Minimum relative entropy inversion: Theory and application to recovering the release history of a groundwater contaminant.” Water Resour. Res., 32(9), 2671–2681.
Yeh, W. W.-G. (1986). “Review of parameter identification procedures in groundwater hydrology: The inverse problem.” Water Resour. Res., 22(2), 95–108.
Yoon, J. H., and Shoemaker, C. A. (2001). “An improved real-coded GA for groundwater bioremediation.” J. Comput. Civ. Eng., 15(3), 224–231.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 131 • Issue 1 • January 2005
Pages: 45 - 57
Copyright
© 2005 ASCE.
History
Received: Nov 6, 2002
Accepted: May 5, 2004
Published online: Jan 1, 2005
Published in print: Jan 2005
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.