Global Optimization by Differential Evolution and Particle Swarm Methods: Evaluation on Some Benchmark Functions

Mishra, SK (2006): Global Optimization by Differential Evolution and Particle Swarm Methods: Evaluation on Some Benchmark Functions.

Abstract

In this paper we compare the performance of the Differential Evolution (DE) and the Repulsive Particle Swarm (RPS) methods of global optimization. To this end, seventy test functions have been chosen. Among these test functions, some are new while others are well known in the literature; some are unimodal, the others multi-modal; some are small in dimension (no. of variables, x in f(x)), while the others are large in dimension; some are algebraic polynomial equations, while the other are transcendental, etc. FORTRAN programs of DE and RPS have been appended. Among 70 functions, a few have been run for small as well as large dimensions. In total, 73 optimization exercises have been done. DE has succeeded in 63 cases while RPS has succeeded in 55 cases. In almost all cases, DE has converged faster and given much more accurate results. The convergence of RPS is much slower even for lesser stringency on accuracy. Some test functions have been hard for both the methods. These are: Zero-Sum (30D), Perm#1, Perm#2, Power and Bukin functions, Weierstrass, and Michalewicz functions. From what we find, one cannot reach at the definite conclusion that the DE performs better or worse than the RPS. None could assure a supremacy over the other. Each one faltered in some cases; each one succeeded in some others. However, DE is unquestionably faster, more accurate and more frequently successful than the RPS. It may be argued, nevertheless, that alternative choice of adjustable parameters could have yielded better results in either method’s case. The protagonists of either method could suggest that. Our purpose is not to join with the one or the other. We simply want to highlight that in certain cases they both succeed, in certain other case they both fail and each one has some selective preference over some particular type of surfaces. What is needed is to identify such structures and surfaces that suit a particular method most. It is needed that we find out some criteria to classify the problems that suit (or does not suit) a particular method. This classification will highlight the comparative advantages of using a particular method for dealing with a particular class of problems.

• Item Type: MPRA Paper
• Language: English
• Keywords: : Global optimization; Stochastic search; Repulsive particle swarm; Differential Evolution; Clustering algorithm; Simulated annealing; Genetic algorithm; Tabu search; Ant Colony algorithm; Monte Carlo method; Box algorithm; Nelder-Mead; Nonlinear programming; FORTRAN computer program; local optima; Benchmark; test functions
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C63 - Computational Techniques ; Simulation Modeling

References

