Empirical Review of Standard Benchmark Functions Using Evolutionary Global Optimization
ABSTRACT
We have employed a recent implementation of genetic algorithms to study a range of standard benchmark functions for global optimization. It turns out that some of them are not very useful as challenging test functions, since they neither allow for a discrimination between different variants of genetic operators nor exhibit a dimensionality scaling resembling that of real-world problems, for example that of global structure optimization of atomic and molecular clusters. The latter properties seem to be simulated better by two other types of benchmark functions. One type is designed to be deceptive, exemplified here by Lunacek’s function. The other type offers additional advantages of markedly increased complexity and of broad tunability in search space characteristics. For the latter type, we use an implementation based on randomly distributed Gaussians. We advocate the use of the latter types of test functions for algorithm development and benchmarking.
We have employed a recent implementation of genetic algorithms to study a range of standard benchmark functions for global optimization. It turns out that some of them are not very useful as challenging test functions, since they neither allow for a discrimination between different variants of genetic operators nor exhibit a dimensionality scaling resembling that of real-world problems, for example that of global structure optimization of atomic and molecular clusters. The latter properties seem to be simulated better by two other types of benchmark functions. One type is designed to be deceptive, exemplified here by Lunacek’s function. The other type offers additional advantages of markedly increased complexity and of broad tunability in search space characteristics. For the latter type, we use an implementation based on randomly distributed Gaussians. We advocate the use of the latter types of test functions for algorithm development and benchmarking.
KEYWORDS
Optimization; Genetic Algorithms; Benchmark Functions; Dimensionality Scaling; Crossover Operators
Optimization; Genetic Algorithms; Benchmark Functions; Dimensionality Scaling; Crossover Operators
Cite this paper
J. Dieterich and B. Hartke, "Empirical Review of Standard Benchmark Functions Using Evolutionary Global Optimization," Applied Mathematics, Vol. 3 No. 10, 2012, pp. 1552-1564. doi: 10.4236/am.2012.330215.
J. Dieterich and B. Hartke, "Empirical Review of Standard Benchmark Functions Using Evolutionary Global Optimization," Applied Mathematics, Vol. 3 No. 10, 2012, pp. 1552-1564. doi: 10.4236/am.2012.330215.
References
[1] A. B. Ozer, “A Multilingual Ontology Framework for R&D Project Management Systems,” Expert Systems with Applications, Vol. 37, No. 6, 2010, pp. 4632-4631. [2] R. Thangaraja, M. Panta and A. Abraham, “New Mutation Schemes for Differential Evolution Algorithm and Their Application to the Optimization of Directional Over-Current Relay Settings,” Applied Mathematics and Computation, Vol. 216, No. 2, 2010, pp. 532-544. doi:10.1016/j.amc.2010.01.071 [3] M. J. Hirsch, P. M. Pardalos and M. G. C. Resende, “Speeding up Continuous GRASP,” European Journal of Operational Research, Vol. 205, No. 3, 2010, pp. 507-521. doi:10.1016/j.ejor.2010.02.009 [4] L. Zhao, F. Qian, Y. Yang, Y. Zeng and H. Su, “Automatically Extracting T-S Fuzzy Models Using Cooperative Random Learning Particle Swarm Optimization,” Applied Soft Computing, Vol. 10, No. 3, 2010, pp. 938-944. doi:10.1016/j.asoc.2009.10.012 [5] Q.-K. Pan, P. N. Suganthan, M. F. Tasgetiren and J. J. Liang, “A Self-Adapting Global Best Harmony Search Algorithm for Continuous Optimization Problems,” Applied Mathematics and Computation, Vol. 216, No. 3, 2010, pp. 830-848. doi:10.1016/j.amc.2010.01.088 [6] “Black Box Optimization Benchmarking,” 2012. http://coco.gforge.inria.fr/ [7] B. Hartke, “Global Geometry Optimization of Clusters Using Genetic Algorithms,” The Journal of Physical Chemistry, Vol. 97, No. 39, 1993, pp. 9973-9976. doi:10.1021/j100141a013 [8] B. Hartke, “Global Cluster Geometry Optimization by a Phenotype Algorithm with Niches,” Journal of Computational Chemistry, Vol. 20, No. 16, 1999, pp. 1752-1759. doi:10.1002/(SICI)1096-987X(199912)20:16<1752::AID-JCC7>3.0.CO;2-0 [9] B. Hartke, “Global Geometry Optimization of Molecular Clusters: TIP4P Water,” Zeitschrift für Physikalische Chemie, Vol. 214, No. 9, 2000, pp. 1251-1264. doi:10.1524/zpch.2000.214.9.1251 [10] B. Bandow and B. Hartke, “Larger Water Clusters with Edges and Corners on Their Way to Ice,” The Journal of Physical Chemistry A, Vol. 110, No. 17, 2006, pp. 5809-5822. doi:10.1021/jp060512l [11] J. M. Dieterich and B. Hartke, “OGOLEM: Global Cluster Structure Optimisation for Arbitrary Mixtures of Flexible Molecules,” Molecular Physics, Vol. 108, No. 3-4, 2010, pp. 279-291. doi:10.1080/00268970903446756 [12] J. M. Dieterich and B. Hartke, “Composition-Induced Structural Transitions in Mixed Lennard-Jones Clusters,” Journal of Computational Chemistry, Vol. 32, No. 7, 2011, pp. 1377-1385. doi:10.1002/jcc.21721 [13] D. Whitley, S. Rana, J. Dzubera and K. E. Mathias, “Evaluating Evolutionary Algorithms,” Artificial Intelligence, Vol. 85, No. 1-2, 1996, pp. 245-276. doi:10.1016/0004-3702(95)00124-7 [14] L. T. Wille and J. Vennik, “Computational Complexity of the Ground-State Determination of Atomic Clusters,” Journal of Physics A: Mathematical and General, Vol. 18, No. 8, 1985, pp. 419-422. doi:10.1088/0305-4470/18/8/003 [15] G. W. Greenwood, “Revisiting the Complexity of Finding Globally Minimum Energy Configurations in Atomic Clusters,” Zeitschrift für Physikalische Chemie, Vol. 211, No. 1, 1999, pp. 105-114. doi:10.1524/zpch.1999.211.Part_1.105 [16] R. Salomon, “Re-Evaluating Genetic Algorithm Performance under Coordinate Rotation of Benchmark Functions,” Biosystems, Vol. 39, No. 3, 1996, pp. 263-278. doi:10.1016/0303-2647(96)01621-8 [17] H. Takeuchi, “Clever and Efficient Method for Searching Optimal Geometries of Lennard-Jones Clusters,” Journal of Chemical Information and Modeling, Vol. 46, No. 5, 2006, pp. 2066-2070. doi:10.1021/ci600206k [18] H. Takeuchi, “Development of an Efficient Geometry Optimization Method for Water Clusters,” Journal of Chemical Information and Modeling, Vol. 48, No. 11, 2008, pp. 2226-2233. doi:10.1021/ci800238w [19] R. L. Johnston, “Atomic and Molecular Clusters,” Taylor & Francis, London, 2002. doi:10.1201/9781420055771 [20] D. E. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison-Wesley, Boston, 1989. [21] J. Nocedal, “Updating Quasi-Newton Matrices with Limited Storage,” Mathematics of Computation, Vol. 35, No. 151, 1980, pp. 773-782. doi:10.1090/S0025-5718-1980-0572855-7 [22] H. Matthies and G. Strang, “The Solution of Nonlinear Finite Element Equations,” International Journal for Numerical Methods in Engineering, Vol. 14, No. 11, 1979, pp. 1613-1626. doi:10.1002/nme.1620141104 [23] R. Dodier, “RISO: An Implementation of Distributed Belief Networks in Java,” 2012. http://riso.sourceforge.net [24] D. H. Ackley, “A Connectionist Machine for Genetic Hillclimbing,” Kluwer Academic Publishers, Dordrecht, 1987. doi:10.1007/978-1-4613-1997-9 [25] T. B?ck, “Evolutionary Algorithms in Theory and Practice,” Oxford University Press, Oxford, 1996. [26] G. Rauhut and B. Hartke, “Modeling of High-Order Many-Mode Terms in the Expansion of Multidimensional Potential Energy Surfaces,” Journal of Chemical Physics, Vol. 131, No. 1, 2009, pp. 014108-014121. doi:10.1063/1.3160668 [27] A. T?rn and A. Zilinskas, “Global Optimization, Lecture Notes in Computer Science No. 350,” Springer Verlag, Berlin, 1980. [28] H. Mühlenbein, D. Schomisch and J. Born, “The Parallel Genetic Algorithm as Function Optimizer,” Parallel Computing, Vol. 17, No. 6-7, 1991, pp. 619-632. doi:10.1016/S0167-8191(05)80052-3 [29] S. Stepanenko and B. Engels, “Tabu Search Based Strategies for Conformational Search,” The Journal of Physical Chemistry A, Vol. 113, No. 43, 2009, pp. 11699-11705. doi:10.1021/jp9028084 [30] H.-P. Schwefel, “Numerical Optimization of Computer Models,” Wiley, Chinchester, 1981. [31] M. Gallagher and B. Yuan, “A General-Purpose Tunable Landscape Generator,” IEEE Transactions on Evolutionary Computation, Vol. 10, No. 5, 2006, pp. 590-603. doi:10.1109/TEVC.2005.863628 [32] B. Addis and M. Locatelli, “A new class of Test Functions for Global Optimization,” Journal of Global Optimization, Vol. 38, No. 3, 2007, pp. 479-501. doi:10.1007/s10898-006-9099-8 [33] M. Gaviano, D. E. Kvasov, D. Lera and Y. D. Sergeyev, “Algorithm 829: Software for Generation of Classes of Test Functions with Known Local and Global Minima for Global Optimization,” ACM Transactions on Mathematical Software, Vol. 29, No. 4, 2003, pp. 469-480. doi:10.1145/962437.962444 [34] M. Lunacek, D. Whitley and A. Sutton, “The Impact of Global Structure on Search,” In: G. Rudolph, T. Jansen, S. Lucas, C. Poloni and N. Beume, Eds., Parallel Problem Solving from Nature, Springer Verlag, Berlin, 2008, pp. 498-507. [35] B. Hartke, “Structural Transitions in Clusters,” Angewandte Chemie International Edition, Vol. 41, No. 9, 2002, pp. 1468-1487. doi:10.1002/1521-3773(20020503)41:9<1468::AID-ANIE1468>3.0.CO;2-K [36] B. Hartke, “Application of Evolutionary Algorithms to Global Cluster Geometry Optimization,” Structure and Bonding, Vol. 110, 2004, pp. 33-53. doi:10.1007/b13932 [37] B. Hartke, “Global Optimization,” Wiley Interdisciplinary Reviews: Computational Molecular Science, Vol. 1, No. 6, 2011, pp. 879-887. doi:10.1002/wcms.70 [38] J. P. K. Doye, M. A. Miller and D. J. Wales, “Evolution of the Potential Energy Surface with Size for Lennard-Jones Clusters,” Journal of Chemical Physics, Vol. 111, No. 18, 1999, pp. 8417-8428. doi:10.1063/1.480217
[1] A. B. Ozer, “A Multilingual Ontology Framework for R&D Project Management Systems,” Expert Systems with Applications, Vol. 37, No. 6, 2010, pp. 4632-4631. [2] R. Thangaraja, M. Panta and A. Abraham, “New Mutation Schemes for Differential Evolution Algorithm and Their Application to the Optimization of Directional Over-Current Relay Settings,” Applied Mathematics and Computation, Vol. 216, No. 2, 2010, pp. 532-544. doi:10.1016/j.amc.2010.01.071 [3] M. J. Hirsch, P. M. Pardalos and M. G. C. Resende, “Speeding up Continuous GRASP,” European Journal of Operational Research, Vol. 205, No. 3, 2010, pp. 507-521. doi:10.1016/j.ejor.2010.02.009 [4] L. Zhao, F. Qian, Y. Yang, Y. Zeng and H. Su, “Automatically Extracting T-S Fuzzy Models Using Cooperative Random Learning Particle Swarm Optimization,” Applied Soft Computing, Vol. 10, No. 3, 2010, pp. 938-944. doi:10.1016/j.asoc.2009.10.012 [5] Q.-K. Pan, P. N. Suganthan, M. F. Tasgetiren and J. J. Liang, “A Self-Adapting Global Best Harmony Search Algorithm for Continuous Optimization Problems,” Applied Mathematics and Computation, Vol. 216, No. 3, 2010, pp. 830-848. doi:10.1016/j.amc.2010.01.088 [6] “Black Box Optimization Benchmarking,” 2012. http://coco.gforge.inria.fr/ [7] B. Hartke, “Global Geometry Optimization of Clusters Using Genetic Algorithms,” The Journal of Physical Chemistry, Vol. 97, No. 39, 1993, pp. 9973-9976. doi:10.1021/j100141a013 [8] B. Hartke, “Global Cluster Geometry Optimization by a Phenotype Algorithm with Niches,” Journal of Computational Chemistry, Vol. 20, No. 16, 1999, pp. 1752-1759. doi:10.1002/(SICI)1096-987X(199912)20:16<1752::AID-JCC7>3.0.CO;2-0 [9] B. Hartke, “Global Geometry Optimization of Molecular Clusters: TIP4P Water,” Zeitschrift für Physikalische Chemie, Vol. 214, No. 9, 2000, pp. 1251-1264. doi:10.1524/zpch.2000.214.9.1251 [10] B. Bandow and B. Hartke, “Larger Water Clusters with Edges and Corners on Their Way to Ice,” The Journal of Physical Chemistry A, Vol. 110, No. 17, 2006, pp. 5809-5822. doi:10.1021/jp060512l [11] J. M. Dieterich and B. Hartke, “OGOLEM: Global Cluster Structure Optimisation for Arbitrary Mixtures of Flexible Molecules,” Molecular Physics, Vol. 108, No. 3-4, 2010, pp. 279-291. doi:10.1080/00268970903446756 [12] J. M. Dieterich and B. Hartke, “Composition-Induced Structural Transitions in Mixed Lennard-Jones Clusters,” Journal of Computational Chemistry, Vol. 32, No. 7, 2011, pp. 1377-1385. doi:10.1002/jcc.21721 [13] D. Whitley, S. Rana, J. Dzubera and K. E. Mathias, “Evaluating Evolutionary Algorithms,” Artificial Intelligence, Vol. 85, No. 1-2, 1996, pp. 245-276. doi:10.1016/0004-3702(95)00124-7 [14] L. T. Wille and J. Vennik, “Computational Complexity of the Ground-State Determination of Atomic Clusters,” Journal of Physics A: Mathematical and General, Vol. 18, No. 8, 1985, pp. 419-422. doi:10.1088/0305-4470/18/8/003 [15] G. W. Greenwood, “Revisiting the Complexity of Finding Globally Minimum Energy Configurations in Atomic Clusters,” Zeitschrift für Physikalische Chemie, Vol. 211, No. 1, 1999, pp. 105-114. doi:10.1524/zpch.1999.211.Part_1.105 [16] R. Salomon, “Re-Evaluating Genetic Algorithm Performance under Coordinate Rotation of Benchmark Functions,” Biosystems, Vol. 39, No. 3, 1996, pp. 263-278. doi:10.1016/0303-2647(96)01621-8 [17] H. Takeuchi, “Clever and Efficient Method for Searching Optimal Geometries of Lennard-Jones Clusters,” Journal of Chemical Information and Modeling, Vol. 46, No. 5, 2006, pp. 2066-2070. doi:10.1021/ci600206k [18] H. Takeuchi, “Development of an Efficient Geometry Optimization Method for Water Clusters,” Journal of Chemical Information and Modeling, Vol. 48, No. 11, 2008, pp. 2226-2233. doi:10.1021/ci800238w [19] R. L. Johnston, “Atomic and Molecular Clusters,” Taylor & Francis, London, 2002. doi:10.1201/9781420055771 [20] D. E. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison-Wesley, Boston, 1989. [21] J. Nocedal, “Updating Quasi-Newton Matrices with Limited Storage,” Mathematics of Computation, Vol. 35, No. 151, 1980, pp. 773-782. doi:10.1090/S0025-5718-1980-0572855-7 [22] H. Matthies and G. Strang, “The Solution of Nonlinear Finite Element Equations,” International Journal for Numerical Methods in Engineering, Vol. 14, No. 11, 1979, pp. 1613-1626. doi:10.1002/nme.1620141104 [23] R. Dodier, “RISO: An Implementation of Distributed Belief Networks in Java,” 2012. http://riso.sourceforge.net [24] D. H. Ackley, “A Connectionist Machine for Genetic Hillclimbing,” Kluwer Academic Publishers, Dordrecht, 1987. doi:10.1007/978-1-4613-1997-9 [25] T. B?ck, “Evolutionary Algorithms in Theory and Practice,” Oxford University Press, Oxford, 1996. [26] G. Rauhut and B. Hartke, “Modeling of High-Order Many-Mode Terms in the Expansion of Multidimensional Potential Energy Surfaces,” Journal of Chemical Physics, Vol. 131, No. 1, 2009, pp. 014108-014121. doi:10.1063/1.3160668 [27] A. T?rn and A. Zilinskas, “Global Optimization, Lecture Notes in Computer Science No. 350,” Springer Verlag, Berlin, 1980. [28] H. Mühlenbein, D. Schomisch and J. Born, “The Parallel Genetic Algorithm as Function Optimizer,” Parallel Computing, Vol. 17, No. 6-7, 1991, pp. 619-632. doi:10.1016/S0167-8191(05)80052-3 [29] S. Stepanenko and B. Engels, “Tabu Search Based Strategies for Conformational Search,” The Journal of Physical Chemistry A, Vol. 113, No. 43, 2009, pp. 11699-11705. doi:10.1021/jp9028084 [30] H.-P. Schwefel, “Numerical Optimization of Computer Models,” Wiley, Chinchester, 1981. [31] M. Gallagher and B. Yuan, “A General-Purpose Tunable Landscape Generator,” IEEE Transactions on Evolutionary Computation, Vol. 10, No. 5, 2006, pp. 590-603. doi:10.1109/TEVC.2005.863628 [32] B. Addis and M. Locatelli, “A new class of Test Functions for Global Optimization,” Journal of Global Optimization, Vol. 38, No. 3, 2007, pp. 479-501. doi:10.1007/s10898-006-9099-8 [33] M. Gaviano, D. E. Kvasov, D. Lera and Y. D. Sergeyev, “Algorithm 829: Software for Generation of Classes of Test Functions with Known Local and Global Minima for Global Optimization,” ACM Transactions on Mathematical Software, Vol. 29, No. 4, 2003, pp. 469-480. doi:10.1145/962437.962444 [34] M. Lunacek, D. Whitley and A. Sutton, “The Impact of Global Structure on Search,” In: G. Rudolph, T. Jansen, S. Lucas, C. Poloni and N. Beume, Eds., Parallel Problem Solving from Nature, Springer Verlag, Berlin, 2008, pp. 498-507. [35] B. Hartke, “Structural Transitions in Clusters,” Angewandte Chemie International Edition, Vol. 41, No. 9, 2002, pp. 1468-1487. doi:10.1002/1521-3773(20020503)41:9<1468::AID-ANIE1468>3.0.CO;2-K [36] B. Hartke, “Application of Evolutionary Algorithms to Global Cluster Geometry Optimization,” Structure and Bonding, Vol. 110, 2004, pp. 33-53. doi:10.1007/b13932 [37] B. Hartke, “Global Optimization,” Wiley Interdisciplinary Reviews: Computational Molecular Science, Vol. 1, No. 6, 2011, pp. 879-887. doi:10.1002/wcms.70 [38] J. P. K. Doye, M. A. Miller and D. J. Wales, “Evolution of the Potential Energy Surface with Size for Lennard-Jones Clusters,” Journal of Chemical Physics, Vol. 111, No. 18, 1999, pp. 8417-8428. doi:10.1063/1.480217