Abstract
The design of large scale water distribution systems is a very difficult optimisation problem which invariably requires the use of time-expensive simulations within the fitness function. The need to accelerate optimisation for such problems has not so far been seriously tackled. However, this is a very important issue, since as MOEAs become more and more recognised as the ‘industry standard’ technique for water system design, the demands placed on such systems (larger and larger water networks) will quickly meet with problems of scaleup. Meanwhile, LEM (Learnable Evolution Model’) has appeared in the Machine Learning literature, and provides a general approach to integrating machine learning into evolutionary search. Published results using LEM show very great promise in terms of finding near-optimal solutions with significantly reduced numbers of evaluations. Here we introduce LEMMO (Learnable Evolution Model for Multi-Objective optimization), which is a multi-objective adaptation of LEM, and we apply it to certain problems commonly used as benchmarks in the water systems community. Compared with NSGA-II, we find that LEMMO both significantly improves performance, and significantly reduces the number of evaluations needed to reach a given target. We conclude that the general approach used in LEMMO is a promising direction for meeting the scale-up challenges in multiobjective water system design.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cheung, P.B., Reis, L.F.R., Formiga, K.T.M., Chaudhry, F.H., Ticona, W.G.C.: Multiobjective evolutionary algorithms applied to the rehabilitation of a water distribution system: a comparative study. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 662–676. Springer, Heidelberg (2003)
Cierniawski, S.E., Eheart, J.W., Ranjithan, S.: Using genetic algorithms to solve a multiobjective groundwater monitoring problem. Water Resources Research 31(2), 399–409 (1995)
Deb, K., Agrawal, S., Pratab, A., Meyarivan, T.: A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: Nsga-II. In: Proceedings of the Parallel Problem Solving from Nature VI Conference, pp. 849–858 (2000)
Dorn, J.L., Ranjithan, S.R.: Evolutionary multiobjective optimization in watershed quality management. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 692–706. Springer, Heidelberg (2003)
Edgington, E.: Randomization tests. Marcel Dekker, New York (1980)
Erickson, M., Mayer, A.S., Horn, J.: The niched pareto genetic algorithm 2 applied to the design of groundwater remediation systems. In: Zitzler, E., Deb, K., Thiele, L., Coello Coello, C.A., Corne, D.W. (eds.) EMO 2001. LNCS, vol. 1993, pp. 681–695. Springer, Heidelberg (2001)
Formiga, K.T.M., Chaudhry, F.H., Cheung, B., Reis, L.F.R.: Optimal design of water distribution system by multiobjective evolutionary methods. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 677–691. Springer, Heidelberg (2003)
Fujiwara, O., Tung, D.B.: A two-phase decomposition method for optimal design of looped water distribution networks. Water Resources Research 26(4), 539–549 (1990)
Halhal, D., Walters, G.A., Ouazar, D., Savic, D.: Multiobjective improvement of water distribution systems using a structured messy genetic algorithm approach. ACSE Journal of Water Resources Planning and Management 123(3), 137–146 (1997)
Handa, H., Horiuchi, T., Katai, O., Baba, M.: A novel hybrid framework of coevolutionary ga and machine learning. International Journal of Computational Intelligence and Applications (2002)
Handa, H., Horiuchi, T., Katai, O., Kaneko, T., Konishi, T., Baba, M.: Coevolutionary ga with schema extraction by machine learning techniques and its application to knapsack problems. In: Proceedings of the 2001 Congress on Evolutionary Computation CEC 2001, COEX, World Trade Center, 159 Samseong-dong, Gangnam-gu, Seoul, Korea, 27-30 May 2001, pp. 1213–1219. IEEE Press, Los Alamitos (2001)
Handa, H., Horiuchi, T., Katai, O., Kaneko, T., Konishi, T., Baba, M.: Fusion of coevolutionary ga and machine learning techniques through effective schema extraction. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), San Francisco, California, USA, 7-11 July 2001, p. 764. Morgan Kaufmann, San Francisco (2001)
Hansen, M.P., Jaszkiewicz, A.: Evaluating the quality of approximations to the non-dominated set. Technical Report TR-IMM-REP-1998-7, Technical University of Denmark (1998)
Knowles, J.D., Corne, D.W.: On metrics for comparing non-dominated sets. In: IEEE Service center (ed.) Congress on Evolutionary Computation (CEC’2002), Piscataway, New Jersey, May 2002, vol. 1, pp. 711–716 (2002)
Larranaga, P., Lozano, J.: Estimation of distribution algorithms: a new tool for evolutionary computation. Kluwer Academic Publishers, Dordrecht (2001)
Michalski, R.S.: Learnable evolution model: Evolutionary processes guided by machine learning. Machine learning 38(1–2), 9–40 (2000)
Michalski, R.S., Cervon, G., Kaufman, K.A.: Speeding up evolution through learning: Lem. In: Intelligent Information Systems 2000, pp. 243–256 (2000)
Michalski, R.S., Larson, J.B.: Selection of most representative training examples and incremental generation of vl1 hypothesis: The underlying methodology and the descriptions of programs esel and aq11. Technical Report Report No. 867, Urbana, Illinois: Department of Computer Science, University of Illinois (1978)
Michalski, R.S., Mozetic, I., Hong, J., Lavrac, N.N.: The multipurpose incremental learning system aq15 and its testing application to three medical domains. In: Proc. of the Fifth National Conference on Artificial Intelligence, pp. 1041–1045. Morgan Kaufmann, PA (1986)
Murphy, L.J., Simpson, A.R., Dandy, G.C.: Pipe network optimisation using an improved genetic algorithm. Technical report, Dept of civil and environment engineering, University of Adelaide, Australia (1993)
Pelikan, M., Goldberg, D.E., Cantu-Paz, E.: Boa: The bayesian optimization algorithm. In: Banzhaf, W., Daida, J., Eiben, A.E., Garzon, M.H., Honavar, V., Jakiela, M., Smith, R.E. (eds.) Proceedings of the genetic and evolutionary computation - GECCO 1999, pp. 525–532. Morgan Kaufmann, San Francisco (1999)
Quinlan, J.R.: C4.5: programs for machine learning. Morgan Kaufmann, San Francisco (1993)
Reed, P.M., Minsker, B.S., Goldberg, D.E.: A multiobjective approach to cost-effective long term groundwater monitoring using an elitist nondominated sorting genetic algorithm with historical data. Journal of Hydroinformatics 3(2), 71–89 (2001)
Rossman, L.A.: Epanet, users manual. Technical report, U.S. Envi. Protection Agency, Cincinnati, Ohio (1993)
Savic, D., Walters, G.: Genetic algorithms for least-cost design of water distribution networks. Journal of Water Resources Planning and Management 123(2), 67–77 (1997)
Savic, D., Walters, G.A., Schwab, M.: Multiobjective genetic algorithms for pump scheduling in water supply. In: Corne, D., Shapir, J. (eds.) AISB-WS 1997. LNCS, vol. 1305, pp. 227–236. Springer, Heidelberg (1997)
Sebag, M., Ravise, C., Schoenauer, M.: Controlling evolution by means of machine learning. In: Evolutionary Programming, pp. 57–66 (1996)
Sebag, M., Schoenauer, M.: Controlling crossover through inductive learning. In: Davidor, Y., Männer, R., Schwefel, H.-P. (eds.) PPSN 1994. LNCS, vol. 866, pp. 209–218. Springer, Heidelberg (1994)
Sebag, M., Schoenauer, M., Ravise, C.: Toward civilized evolution: Developing inhibitions. In: Bäck, T. (ed.) Proc. of the Seventh Int. Conf. on Genetic Algorithms, pp. 291–298. Morgan Kaufmann, San Francisco (1997)
Zitzler, E.: Evolutionary algorithms for multiobjective optimization: Methods and applications. Master’s thesis, Swiss federal Institute of technology (ETH), Zurich, Switzerland (November 1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jourdan, L., Corne, D., Savic, D., Walters, G. (2005). Preliminary Investigation of the ‘Learnable Evolution Model’ for Faster/Better Multiobjective Water Systems Design. In: Coello Coello, C.A., Hernández Aguirre, A., Zitzler, E. (eds) Evolutionary Multi-Criterion Optimization. EMO 2005. Lecture Notes in Computer Science, vol 3410. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31880-4_58
Download citation
DOI: https://doi.org/10.1007/978-3-540-31880-4_58
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24983-2
Online ISBN: 978-3-540-31880-4
eBook Packages: Computer ScienceComputer Science (R0)