×

Injecting problem-dependent knowledge to improve evolutionary optimization search ability. (English) Zbl 1329.90175

Summary: The flexibility introduced by evolutionary algorithms (EAs) has allowed the use of virtually arbitrary objective functions and constraints – even when evaluations require, as for real-world problems, running complex mathematical and/or procedural simulations of the systems under analysis. Even so, EAs are not a panacea. Traditionally, the solution search process has been totally oblivious of the specific problem being solved, and optimization processes have been applied regardless of the size, complexity, and domain of the problem. In this paper, we justify our claim that far-reaching benefits may be obtained from more directly influencing how searches are performed. We propose using data mining techniques as a step for dynamically generating knowledge that can be used to improve the efficiency of solution search processes. In this paper, we use Kohonen SOMs and show an application for a well-known benchmark problem in the water distribution system design literature. The result crystallizes the conceptual rules for the EA to apply at certain stages of the evolution, which reduces the search space and accelerates convergence.

MSC:

90C59 Approximation methods and heuristics in mathematical programming

Software:

SOM; Borg; EPANET; kohonen
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, Ma · Zbl 0721.68056
[2] Dorigo, M.; Maniezzo, V.; Colorni, A., The ant system: optimization by a colony of cooperating ants, IEEE Trans. Syst. Man Cybern. B, 26, 1, 1-13 (1996)
[4] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162
[5] Černý, V., Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, J. Optim. Theory Appl., 45, 41-51 (1985) · Zbl 0534.90091
[6] Duan, Q.; Gupta, V. K.; Sorooshian, S., A shuffled complex evolution approach for effective and efficient global optimization, J. Optim. Theory Appl., 76, 501-521 (1993) · Zbl 0792.90065
[7] Geem, Z. W., Optimal cost design of water distribution networks using harmony search, Eng. Optim., 38, 3, 259-280 (2006)
[9] Montalvo, I., Diseño óptimo de sistemas de distribución de agua mediante agent swarm optimization (2011), Universitad Politècnica de València: Universitad Politècnica de València Valencia, Spain, (Ph.D. thesis)
[10] Izquierdo, J.; Montalvo, I.; Pérez-García, R.; Matías, A., On the complexities of the design of water distribution networks, Math. Probl. Eng., 2012, 1-25 (2012) · Zbl 1264.90028
[11] Liong, S. Y.; Atiquzzama, M., Optimal design of water distribution network using shuffled complex evolution, J. Inst. Eng. Singap., 144, 1, 93-107 (2004)
[13] Jin, X.; Zhang, J.; Gao, J. L.; Wu, W. Y., Multi-objective optimization of water supply network rehabilitation with non-dominated sorting genetic algorithm-II, J. Zhejiang Univ. Sci. A, 9, 3, 391-400 (2008) · Zbl 1135.90449
[14] Montalvo, I.; Izquierdo, J.; Schwarze, S.; Pérez-García, R., Multi-objective particle swarm optimization applied to water distribution systems design: an approach with human interaction, Math. Comput. Modelling, 52, 1219-1227 (2010) · Zbl 1205.90190
[19] Montalvo, I.; Izquierdo, J.; Herrera, M.; Pérez-García, R., Water supply system computer-aided design by agent swarm optimization, Comput.-Aided Civ. Infrastruct. Eng., 29, 6, 433-448 (2014)
[20] Montalvo, I.; Izquierdo, J.; Pérez-García, R.; Herrera, M., Improved performace of PSO with self-adaptive parameters for computing the optimal design of water supply systems, Eng. Appl. Artif. Intell., 23, 5, 727-735 (2010)
[21] Clerc, M., Particle Swarm Optimization (2006), ISTE Ltd. · Zbl 1130.90059
[22] Lessmann, S.; Caserta, M.; Montalvo, I., Tuning metaheuristics: a data mining based approach for particle swarm optimization, Expert Syst. Appl. Int. J., 38, 10, 12826-12838 (2011)
[23] Vrugt, J. A.; Robinson, B. A., Improved evolutionary search from genetically adaptive multi-search method, Proc. Natl. Acad. Sci. USA, 104, 3, 708-711 (2007)
[24] Vrugt, J. A.; Robinson, B. A.; Hyman, J. M., Self-adaptive multimethod search for global optimization in real-parameter spaces, IEEE Trans. Evol. Comput., 13, 2, 243-259 (2009)
[25] Hadka, D.; Reed, P., Borg: an auto-adaptive many-objective evolutionary computing framework, Evol. Comput., 21, 2, 231-259 (2013)
[26] McClymont, K.; Keedwell, E. C.; Savic, D.; Randall-Smith, M., A general multi-objective hyper-heuristic for water distribution network design with discolouration risk, J. Hydroinf., 15, 3, 700-716 (2013)
[27] Kohonen, T., Self-Organizing Maps (2001), Springer-Verlag: Springer-Verlag Berlin, Heidelberg · Zbl 0957.68097
[28] Bertsimas, D.; Nohadani, O.; Teo, K. M., Robust optimization for unconstrained simulation-based problems, Oper. Res., 58, 1, 161-178 (2010) · Zbl 1226.90074
[29] Goulter, I. C.; Coals, A. V., Quantitative approaches to reliability assessment in pipe networks, J. Transp. Eng., 112, 3, 287-301 (1986)
[30] Goulter, I. C.; Bouchart, F., Reliability-constrained pipe network model, J. Hydraul. Eng. ASCE, 116, 2, 211-229 (1990)
[31] (Walski, T. M., Advanced Water Distribution Modeling and Management (2003), Haestad Press: Haestad Press Waterbury, Conn., USA)
[32] Martínez-Rodríguez, J. B.; Montalvo, I.; Izquierdo, J.; Pérez-García, R., Reliability and tolerance comparison in water supply networks, Water Resour. Manage., 25, 1437-1448 (2011)
[34] Matías, A. S., Diseño de redes de distribución de agua contemplando la fiabilidad, mediante algoritmos genéticos (2003), Universidad Politécnica de Valencia: Universidad Politécnica de Valencia Valencia, Spain, (Ph.D. thesis)
[35] Izquierdo, J.; Pérez, R.; Iglesias, P. L., Mathematical models and methods in the water industry, Math. Comput. Modelling, 39, 1353-1374 (2004) · Zbl 1093.91051
[36] Rossman, L. A., EPANET 2 User’s Manual (2000), Environmental Protection Agency: Environmental Protection Agency Cincinati, IN, USA
[37] Nguyen, V. V.; Hartmann, D.; König, M., A distributed agent-based approach for simulation-based optimization, Adv. Eng. Inf., 26, 814-832 (2012)
[38] Wolpert, D. H.; Macready, W. G., No free lunch theorems for optimization, IEEE Trans. Evol. Comput., 1, 1, 67-82 (1997)
[39] Alperovitz, E.; Shamir, U., Design of optimal water distribution systems, Water Resour. Res., 13, 6, 885-900 (1977)
[40] Kohonen, T., Essentials of the self-organizing map, Neural Netw., 37, 52-65 (2013)
[41] Wehrens, R.; Buydens, L. M.C., Self- and super-organizing maps in R: the kohonen package, J. Stat. Softw., 21, 5, 1-19 (2007)
[42] Cunha, M. C.; Sousa, J., Water distribution network design optimization: simulated annealing approach, J. Water Resour. Plann. Manage., 125, 4, 215-221 (1999)
[44] Zecchin, A. C.; Simpson, A. R.; Maier, H. R.; Nixon, J. B., Parametric study for an ant algorithm applied to water distribution system optimization, IEEE Trans. Evol. Comput., 9, 2, 175-191 (2005)
[45] Montalvo, I.; Izquierdo, J.; Pérez, R.; Tung, M. M., Particle swarm optimization applied to the design of water supply systems, Comput. Math. Appl., 56, 3, 769-776 (2008) · Zbl 1155.90486
[46] Montalvo, I.; Izquierdo, J.; Pérez, R.; Iglesias, P. L., A diversity-enriched variant of discrete PSO applied to the design of water distribution networks, Eng. Optim., 40, 7, 655-668 (2008)
[47] Wu, Z. Y.; Simpson, A. R., Competent genetic-evolutionary optimization of water distribution systems, J. Comput. Civil Eng., 15, 2, 89-101 (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.