· Bauer, J.M.: “Harnessing the Swarm: Communication Policy in an Era of Ubiquitous Networks and Disruptive Technologies”, Communications and Strategies, 45, 2002. · Box, M.J.: “A new method of constrained optimization and a comparison with other methods”. Comp. J. 8, pp. 42-52, 1965. · Bukin, A. D.: New Minimization Strategy For Non-Smooth Functions, Budker Institute of Nuclear Physics preprint BUDKER-INP-1997-79, Novosibirsk 1997. · Cerny, V.: "Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm", J. Opt. Theory Appl., 45, 1, 41-51, 1985. · Eberhart R.C. and Kennedy J.: “A New Optimizer using Particle Swarm Theory”, Proceedings Sixth Symposium on Micro Machine and Human Science, pp. 39–43. IEEE Service Center, Piscataway, NJ, 1995. · Fleischer, M.: “Foundations of Swarm Intelligence: From Principles to Practice”, Swarming Network Enabled C4ISR, arXiv:nlin.AO/0502003 v1 2 Feb 2005. · G.E.P. Box, “Evolutionary operation: A method for increasing industrial productivity”, Applied Statistics, 6 , pp. 81-101, 1957. · Glover F.," Future paths for Integer Programming and Links to Artificial Intelligence", Computers and Operations Research, 5:533-549, 1986. · Hayek, F.A.: The Road to Serfdom, Univ. of Chicago Press, Chicago, 1944. · Holland, J.: Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, Ann Arbor, 1975. · Karush, W. Minima of Functions of Several Variables with Inequalities as Side Constraints. M.Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois, 1939. · Kirkpatrick, S., Gelatt, C.D. Jr., and Vecchi, M.P.: "Optimization by Simulated Annealing", Science, 220, 4598, 671-680, 1983. · Kuhn, H.W. and Tucker, A.W.: “Nonlinear Programming”, in Neymann, J. (ed) Proceedings of Second Berkeley Symposium on Mathematical Statistics and Probability, Univ. of California Press, Berkrley, Calif. pp. 481-492, 1951. · Metropolis, N. The Beginning of the Monte Carlo Method. Los Alamos Science, No. 15, Special Issue, pp. 125-130, 1987. · Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E.: "Equation of State Calculations by Fast Computing Machines", J. Chem. Phys.,21, 6, 1087-1092, 1953. · Mishra, S.K.: “Some Experiments on Fitting of Gielis Curves by Simulated Annealing and Particle Swarm Methods of Global Optimization”, Social Science Research Network (SSRN): http://ssrn.com/abstract=913667, Working Papers Series, 2006 (a). · Mishra, S.K.: “Least Squares Fitting of Chacón-Gielis Curves by the Particle Swarm Method of Optimization”, Social Science Research Network (SSRN), Working Papers Series, http://ssrn.com/abstract=917762 , 2006 (b). · Mishra, S.K.: “Performance of Repulsive Particle Swarm Method in Global Optimization of Some Important Test Functions: A Fortran Program” , Social Science Research Network (SSRN), Working Papers Series, http://ssrn.com/abstract=924339 , 2006 (c). · Mishra, S.K.: “Some New Test Functions for Global Optimization and Performance of Repulsive Particle Swarm Method”, Social Science Research Network (SSRN) Working Papers Series, http://ssrn.com/abstract=927134, 2006 (d). · Mishra, S.K.: “Repulsive Particle Swarm Method on Some Difficult Test Problems of Global Optimization” ,SSRN: http://ssrn.com/abstract=928538 , 2006 (e). · Nagendra, S.: Catalogue of Test Problems for Optimization Algorithm Verification, Technical Report 97-CRD-110, General Electric Company, 1997. · Nelder, J.A. and Mead, R.: “A Simplex method for function minimization” Computer Journal, 7: pp. 308-313, 1964. · Parsopoulos, K.E. and Vrahatis, M.N., “Recent Approaches to Global Optimization Problems Through Particle Swarm Optimization”, Natural Computing, 1 (2-3), pp. 235- 306, 2002. · Prigogine, I. and Strengers, I.: Order Out of Chaos: Man’s New Dialogue with Nature, Bantam Books, Inc. NY, 1984. · Silagadge, Z.K.: “Finding Two-Dimensional Peaks”, Working Paper, Budkar Insttute of Nuclear Physics, Novosibirsk, Russia, arXive:physics/0402085 V3 11 Mar 2004. · Simon, H.A.: Models of Bounded Rationality, Cambridge Univ. Press, Cambridge, MA, 1982. · Smith, A.: The Theory of the Moral Sentiments, The Adam Smith Institute (2001 e-version), 1759. · Sumper, D.J.T.: “The Principles of Collective Animal Behaviour”, Phil. Trans. R. Soc. B. 361, pp. 5-22, 2006. · Törn, A.A and Viitanen, S.: “Topographical Global Optimization using Presampled Points”, J. of Global Optimization, 5, pp. 267-276, 1994. · Törn, A.A.: “A search Clustering Approach to Global Optimization” , in Dixon, LCW and Szegö, G.P. (Eds) Towards Global Optimization – 2, North Holland, Amsterdam, 1978. · Tsallis, C. and Stariolo, D.A.: “Generalized Simulated Annealing”, ArXive condmat/9501047 v1 12 Jan, 1995. · Valentine, R.H.: Travel Time Curves in Oblique Structures, Ph.D. Dissertation, MIT, Mass, 1937. · Veblen, T.B.: "Why is Economics Not an Evolutionary Science" The Quarterly Journal of Economics, 12, 1898. · Veblen, T.B.: The Theory of the Leisure Class, The New American library, NY. (Reprint, 1953), 1899. · Vesterstrøm, J. and Thomsen, R.: “A comparative Study of Differential Evolution, Particle Swarm Optimization, and Evolutionary Algorithms on Numerical Benchmark Problems”, Congress on Evolutionary Computation, 2004. CEC2004, 2, pp. 1980-1987, 2004. · Whitley, D., Mathias, K., Rana, S. and Dzubera, J.: “Evaluating Evolutionary Algorithms”, Artificial Intelligence, 85, pp. 245-276, 1996. · Yao, X. and Liu, Y.: “Fast Evolutionary Programming”, in Fogel, LJ, Angeline, PJ and Bäck, T (eds) Proc. 5th Annual Conf. on Evolutionary programming, pp. 451-460, MIT Press, Mass, 1996.