Recent Advances in Global Optimization for Combinatorial Discrete Problems

Adel R. Awad¹, Samia O. Chiban²

¹Department of Environmental Engineering, Tishreen University, Lattakia, Syria.
²Higher Institute of Environmental Research, Tishreen University, Lattakia, Syria.

DOI: 10.4236/am.2015.611162                

Abstract

The optimization of discrete problems is largely encountered in engineering and information domains. Solving these problems with continuous-variables approach then convert the continuous variables to discrete ones does not guarantee the optimal global solution. Evolutionary Algorithms (EAs) have been applied successfully in combinatorial discrete optimization. Here, the mathematical basics of real-coding Genetic Algorithm are presented in addition to three other Evolutionary Algorithms: Particle Swarm Optimization (PSO), Ant Colony Algorithms (ACOA) and Harmony Search (HS). The EAs are presented in as unifying notations as possible in order to facilitate understanding and comparison. Our combinatorial discrete problem example is the famous benchmark case of New-York Water Supply System WSS network. The mathematical construction in addition to the obtained results of Real-coding GA applied to this case study (authors), are compared with those of the three other algorithms available in literature. The real representation of GA, with its two operators: mutation and crossover, functions significantly faster than binary and other coding and illustrates its potential as a substitute to the traditional optimization methods for water systems design and planning. The real (actual) representation is very effective and provides two near-optimal feasible solutions to the New York tunnels problem. We found that the four EAs are capable to afford hydraulically-feasible solutions with reasonable cost but our real-coding GA takes more evaluations to reach the optimal or near-optimal solutions compared to other EAs namely the HS. HS approach discovers efficiently the research space because of the random generation of solutions in every iteration, and the ability of choosing neighbor values of solution elements “changing the diameter of the pipe to the next greater or smaller commercial diameter” beside keeping good current solutions. Our proposed promising point to improve the performance of GA is by introducing completely new individuals in every generation in GA using a new “immigration” operator beside “mutation” and “crossover”.

Keywords

