Summary
Because real-world problems generally include computationally expensive objective and constraint functions, an optimization run should be terminated as soon as convergence to the optimum has been obtained. However, detection of this condition is not a trivial task. Because the global optimum is usually unknown, distance measures cannot be applied for this purpose. Stopping after a predefined number of function evaluations has not only the disadvantage that trial-and-error methods have to be applied for determining a suitable number of function evaluations, but the number of function evaluations at which convergence occurs may also be subject to large fluctuations due to the randomness involved in evolutionary algorithms. Therefore, stopping criteria should be applied which react adaptively to the state of the optimization run. In this work several stopping criteria are introduced that consider the improvement, movement or distribution of population members to derive a suitable time for terminating the Differential Evolution algorithm. Their application for other evolutionary algorithms is also discussed. Based on an extensive test set the criteria are evaluated using Differential Evolution, and it is shown that a distribution-based criterion considering objective space yields the best results concerning the convergence rate as well as the additional computational effort.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Storn, R., Price, K.: Differential Evolution - A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces. Technical Report TR-95-012, International Computer Science Institute, Berkeley, CA (1995)
Mezura-Montes, E., Velázquez-Reyes, J., Coello Coello, C.A.: A Comparative Study of Differential Evolution Variants for Global Optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference (2006)
Huang, V., Qin, A., Suganthan, P.: Self-adaptive Differential Evolution Algorithm for Constrained Real-Parameter Optimization. In: Proceedings of the IEEE Congress on Evolutionary Computation (2006)
Takahama, T., Sakai, S.: Constrained Optimization by the ε Constrained Differential Evolution with Gradient-Based Mutation and Feasible Elites. In: Proceedings of the IEEE Congress on Evolutionary Computation, pp. 308–315 (2006)
Tasgetiren, M.F., Suganthan, P.: A Multi-Populated Differential Evolution Algorithm for Solving Constrained Optimization Problem. In: Proceedings of the IEEE Congress on Evolutionary Computation, pp. 340–347 (2006)
Price, K.V., Storn, R.M., Lampinen, J.A.: Differential Evolution - A Practical Approach to Global Optimization. Springer, Heidelberg (2005)
Brest, J., Žumer, V., Maučec, M.S.: Self-Adaptive Differential Evolution Algorithm in Constrained Real-Parameter Optimization. In: Proceedings of the IEEE Congress on Evolutionary Computation, pp. 919–926 (2006)
Kukkonen, S., Lampinen, J.: Constrained Real-Parameter Optimization with Generalized Differential Evolution. In: Proceedings of the IEEE Congress on Evolutionary Computation, pp. 911–918 (2006)
Mezura-Montes, E., Velázquez-Reyes, J., Coello Coello, C.A.: Modified Differential Evolution for Constrained Optimization. In: Proceedings of the IEEE Congress on Evolutionary Computation, pp. 332–339 (2006)
Zielinski, K., Laur, R.: Constrained Single-Objective Optimization Using Differential Evolution. In: Proceedings of the IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada, pp. 927–934 (2006)
Liang, J., Runarsson, T.P., Mezura-Montes, E., Clerc, M., Suganthan, P., Coello Coello, C.A., Deb, K.: Problem Definitions and Evaluation Criteria for the CEC 2006 Special Session on Constrained Real-Parameter Optimization. Technical report, Nanyang Technological University, Singapore (2006)
Onwubolu, G.C.: Optimizing CNC Drilling Machine Operations: Traveling Salesman Problem-Differential Evolution Approach. In: Onwubolu, G.C., Babu, B. (eds.) New Optimization Techniques in Engineering, pp. 537–566. Springer, Heidelberg (2004)
Lampinen, J., Storn, R.: Differential Evolution. In: Onwubolu, G.C., Babu, B. (eds.) New Optimization Techniques in Engineering, pp. 123–166. Springer, Heidelberg (2004)
Storn, R., Price, K.: Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization 11, 341–359 (1997)
Gämperle, R., Müller, S.D., Koumoutsakos, P.: A Parameter Study for Differential Evolution. In: Grmela, A., Mastorakis, N. (eds.) Advances in Intelligent Systems, Fuzzy Systems, Evolutionary Computation, pp. 293–298. WSEAS Press (2002)
Zielinski, K., Weitkemper, P., Laur, R., Kammeyer, K.D.: Parameter Study for Differential Evolution Using a Power Allocation Problem Including Interference Cancellation. In: Proceedings of the IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada, pp. 6748–6755 (2006)
Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. Wiley, Chichester (2001)
Deb, K., Pratap, A., Agrawal, S., Meyarian, T.: A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6(2), 182–197 (2002)
Onwubolu, G.C.: Differential Evolution for the Flow Shop Scheduling Problem. In: Onwubolu, G.C., Babu, B. (eds.) New Optimization Techniques in Engineering, pp. 585–611. Springer, Heidelberg (2004)
Zielinski, K., Peters, D., Laur, R.: Stopping Criteria for Single-Objective Optimization. In: Proceedings of the Third International Conference on Computational Intelligence, Robotics and Autonomous Systems, Singapore (2005)
Zielinski, K., Weitkemper, P., Laur, R., Kammeyer, K.D.: Examination of Stopping Criteria for Differential Evolution based on a Power Allocation Problem. In: Proceedings of the 10th International Conference on Optimization of Electrical and Electronic Equipment, Braşov, Romania, vol. 3, pp. 149–156 (2006)
Zielinski, K., Laur, R.: Stopping Criteria for a Constrained Single-Objective Particle Swarm Optimization Algorithm. Informatica 31(1), 51–59 (2007)
Schwefel, H.P.: Evolution and Optimum Seeking. John Wiley and Sons, Chichester (1995)
van den Bergh, F.: An Analysis of Particle Swarm Optimizers. PhD thesis, University of Pretoria (2001)
Syrjakow, M., Szczerbicka, H.: Combination of Direct Global and Local Optimization Methods. In: Proceedings of the IEEE International Conference on Evolutionary Computing (ICEC 1995), Perth, WA, Australia, pp. 326–333 (1995)
Espinoza, F.P.: A Self-Adaptive Hybrid Genetic Algorithm for Optimal Groundwater Remediation Design. PhD thesis, University of Illinois (2003)
Vasconcelos, J., Saldanha, R., Krähenbühl, L., Nicolas, A.: Genetic Algorithm Coupled with a Deterministic Method for Optimization in Electromagnetics. IEEE Transactions on Magnetics 33(2), 1860–1863 (1997)
Zaharie, D., Petcu, D.: Parallel Implementation of Multi-Population Differential Evolution. In: Proceedings of the 2nd Workshop on Concurrent Information Processing and Computing (2003)
Babu, B.V., Angira, R.: New Strategies of Differential Evolution for Optimization of Extraction Process. In: Proceedings of International Symposium & 56th Annual Session of IIChE (CHEMCON 2003), Bhubaneswar, India (2003)
Mezura-Montes, E., Coello Coello, C.A.: A Simple Multimembered Evolution Strategy to Solve Constrained Optimization Problems. IEEE Transactions on Evolutionary Computation 9(1), 1–17 (2005)
Mezura-Montes, E., Coello Coello, C.A.: What Makes a Constrained Problem Difficult to Solve by an Evolutionary Algorithm. Technical report, Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional, Mexico (2004)
Michalewicz, Z., Schoenauer, M.: Evolutionary Algorithms for Constrained Parameter Optimization Problems. Evolutionary Computation 4(1), 1–32 (1996)
Rudenko, O., Schoenauer, M.: A Steady Performance Stopping Criterion for Pareto-based Evolutionary Algorithms. In: Proceedings of the 6th International Multi-Objective Programming and Goal Programming Conference, Hammamet, Tunisia (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Zielinski, K., Laur, R. (2008). Stopping Criteria for Differential Evolution in Constrained Single-Objective Optimization. In: Chakraborty, U.K. (eds) Advances in Differential Evolution. Studies in Computational Intelligence, vol 143. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68830-3_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-68830-3_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68827-3
Online ISBN: 978-3-540-68830-3
eBook Packages: EngineeringEngineering (R0)