Evolutionary Algorithms, Meta-Heuristic Algorithms, Real-Coding Genetic Algorithms, Water Supply System, New-York Tunnels, Optimal Design

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Neumaier, A. (2004) Complete Search in Continuous Global Optimization and Constraint Satisfaction. In: Iserles, A., Ed., A Chapter for Acta Numerica, Cambridge University Press, Cambridge. http://dx.doi.org/10.1017/s0962492904000194
[2]	Arora, J.S., Huang, M.W. and Hsieh, C.C. (1994) Methods for Optimization Variables of Nonlinear Problems with Discrete: A Review. Structural Optimization, 8, 69-85. http://dx.doi.org/10.1007/BF01743302
[3]	Olsson, R.J., Kapelan, Z. and Savic, D.A. (2009) Probabilistic Building Block Identification for the Optimal Design and Rehabilitation of Water Distribution Systems. Journal of Hydroinformatics, 11, 89-105. http://dx.doi.org/10.2166/hydro.2009.047
[4]	Awad, A. and Poser, I. (2005) Genetic Algorithm Optimization of Water Supply Networks. Water Intelligence Online Journal (WIO), International Water Association (IWA) Publishing, 8, 1-25.
[5]	Montalvo, I., Izquierdo, J., Perez-Garcia, R. and Tung, M.M. (2008) Particle Swarm Optimization Applied to the Design of Water Supply Systems. Computers and Mathematics with Applications, 56, 769-776. http://dx.doi.org/10.1016/j.camwa.2008.02.006
[6]	Montalvo, I., Izquierdo, J., Perez-Garcia, R. and Herrera, M. (2010) Improved Performance of PSO with Self-Adaptive Parameters for Computing the Optimal Design of Water Supply Systems. Engineering Applications of Artificial Intelligence, 23, 727-735. http://dx.doi.org/10.1016/j.engappai.2010.01.015
[7]	Coelho, B. and Andrade-Campos, A. (2014) Efficiency Achievement in Water Supply Systems—A Review. Renewable and Sustainable Energy Reviews, 30, 59-84. http://dx.doi.org/10.1016/j.rser.2013.09.010
[8]	Swamee, P.K. and Sharma, A.K. (2008) Design of Water Supply Pipe Networks. John Wiley & Sons, Inc., New Jersey. http://dx.doi.org/10.1002/9780470225059
[9]	Dorigo, M., Maniezzo, V. and Colorni, A. (1996) The Ant System: Optimization by a Colony of Cooperating Ants. IEEE Transactions on Systems, Man, and Cybernetics Society, 26, 29-42. http://dx.doi.org/10.1109/3477.484436
[10]	Schaake, J.C. and Lai, D. (1969) Linear Programming and Dynamic Programming Applications to Water Distribution Network Design. Department of Civil Engineering, Cambridge.
[11]	Fujiwara, O. and Khang, D.B. (1990) A Two-Phase Decomposition Method for Optimal Design of Looped Water Distribution Networks. Water Resources Research, 26, 539-549. http://dx.doi.org/10.1029/WR026i004p00539
[12]	Geem, Z.W. (2006) Optimal Cost Design of Water Distribution Networks Using Harmony Search. Engineering Optimization, 38, 259-280. http://dx.doi.org/10.1080/03052150500467430
[13]	Maier, H.R., Simpson, A.R., Zecchin, A.C., Foong, W.K., Phang, K.Y., Seah, H.Y. and Tan, C.L. (2003) Ant Colony Optimization for Design of Water Distribution Systems. Journal of Water Resources Planning and Management, 129, 200-209. http://dx.doi.org/10.1061/(ASCE)0733-9496(2003)129:3(200)
[14]	Bragalli, C., D’Ambrosio, C., Lee, J., Lodi, A. and Toth, P. (2012) On the Optimal Design of Water Distribution Networks: A Practical MINLP Approach. Optimization and Engineering, 13, 219-246. http://dx.doi.org/10.1007/s11081-011-9141-7
[15]	Bonabeau, E., Dorigo, M. and Theraulaz, G. (1999) From Natural to Artificial Swarm Intelligence. Oxford University Press, New York.
[16]	Kennedy, J., Eberhart, R.C. and Shi, Y. (2001) Swarm Intelligence. Morgan Kaufmann Publishers, Burlington.
[17]	Coelho, B. and Andrade-Campos, A. (2012) Using Different Strategies for Improving Efficiency in Water Supply Systems. Proceedings of 1st ECCOMAS Young Investigators Conference, Aveiro, 24-27 April 2012.
[18]	Broad, D.R., Dandy, G.C. and Maier, H.R. (2015) A Systematic Approach to Determining Metamodel Scope for Risk Based Optimization and Its Application to Water Distribution System Design. Environmental Modelling & Software Volume, 69, 382-395. http://dx.doi.org/10.1016/j.envsoft.2014.11.015
[19]	May, R.J., Dandy, G.C., Maier, H.R. and Nixon, J.B. (2008) Application of Partial Mutual Information Variable Selection to ANN Forecasting of Water Quality in Water Distribution Systems. Environmental Modelling & Software, 23, 1289-1299. http://dx.doi.org/10.1016/j.envsoft.2008.03.008
[20]	Bowden, G.J., Nixon, J.B., Dandy, G.C., Maier, H.R. and Holmes, M. (2006) Forecasting Chlorine Residuals in a Water Distribution System Using a General Regression Neural Network. Mathematical and Computer Modelling, 44, 469-484. http://dx.doi.org/10.1016/j.mcm.2006.01.006
[21]	Gibbs, M.S., Morgan, N., Maier, H.R., Dandy, G.C., Nixon, J.B. and Holmes, M. (2006) Investigation into the Relationship between Chlorine Decay and Water Distribution Parameters Using Data Driven Methods. Mathematical and Computer Modelling, 44, 485-498. http://dx.doi.org/10.1016/j.mcm.2006.01.007
[22]	Bi, W., Dandy, G.C. and Maier, H.R. (2015) Improved Genetic Algorithm Optimization of Water Distribution System Design by Incorporating Domain Knowledge. Environmental Modelling & Software, 69, 370-381. http://dx.doi.org/10.1016/j.envsoft.2014.09.010
[23]	Beheshti, Z. and Shamsuddin, S.M. (2015) Non-Parametric Particle Swarm Optimization for Global Optimization. Applied Soft Computing, 28, 345-359. http://dx.doi.org/10.1016/j.asoc.2014.12.015
[24]	Holland, J.H. (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.
[25]	Goldberg, D.E. (1989) Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading.
[26]	Shi, Y.H. and Eberhart, R. (1998) A Modified Particle Swarm Optimizer. The 1998 IEEE International Conference on Evolutionary Computation Proceedings, IEEE World Congress on Computational Intelligence, Anchorage, 4-9 May 1998, 69-73. http://dx.doi.org/10.1109/icec.1998.699146
[27]	Yao, X., Liu, Y. and Lin, G.M. (1999) Evolutionary Programming Made Faster. IEEE Transactions on Evolutionary Computation, 3, 82-102. http://dx.doi.org/10.1109/4235.771163
[28]	Dorigo, M. and Di Caro, G. (1999) The Ant Colony Optimization Metaheuristic. In: Corne, D., Dorigo, M. and Glover, F., Eds., New Ideas in Optimization, McGraw-Hill, London, 11-32.
[29]	Stützle, T. and Hoos, H.H. (2000) MAX-MIN Ant System. Future Generation Computer Systems, 16, 889-914. http://dx.doi.org/10.1016/S0167-739X(00)00043-1
[30]	Geem, Z.W., Kim, J.H. and Loganathan, G.V. (2001) A New Heuristic Optimization Algorithm: Harmony Search. Simulation, 76, 60-68. http://dx.doi.org/10.1177/003754970107600201
[31]	Lee, K.S. and Geem, Z.W. (2004) A New Structural Optimization Method Based on the Harmony Search Algorithm. Computers and Structures, 82, 781-798. http://dx.doi.org/10.1016/j.compstruc.2004.01.002
[32]	Kim, J.H., Geem, Z.W. and Kim, E.S. (2001) Parameter Estimation of the Nonlinear Muskingum Model Using Harmony Search. Journal of the American Water Resources Association, 37, 1131-1138. http://dx.doi.org/10.1111/j.1752-1688.2001.tb03627.x
[33]	Rossman, L.A. (1993) EPANET, Users Manual. US Environmental Protection Agency, Cincinnati.